Design a Web Crawler

The single-server version ran the whole loop in one process. The first move is to pull it apart into a shape that can grow. Three roles are obviously different. One role is fetching pages — the part that spends its life waiting on the network. One role is holding the list of URLs still to fetch. And one role is storing the pages that come back. Splitting them lets each scale on its own. A crawl needs to fetch thousands of pages a second, but each fetch is mostly waiting — so what fetches the pages, where do the URLs waiting to be fetched live, and where do the fetched pages go?

The HTTP fetch is an inlet, not a connection design, and it is worth saying why once and moving on. A worker "fetches a page over HTTP." Underneath that sentence is a whole world — holding TCP connections open, reusing them, negotiating TLS, tuning socket timeouts and retries. That transport layer is a real engineering problem, and it is one another board owns. Here it is an inlet: the worker asks for a page and gets bytes back. Re-deriving the connection layer would rebuild another board's signature, so the design names the fetch and moves on.

That leaves the real shape decision, which is about where state is allowed to live. The fetch workers must hold nothing durable, because they sit on the firehose and die routinely: when a worker dies, the handful of URLs it had in flight are simply never marked done, so they stay pending in the frontier and get handed to another worker later. Nothing is lost, because the frontier owns the work, not the worker. Push all the pending-work state into the shared frontier and all the fetched pages into the store, and the fleet becomes a pure fetcher you scale flat — which is why the two hard problems that follow, the politeness of the queue and the memory of the seen-set, land on the frontier and the URL-seen store and nowhere else.

A stateless Fetcher fleet pulling from a single shared URL frontier, writing to a Page store. Put fetching in a horizontally scaled Fetcher fleet, hand it URLs from a single shared URL frontier, and write pages to a Page store. The fleet is many stateless worker processes, each holding a large number of fetches in flight at once, so that while one fetch waits on the network, hundreds of others are in progress on the same worker. A worker takes a URL, fetches the page, hands the page to the store, extracts the links, and checks each link against the record of URLs already fetched — enqueuing the new ones. The workers hold no long-term state of their own; everything durable lives in the pieces around them. The list of URLs still to fetch becomes its own component, the URL frontier, and right now — established here as the baseline the next use case attacks — it is the simplest possible thing: a single shared queue that every worker pulls from, first URL in is the first URL out.

The fetchers scale by simply adding more stateless workers — the fetch rate is a matter of how many concurrent fetches the fleet can hold open, so more workers means more pages a second. The frontier hands out URLs; the store keeps pages. But drawn honestly as the baseline the next use case demolishes, the frontier is a single shared first-in-first-out queue, and it carries the fatal flaw from the single-server version straight into the fleet: a flat queue cannot be polite, because it has no idea which host a URL belongs to. The very next use case faces exactly that.

The pipeline has a shape now, but the URL frontier is still the single shared queue from the last use case, and that queue carries the flaw that has been sitting in this design since the single-server version. The fleet has to stay busy at a couple of thousand pages a second. But a single host might own millions of the URLs in the queue, and you may only fetch that host gently, one page every so often. With one shared first-in-first-out queue, which URL does a free worker fetch next?

Follow the obvious answer first, because it is what most people reach for: make the shared queue bigger, or shard it across a few machines so it can hold more URLs and hand them out faster. The attraction is real — it is the design you already have. But making the queue bigger does not touch what actually breaks. Picture a giant forum with three million URLs. As the crawl discovers them, they pour into the shared queue and cluster together near the front. Now every free worker pulls the next URL, and the next, all from that one forum, back-to-back as fast as the fleet can go. Two things break at once: that one forum is hit by the full weight of the fleet — the denial-of-service you must never be — and every other host is stuck behind three million forum URLs, so the rest of the web is starved. A bigger queue holds more URLs and starves them harder; a sharded queue spreads the URLs but still has no idea that those three million belong to one host. The problem is not the queue's size. The problem is that a flat queue has no notion of which host a URL belongs to, and politeness is entirely about the host.

So how polite is "gentle," and where does that number come from? Not from a config file. The intuitive answer is that a site declares a Crawl-delay in its robots.txt and you obey it — true for some crawlers, Bing and Yandex among them, but false for the biggest one. Google's own documentation says plainly that Googlebot does not support the crawl-delay field at all. Instead the per-host pace is adaptive: read off how the host is actually behaving right now. If it answers quickly and cleanly, the crawler raises the rate and uses more connections; if it slows or returns errors, the crawler lowers the rate and backs off. The next-contact interval the heap uses is set by this live signal, not a number someone typed once. It is worth being precise about what this is not: it is not a counter ticking off requests per second against a limit — that counting machinery is a different, solved problem. Here the pace is a scheduling signal, and the frontier's job is to decide whose turn is next, and when.

A host-partitioned frontier — front queues for priority, back queues holding one host each, scheduled by a next-contact heap. Give the queue structure, because the structure is the design. Split the frontier into two layers with a scheduler between the fleet and the queues — the Mercator design. The first layer is a set of front queues: new URLs arrive here and are routed by priority, so the crawl is ordered by what matters more. The second layer is a set of back queues, and this is where politeness lives, held by a single invariant: each back queue holds URLs from exactly one host. All of one wiki goes in one back queue; all of that giant forum goes in another; a tiny blog gets its own. Because one back queue is one host, "be gentle to this host" becomes "do not pull from this back queue too often" — a property of a single queue, which is something you can actually schedule.

And the scheduling is the last piece: a min-heap of next-contact times. The frontier keeps, for each back queue, the earliest moment its host is allowed to be contacted again, and it keeps those moments in a heap so the soonest one is always on top. A free worker does not pick a URL directly — it asks the heap for the back queue whose host is due soonest, waits if that moment has not arrived, takes one URL from that back queue, and fetches it; then it sets that host's next-contact time a polite interval into the future and pushes it back on the heap. Run roughly three times as many back queues as fetch threads, so there are always eligible hosts and the fleet stays busy. The aha is that the hardest constraint — fast overall, gentle per host — is not a tension you tune away. It is a data structure: one host per back queue, and a heap that tracks which host is due next.

The frontier decides which URL to fetch next. But every fetched page yields dozens of links, and before a link can be added to the frontier the crawler has to answer one question, billions of times over: have I already fetched this URL? Get that check wrong and the crawl either loops forever over pages it has seen, or spends a fortune on machines that do nothing but remember URLs. Over a year of crawling, the record of URLs already fetched grows to tens of billions of entries. How do you hold that record so the check is both fast and cheap enough in memory to be affordable?

Follow the obvious answer first, because it is the one the single-server version used: store every URL you have fetched as a string, in a big distributed hash set, and check membership directly. It is technically correct — a hash set answers "seen it?" in about constant time, and it never makes a mistake. The trouble is the memory. Size it from the bytes up. A real crawler dataset measured the average URL at about 77 bytes. Ten billion URLs at 77 bytes each is about 770 gigabytes of raw strings — and that is before the overhead a hash table adds on top to index them. You are holding most of a terabyte of memory whose entire job is to answer a yes-or-no question. It works, and it is honest to say so, but it is enormously wasteful for what it does.

So the real question is not "hash set or something else" as a binary. It is: how much can you shrink that memory, and what do you have to give up to shrink it? A Bloom filter answers it by storing no URLs at all — only bits — which is why it beats storing the strings by roughly forty times, and why the published bits-per-element formula is independent of how long the URLs are. The asymmetry that makes it safe is mechanical: adding a URL sets several bits to one, and those bits are never cleared, so a genuine member always tests as present — the filter can miss, but it can never wrongly re-admit. That is exactly the property a crawler wants: never waste a fetch, occasionally miss one.

A Bloom filter for the URL-seen store — store no URLs, just bits. You do not actually need to store the URLs. You only need to answer "have I seen this one?" A Bloom filter does exactly that and nothing more: a bit array plus a few hash functions, where adding a URL sets a handful of bits and checking a URL tests those same bits. It never stores the URL itself, so it is dramatically smaller. Size it from the bits up. The published formula says a Bloom filter needs about 14.4 bits per element to hold a tenth-of-a-percent false-positive rate. Ten billion URLs at 14.4 bits each is about eighteen gigabytes — against 770 gigabytes for the raw strings. That is roughly forty times smaller, and it is the whole reason to use one.

The forty-times win comes with exactly one cost, and it is a cost a crawl can afford. A Bloom filter can return a false positive — say "yes, seen it" about a URL that was never fetched. But it never returns a false negative: it will never say "no, not seen" about a URL it actually has. So the only thing a false positive can ever cause is the crawler skipping a URL it had not really fetched. It can never cause the crawler to fetch the same URL twice. Read that trade carefully: the mistake the filter can make is occasionally missing a page, never wastefully re-fetching one, and the rate of that mistake is a knob you tune by spending a few more bits per element. Trading a tiny, tunable chance of missing a page for a forty-times memory reduction is a trade a web-scale crawl takes every time.

The board reads well now: the frontier is polite, and the seen-check is cheap. Time to keep the crawl correct and current, which the naive loop ignores in two ways. Two different URLs routinely serve the same content — a syndicated article, a mirror, the same page with a tracking parameter tacked on — and the URL-seen store cannot catch that, because the URLs really are different. And separately, a page fetched last week has probably changed by now, so the crawl has to revisit it — and the obvious revisit policy is wrong. Both problems land on the durable output of the whole system, the Page store.

Start with the duplicate content, because it is the sharper myth. The instinct is to say different URLs mean different pages, so the URL-seen store already handles duplicates. That is false, and it is a different problem from the one the URL-seen store solves. The URL-seen store answers "did I fetch this exact URL string?" It has nothing to say about two different URLs that return the same bytes. And that case is everywhere: a news story syndicated to a dozen sites, a documentation page mirrored across domains, the identical article reachable with and without a tracking parameter. Each of those is a distinct URL, so the URL-seen store correctly says "new," and the crawler correctly fetches it — and then the store would hold the same content many times over. Catching that needs a content-level check, which is what simhash is for.

Then freshness, where the intuitive policy loses. Recrawling fast-changing pages more often feels right and measures worse, because a page that changes every hour is stale no matter how often you revisit it — recrawl budget poured into it is wasted, while the steady pages you neglected go out of date. Spreading the budget uniformly keeps more of the archive fresh on average. Three distinct fixes — content dedup, durable storage, uniform recrawl — all land on the one durable output of the crawl, which is why this use case is also where the Page store becomes a real store.

A WARC store, a simhash near-dup gate on its write path, and a uniform recrawl feed. Catch duplicate content with a simhash gate on the write path, store pages in a compressed WARC container, and drive recrawls at a uniform rate. A simhash is a fingerprint computed from a page's content such that near-identical pages get near-identical fingerprints — unlike an ordinary hash, where a one-character change scrambles the whole value. The store computes a sixty-four-bit simhash of each incoming page and compares it against the fingerprints it has already stored; if a new page's fingerprint differs from an existing one in at most a few bit positions — the validated threshold is k=3, at most three differing bits — the two are near-duplicates, and the store skips or links the new copy instead of keeping it whole. This is a gate on the write path of the Page store: content comes in, the fingerprint is checked, and near-duplicates are caught before they cost storage. Google researchers validated this at a repository of eight billion pages, the scale that matters here.

Now freshness. Pages change, so the crawl feeds already-fetched pages back through the frontier to refetch them, on some schedule. The intuitive schedule is obvious and wrong: recrawl fast-changing pages more often than slow-changing ones — a proportional policy. It feels right, and it is worse. Cho & Garcia-Molina's foundational study tracked 720k pages across 270 sites for four months and found that a uniform recrawl rate — revisit every page at the same cadence — produces better average freshness than the proportional one. The intuition fails because a page that changes constantly is nearly always stale no matter how often you revisit it, so pouring recrawl budget into it is wasted, while the steady pages you neglected drift out of date. So the recrawl feed runs at a uniform rate, re-enqueuing already-crawled URLs into the frontier's front queues, competing for the same fetch capacity as fresh crawling.

Step back and look at what is built. It is correct and complete for a well-behaved crawl: the frontier is polite, the seen-check is cheap, content duplicates are caught, and the archive stays fresh. Now the premise arrives already broken, the way a real incident does — and the twist is that the thing that breaks is not any component on this board. It is what happens to the sites being crawled when crawlers, in aggregate, stop being polite. The frontier is fine. The URL-seen store is fine. The Page store is fine. Real websites fall over anyway. The Wikimedia Foundation, which runs Wikipedia and its sibling projects, reported that automated crawlers had become a serious operational problem: bots were generating at least 65% of the most resource-expensive traffic while being only about 35% of pageviews, and the bandwidth for downloading multimedia grew 50% in little more than a year. Nothing in Wikimedia's own infrastructure had a bug.

The instinct is to read the incident as "the sites should just block the bots" or "add more capacity at the origin." Both miss the mechanism, and the mechanism is the whole lesson. Bots consume two-thirds of the expensive traffic while being a third of pageviews because of a cache-miss asymmetry: humans cluster on popular pages that sit in a content delivery network's edge cache, cheap and close to the user, while a crawler bulk-reads the long tail of unpopular pages that miss the edge and get forwarded to the origin core datacenter, the expensive place to serve from. The crawler's load hurts more than its pageview share suggests not because it makes more requests, but because it makes the costly ones humans never trigger.

So the engineering answer is not at the sites; it is in the crawler's own scheduling. You can build a flawless frontier, a perfectly cheap URL-seen store, and a durable, deduped page store — everything in the four use cases before this — and the crawler can still be a disaster, because the thing that fails is not any component. It is the crawler's relationship with the hosts it reads. The frontier's adaptive per-host pace, which looked like good-citizen politeness, is really the load-bearing contract: read each host's live health and let the crawl slow itself down — widen the interval when a host slows, back off hard on errors, honor robots — before the origin has to defend itself.

Treat adaptive back-off and robots compliance as the load-bearing contract. Why do bots consume two-thirds of the expensive traffic while being a third of pageviews? Because of a cache-miss asymmetry. A human reader clusters on popular pages — the same few thousand articles everyone reads — and those pages sit in a content delivery network's edge cache, close to the user, cheap to serve. A crawler does the opposite: it bulk-reads the long tail, every obscure article, every rarely-visited page, precisely the pages that are not in the edge cache. So a crawler's requests miss the cache and get forwarded to the origin core datacenter, the expensive place to serve from. The crawler's load is disproportionately expensive not because it makes more requests, but because it makes the costly requests — the ones humans never trigger. So the frontier's adaptive back-off and robots compliance are the load-bearing contract, not a nicety.

Back in the frontier, the per-host pace was adaptive: speed up when a host responds well, slow down when it slows or errors. That looked like good-citizen politeness. The Wikimedia report shows it is actually the contract that keeps a crawler from becoming the incident. A crawler that ignores adaptive per-host pacing — that fetches every host as fast as its fleet allows — does not just risk getting blocked; at aggregate scale it becomes a de-facto denial-of-service on the origins it reads, and the cache-miss asymmetry is what makes that load bite so hard. So the frontier's job under load is to degrade gracefully against the origin's health: widen the next-contact interval when a host slows, back off hard when it returns errors, and honor the robots contract about what not to fetch at all. The reframe is bigger than this board: a crawler is a guest on millions of servers it does not own, and its politeness is not manners — it is the mechanism that keeps it from taking those servers down.