Track 3 · Scale machinery
hardWeb Crawler
Fetch billions of pages without hammering any one site, fetching the same page twice, or losing your place. The hard part is the queue, not the fetch.
Suggested architecture
Scenario
A crawler is a fetch rate you choose. Fetchers wait on the web, so they fill by connections; the seen-URL check runs once per link, not per page, so it is the busiest thing in the design by a factor of forty.
The crawl rate. A billion pages a month is about 400 a second; a search engine is far more.
How long the average page takes to arrive. Slow hosts hold a fetcher's connection for the whole wait.
Outgoing links per page, each checked against the seen set.
Each holds 2,000 connections. Size by fetch time × rate.
Click a component for its role, common technology choices and tradeoffs, and what it is carrying at this scale. Hover a connection to see what flows along it. Drag to rearrange — layout changes are local and reset on reload.
Every figure here is a rough estimate from simple capacity arithmetic, not a benchmark. Each part carries its own assumption about what one copy can do — real numbers depend on your hardware, payloads and access pattern. The point is which component moves first as you turn the dials, not the digits themselves.
In plain words
A web crawler downloads pages, finds the links in them, and downloads those too — for the whole web. The loop is easy. What is hard is remembering a billion addresses you have already seen, being polite to each website while still going fast overall, and not losing your place when a machine dies.
The shape of the problem
A crawler sounds like a loop: take a URL, fetch it, extract the links, repeat. The loop is the easy part. The problems are everything the loop assumes: that you know whether you have seen a URL before (across a billion of them), that you can fetch from a site without knocking it over, that a worker dying does not lose the frontier, and that you can tell the same page apart from itself under twenty different URLs.
Assume a billion pages a month, so about 400 pages/s sustained, with room to run ten times that during a full re-crawl. Each page yields around 40 links, of which nearly all have been seen.
The fetch rate is chosen, not discovered. Everything downstream is sized from it, and the seen-URL check — forty per page — is the busiest operation in the system.
The frontier is the crawler
The URL frontier — the crawler's to-do list — is a queue with two jobs that pull in opposite directions. Priority says important pages should be fetched first: a news front page before a forum archive. Politeness says no host should be fetched more than once every few seconds, whatever its priority.
The standard structure is two layers. Front queues, one per priority level, hold URLs by importance. Back queues, one per host, hold URLs for that host in order. A worker asks the frontier for the next URL and gets one from a host whose politeness timer has expired, chosen from the highest-priority front queue that has something for it. No worker ever coordinates with another about a host; the frontier does it for them.
Politeness is a property of the queue, not of the fetcher. If workers have to remember when they last hit a host, they will get it wrong the moment there are two of them.
Have we seen this URL?
Forty links per page, 400 pages a second, is 16 000 "seen?" checks a second against a set of a billion URLs. An exact set is tens of gigabytes; a hash table that size does not live in one machine's memory and is too slow on disk at that rate.
A Bloom filter answers the question from memory in a fraction of the space: a billion URLs at a 1% false-positive rate (how often it wrongly says "seen") is about 1.2 GB. It never says "not seen" for a URL that was seen. It occasionally says "seen" for one that was not — and the crawler simply skips that page. A few missed pages in a billion is a price worth paying for a check that costs nothing. The exact set still exists, on disk, for the rare cases that need certainty.
The same trick, applied to content rather than URLs, catches duplicates: a simhash of the page text — a fingerprint where similar text gives similar bits — compared by counting the bits that differ, finds the same article mirrored under a different address.
Fetchers wait, parsers work
A fetch is 400 ms of waiting for a remote server, so a fetcher's capacity is concurrent connections — thousands per instance with non-blocking I/O (one thread juggling many connections instead of one thread per connection) — and the slider for fetch time is what fills them. Parsing is the opposite: CPU-bound, a few milliseconds of real work per page, scaled by instance count in the ordinary way. They are different kinds of machine and should be sized separately.
DNS — turning a hostname into an address — is the dependency nobody draws. A billion pages is a billion hostnames to resolve; a local caching resolver turns that into a few percent of misses.
Where this design breaks
- A single huge host. Politeness caps any one host at a few requests a second, so crawling a site with a hundred million pages takes a year. That is correct; the fix is a separate agreement with the site, not a faster crawler.
- Crawler traps. Calendars that generate a page for every date, forever. Depth limits and per-host page budgets, enforced in the frontier.
- Losing the frontier. If it lives only in worker memory, one crash loses the crawl's place. It is a durable queue for exactly this reason.
- Re-crawl policy. Fetching everything monthly wastes most fetches on pages that never change. Track change frequency per page and let the scheduler use it.
Take this with you
- The one idea: the frontier is the crawler. Priority and politeness live in the queue, so workers can be dumb and many.
- In an interview, explain the two-layer frontier, the Bloom filter for "seen?", and why fetchers and parsers are different kinds of machine.
- At work, the same pattern — a durable to-do list feeding waiting-bound workers — is most batch pipelines. Size the workers by concurrent calls.