Design a web crawler

Requirements

Every requirement below maps directly to one of the two failures in the hook. When you read the list, match each constraint to the weekend crawler that broke it — that mapping is the design.

Functional

• Start from a seed set of URLs and discover the reachable web by following links.
• Fetch each page, extract links, and hand the content to downstream consumers (indexer, archiver).
• Respect robots.txt and crawl-delay directives — non-negotiable.
• Deduplicate: never re-fetch a URL needlessly, and detect when two URLs return the same content.
• Recrawl for freshness: revisit pages so the index doesn’t go stale.

Non-functional

• Politeness is a hard constraint, not a nicety. Never overload a single host; a crawler that DDoSes sites gets blocked and is a bad citizen.
• Massive scale. Billions of pages, so the design is distributed across many machines from day one.
• Robustness. The web is adversarial — malformed HTML, redirect loops, infinite URL spaces, slow servers, spider traps. The crawler must survive all of it without stalling or looping.
• Extensible. New content types and downstream consumers plug in without a rewrite.

The two constraints that dominate the design are politeness (how to be fast in aggregate while gentle per host) and dedup (how to not drown in the same content twice).

Estimation

• Target 1 billion pages/month. That’s 10^9 / (30 × 10^5 s) ≈ ~400 pages/sec sustained — but the real number is higher because most fetch time is waiting on the network, so concurrency, not CPU, sets the rate.
• Average page ~100 KB of HTML → 10^9 × 100 KB = ~100 TB/month of raw fetched content, before dedup. Storage and bandwidth, not compute, dominate.
• URL bookkeeping: to crawl a billion pages you must remember tens of billions of seen URLs to avoid re-fetching. At ~100 bytes/URL, an exact seen set of 10 billion URLs is ~1 TB of RAM — too expensive to keep exactly in memory, which is the whole motivation for a bloom filter (a few bits per URL instead of 100 bytes).
• DNS: every fetch needs a hostname resolved; at ~400 pages/sec with no caching, DNS becomes a synchronous bottleneck — so a local resolver/cache is mandatory, not optional.

The bookkeeping number is the design driver: you cannot afford to remember every URL exactly, so dedup is probabilistic, and that single fact shapes the architecture.

High-level design

A URL frontier holds URLs to crawl, ordered for politeness and priority. Workers pull from the frontier, resolve DNS, fetch the page (after a robots.txt check), test the content for duplication, store it, extract new links, filter them against the seen set, and feed the survivors back into the frontier.

Deep dive

The URL frontier and politeness

The frontier is not a simple FIFO queue — it is the politeness engine, and getting it wrong is what DDoSes a site. A real frontier (the Mercator design) is two-stage:

• Front queues — priority. Incoming URLs are sorted into queues by priority (importance, freshness need), so high-value pages are crawled sooner. A prioritizer picks which front queue to pull from.
• Back queues — politeness. Each back queue is mapped to exactly one host, and a router guarantees no two back queues serve the same host. A worker is assigned a back queue and a timestamp of when it may next hit that host; it sleeps until the host’s crawl-delay (from robots.txt, or a default) has elapsed. This is what enforces “at most one request to host X every N seconds” regardless of how many URLs from that host are waiting.

So the frontier simultaneously says crawl important things first (front queues) and never hammer one host (back queues) — two goals that a single queue cannot serve. Politeness is per host, not per IP or per crawler, because one slow server behind one hostname is what you must protect.

Dedup: bloom filter for URLs, content hash for pages

There are two distinct dedup problems, and they need two different tools.

Have I seen this URL? With tens of billions of URLs, an exact in-memory set is ~1 TB — unaffordable. A bloom filter answers “have I seen this URL?” in a few bits per URL with no false negatives (if it says not seen, it’s definitely new) and a tunable false-positive rate (it may occasionally say seen when it wasn’t, harmlessly skipping a genuinely new URL). For a crawler this asymmetry is perfect: the cost of a false positive is one un-crawled page out of billions; the cost of an exact set is a terabyte of RAM. (The bloom-filter prerequisite covers the bit-array mechanics; here it’s the memory trick that makes web-scale dedup possible.)

Have I seen this content? Two different URLs often return identical bytes — http vs https, ?utm=... tracking params, mirror sites, printer-friendly pages. URL dedup can’t catch these because the URLs differ. So you also hash the content (e.g. an MD5/SHA of the normalized body, or a SimHash for near-duplicates) and skip storing a page whose content hash you’ve already seen. URL dedup stops you re-fetching; content dedup stops you re-storing and re-indexing the same text reachable by many paths.

Traps, freshness, and recrawl

Traps are the calendar widget from the hook: pages that generate infinite, ever-changing URLs (session IDs in the path, ?page=1,2,3… to infinity, deep dynamic facets). A naive crawler treats each as new and loops forever. Defences: cap crawl depth per host, cap URLs per host, detect URL patterns that explode, and lean on content hashing (the trap’s pages are often near-identical, so the content-hash check culls them even when the URLs differ). robots.txt Disallow rules also fence off many trap-prone paths.

Freshness is the opposite problem: the web changes, so a crawl is never “done.” Pages must be recrawled, but not uniformly — a news homepage changes hourly, an archived PDF changes never. So recrawl priority is driven by an estimated change rate per page: track how often a page’s content hash actually changed across past crawls, and schedule the volatile pages often and the static ones rarely. This makes the frontier a continuous system (URLs are re-added on a freshness schedule), not a one-shot drain.

Bottlenecks & tradeoffs

• Frontier scale & balance. With billions of URLs the frontier doesn’t fit on one machine; it’s partitioned (often by host hash) across nodes — but then one giant host (a huge site) can overload its partition while others idle. Balancing host-to-partition assignment is a real operational problem.
• DNS as a hidden bottleneck. Synchronous DNS at hundreds of lookups/sec stalls fetchers; a local caching resolver is mandatory, and even then a flood of new hosts can saturate it.
• Politeness vs throughput. Strict per-host rate limits cap how fast you can crawl any single large site — so total throughput comes from crawling many hosts in parallel, not any one fast. A crawler stuck behind a few mega-hosts underperforms even with spare capacity.
• Dedup false positives & content normalization. The bloom filter occasionally drops a real new URL (tune the size for an acceptable rate); content hashing without normalization treats rotating-content pages as endlessly new, inverting dedup into wasted work — both are correctness-vs-cost knobs, not free wins.