Chapter 9 · System Design Fundamentals

Design a Web Crawler

A deceptively simple loop — download a page, extract its links, repeat — that becomes a hard distributed-systems problem at web scale. Here politeness and traps matter as much as throughput, and the cleverness lives in the queues, not the loop.

Strip a crawler to its core and it is a four-step cycle: a frontier hands out a URL, a fetcher downloads the page, a parser extracts text and links, and a store keeps the bytes. The freshly found links feed back into the frontier, and the wheel turns again. Everything hard — billions of URLs, not hammering one host, not running forever — is about controlling that loop, not changing it.

What a crawler is for Slide 2

The mechanics barely change between jobs; the constraints do. Decide the goal first — coverage, freshness, fidelity, or budget — and the rest of the design follows from it. Four jobs cover most of what crawlers are built to do.

The crawl loop Slide 4

Read the cycle first — it is the system. Seed URLs prime the frontier; the fetcher downloads HTML; the parser pulls out text and links; content is checked for duplicates and stored. The extracted links pass through a URL-seen? filter and the survivors flow back into the frontier, closing the loop. Each box is a place to apply a limit.

Requirements in tension Slide 3

Four goals pull in different directions, and the whole design lives on the tradeoff curve between them. Crawl aggressively and you damage target sites and get banned; crawl politely and throughput drops. Name what each one actually demands before you start drawing boxes.

These are non-functional requirements doing the real work. The functional surface — "fetch pages, follow links, store results" — is almost trivial by comparison.

The URL frontier — two queues stacked Slide 5

The frontier decides what to crawl next and when. It does this with two rows of queues. A prioritizer scores each URL and drops it into one of several front queues by importance. A router then maps each URL to one of many back queues, one host per queue. A back-queue selector with a per-host timer releases URLs so a single host is never hit too fast. Front decides priority; back decides politeness.

Why BFS, not DFS Slide 11

The frontier behaves like a breadth-first queue, and that is deliberate. Depth-first would chase one site down a deep chain of links — fetching page after page from the same host back to back, exactly the hammering politeness forbids. Breadth-first spreads the work across many hosts at once, so the per-host pacing has other work to do while one host cools down.

Politeness Slide 6

Treat every origin as a guest in someone else's home. Three rules carry most of the weight: read the welcome mat, throttle per host, and make politeness hold across all your workers, not just one.

Send an honest User-Agent that names the crawler and links a policy page; back off on 429 / 503 by doubling the delay. Identified, well-behaved bots get the benefit of the doubt — anonymous ones get blocked first.

Deduplication — two different hashes Slide 7

The web has more copies than originals, so the crawler dedupes twice, with two different hashes. URL-seen stops us fetching the same address twice: canonicalize the URL (lowercase host, strip default port and tracking params) and hash that. Content-seen stops us storing the same article ten times under ten addresses: hash the page's normalized content and compare. The first hashes an address; the second hashes a body.

DNS resolution as its own subsystem Slide 8

DNS is the hidden bottleneck. A naive crawler does a fresh lookup per URL and turns its resolver into a smoking pile; at billions of fetches a day, name resolution is a tier-one dependency that needs its own cache. Because URL extraction tends to discover many pages from the same host, a local host → IP cache (honouring TTLs) hits well over 90% of the time.

Crawler traps Slide 9

Follow every link reachable from a seed and you will never finish — some traps are accidental, some adversarial. The defences are mostly limits (depth, count, shape), not cleverness. Cap everything, and bound loops finish.

Freshness — when to come back Slide 10

Crawling a page once is easy; knowing when to return is what separates a search index from a museum. The recrawl interval is set per-URL by importance × change rate — a busy homepage of a major site earns minutes, a hobbyist's static archive earns weeks.

Estimate change rate from observed history, weight importance with PageRank or query traffic, and lean on free signals: sitemap lastmod, RSS feeds, and conditional If-Modified-Since / ETag GETs — a 304 confirms freshness for almost nothing.

Scaling — partition by host hash Slide 11

One machine can't crawl the web, so distribute the work by hashing hosts, not URLs. Each shard owns a slice of hosts and runs its own frontier, fetchers, and per-host pacing — so politeness stays local and shards never coordinate rate limits. The BFS expansion just gets wider as more shards join. A URL extracted for another host is routed to whichever shard owns it.

Storage — big bytes vs small facts Slide 12

Page bodies are large, immutable, and read in bulk — perfect for object storage. Metadata is small, hot, and queried by URL — perfect for a database. Don't mix the two. And keep the URL-seen set in a fast in-memory structure (a Bloom filter) so the hot dedup check never waits on disk.

Per-URL metadata — last fetched, status, ETag, content hash, blob pointer, depth — lives in a wide-column store or partitioned Postgres. The link graph sits apart because its access pattern is traversal, not lookup. Parsed pages get pushed to a stream so indexers consume crawl events independently.

Principles Slide 13

Active recall

Cover the answers. Say each one out loud before you tap to check.

Check yourself