Case study: Web crawler
Design a polite, planet-scale web crawler: two-tier priority and per-host frontier queues, Bloom-filter URL deduplication, SimHash content deduplication, and spider-trap defences.
35 min9 steps
By the end you can
- Estimate crawl throughput, ingress bandwidth, Bloom filter memory, and fetcher concurrency
- Design a two-tier URL frontier that separates global page priority from per-host politeness
- Combine URL canonicalisation, Bloom filters, and SimHash to eliminate duplicate work
- Predict how the crawler handles link discovery bursts, fetcher crashes, and spider traps
Pin down what you are building
Fetch, parse, deduplicate
- Seed URLs; canonicalisation; robots directives; prioritised recrawls
Polite and durable
- One in-flight request/host + delay; persistent frontier; trap protection
Work out the numbers
Fetches/s
5,800
15B/month / 30 / 86,400; 12k peak
Ingress
580 MB/s
5,800 / 100 KB; 4.6 Gbit/s
HTML/cycle
1.5 PB
15B / 100 KB
URL checks/s
460k
~80 links/page
Bloom memory
27 GB
15B / 14.4 bits; 0.1% false positives
Fetch concurrency
3,000
6,000/s / 0.5s
Design the internal interfaces
POST /v1/frontier/urls; GET /v1/robots/{domain}
- Batch rawUrl/sourceHost/depth; cached directives up to 24h
POST /v1/frontier/lease
- Lease ready hosts; acknowledge after durable HTML + metadata
Model the data
Dedup + politeness
- urlseen Bloom/KV; robotsRules by domain + expiry
Page archive
- urlId / domain/status/crawledAt/SimHash; immutable HTML blobs separate
Draw the high-level architecture
Put the steps of processing a newly discovered link in order.
- 1Check the URL seen filter (Bloom filter + KV); drop if already seen
- 2Route the URL through priority and per-host politeness frontier queues
- 3Compute the page's SimHash, store HTML + metadata, and extract outgoing links
- 4Canonicalise the raw URL (lowercase host, strip fragments, sort query params)
- 5Check cached robots.txt for the host, then fetch the page over HTTP
Deep dive: Mercator frontier, Bloom filters, and SimHash
Mercator frontier
- Priority front queues / host FIFOs; min-heap next-fetch times
Dedup mechanisms
- Bloom: possible false positives; SimHash: near-duplicate text by <=3 differing bits
Evaluate alternatives
No robots cache
- Store saturates; <90% fixture goodput
Disk URL dedup
- 460k checks/s require substantial capacity
Host-worker hashing
- Local politeness queue and connection reuse
Run the failure scenarios
Inject
link-burst: 2x
Observe
Seen filter removes duplicates
Result
Frontier queues buffer; fetchers stay polite
Inject
fetcher-crash: 500ms
Observe
Unacknowledged leases expire
Result
URLs become visible for safe recovery
Inject
slow-archive: 4x
Observe
Blob writes slow workers
Result
Queue decouples scheduling/robots; monitor backlog
Wrap up and self-assess
Trap defences
- Canonical URLs; length/depth limits; per-host crawl budgets
Detect waste
- Repeated near-identical SimHashes demote host priority
Answer this step to continue.