BOOKS DEEP-READ · SYSTEM DESIGN INTERVIEW VOL 1 · CH 9
System Design Interview Vol 1 · Ch 9 · Alex Xu · 2020
You type two words into a search box and ten thousand results appear in half a second. Those pages obviously were not read while you were typing — a program had already copied them down, one by one, and filed them away. That program is a web crawler, and chapter 9 of System Design Interview asks you to build one from scratch.
Think of the crawler as a copyist holding nothing but a list of addresses. He goes to the first address, copies down everything he finds there, and notices that the text mentions twenty other addresses — so he appends those twenty to the end of his list. Then on to the next address, and around again.
The strange part is that the list keeps getting longer. The more he copies, the longer it grows. That is how the entire web gets pulled in, one loop at a time.
Downloading a page is the easy step. The hard question is where to go next, and there are tens of billions of addresses waiting. Two things go wrong.
First, addresses come in clumps. Most links on a page point back at the same site — navigation bars, sidebars, related articles. So if you simply work through the list in order, you get hundreds of consecutive addresses belonging to one host, and your copyist sprints over and hammers on their door hundreds of times. They get annoyed and lock you out, and now you can copy nothing at all.
Second, not all addresses deserve equal treatment. A news home page changes every hour; a static page nobody has touched in ten years needs copying once. A list that ignores importance will spend its best hours in the least useful corners of the web.
The soul of this chapter is one move: split "who goes first" and "whom must we not pester" into two separate rows of queues.
The front row sorts by importance — pages that matter, and pages that change often, get called sooner. The back row sorts by street address: every site gets its own private queue, only one messenger is sent per site, and he has to wait a while between knocks. Two requirements that pull against each other, solved by two rows of queues instead of one.
The honest cost: politeness is slowness. The better behaved you are, the longer a full sweep of the web takes — and the only way to speed up is to work on more sites at once, never to knock harder on any one of them.
One is copying the same thing twice. The same article often hangs off several addresses. So the copyist needs two checkpoints: before setting out, "have I been to this address?"; after copying, "do I already have this text?"
The other is walking into a maze. Some sites can generate directory levels forever, and a copyist who wanders in never comes out. The cheapest defence is to cap the address length and refuse anything longer; the rest has to be a hand-maintained blacklist of known mazes.
A crawler is hard not because downloading is hard but because queueing is. Two tiers of queues separate "fetch the important things first" from "do not knock any one site over"; then two dedup checkpoints — one before fetching, one before storing — throw away addresses you have visited and text you already hold.
Want the mechanisms, the notation and the diagrams? → Switch to the deep read
This looks like a question about downloading pages; it is really a question about scheduling. The URL frontier uses a two-tier structure — front queues own priority, back queues own politeness — to satisfy two constraints that actively fight each other: fetch the valuable pages first, and never overwhelm anyone's server. Everything else (robots.txt, DNS caching, two dedup gates, trap defences) is protective plumbing around that spine. A naive breadth-first search does not survive one minute on the real web, and the entire engineering content of this chapter is the work of making it production-worthy.
The chapter belongs to Part II, the case studies, and it is the first problem in the volume that is not request/response shaped. From the rate limiter in Ch 4 through the URL shortener in Ch 8 there is always a user on the other side waiting for an answer. Here there is no user at all — only a pipeline that feeds itself in a loop. You do not judge it by p99 latency but by throughput, coverage, and whether it has made enemies. Its output is the raw material for Ch 13's autocomplete and for the whole search stack. In the real world it is Googlebot, Bingbot, the Internet Archive's Heritrix, and the public Common Crawl dataset.
As always, turn the problem into numbers first. The book assumes 1 billion pages downloaded per month, an average page of 500 KB, and data retained for 5 years. Therefore:
400 pages/sec; peak at 2× ≈ 800 pages/sec.500 TB.30 PB.And yet none of those three numbers is the hard part. Thirty petabytes goes into object storage and is forgotten; 400 pages/sec is not even a demanding rate for one machine. The difficulty hides somewhere counter-intuitive: which 400 of tens of billions of candidates do you fetch this second?
Skip that design and here is what happens. You push discovered URLs into one FIFO queue, start a hundred threads, and within the first second you have fired a thousand requests at a single domain — which either gets your IP banned or takes their site down (and is, in plain terms, a denial-of-service attack). It looks like a fetching problem and is a scheduling problem. Of the book's four design goals — scalability, robustness, politeness, extensibility — politeness is the only one whose constraint comes from outside your system and must be obeyed unconditionally.
A crawler is a closed loop, not a pipeline. Seed URLs enter the URL frontier; the HTML downloader takes them (resolving DNS first); the parser validates and cleans each page; the content passes a content-seen gate before being stored; links extracted from that page pass a filter (dropping uninteresting file types and blacklisted domains) and a URL-seen gate, and whatever survives flows back into the frontier — closing the loop.
Treat pages as a graph and links as edges and there are only two ways to walk it. Depth-first is unusable: link depth can be enormous or unbounded, and you never come back up. Breadth-first — expanding ring by ring out of a FIFO queue — is what every real crawler uses. But the book immediately names its two fatal flaws.
First, links on a page are heavily same-host: nearly all outbound links come from navigation, sidebars and related articles, so the queue fills with hundreds of consecutive same-domain URLs, a pool of workers pulls them at once, and you have run a small DoS attack. Second, BFS has no notion of priority — every URL is treated alike, while real pages differ in value by orders of magnitude.
Running the arithmetic backwards makes it concrete. Suppose you honour the common politeness line of at most one request per second per host. To sustain 400 pages/sec on average, you must have at least 400 distinct hosts in flight at any instant. In other words, a crawler's throughput does not come from adding threads to one site; it comes from spreading across more hosts — and that single sentence determines the entire structure of the frontier.
The fix is to split the two demands into two tiers joined by a host → queue mapping table.
The upper tier — front queues — owns priority. A prioritizer scores each URL from signals such as PageRank, site traffic and update frequency, and the score decides which of f1…fn it lands in. To dequeue, a front-queue selector picks a queue at random but biased toward the higher-priority ones. The bias is deliberate rather than a strict ordering: strict priority would starve low-priority URLs forever.
The lower tier — back queues — owns politeness. URLs leaving the front tier go to a back-queue router, which consults the mapping table: if the host already has a dedicated queue it joins it, otherwise a new one is created. The key property is that each back queue holds URLs for exactly one host and is served by exactly one worker thread, and that thread waits a fixed delay after finishing one URL before taking the next. So the rule "at most one in-flight request per host, with a gap between requests" is guaranteed by the shape of the data structure — no locks, no global counters. That is the prettiest move in the chapter.
Two more concerns hang off the frontier. Freshness: already-fetched URLs are rescheduled by their observed update history — a daily news page is worth revisiting constantly, a page untouched for years is wasted effort. Storage: hundreds of millions of URLs are too expensive to hold in memory and too slow to hold entirely on disk, so the real answer is hybrid — the bulk lives on disk with an in-memory buffer at each end (enqueue and dequeue) syncing periodically.
The brake is robots.txt. Before fetching anything from a site, read its robots.txt and respect the paths it forbids. The book's practical note matters: cache that file and refresh it periodically, or you add one extra request per page fetched and end up less polite, not more.
The three accelerators:
10–200 ms per DNS request, and the standard resolver interface is synchronous and blocking. Do the arithmetic: at 100 ms a lookup, one thread resolves 10 domains a second, so sustaining 400 pages/sec would park roughly 40 threads on DNS alone. A local domain-to-IP cache with periodic refresh is close to free performance.On robustness the book names three more: use consistent hashing to assign downloaders so machines can be added and removed (see Ch 5); checkpoint crawl state to disk so a crash resumes rather than restarting from the seeds; and handle exceptions and validate data so one malformed page cannot take a worker down.
Beginners collapse these into one thing. They defend entirely different budgets.
URL dedup (URL Seen?) sits before the fetch, blocking addresses already fetched or already queued, and what it saves is bandwidth and crawl budget. At tens of billions of entries an exact hash table will not fit, so the standard answer is a Bloom filter: orders of magnitude less memory, at the price of a tiny chance of falsely deciding "seen" and permanently losing a page. That is a consciously accepted trade — missing one page is far cheaper than refetching a hundred million.
Content dedup (Content Seen?) sits before the store, blocking pages whose text you already hold (one article on several addresses, mirror sites, the same page with tracking parameters), and what it saves is storage and indexing cost. It works by checksumming the page body. The book cites a study putting about 29% of web pages at duplicate content — nearly a third of your storage and indexing bill.
Spider traps are structures that mint URLs forever — the classic being a calendar whose "next month" link never runs out, or unbounded directory nesting. The book's remedy is blunt: cap the maximum URL length (crude and cheap, at the cost of losing legitimately deep links), plus a hand-maintained blacklist of known traps. This is one of the few places in the chapter with no elegant answer, only operations. Data noise — ads, code fragments, spam pages — is excluded at parse time and never reaches storage.
Table 1 · Three traversal strategies, and why the answer is "BFS plus two tiers"
| Depth-first | Naive breadth-first | BFS + two-tier frontier | |
|---|---|---|---|
| Implementation | Stack / recursion | One FIFO queue | Front queues (priority) + back queues (host) |
| Fatal flaw | Depth can be unbounded | Same-host link clumping → hammering one host | None — one tier per demand |
| Priority | None | None; all URLs alike | Scored by PageRank / traffic / update rate |
| Politeness | None | None; needs extra machinery | Guaranteed by the structure, no locking |
| Cost | — | — | More components, large state, frontier must spill to disk |
Table 2 · Three grades of politeness: the better behaved, the longer a full sweep takes
| No limiting | Global rate limit | Per-host queue + delay | |
|---|---|---|---|
| Mechanism | Fetch whatever you dequeue, on as many threads as you can start | One fixed overall QPS ceiling | One queue and one thread per host, forced gap between fetches |
| How it feels to them | Indistinguishable from a DoS; IP banned in minutes | Can still concentrate on one site | Load on any single site is bounded and steady |
| How to add throughput | Add threads (then get banned) | Raise the global ceiling (treats the symptom) | Spread across more hosts: 400 pages/sec needs ≥400 active hosts |
| Cost | Cannot crawl for more than a few days | Hard to tune, too coarse | Slow: small sites are inherently slow to crawl; queue and map state |
| Who uses it | — | Toy crawlers | Googlebot, Heritrix and other production crawlers |
What makes this question valuable in an interview is that it is one of the rare system design problems where you do not get to decide the answer alone. In earlier chapters you can always add machines and caches; here you must yield to somebody else's server. Whether a candidate volunteers robots.txt, per-host rate limiting and "throughput comes from more hosts, not more threads" is close to the dividing line between having read about crawlers and having thought about them.
This skeleton is the shared shape of Googlebot, Bingbot, Heritrix and Common Crawl. It has also acquired a new relevance: gathering training corpora for large language models runs on exactly the same frontier-plus-politeness-plus-dedup machinery.
delayFactor / minDelayMs / maxDelayMs controlling the interval between requests. A production crawler with twenty years of service independently confirms the book's back-queue design: one queue per host, one thread per queue, a delay between requests. Heritrix3 Wiki · Politeness parameters ↗500 KiB — and states plainly that robots.txt is not a security measure, since listing a path there publishes it. RFC 9309 · Robots Exclusion Protocol, 2022 ↗2.74 billion pages, 468 TiB of uncompressed content, drawn from 47.5 million hosts, of which only 838 million URLs had never been visited in any prior crawl. Two things confirmed with real numbers: the host count dwarfs what one machine's queues can hold, and the URL-seen gate is filtering out the large majority of traffic. Common Crawl Blog · April 2025 Crawl Archive ↗① Capacity draws the boundaries: 1B pages/month → 400 pages/sec (peak 800); 500 KB per page → 500 TB/month; 30 PB over five years. None of those numbers is the hard part.
② The hard part is scheduling: which 400 out of tens of billions of candidates. Of the four design goals, politeness is the only constraint imposed from outside the system and owed unconditional obedience.
③ DFS is unusable (unbounded depth) and BFS is the base, but naive BFS has two fatal flaws: same-host link clumping hammers a single host, and it has no priority at all.
④ The answer is the URL frontier's two tiers: front queues split by priority (biased random selection so low priority never starves), back queues split by host (one queue per host, one thread per queue, a forced delay between requests) — politeness guaranteed by structure.
⑤ Throughput ≈ active hosts × per-host rate: at one request per second per host, 400 pages/sec needs 400 hosts in flight. Adding threads does nothing; spreading across hosts does everything.
⑥ The downloader has one brake and three accelerators: robots.txt (cache it); distributed crawling, DNS caching (10–200 ms per lookup, synchronous and blocking), locality plus short timeouts.
⑦ The two dedup gates guard different budgets: URL dedup before the fetch saves bandwidth (Bloom filter, tolerating a rare permanent page loss); content dedup before the store saves storage (the book cites ~29% of pages as duplicates).
⑧ Traps have only blunt answers: cap URL length plus a manual blacklist. Spill the frontier to disk and checkpoint crawl state, so a crash resumes instead of restarting from the seeds.