Design a Web Crawler
1. What a crawler is
A program that downloads web pages, finds the links inside them, and follows those links to find more pages. Also called a robot or spider.
The basic algorithm is 3 lines:
1. take a list of URLs, download those pages
2. pull the links out of each page
3. add the new links to the list → repeatThe whole chapter is about why these 3 lines hide a big distributed system.
Used for: search indexing (Googlebot — the usual interview assumption), web archiving (national libraries), web mining (e.g. downloading annual reports), web monitoring (finding pirated content).
2. Scope questions and the grading rubric
Book's scoped answers: search indexing · 1 billion pages/month · HTML only · also crawl new/edited pages · store content 5 years · ignore duplicate content.
The 4 traits of a good crawler — say these early, they grade the design:
| Trait | Plain meaning |
|---|---|
| Scalability | billions of pages → must crawl in parallel |
| Robustness | bad HTML, dead servers, evil links — survive all of it |
| Politeness | never hammer one website with rapid requests (the star topic) |
| Extensibility | adding a new content type (images) must not mean a redesign |
Estimation:
1B pages/month ÷ (30 × 24 × 3600) ≈ 400 pages/sec, peak = 2× = 800
avg page 500 KB → 1B × 500 KB = 500 TB/month
5 years: 500 TB × 12 × 5 = 30 PB total storageTakeaways: hundreds of parallel downloads at all times; blob-scale storage.
3. The pipeline (high-level design)
Pages flow left to right; new links loop back to the start. Each piece:
- Seed URLs — where the crawl starts. Split the URL space into chunks: by country, or by topic (shopping, sports…). Open-ended; think out loud.
- URL frontier — the queue of URLs to be downloaded. Crawl state splits into "to do" (frontier) and "done" (URL storage). Naively a FIFO queue; really the most interesting component (§4).
- HTML downloader — fetches pages. Respects robots.txt first: a file at the site root where the site says what crawlers may touch. Cache it per host; re-download periodically.
- DNS resolver — turns a hostname into an IP address. Slow (10–200 ms) and synchronous → a bottleneck at 400 fetches/sec → keep your OWN DNS cache, refreshed by cron (§5).
- Content parser — checks the page is valid HTML; drops malformed junk so it doesn't waste storage downstream. Separate component so parsing doesn't slow the crawl servers.
- Content seen? — ~29% of pages are copies hosted at other URLs. Comparing pages character by character is hopeless → compare hashes of the content. Same hash = same page = discard.
- Content storage — the 30 PB. Mostly disk; popular content cached in RAM.
- URL extractor — pulls links out of the page; converts relative paths ("/wiki/Cat") into absolute URLs ("https://en.wikipedia.org/wiki/Cat").
- URL filter — drops unwanted types, file extensions, error links, blacklisted sites.
- URL seen? — have we already crawled or queued this URL? Implemented with a Bloom filter + hash table. Stops duplicate work and infinite loops.
- URL storage — the permanent record of every URL already visited.
Duplicates die at two gates: URL seen? (same URL twice) and content seen? (same page at different URLs). Different keys, different gates.
4. Deep dive: the URL frontier
4.1 Why not plain BFS?
The web is a graph (pages = nodes, links = edges). DFS (follow the first link, then its first link…) goes too deep — bad choice. BFS (a FIFO queue) is the standard — but naive BFS has 2 problems:
- Most links on a page point back to the SAME host → a FIFO full of wikipedia URLs floods wikipedia with parallel requests. Impolite.
- FIFO treats every URL as equally important. They aren't.
The frontier fixes both, with two banks of queues in series:
4.2 Front half = WHICH URL next (priority)
- Prioritizer — scores each incoming URL by usefulness: PageRank, site traffic, update frequency.
- Front queues f1…fn — one queue per priority level.
- Front queue selector — picks which front queue to pull from: randomly, biased toward high priority. Why random? Strict "highest first" would starve low-priority URLs forever. Bias = important pages go sooner; randomness = nothing waits forever.
4.3 Back half = WHEN a host may be hit (politeness)
Rule: download one page at a time from the same host, with a delay between downloads. The structure enforces it:
- Back queue router — reads the URL's hostname, files it into that host's queue using the mapping table (wikipedia→b1, apple→b2, …). New host → assign a free queue, write a new table entry.
- Back queues b1…bn — each queue holds URLs from ONE host only. ~3× as many queues as workers. They hold only the hosts currently being crawled — not the whole internet.
- Back queue selector — decides which queue may release a URL, and when. Book version: each worker is mapped to a queue and a delay is added between tasks. Production version (Mercator): a timing heap — see §4.4.
- Worker threads — dumb download loops: ask for a URL → DNS (cached) → robots check (cached) → HTTP GET → hand HTML to the parser → ask again. Hundreds of them (each fetch takes ~0.1–1 s; we need 400/sec). All the cleverness stays behind the selector; workers stay stateless.
One line: one host per queue makes politeness a property of the STRUCTURE, not a promise by workers.
4.4 How the back selector actually decides (Q&A #1)
Workers PULL; nothing is pushed. The selector keeps two small in-memory structures:
- Mapping table — host → which back queue (hash map)
- Timing heap — one entry per back queue, sorted by that host's next-allowed-fetch time
The cycle:
worker asks → look at heap root (earliest ready time)
→ not ready yet? worker waits briefly
→ ready? pop it, hand ONE URL from that host's queue
while the entry is popped OUT, no other worker can get that host
→ download finishes → push entry back: ready = now + delay- The delay comes from robots.txt's Crawl-delay if set, else a default of a few seconds; a nice refinement: delay = k × last response time (slow servers get gentler treatment automatically).
- Empty back queue → refill from the front queues. New host → the empty queue is REASSIGNED: old mapping entry deleted, new host written in.
Where is all this stored? In the frontier process's RAM — a hash map + a heap, tiny (they track only active hosts, a few hundred), checkpointed to disk. The URLs themselves (the big data) live in disk-backed queues with memory buffers (§4.6). When the frontier spans machines, hosts are split across them by hash(hostname) → one host's queue, timer and table entry live on exactly ONE machine → politeness needs no cross-server locks.
4.5 The returning-host corner case (Q&A #2 — senior gold)
Scenario: nike's queue empties at t=0.4 and gets reassigned to bbc — nike's timing memory is DESTROYED with its mapping entry. A new nike URL arrives at t=0.9 → router sees "new host" → fresh queue, ready NOW → nike gets hit only 0.6 s after the last time. Politeness violation.
Two fixes:
- Fix A — cooldown-aware eviction: a queue may only be reassigned after its heap time has passed. Empty but reserved until the cooldown ends. The host's timer and identity die together, never separately.
- Fix B — recent-hosts map (what real crawlers do): a small TTL map
host → last_fetch_time(entries expire after the delay period; a few hundred entries max). When ANY host gets a queue — including a returning one — seed its heap entry withready = max(now, last_fetch + delay). Also survives restarts, and it's the natural home for per-host Crawl-delay values.
One-line version: "the heap entry IS the politeness memory while a host is in rotation; eviction destroys it, so reserve the queue through its cooldown or keep a short-TTL last-fetch map."
4.6 Freshness and frontier storage
- Freshness: pages change → recrawl. Recrawling everything is too expensive → recrawl based on update history; recrawl important pages first and more often (news homepage: minutes; static page: monthly).
- Storage: hundreds of millions of URLs — too many for RAM, and disk alone is too slow. Hybrid: bulk on disk + in-memory buffers for enqueue/dequeue, flushed periodically.
5. HTML downloader details
- robots.txt — fetch and obey before crawling a site; cache per host. (Amazon's disallows Googlebot from /creatorhub etc.)
- Distributed crawl — split the URL space across many servers; each owns a slice (see §7).
- DNS cache — own domain→IP map, refreshed by cron, because live DNS is a 10–200 ms synchronous call that blocks threads.
- Locality — put crawl servers geographically near the sites they crawl; applies to caches, queues, storage too.
- Short timeout — some servers never answer; give up after a max wait and move on.
6. Robustness and extensibility
Robustness:
- Consistent hashing distributes load among downloaders; add/remove a downloader without reshuffling everything (ch.5)
- Save crawl state + data continuously → a crash restarts from checkpoint. You cannot re-crawl the internet from scratch.
- Exception handling — errors are normal; never let one crash the system
- Data validation — check what enters the system
Extensibility: the pipeline shape pays off — new modules plug in beside the URL extractor: a PNG downloader for images, a web-monitor module for copyright tracking. Nothing else changes.
7. Distributed crawl: no page crawled twice (Q&A #3)
Three layers, in order of importance:
- Ownership (structural — the main answer). Assign every HOST to
exactly one crawl server:
hash(hostname) → server(consistent hashing). Server A parses a page, finds a link to apple.com, sees apple belongs to B → forwards the URL to B instead of crawling it. Two servers can never duplicate work they don't share. Bonus: the same one-owner-per-host rule is what makes politeness timers work without cross-server locks. - Bloom filter (fast check, in RAM). Inside each server, every candidate URL is checked first. Its failure direction is safe: a false positive skips a genuinely new page (tiny loss, ~0.1–1%); it can NEVER say "not seen" about a seen URL → the filter never causes a duplicate crawl.
- URL storage (the durable truth). A persistent per-partition record of every URL crawled/queued. Needed because the Bloom filter is RAM-only — after a crash, rebuild the filter FROM this store. Filter = speed; storage = truth.
Fine print: this dedups URLs. The ~29% content duplicates live on DIFFERENT hosts → different owners → per-host records can't catch them. That's the separate "content seen?" gate: page fingerprints (hash/SimHash), in a store sharded BY FINGERPRINT, not by host. Two dedup gates, two sharding keys.
8. End-to-end frontier trace (Q&A #4 — narrate this in interviews)
Setup: 3 workers, 4 back queues, delay = 2 s per host. Arriving URLs: wiki/Cat, wiki/Dog, apple/mac, nike/shoes, bbc/news.
t=0.0 fill: selector pulls from front queues (biased random)
wiki/Cat → new host → b1 wiki/Dog → table hit → b1 (behind Cat)
apple/mac → b2 nike/shoes → b3
heap: (b1@0) (b2@0) (b3@0)
t=0.0 dispatch: W1←Cat(b1) W2←mac(b2) W3←shoes(b3)
3 hosts download IN PARALLEL — full speed, zero rudeness
t=0.3 shoes done → b3 back in heap @2.3 → W3 asks → nothing ready
→ refill: bbc/news → new host → b4@now → W3←news
t=0.4 Cat done → b1 back in heap @2.4
/Dog sits in b1, W1 is idle — and the answer is NO.
idle worker + waiting URL from a recent host = CORRECT, not a bug
t=2.4 b1 ready → some worker gets /Dog
wikipedia hit at 0.0 and 2.4 — exactly 2 s apart, enforced by
the structure, checked by no one
Component one-liners (the five things people confuse):
| Part | One line |
|---|---|
| Front queue selector | picks WHICH front queue supplies the next URL — biased random by priority |
| Back queue router | reads the hostname, files the URL into that host's back queue via the mapping table |
| Back queues | per-host FIFO lanes (~3× worker count); one host per queue = politeness by structure |
| Back queue selector | the stopwatch: timing heap of next-allowed times; hands workers one URL from whichever host is DUE |
| Workers | dumb download loops (ask → DNS → robots → GET → hand off → ask); all scheduling stays behind the selector |
9. Problematic content (three villains)
| Villain | Defense |
|---|---|
| Duplicates (~29%) | content hashes/checksums; near-duplicates (same article, different ads) need similarity hashing (SimHash) |
| Spider traps (pages generating infinite URLs, e.g. /foo/bar/foo/bar/… or a calendar's endless "next day") | max URL length, max depth, max pages per domain; no automatic rule catches all — manual blocklisting is normal and fine to say |
| Data noise (ads, spam URLs, near-empty pages) | filter out; they cost storage and pollute the index |
10. Wrap-up extras (say if time remains)
- Server-side rendering: many sites build links with JavaScript — a raw HTML fetch misses them; render the page first, then parse
- Anti-spam filtering of low-quality pages
- DB replication + sharding for the storage layer
- Horizontal scaling: hundreds/thousands of crawl servers — keep them STATELESS
- Availability, consistency, reliability; analytics for tuning
11. Interview script
1. clarify purpose (search index), 1B pages/month, HTML only, 5 yrs, dedup
2. rubric scalability · robustness · POLITENESS · extensibility
3. estimate 400/sec (peak 800) · 500 TB/month · 30 PB in 5 years
4. pipeline seed → frontier → downloader(+DNS, robots) → parser →
content seen? → store | extractor → filter → URL seen? → loop
5. traversal BFS not DFS — but naive BFS is impolite and priority-blind
6. frontier front = priority (biased random), back = one host per queue
+ delay; timing heap; freshness; hybrid disk+RAM ← centerpiece
7. downloader robots cache, distributed by consistent hashing, DNS cache,
locality, short timeout
8. villains 29% dups (hash/SimHash), spider traps (caps), noise ← unprompted
9. wrap-up JS rendering, checkpoints, sharded storage, stateless servers12. The lines that earn the most
- "Politeness isn't worker behavior — it's queue TOPOLOGY. One host per back queue makes over-hitting a server structurally impossible."
- "Biased random selection over the priority queues prevents starvation."
- "The heap entry is the politeness memory — and eviction destroys it, so I reserve queues through their cooldown or keep a last-fetch TTL map."
- "Don't share the dedup problem: hash(host) gives every URL exactly one owner; Bloom + a durable URL store dedupe locally inside the owner."
- "A calendar widget is an infinite URL generator — depth caps and per-domain budgets are non-negotiable."
- "DNS is a hidden synchronous bottleneck at 400 fetches/sec — run your own cache."
- "The crawl must checkpoint — you cannot restart the internet."
13. Numbers to remember
| Thing | Value |
|---|---|
| Load | 1B pages/month → 400/sec, peak 800 (2×) |
| Page size / storage | 500 KB avg → 500 TB/month → 30 PB in 5 years |
| Duplicate content | ~29% of the web |
| DNS latency | 10–200 ms per uncached lookup |
| Back queues | ~3× the number of worker threads |
| Politeness delay | robots Crawl-delay, else a few seconds (or k × response time) |
14. When NOT to go deep
If the crawler is a sub-part of a bigger question ("design Google Search"), one sentence:
"A distributed crawler feeds the index — host-partitioned by consistent hashing, a two-bank frontier for priority and politeness, Bloom-filtered URL dedup, content fingerprints for the ~30% duplicate pages."
Go deep only when the crawler IS the question.
15. Glossary (A–Z, one line each)
| Term | Meaning |
|---|---|
| anti-entropy / checkpoint | continuously saving crawl state so a crash resumes instead of restarting |
| back queue | FIFO holding URLs from exactly one host — the politeness unit |
| back queue router | files each URL into its host's back queue using the mapping table |
| back queue selector | decides which host's queue may release a URL and when (timing heap) |
| BFS / DFS | breadth-first (queue, level by level) vs depth-first (dive down one path); crawlers use BFS |
| biased random selection | mostly pick high-priority queues, sometimes low → importance without starvation |
| Bloom filter | RAM structure: "definitely not seen" or "maybe seen"; never a false "not seen" → never causes duplicate crawls |
| content seen? | dedup gate comparing page HASHES — catches the same page at different URLs |
| crawl-delay | robots.txt hint for the per-host politeness gap |
| DNS resolver / cache | hostname → IP; live lookups are 10–200 ms and synchronous → keep your own cache |
| freshness | recrawling changed pages — by update history, important pages more often |
| front queue | FIFO holding one priority level of URLs |
| front queue selector | biased-random picker over the front queues |
| frontier | the whole "URLs to be downloaded" component (both queue banks + storage) |
| mapping table | in-memory hash map: host → its current back queue |
| min-heap | structure that always hands you the smallest key — here, the earliest ready time |
| PageRank | link-based importance score — a prioritizer signal |
| politeness | never hit one host too fast: one request in flight per host + a delay |
| prioritizer | scores incoming URLs (PageRank, traffic, update frequency) into front queues |
| recent-hosts TTL map | host → last fetch time, entries expiring after the delay — fixes the returning-host bug |
| robots.txt | Robots Exclusion Protocol: the site's rules for crawlers; fetch, obey, cache |
| seed URLs | the starting set — split the web by locality or topic |
| server-side rendering | executing a page's JavaScript before parsing, to see dynamically generated links |
| SimHash | similarity hash — near-identical pages get near-identical fingerprints; catches near-duplicates |
| spider trap | page generating infinite URLs (calendars, /foo/bar/foo/bar/…) — capped by URL length/depth/domain budget |
| timing heap | min-heap of (next-allowed time, back queue) — the back selector's stopwatch |
| URL seen? | dedup gate for URLs: Bloom filter (fast) + URL storage (truth) |
| worker | download loop thread: ask → DNS → robots → GET → hand to parser → ask again |