Web Crawler: requirements, scale and the crawl loop

The prompt: "Design a web crawler."

Attempt it for 45 minutes on paper first. This is the first genuinely large pipeline in the course, and the interesting constraints are not the ones candidates expect.

This lesson covers the first half of that 45 minutes: the questions that fix the scope, the estimate that reframes the whole problem, and the crawl loop you draw as the high-level design. The estimate produces a genuinely counter-intuitive result — on bandwidth alone, a billion pages a month is a two-machine job — and getting to it is worth more than any individual number.

What a crawler does

Start from a set of seed URLs. Fetch each page, store it, extract the links it contains, and add the new ones to the list of pages to fetch. Repeat. It is a graph traversal over the web, and the traversal itself is the easy part.

The questions

1. What is the crawl for? The purpose changes the design substantially.

Ask, and design for the answer. A candidate who assumes "search index" without asking has skipped the scoping step.

2. How many pages, and how fresh? "One billion pages a month" is a typical answer and it is the number every estimate hangs off. Freshness is a separate question — a news site changes hourly, a documentation page changes yearly, and recrawling everything at the same rate wastes almost all of your capacity.

3. What content types? HTML only is the sensible default. Images, PDFs, and video multiply storage by a large factor and add parsing complexity. Say what you are excluding.

4. Must it respect robots.txt? Yes — say so unprompted, before being asked. The Robots Exclusion Protocol is a file at the root of a site listing which paths crawlers may fetch and, by convention, a Crawl-delay requesting a minimum gap between requests. It is a convention rather than a legal instrument, but ignoring it gets your crawler blocked, gets your addresses blacklisted, and in a commercial context creates legal and reputational exposure. A candidate who has to be prompted to mention it has signalled something an interviewer will remember.

5. Is the crawl distributed, and across how many machines? It has to be, and the estimate below shows why in a way that may surprise you.

Two design properties to state as requirements

Politeness. Never send more than one request at a time to a single host, with a delay between requests. A crawler that opens 200 parallel connections to one small site is indistinguishable from a denial-of-service attack. This constraint shapes the entire frontier design in The URL frontier.

Robustness. The open web is hostile: malformed HTML, pages that never finish loading, servers that return 200 for everything, and deliberately constructed infinite URL spaces. The crawler must survive all of it without a human intervening. Robustness and traps covers this.

Add extensibility — a new content type or a new extraction step should be a new module, not a rewrite — and scalability, meaning capacity is added by adding machines.

Estimating the scale

With the scope fixed, put numbers on it. The individual figures matter less than where they lead.

Assumptions

"One billion pages a month. Average HTML page around 500 KB uncompressed, compressing about 5:1 for storage. Store raw HTML for five years. Text and links only — no images or video."

Fetch rate

1 billion ÷ 2.6 million seconds a month = ~385 pages per second average

Peak at 2× = ~770 pages per second

Bandwidth

385 pages/s × 500 KB = ~192 MB/s, or about 1.5 Gbps sustained

Storage

Stored compressed at 100 KB per page: 1 billion × 100 KB = 100 TB a month = 1.2 PB a year → 6 PB over five years before replication; × 3 for replication = ~18 PB

That is object storage territory (Section 26), not database territory. Metadata about each page — its URL, fetch time, status code, content hash — is small and belongs in a database; the HTML itself belongs in a blob store.

The counter-intuitive part

Now compute the machine count from bandwidth. A machine with a 1 Gbps link moves 125 MB/s, which at 500 KB per page is 250 pages per second.

385 pages/s ÷ 250 = about 2 machines

Two machines. A billion pages a month is, in pure throughput terms, a small job. Say this out loud, because it reframes the problem correctly:

"On bandwidth alone this is a couple of machines. So throughput is not what makes this hard. What makes it hard is politeness — I can only hit one host at a time, so I need enormous concurrency across different hosts to keep those two machines' pipes full — plus the deduplication state across billions of URLs, and surviving the hostile parts of the web."

That is a senior-level reframing and it changes what the rest of the design is about.

Why it is distributed anyway

Four reasons that have nothing to do with raw throughput:

1. Politeness forces concurrency. At one request per host per second, saturating 1.5 Gbps requires roughly 385 different hosts being fetched simultaneously, sustained — and many will be slow or unresponsive, so in practice thousands of in-flight requests.
2. Latency, not bandwidth, is the per-connection limit. A fetch takes 200 ms to 2 seconds between DNS, connection setup, and the server's own response time. One connection therefore yields at most a handful of pages per second regardless of how fat your pipe is.
3. DNS is a bottleneck of its own. A DNS lookup takes 20–100 ms and is synchronous unless you make it otherwise. At 385 pages per second across many hosts, DNS resolution alone needs caching and an asynchronous resolver, or it caps the whole crawler.
4. Fault tolerance. A single-machine crawler that dies loses its frontier — the entire list of what to fetch next — which is a bigger loss than the pages themselves.

The state that actually needs sizing

The seen-URL set is the memory problem. Crawling a billion pages a month discovers far more URLs than it fetches — call it 10 billion known URLs.

Storing them literally: 10 billion × 100 bytes = 1 TB, which cannot sit in memory on one machine.

Duplicate detection shows the standard answer: a Bloom filter at about 12 GB for a 1% false-positive rate. Note the number now, because it is the one that decides the architecture of the duplicate detector.

The high-level design: the crawl loop

With the reframing in place — throughput is easy, politeness, deduplication and survival are hard — draw the design. It is eight components in a cycle. Drawing this loop and walking one URL through it is the core of the high-level design.

The components, in order

1. Seed URLs. The starting set. Choosing them well matters more than it sounds: seeds determine what the crawler can reach at all. A general crawler seeds from popular directories and known high-quality sites; a topical crawler seeds from within its topic.

2. URL frontier. The queue of URLs to fetch, holding priority and politeness state. It is the heart of the design and gets its own deep dive (The URL frontier).

3. DNS resolver. Translates a hostname to an address. At 20–100 ms per uncached lookup this is a genuine bottleneck, so it needs an aggressive local cache keyed by hostname and honouring record time-to-live, plus an asynchronous resolver so a slow lookup does not block a fetch thread.

4. HTML downloader. Fetches the page. Sends a descriptive user-agent string identifying the crawler and a contact address — this is a politeness convention and it is what lets a site owner ask you to stop rather than blocking you. Applies connect and read timeouts, follows a bounded number of redirects, and caps response size so one enormous file cannot exhaust memory.

5. Content parser. Parses and validates HTML. Malformed markup is the norm, not the exception, so the parser must be tolerant. This step is separate from the downloader deliberately: a parser that crashes or hangs on hostile input should not take a fetcher with it.

6. Content-seen check. Has this content been fetched before, possibly under a different URL? Different from the URL check. Duplicate detection covers both.

7. Content store. Raw HTML to blob storage, metadata to a database. Most of the volume is in the blob store; the recently-used portion may be cached in memory or on local disk.

8. Link extractor → URL filter → URL-seen check → back to the frontier.

• Link extractor pulls href values and resolves relative URLs against the page's base.
• URL filter removes what you will never crawl: excluded file extensions, blocked domains, robots.txt-disallowed paths, and anything failing a URL sanity check.
• URL-seen check removes URLs already known, which is where the Bloom filter of Duplicate detection lives.
• Survivors are added to the frontier with a priority, and the loop repeats.

Walking one URL through it

https://example.com/articles/42 leaves the frontier. Its host resolves from the DNS cache in under a millisecond. The downloader checks the cached robots.txt for example.com, sees the path is allowed, and fetches — 800 ms, 480 KB of HTML. The parser extracts text and 60 links. A hash of the normalised content is checked against the content-seen store; it is new, so the HTML is compressed to ~95 KB and written to blob storage, with a metadata row recording the URL, fetch time, status 200, and content hash. The 60 links are normalised; 12 are filtered out as image files or disallowed paths; the remaining 48 are checked against the Bloom filter, 40 are already known, and 8 new URLs are added to the frontier.

That walkthrough, spoken in about forty seconds, is the answer to "how does it work?".

Breadth-first, not depth-first

The traversal is breadth-first. Depth-first would follow one site downward indefinitely, which violates politeness (all requests to one host) and risks falling into an infinite subtree (Robustness and traps). Breadth-first spreads across hosts naturally, which is exactly what the politeness constraint wants — though the frontier's priority ordering modifies pure breadth-first in practice.