Design a web crawler

A crawler looks like a fetcher but is really a scheduler with manners. The fetching is trivial; the hard part is deciding what to fetch next at a billion-page scale without hammering any single site — and politeness, not bandwidth, is what sets the floor on how fast you can possibly go.

Source: Vol. 1 Ch. 9, archive Case drill Trade-off first

First principle — politeness is a hard rate cap, not a feature

You cannot hit one host harder than roughly 1 request per second (or whatever its robots.txt Crawl-delay says) without being abusive — and an abusive crawler gets its IP range blocked, which destroys coverage. So your throughput is not set by how many fetchers you can afford; it is set by how many distinct hosts you can keep in flight at once. That single observation forces the entire architecture: the design problem is not "fetch fast," it is "schedule across hundreds of thousands of polite, slow per-host streams in parallel." Everything below derives from that.

Why politeness dictates the math

Suppose you want to crawl 1 billion pages and your fleet can drive 12,000 pages/second aggregate. If politeness allows 1 page/s/host, then to sustain 12,000 pps you must have ~12,000 distinct hosts being fetched concurrently at every instant. A crawler that tried to pull those 12,000 pps from a few thousand hosts would be exceeding 1 req/s/host and getting blocked. Parallelism in a crawler means host parallelism, full stop.

Now the wall-clock floor. Even with perfect parallelism and never a wasted fetch:

T_min = 1e9 pages / 12,000 pps ≈ 83,333 s ≈ 23.1 hours

That is the best case — it assumes you always have 12,000 eligible hosts ready and never idle a fetcher waiting on a politeness timer. In reality link graphs are skewed (a few mega-hosts, a long tail of tiny ones), so you will often have fetchers idle because the only eligible URLs belong to hosts already in their cool-down window. The realistic figure is days, not hours, and the lever that moves it is "discover and keep more distinct hosts hot," not "buy more fetchers."

Storage, sized honestly

Per page: ~100 KB of content + ~1 KB of metadata (status, headers, fetch time, fingerprint, outlinks). For 1B pages:

Raw content: 1e9 × 100 KB = 1e14 bytes = 100 TB.
HTML compresses ~3–4×, so 100 TB / ~3.3 ≈ 30 TB stored.
Metadata: 1e9 × 1 KB = 1 TB — small, but it's the hot index, so it lives in fast storage while content goes to cheap blob storage.

Concurrent hosts to hit 12k pps

~12,000

Wall-clock floor for 1B pages

~23 h

Raw content (100 KB/page)

100 TB

After ~3.3× compression

~30 TB

1. Clarify the contract

Treat the prompt as a product contract before drawing boxes. The crawler must:

Discover pages from seed URLs and links extracted from fetched pages.
Respect robots.txt, per-host politeness, and any declared crawl delay — this is non-negotiable.
Avoid re-fetching URLs already seen and avoid storing duplicate content.
Persist content + metadata + outlinks for downstream indexing.
Scale fetchers horizontally while the per-host rate cap stays enforced globally.

And explicitly what it need not do: it is not a search index (no ranking/query serving — that's downstream), it does not render JavaScript by default (a separate, far more expensive rendering tier handles SPAs), and it makes no freshness guarantee tighter than its recrawl policy. Saying these out loud keeps the scope honest.

2. The surface area

Keep the API small; it should express the operation, not leak the queue/shard layout.

API / operation	Why it exists
`enqueue(url, priority)`	Admit a discovered URL into the frontier (after normalization + dedup).
`lease_next() → url`	A fetcher asks the scheduler for the next URL whose host is politeness-eligible.
`commit(url, content, links, status)`	Write the page record to the content sink and feed outlinks back into `enqueue`.

3. Model the data

The data model is the first architecture. State the owners:

URL frontier (front + back queues)host policy cache (robots, crawl-delay, next-eligible-time)seen-URL set (dedup)content-hash set (near-dedup)fetch history (for adaptive recrawl)

4. Linearized design — the URL frontier

Walk one URL through the system. The frontier is the heart of it: a two-stage queue that separates priority (which page matters more) from politeness (which host is allowed to be touched right now).

discovered URLs │ ▼ ┌───────────────┐ admission: is this URL new? │ NORMALIZE + │──▶ Bloom filter (seen-URL set) │ DEDUP gate │ hit ⇒ drop · miss ⇒ admit + set bit └───────────────┘ │ (new URLs only) ▼ ┌─────────────── FRONT QUEUES (priority) ───────────────┐ │ [P0 news/price] [P1 important] [P2 normal] [P3 …] │ pick by priority └───────────────────────────────────────────────────────┘ │ router: hash(host) → back queue ▼ ┌─────────────── BACK QUEUES (one per host) ────────────┐ │ host_a: u u u host_b: u u host_c: u u u │ └───────────────────────────────────────────────────────┘ │ ▼ ┌──────────── POLITENESS HEAP ───────────────┐ │ min-heap keyed by next_eligible_time(host) │ pop host whose timer ≤ now │ host_b @ 12:00:01 host_a @ 12:00:02 … │ └─────────────────────────────────────────────┘ │ host eligible ▼ ┌──────────────┐ fetch · parse · extract links │ FETCHER POOL │ ───────────────────────────────▶ content sink (blob + meta) │ (N workers) │ set host next_eligible = now + crawl_delay └──────────────┘ ───────────────────────────────▶ outlinks back to NORMALIZE

1. Normalize the URL (lowercase host, strip default ports, sort query params, drop fragments) so trivial variants collapse to one key.
2. Check it against the seen-URL Bloom filter. Hit ⇒ drop; miss ⇒ admit and set the bits. This admission gate is where cheap dedup happens.
3. Place it in a front queue by priority (news/price pages high, deep boilerplate low).
4. A router hashes host to a back queue — one logical queue per host — so politeness is enforceable per host (lesson 07: partition by the key you must serialize on).
5. A min-heap keyed by each host's next-eligible-time decides which host a free fetcher may touch. Pop the host whose timer has elapsed.
6. Fetch (after consulting the cached robots.txt policy), parse, extract outlinks, write content + metadata to the sink, and set next_eligible(host) = now + crawl_delay. Outlinks loop back to step 1.

5. Deep dives

(1) Why one global priority queue can't work — and the two-stage fix

The naive design is a single global priority queue: always fetch the highest-priority URL next. It collapses immediately under politeness. Imagine the top 12,000 URLs by priority all belong to en.wikipedia.org. A global priority queue hands them all to fetchers at once — and now you're firing 12,000 req/s at one host, exactly the abuse that gets you blocked. Priority and politeness pull in opposite directions: priority says "fetch the best URL," politeness says "but only one per second per host."

The resolution is the two-stage frontier above. Front queues own priority; back queues own politeness (one per host); and a global min-heap keyed by next_eligible_time is the scheduler that reconciles them. A fetcher never asks "what's the most important URL?" It asks "which host is eligible right now?", pops that host off the heap, takes the head of that host's back queue, fetches it, and re-inserts the host with next_eligible = now + crawl_delay. This is DDIA Ch. 11's work-queue / stream-processing pattern: the heap is a scheduler over many independent per-key streams, and the per-host queues are partitions of that stream (DDIA Ch. 6 — partition the frontier by host so the politeness invariant is local to one partition and never needs cross-partition coordination).

The state-size trap

A million hosts × thousands of queued URLs each is far too much to hold in RAM. So back queues spill to disk/an external store keyed by host, and only the heads plus the heap of next-eligible-times stay hot. The heap holds one entry per active host (~tens of thousands), not one per URL — that's what makes the scheduler O(log hosts) per pop instead of O(log URLs).

(2) Exact dedup vs near-dedup — and what the Bloom filter costs

Two different duplicates, two different mechanisms:

Exact URL dedup is set membership: "have I seen this exact normalized URL?" At 1B+ URLs a real hash set is huge (a 64-bit fingerprint × 1B ≈ 8 GB just for keys, before set overhead). So the admission gate uses a Bloom filter — say ~1.2 GB for 1B URLs at a ~1% false-positive rate. The catch is the failure direction: a Bloom filter never yields a false negative (it won't claim an unseen URL was seen), but it does yield false positives — ~1% of genuinely-new URLs get reported as "already seen" and silently dropped. That's lost coverage. You trade memory for completeness: tighten the FP rate (more bits) and you crawl more of the web; loosen it and you save RAM. This is DDIA Ch. 3's classic Bloom-filter-as-index-membership tradeoff.
Near-dedup / content dedup catches a different beast: the same article served at ten URLs (print view, AMP, tracking params you didn't normalize away), or templated pages that differ only in a sidebar. Exact-URL dedup can't see these. The tools are SimHash or MinHash: hash the content into a fingerprint where near-identical documents land within a small Hamming/Jaccard distance, so "is this basically a page I already stored?" becomes a cheap distance check instead of a full diff. This is more expensive than URL dedup and runs at commit time, suppressing storage and downstream indexing of mirror/templated content. Exact-URL dedup is the cheap frontier gate; near-dedup is the content-quality gate behind it.

(3) Adaptive recrawl from observed change frequency

Crawling everything on a fixed schedule is wasteful and rude: a news front page changes every few minutes, a 2009 forum post never changes again. Re-fetching the forum post hourly burns the politeness budget you needed for the news page. The fix is to learn each page's change rate from its own history and set its recrawl interval from that. Record a content fingerprint each fetch; if the page changed, shorten its interval (it's volatile); if it's been identical for the last K crawls, lengthen it (back off exponentially toward a cap). A simple, defensible rule: next_interval = clamp(prev_interval × (changed ? 0.5 : 2), min, max). This concentrates the scarce per-host budget on pages that actually move, which is the whole game once you've accepted that throughput is capped by politeness.

6. Trade-offs

Choice	Buys	Costs	Choose when
Breadth-first vs priority crawl	coverage / discovery breadth	less freshness for important pages	initial bootstrap from seeds
Per-host back queues vs single global queue	enforceable politeness	more scheduling state (heap + per-host queues)	any public-web crawl (mandatory)
Exact URL dedup vs near-dedup	cheap O(1) frontier suppression	misses mirrored/templated duplicates	frontier admission gate; add SimHash at commit
Aggressive recrawl vs adaptive recrawl	maximal freshness	wastes politeness budget; looks abusive	news/price pages → adaptive everywhere else

The sharpest one is the third row, and it's about where each mechanism lives. Exact-URL dedup belongs at admission because it must be cheap (it runs on every discovered link, billions of times) and a false positive only costs one page of coverage. Near-dedup belongs at commit because it's expensive (SimHash distance over content) and you only pay it once per actually-fetched page — and that's the right place, because by then you have the content the fingerprint needs. Putting near-dedup at admission would be impossible (no content yet); putting exact-dedup at commit would waste a fetch on every duplicate URL. The two gates are deliberately at different points in the pipeline.

7. Failure modes

Failure	Mitigation
Crawler trap (infinite calendar / faceted-search URLs)	URL-pattern detection + depth limits + per-host budget caps (see the senior Q below).
robots.txt policy stale	Cache host policy with a TTL; revalidate on host errors and before honoring high-volume crawls.
A fetcher accidentally overloads a site	Politeness is enforced by the global heap, not per-fetcher; add an emergency per-host blocklist and honor `Retry-After` / 429 from the site.
Content sink backpressure	When the sink lags, slow or pause frontier leasing (lesson 13 backpressure) rather than buffering unboundedly and OOMing.
Fetcher crash mid-lease	Leases have a timeout; an un-committed URL becomes eligible again so work isn't lost (at-least-once; near-dedup absorbs the occasional re-fetch).

8. Interview Q&A

How do you avoid getting stuck in an infinite calendar or crawler trap? (senior answer) Traps are URL spaces that generate links forever — a calendar with "next month" forever, faceted search with every filter combination, or session IDs that mutate the URL endlessly. Three layers defend against it: (a) URL-pattern detection — flag hosts emitting huge numbers of near-identical, deeply-parameterized URLs and stop expanding them; (b) depth limits — cap how many link-hops from a seed you'll follow, since traps are almost always deep; (c) per-host budget caps — a hard ceiling on URLs crawled per host per cycle, so even an undetected trap can only waste a bounded slice of the budget. The budget cap is the backstop: it makes the failure bounded even when detection misses.
Why can't a single global priority queue enforce politeness? (senior answer) Priority is per-URL, politeness is per-host, and they conflict: the top-N priority URLs can all belong to one host, so a global queue would fire N concurrent requests at it. You need per-host back queues for politeness plus a global heap keyed by next-eligible-time so the scheduler picks the next eligible host, not the next URL.
Exact dedup vs near-dedup — when each? (senior answer) Exact URL dedup (Bloom filter at admission) is cheap and runs on every discovered link; it catches identical URLs. Near-dedup (SimHash/MinHash at commit) catches mirrored, AMP, print-view, and templated pages whose URLs differ but content is ~identical. Different cost, different pipeline stage — admission can't do near-dedup because there's no content yet.
What's the false-positive cost of the Bloom filter? (senior answer) A Bloom filter has no false negatives but does have false positives: at a 1% rate, ~1% of genuinely-new URLs are reported "seen" and dropped — pure lost coverage. You buy lower FP rate with more bits (~1.2 GB for 1B URLs at 1%). Tune it by how much coverage loss you can tolerate vs. RAM budget.
How do you set throughput targets? (senior answer) Not from fleet size — from host parallelism. At 1 req/s/host, hitting 12k pps requires ~12k concurrent distinct hosts; 1B pages / 12k pps ≈ 23 hours is the wall-clock floor with perfect parallelism. The real lever is discovering and keeping more distinct hosts hot, not adding fetchers, because idle fetchers waiting on politeness timers are the actual bottleneck.
How do you decide what to recrawl? (senior answer) Learn each page's change rate from its fetch history (content fingerprint comparisons) and set its recrawl interval adaptively — halve it when the page changed, double it (toward a cap) when it didn't. This concentrates the scarce politeness budget on volatile pages instead of hammering static ones, which is mandatory once you accept throughput is politeness-capped.
The content store falls behind — what happens to the frontier? (senior answer) Apply backpressure: slow or pause leasing when the sink lags, rather than buffering fetched content unboundedly in memory. This is lesson 13's backpressure — the frontier is a work queue (DDIA Ch. 11), and a healthy queue must be allowed to push back on producers.

Related foundation lessons

The frontier is fundamentally an asynchronous work queue — lesson 11 (async messaging) is the spine: producers (link extractors) and consumers (fetchers) are decoupled through the queue, which is exactly what lets you scale fetchers independently. Lesson 07 (partitioning) explains why the back queues are partitioned by host: the politeness invariant must be local to one partition so the scheduler never needs cross-partition coordination to enforce it. And lesson 13 (fault tolerance) supplies the backpressure mechanism for when the content sink lags behind the fetchers — pause leasing rather than buffer unboundedly.

Async messaging Partitioning Data modeling and storage Fault tolerance

Takeaway

A crawler's speed limit is set by manners, not machines: at 1 req/s/host, throughput equals the number of distinct hosts you keep hot, and 1B pages / 12k pps ≈ 23 hours is the floor even with perfect parallelism. That forces the two-stage frontier — front queues for priority, per-host back queues for politeness, and a global heap keyed by next-eligible-time to reconcile them. Dedup at two gates: a cheap Bloom filter on URLs at admission (eating a ~1% coverage loss for ~1.2 GB), SimHash/MinHash on content at commit. Then spend the scarce politeness budget where it pays — adaptive recrawl by observed change rate — and cap per-host budgets and crawl depth so a trap can only ever waste a bounded slice of your day.