Design a Web Crawler

Prompt

"Design a web crawler that fetches and stores a large fraction of the public web and keeps it reasonably fresh, to feed a search index."

Clarifying questions

• Scale? Aim for a few billion pages in the corpus, re-crawled on a schedule that depends on how often each page changes.
• What do we store? The raw HTML (or a normalised form) plus fetch metadata. Indexing and ranking are downstream; we only produce a stream of documents.
• Do we execute JavaScript? Not in the first version. Rendering is a follow-up with a large cost multiplier.
• Politeness rules? Respect robots.txt and never overload a host; a small site should see at most one request every few seconds from us.
• Content types? HTML only; skip binaries and media, but record links to them.
• Prioritisation? Yes: important and frequently changing pages should be crawled more often than obscure static ones.
• Freshness target? Popular pages within hours; the long tail within weeks.
• Duplicate content? Yes, detect near-duplicates so mirrors and boilerplate variants are not stored many times.

Requirements

Functional

• Seed with a set of URLs; discover new URLs by extracting links from fetched pages.
• Fetch pages respecting robots.txt and per-host rate limits.
• Store content and metadata; emit fetched documents to a downstream consumer.
• Re-crawl pages on a per-page schedule derived from observed change frequency and importance.
• Detect duplicate URLs and near-duplicate content.

Non-functional

• Throughput: the crawler must sustain a high fetch rate across millions of hosts while never exceeding a low rate on any single host.
• Robustness: malformed pages, crawler traps (infinite calendars, session-id URLs), slow servers, and huge responses must not stall the system.
• Extensibility: adding a renderer or a new content parser should not require redesign.

Back-of-envelope

• Target corpus: 5B pages. Re-crawl the whole corpus on average once a month → 5B / (30 × 86,400 s) ≈ 1,900 pages/s average. Add newly discovered pages and higher-frequency re-crawls of the head, and plan for 5,000 fetches/s sustained, 10,000/s peak.
• Bandwidth: average page 100 KB (HTML only, compressed transfers around 30 KB). 5,000 × 100 KB = 500 MB/s uncompressed content received; wire traffic around 150 MB/s. A modest number of fetch machines with good network handles this; concurrency, not bandwidth, is the constraint, because each fetch may wait seconds on a slow server.
• Concurrency: at 5,000 fetches/s and 2 s average latency, 10,000 in-flight connections. Split across 50 fetcher nodes that is 200 connections each, but they must be spread over thousands of distinct hosts to stay polite.
• Storage: 5B pages × 100 KB = 500 TB per full snapshot uncompressed, roughly 150 TB compressed. Keeping the current version plus a few historical versions of the head: budget 500 TB. Write rate 500 MB/s is a job for a distributed file or object store, not a database.
• URL frontier: 5B known URLs plus a discovery backlog; at 100 B per URL record with metadata, 500 GB to 1 TB. Persisted on disk, partitioned, with hot portions in memory.
• Seen-URL set: 5B entries. A Bloom filter at 10 bits per entry is about 6 GB with a false-positive rate around 1%; an exact hash set of 64-bit fingerprints is 40 GB.
• Content fingerprints for near-duplicate detection: 64-bit simhash per page, 40 GB, sharded.