How to design a web crawler

A crawler is bound by host diversity, not hardware: throughput is hosts_in_flight x 0.833, and every other number is downstream of that one constant.

Core numbers

• Target: 1 B pages/month = ~33 M/day = ~333 pages/s avg, ~666 pages/s peak (2x).
• Per-host ceiling: 0.1 s RTT + 0.1 s transfer + 1.0 s delay = 1.2 s period = 0.833 pages/s per host.
• Peak needs 800 distinct hosts in flight (666 / 0.833), not 800 machines.
• Bandwidth: 100 KB/page gzipped (not 2 MB browser render, the 20x error) = 267 Mbps avg, 533 Mbps peak, ~53% of one 1 Gbps NIC.
• Storage: ~20 KB/page after 5:1 recompress, RF 3 = ~730 TB/year (~20 boxes).
• Corpus target = 10^10 URLs; ~100 links/page, ~10 genuinely new (branching factor).

The frontier: two layers

The frontier is the to-do list of discovered-but-unfetched URLs plus the scheduler. It never drains (breaks even at 1% novelty; real crawls are far above), so the question is prioritization, not speed.

• Front queues carry priority (0–4, weighted-random selection so low queues still run and host diversity survives).
• Back queues carry politeness: 1,024 queues, one host each, worker takes one at a time, so overlapping requests are structurally impossible.
• Router = sticky table (host keeps its slot while it has work), not a hash (collisions block hosts).
• Ready heap keyed on next_fetch_at, so “what may I fetch now” is O(log b), not a scan.
• Back-queue count is a hard ceiling: b x 0.833 pages/s. 1,024 chosen (>= 800, power of two, ~1.28x headroom).
• Politeness debt (last_fetch_at) lives outside the slot table: a recycled slot still owes the full 1.2 s.

Politeness rules (get these right)

• Key on IP, not hostname. Shared hosting = thousands of “polite” hostname streams hit one box = DoS. Use IP or (host, IP) pair (CDN anycast needs the pair).
• One large site is uncrawlable: 100 M pages at 0.833/s = ~3.8 years. Negotiate (sitemap/feed/export), don’t schedule.
• last_fetch_at must survive restart, else a fleet restart bursts every known host at once.
• robots.txt: 4xx = allow-all (nothing said), 5xx/timeout = disallow-all (site is unwell). Cache negative verdict with short TTL.

Two dedup filters, both fail silently

• Bloom knobs: k = (m/n) ln 2, FP rate p = 0.6185 ^ (m/n). Crawler runs at 20 bits/key (25 GB, 0.0067% FP, ~670 K pages lost/pass); LSM store runs at 10, same formula, different cost of being wrong. A bloom FP = a page never crawled, never logged.
• Failure is a cliff: 2x the design keys halves m/n but k stays fixed → ~283x FP jump. Alert on fill ratio / inserted-key count, not measured error (no ground truth).
• Simhash: shingle → hash → per-bit vote → 1 where total positive. Near-dup = distance <= 3.
• Pigeonhole query: split 64 bits into B blocks; if <= 3 bits differ, >= B-3 blocks are clean. B=6, index every 3-block combo = C(6,3) = 20 tables, ~93 candidates/query, 1.6 TB. Beats the 4-table split (406 M vs 62 K comparisons/s).
• Simhash (8 B) over minhash (~512 B): a yes/no threshold test needs no graded Jaccard score.

Traps: guards are arithmetic, not guesses

• Depth cap = 16. Corpus reachable at depth 10 (branching factor 10); 16 gives 6 orders of slack. Move the factor, the cap moves.
• Per-host budget = 10,000/month. Doubles as the diversity control: filling 1 B/month needs 100,000 hosts. Binds long before politeness (a host can yield ~72,000/day).
• URL length cap ~1,000 B (~15x the ~66 B median).
• Strip session ids/tracking params on canonicalization; reject >3 repeated path segments; a 200 that simhashes to the error page is a soft 404.
• DNS: blocking getaddrinfo serializes the fleet (process-wide libc lock). Use an async resolver + aggressive cache (over-hold TTLs), so only ~10 recursions/s at ~97% hit.
• robots.txt cache must be shared, not per-process (16 processes = 16x fetches, each burning a politeness slot on the protected host).

Freshness: uniform beats proportional

• F = (1 - e^(-lambda T)) / (lambda T), sole input is lambda T (changes per interval).
• Crawling exactly as often as a page changes (lambda T = 1) leaves you fresh only 63% of the time.
• Uniform re-crawl scores 0.956 vs proportional’s 0.198 (4.8x worse). Fast-changing pages are stale no matter what, so effort there buys nothing. Ship uniform; it’s within 0.6% of optimal, no per-page estimate needed.
• A 304 is evidence of no change and must update the lambda estimate. Conditional GET (ETag/Last-Modified) saves bytes (200x) but not fetch slots (still burns a full delay) — the resource you’re short of.

Bottlenecks (only the first two bind)

Two shard keys, each making its concern local: frontier on hash(ip) (politeness = local timestamp compare, no locks/RPC), seen-set on hash(url) (dedup is per-URL).