a scalable, extensible crawler
The Mercator paper by Heydon and Najork described a crawler with per-host queues to enforce politeness, a disk-based URL-seen set and pluggable processing modules, a design later crawlers closely follow.
Design Interviews · lesson 9 of 15 · about 30 min
Design a web crawler
A web crawler end to end: how fast it has to fetch, why a plain queue fails under politeness, how it remembers billions of URLs, how it avoids endless sites, how it spends a recrawl budget and what happens when it forgets to be polite. Tap any for a plain-language card.
0 / 9 sections done
A treadmill, not a trip
Fetch every page on the web, then do it again before the pages change. How fast is that?
Requirements beyond speed matter as much: be polite (never overload a site), robust (broken HTML, endless pages, slow servers), extensible (new content types) and efficient (do not fetch the same content twice). Size yours.
50 billion pages revisited every 30 days is about 19,300 fetches a second and 15 Gbps of download; at 100 KB a page that is 5 PB of raw content, about 1.5 PB compressed.
Fetches per second19.3K
Download bandwidth15.4 Gbps
Raw content per full crawl5.0 PB
Stored (compressed)1.5 PB
50 billion pages revisited every 30 days need 19.3K fetches a second and 15.4 Gbps. One full crawl is 5.0 PB raw, 1.5 PB compressed. The fetchers must be spread over many machines and many networks.
Arithmetic with illustrative inputs; real crawlers revisit important pages far more often and unimportant ones rarely, which the freshness scene explores.
Many workers, one polite queue
You must not fetch from one site more than once every couple of seconds. A plain first-in-first-out queue ignores that. What happens to your workers?
A proper frontier is built around hosts. A back queue per host holds its URLs and a timestamp for when the host may be hit again; a priority structure picks the host that is ready soonest; a front layer orders by importance and freshness. Workers always find something ready if enough different hosts have work, so throughput approaches workers ÷ fetch time. Compare the two on Zipf-distributed hosts, over a 60-second window.
20 workers at 0.4 s per fetch could do 3,000 pages in a minute. Behind a FIFO queue with a 2 s politeness delay they manage 234; with host-aware scheduling they reach all 3,000.
Pages fetched in 60 s: FIFO234
Pages fetched in 60 s: host-aware3,000
Advantage12.8×
With 20 workers, 500 hosts and a 2 s delay, a FIFO queue fetched 234 pages in a minute because workers sat waiting on busy hosts; a host-aware frontier fetched 3,000, 12.8× as many.
Event-driven simulation of 12,000 URLs on Zipf-popular hosts, 0.4 s per fetch. In FIFO mode a worker that pulls a URL for a host still in its delay waits; host-aware mode always picks the host that is ready soonest.
Ten billion questions an hour
Every page links to dozens of others, most already known. Before queueing a URL you must know: have we already got it?
A false “seen” means a page is never crawled, which is a small permanent loss, acceptable for a crawler (not for, say, a payments ledger). Content can repeat under different URLs too, so crawlers also fingerprint page content (a hash, or SimHash for near-duplicates) to avoid indexing mirrors twice. URLs are first normalised (lower-case host, remove fragments and tracking parameters, sort query strings) so that trivial variants collapse.
50 billion URLs: exact fingerprints need 800 GB; a 10-bit-per-URL Bloom filter needs 63 GB and wrongly skips 0.8% of new pages (about 410 million).
Exact fingerprints (16 B each)800 GB
Bloom filter63 GB
False-positive rate0.82%
New pages wrongly skipped410M
50 billion URLs need 800 GB exactly, or 63 GB in a 10-bit-per-URL Bloom filter, which wrongly treats 0.82% of new URLs as seen (410M pages never fetched).
Bloom false-positive rate with the optimal number of hash functions: (1 − e^(−k/bits))^k with k = bits × ln 2.
A calendar with no end
One site has a “next month” link on every page, for ever. Another puts a session id in every URL. The crawler thinks it has found a million new pages.
Defences are blunt and necessary: a cap on pages per host (crawl budget) so no site can take unlimited share, limits on URL length and depth, detecting repeating path patterns, normalising away session ids, and ranking the frontier by value so low-quality, endless areas drop to the bottom. See how much of the crawl five trap hosts can swallow among a thousand ordinary sites.
1,000 ordinary 200-page sites plus 5 trap hosts, 20,000 fetches and no cap: 82% of fetches go to the traps. With a cap of 100 pages per host it falls to 2%.
Fetches20,000
Pages crawled per ordinary site3.7
Trap hosts' share of the crawl82%
With 5 trap hosts among 1,000 ordinary sites and no per-host cap, 82% of 20,000 fetches went into traps and each real site got 3.7 pages crawled.
Seeded simulation: the frontier is sampled uniformly; ordinary sites reveal up to 3 new URLs per fetch until exhausted; a trap host reveals 10 new URLs per fetch indefinitely.
News changes hourly, an old manual never does
You can afford 300,000 fetches a day for a million pages. Give each page the same share, or spend more where change matters?
The result has a twist: pages that change too fast to ever stay fresh are not worth chasing, since each fetch is stale almost at once. The best allocation spends more on valuable fast pages, but not unboundedly. Real crawlers also predict each page's change rate from its history and use signals such as sitemaps and push feeds to be told about changes instead of guessing. Move the budget and the weight.
With 300,000 fetches a day, 20% of pages changing twice a day and fast pages worth 3× a slow one, a uniform plan keeps 62% fresh (value-weighted); giving the fast pages 72% of the budget raises value-weighted freshness to 72%.
Share of budget to fast pages: uniform / best20% / 72%
Freshness gain+9.8 points
A uniform plan keeps 62% of the value fresh; giving the frequently changing pages 72% of the 300K daily fetches instead of 20% keeps 72% fresh, a gain of 9.8 points from the same budget.
Exact for Poisson page changes: freshness of a page fetched c times a day with change rate l is (1 − e^(−l/c)) ÷ (l/c); slow pages change 0.02 times a day. The best split is found by search.
Pick the mechanism
Six problems, four mechanisms.
Each problem has one mechanism that fits best. Each answer is worth 20 XP.
Match the symptom: idle workers, huge seen-set, endless URLs, or stale important pages?
Question 1 / 6
Hundreds of workers sit idle waiting for the same few hosts' delays.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Crawlers in the wild.
Published designs and standards for crawling.
Robots Exclusion Protocol
The long-informal robots.txt convention was standardised by the IETF in 2022 as RFC 9309, defining how sites tell crawlers which paths they may fetch and how crawlers must interpret the file.
a public web archive
Common Crawl publishes regular crawls of billions of web pages as open datasets, a resource many research projects and language models use instead of running their own crawler.
page refresh policies
Cho and Garcia-Molina's studies of web page change showed pages change at very different, roughly Poisson, rates and analysed refresh policies, including that pages changing too fast to stay fresh may not be worth chasing.
Interview angle
What interviewers actually ask.
Six questions, each worth 20 XP. Strong answers treat politeness as a hard constraint.
Say how the frontier is organised, how duplicates are avoided and how traps are bounded.
Question 1 / 6
Why is a plain FIFO frontier a bad idea?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
The crawler finds a hobbyist's recipe site with 50,000 pages, all linking to each other. Two hundred workers converge on it at once.
Being a good citizen is also good engineering. Honour robots.txt (which paths, and a requested Crawl-delay), enforce a minimum delay per host that adapts to its response time (slow down when it slows down), identify yourself in the User-Agent with a contact address, back off on 429 and 503 responses, and limit concurrent connections per host and per IP. Politeness is a hard constraint in the frontier, not a setting. Compare the two.
200 workers at 0.4 s per fetch make 500 requests a second against a host that can handle 100: 5× overload. With a 2-second per-host delay the load is 0.5 requests a second, 0.5% of its capacity.
Requests reaching that site500/s
Share of the site's capacity500%
Pages the site can be crawled for per day (polite)43,200
200 workers at 0.4 s per fetch send 500 requests a second to a site that can serve 100: 5.0× overload. It will go down, and then it will block you.
Arithmetic: unrestricted load = workers ÷ fetch time (0.4 s); polite load = 1 ÷ delay. Real crawlers also adapt the delay to the host's response time.