Under the Hood: Harvesting the Web at Scale
A web crawler (like Googlebot) systematically navigates the World Wide Web to discover, download, and index billions of web pages. Operating at this scale requires solving polite crawling, infinite URL traps, duplicate page detection, and high-throughput HTML extraction.
The Mercator Web Crawler Architecture
Under the Hood: Key Engineering Mechanisms
- Politeness Queues: Flooding a web host with 1,000 requests per second is a Denial of Service attack. The URL Frontier maintains a separate queue per host domain, strictly enforcing a delay (e.g. 500ms) between consecutive requests to the same IP.
- Near-Duplicate Detection (SimHash): Web pages often have identical text with minor differences (timestamps, copyright footers, ads). SimHash maps 10,000-word documents to a 64-bit fingerprint where small text changes produce small Hamming distances (differing by ≤ 3 bits), giving compact fingerprints that enable efficient near-duplicate lookup (finding all fingerprints within 3 bits needs several permuted, sorted tables, not a single hash probe).
- DNS Resolution Bottlenecks: Standard OS DNS lookups block worker threads. Large-scale crawlers maintain in-memory asynchronous DNS caches with custom TTLs to bypass global DNS roundtrips.
Worked example: back-of-envelope for 1 billion pages per month
| Quantity | Calculation | Result |
|---|---|---|
| Fetch rate | 1,000,000,000 divided by 2,592,000 seconds in 30 days | about 390 pages per second |
| Bandwidth | 390 x 100 KB average page | about 39 MB/s, roughly 310 Mbit/s |
| Raw storage | 1 billion x 100 KB | about 100 TB per month before compression |
| Concurrent hosts needed | 390 pages/s with 1 request every 2 s per host | at least about 780 hosts in flight |
Worked example: sizing the URL-seen Bloom filter
For n = 10 billion URLs at a 1 percent false-positive rate, the optimal size is n x ln(1/p) divided by (ln 2) squared, about 9.6 bits per URL: roughly 96 billion bits, or 12 GB, with about 7 hash functions. A false positive means a new URL is wrongly skipped, which is acceptable for a crawler; a false negative cannot happen. Plain Bloom filters cannot delete entries, so recrawl scheduling is kept in a separate store keyed by URL.
SimHash in practice
Google's 2007 paper by Manku, Jain and Das Sarma used 64-bit SimHash fingerprints on about 8 billion pages and treated fingerprints differing in at most 3 bits as near duplicates. Finding all fingerprints within 3 bits is not a single hash lookup: they stored several permuted, sorted copies of the fingerprint table so that any match must agree exactly on some high-order block, turning the search into a few table probes.
Design choices
| Choice | Option A | Option B |
|---|---|---|
| Frontier storage | In-memory queues, fast, lost on crash | Kafka or a disk-backed queue, durable, slightly slower |
| Rendering | Raw HTML only, cheap | Headless browser for JavaScript sites, 10x or more CPU per page |
| Recrawl policy | Uniform interval | Adaptive, based on observed change rate and page importance |
Always honour robots.txt, cache it per host with a TTL, and back off on HTTP 429 and 503 responses.