Cruxly

Cruxly › System design › Design Exercises

Web Crawler

the frontier is the hard data structure, not the fetching

Open the interactive lesson

Prompt: design a web crawler that discovers URLs by following links, fetches pages, and stores them for indexing. Do not overwhelm any single site, and do not fetch the same page repeatedly.

40 minutes first. Fetching a page is a solved problem. Deciding what to fetch next, politely, at scale, is the whole exercise.

Applying the four moves: Scope — discover via links, fetch, store for indexing, politely, without refetching; rendering JavaScript and ranking out. Estimate — target pages per second against a per-host politeness limit, which means the parallelism has to come from crawling many hosts at once, not from crawling any one host faster. Sketch — a URL frontier, a dedup check before enqueue, fetchers, and storage. Deep dive — the frontier is the whole exercise: per-host queues with their own rate limits, priority across hosts, and dedup at a scale where an exact seen-set doesn't fit in memory (probabilistic structures, with the false-positive cost named).

Scope, and the constraint that shapes everything

In scope: URL discovery via link extraction, fetching, dedup, per-host politeness, storage handoff to indexing. Out of scope: the indexing and ranking that consume the crawled pages (a separate system, covered by the search-autocomplete exercise's neighbours), JavaScript rendering (assume mostly static HTML, name the SPA problem as a follow-up), malware/spam filtering.

Estimate. Say a target of 1 billion pages crawled per month, average page size 100KB.

The frontier: two queues, not one

A naive single queue of "URLs to fetch" fails immediately: if URLs from one popular domain cluster together, workers pull them consecutively and hammer that host, and there is nothing to make them ordered and politeness-respecting at the same time.

The fix: partition the frontier by host, and round-robin across hosts.

front queues by priority router hash(host) queue: host A queue: host B queue: host C worker pool one host's turn Each host's queue is served at most once per politeness interval — global throughput stays high because thousands of hosts run in parallel.
Politeness is enforced per host-queue, not globally — which is exactly why the crawler can be fast in aggregate and polite individually at the same time.

Front queues hold discovered URLs, prioritised (a page linked from many places, or from a high-authority site, is worth crawling sooner). Back queues, one per host, hold URLs about to be fetched, each with a last-fetched timestamp. A worker asks the back-queue router for the next available host — one whose politeness interval has elapsed — pulls one URL, fetches it, and updates that host's timestamp before returning for more.

The router is the actual design. With potentially millions of live hosts, you cannot hold one queue-and-timer per host in a single process indefinitely — shard host-queues across crawler nodes by hash(host), the same partition-by-what's-in-your-WHERE-clause principle used for database sharding elsewhere in this track. A given host's queue always lands on the same node, so its politeness state never needs to be coordinated across machines.

Dedup: URL-seen and content-seen are different problems

URL-level dedup stops you from queueing a URL you have already queued. At billions of URLs, an exact set is too large to hold cheaply, so use a Bloom filter — a probabilistic set that can false-positive (say "seen" for a URL you haven't) but never false-negative. A false positive means you skip crawling a page you should have crawled; tune the filter's size for a false-positive rate low enough that this is a rounding error, not a real gap. This is a real, standard trade: sub-linear memory in exchange for a small, bounded, tunable miss rate.

Content-level dedup catches something URL dedup cannot: two different URLs, identical content. Mirrors, tracking-parameter variations of the same page (?utm_source=x appended to an otherwise identical URL), and syndicated content all produce this. Hash the page body (a simple content hash, or a near-duplicate detector like simhash if approximate matches matter) and check that hash before storing — this is a separate check from the URL Bloom filter, done after fetching, and it is the one most candidates forget entirely.

URL normalization happens before either check. Strip default ports, lowercase the host, sort query parameters, resolve . and .. in paths. Without this, example.com:80/page and example.com/page are treated as different URLs and fetched twice — the cheapest possible bug to prevent and one of the most common in a naive implementation.

Politeness beyond rate limiting, and the failure modes

robots.txt is not optional and is not just about rate. Fetch and cache it per host before crawling anything else there; it can disallow entire paths outright. Treat ignoring it as a correctness bug, not a nice-to-have — in production this is also a legal and reputational exposure, not just an engineering one.

Respect Crawl-delay when a site specifies one; otherwise use an adaptive default (start conservative, watch response times and error rates, back off on 429s and 5xxs exactly like the client-side backoff covered in the rate-limiting lesson elsewhere in this track — the crawler is the client here, and a well-behaved client backs off the same way a well-behaved API consumer does).

DNS resolution at this scale needs its own cache. Resolving the same handful of thousands of hosts millions of times is wasted latency and a needless load on DNS infrastructure; cache resolutions with a sensible TTL respecting the DNS record's own TTL.

Failure modes to raise unprompted:

A spider trap. A site generates infinite URLs dynamically (calendar pages that link to "next month" forever, faceted search that enumerates every filter combination). Bound crawl depth per host and cap total pages per host per unit time — without a limit, one pathological site can consume an unbounded fraction of your entire crawl budget.

A malicious or broken site returns huge or malformed responses. Cap response size and enforce a fetch timeout; a fetch that hangs forever or downloads gigabytes ties up a worker indefinitely.

Distributed crawl coordination. Multiple crawler nodes must not independently discover and fetch the same URL simultaneously. Since the router shards by host consistently, this mostly falls out for free — two nodes never own the same host's queue — but the Bloom filter for URL-seen dedup needs to be shared or partitioned consistently across nodes too, or each node happily reduplicates the others' work.

Freshness versus discovery. Recrawling existing pages for updates competes for the same worker budget as discovering new ones. Weight recrawl priority by how often a page has historically changed — a news homepage recrawled hourly, a static documentation page recrawled monthly — rather than treating every URL as equally likely to have changed.

How to say it in the interview

"Two constraints fight each other here: I want maximum parallelism across the crawl, and I must not send more than one request at a time to any single host. The frontier — the data structure that decides what gets fetched next — exists entirely to reconcile those two."

Checklist

Practice this interactively
Share this lessonWhatsAppLinkedInX

Related lessons