Design a web crawler

Design a web crawler for a search engine. Start with one process and one queue, grow it with a polite per-host frontier, parsing off the fetch path, a seen set and recrawls, then stress it with the Bloom filter, ten times the pages, spider traps and near-duplicates, with code.

Mid-level27 min core · 45 min full depth

Read first: Estimation Queues and streams
Scaling patterns: Timeouts, retries and circuit breakers Backpressure and load shedding
Building blocks: Bloom filters and sketches Queues and streams Partitioning Blob storage Rate limiting Consensus
Related: Distributed rate limiter Distributed job scheduler

“Design a web crawler for a search engine. It should crawl about a billion pages a month.”

The loop fits in five lines: take a URL, fetch it, save it, pull out the links, and queue the new ones. Everything hard is about what that loop does to other people’s servers, and to your memory.

A crawler walks a graph nobody owns. Every step costs a request to a stranger’s server, and that stranger can block you. So this page starts with one process and one queue, and lets the numbers grow it. Then it tests the result against three questions. How do you remember 10 billion URLs? How do you avoid wasting the budget on traps and copies? And which pages do you fetch at all?

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains each part.

Keep one queue per website host, and a heap of when each host may next be fetched. A fetcher only ever gets a URL for a host that is due. So the crawler stays polite, however many fetchers there are.
Wait at least ten times as long as the last fetch took. A slow server gets fewer requests, with no configuration. robots.txt is read first and cached for a day.
Remember URLs as 8-byte fingerprints, with a Bloom filter in memory in front. The filter answers “definitely new” for free. Every “maybe seen” is checked against the exact fingerprints, so no page is ever lost to a wrong guess.
Split the frontier by website. Each node owns whole sites: their queues, their timers and their part of the seen set. So politeness never needs coordination between machines.
Spend a fixed budget. Each site gets a page budget that grows with how many other sites link to it. Traps and spam farms burn their own small budget, not the crawl.

Scope it

A few questions decide how the crawler chooses pages, how often it returns, and what each page costs.

Interviewerminute 0

Design a web crawler for a search engine. About a billion pages a month.

What they are testing

Whether you ask what the crawl is for, how fresh it must be and what content counts, because those decide the frontier and the storage. Two or three minutes. Starting with “we’ll use Kafka and a fleet of workers” before asking what the pages are for reads as a memorized diagram.

These four questions matter most:

What is the crawl for? A general web search index. An archive would keep every version. A fixed list of sites would need no discovery at all.
How many pages? 1 billion fetches a month, out of about 10 billion URLs we know about. So we can never fetch everything, and choosing which pages matters.
How fresh? Important pages within a day, a typical page within 30 days. News in minutes would need a separate fast lane.
Do we run JavaScript? No, HTML only. A real browser costs 10 to 100 times the CPU per page, and needs its own queue.

From these answers we make five promises:

Polite. At most one open connection per host. A gap of at least a second, and at least ten times the last fetch time. Back off on the first “too many requests” answer. This must hold even during failures.
Fast enough. 1 billion pages a month, with room for three times that rate to catch up after an outage.
Fresh. The top 1% of pages fetched again within a day, a typical page within 30 days.
Never lose a page. A page handed to the indexer is never lost. A crash costs at most a few minutes of work that can be redone.
Accurate. Fewer than one new URL in a billion is wrongly treated as already seen.

We leave out indexing and ranking, which use our output. We also leave out JavaScript and pages behind logins.

Go deeperMore questions, and what each changes1 min

Question	We assume	If the answer were different
How long to keep?	Every fetched version, 5 years	Latest version only divides storage by about 60
Ten times bigger?	Not yet	Splitting the frontier becomes a day one decision
Which content?	HTML, no images or PDFs	Each type needs its own parser and its own size limits

The numbers that decide it

Now we work out the numbers. Each one should change a decision.

Assumptions

Pages fetched a month: 1 billion
Provisioned over average: 3×
Average page, uncompressed: 100 KB
Compression on disk: 4×
Links per page: 40
Seconds per fetch: 1
Seconds between hits on one host: 10
URLs the seen set remembers: 10 billion
Years of pages to keep: 5 years

Fetch rate390/s1,200/s provisioned

1 billion ÷ (30 × 86,400 seconds) is about 390 fetches a second. A crawler has no traffic peaks, because we choose the rate. We still plan for three times that, to catch up after an outage.

So we size every part for 1,200.

In flight1,200fetches at once

A fetch takes about a second, mostly waiting for the other server. Fetches in flight = rate × time = 1,200 × 1 second.

So we use async I/O on a few servers, not a thread per request.

Hosts12,000in rotation

Each host gives us at most one page every 10 seconds or so. To fetch 1,200 pages a second, we need at least 1,200 × 10 = 12,000 hosts with URLs waiting and due.

So we organize the frontier by host. One plain queue of URLs can't do it.

Storage25 TBa month; 1.5 PB kept

Pages compress about 4 to 1, so a billion pages is 25 TB a month, and 1.5 PB over 5 years.

So we write large batched files to object storage, never a database row per page.

Seen set46,000/schecks

10 billion known URLs, and about 40 links on each page: 46,000 checks a second. As 80-byte strings that is 800 GB. As 8-byte fingerprints, 160 GB. As a Bloom filter, 12 GB.

So we store fingerprints, not URLs, with a Bloom filter in memory in front.

Bandwidth comes out at 1,200 × 100 KB = 120 MB a second, about 1 Gbit/s. That’s small, so it doesn’t drive the design. Change an assumption in the calculator to see what flips. At ten times the pages, one frontier node can’t keep up, so the frontier must be split from day one.

Change an assumption

Pages fetched a month1 billionProvisioned over average3×Average page, uncompressed100 KBCompression on disk4×Links per page40Seconds per fetch1Seconds between hits on one host10URLs the seen set remembers10 billionYears of pages to keep5 years

Fetches, average: 390/s
Fetches, provisioned peak: 1,200/s; One frontier node can dispatch this; a handful of fetcher servers do the work.
Fetches in flight at peak: 1,200; Little's law: concurrency is rate times time. Async I/O, not a thread per fetch.
Hosts that must be ready at once: 12,000; Each host gives at most one page per gap, so the frontier must keep this many hosts queued or fetchers idle.
Download bandwidth, peak: 120 MB/s; About 1 Gbit/s of inbound traffic, which most clouds do not charge for.
Seen-set checks, peak: 46,000/s; Past what one node takes as a call per link: batch the checks and keep the set in memory as fingerprints behind a Bloom filter.
New page data a month: 25 TB
Page data over the plan: 1.5 PB; Petabytes: large batched WARC files on object storage, never a database row per page.
Seen set as URL strings: 800 GB; Too big for one machine’s RAM: store 8 byte fingerprints instead of the URLs.
Seen set as 8 byte fingerprints: 160 GB; 8 bytes a key plus index overhead. Fits one large machine, on SSD with a Bloom filter in RAM.
Bloom filter, 1% false positives: 12 GB; 9.6 bits per URL and 7 hash functions. Every false positive is a page never crawled.
Bloom filter, 0.1% false positives: 18 GB; 14.4 bits per URL and 10 hash functions: 50% more memory for 10 times fewer losses.
Page metadata: 2 TB; About 200 bytes a URL: a wide-column store on a few nodes.

Build the design

We start with the simplest design that works. Then we let the numbers break it, one at a time. Each step fixes only what broke, adds only the boxes that fix needs, and says what the fix costs. The numbers already told us two things: politeness, not bandwidth, limits the rate, and the seen set is too big to hold as strings.

Step 1. One crawler process

The simplest version is one process with one first-in, first-out queue. It takes a URL, fetches it, saves it, and queues the new links.

Web crawler · architecture

Stage 1: One crawler process

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Pages fetched per second: 1,200

Stage 1 of 6

One crawler process

Why this stage

Nothing yet.

This is the smallest design that crawls at all.

What we add

One process that pops a URL from a FIFO queue, fetches it, saves the page to local disk, extracts links, and enqueues the ones a hash set has not seen.

What it costs

It hammers whichever host it is on, ignores robots.txt, does about 100 pages a second, and loses everything if it crashes.

At 1k pages fetched per second, Fetchers is 1200% busy. Stage 2 is the fix.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One crawler process with blocking fetches and parsing handles about 100 pages a second.
One async fetcher server handles about 200 pages a second while it also parses, or 500 when it only fetches.
One parser server handles about 300 pages a second.
One frontier node hands out about 5,000 URLs a second and takes in 100,000.

Checking for seen links

A seen set that makes one network call per link handles about 30,000 checks a second.
Batched against a Bloom filter in memory, it handles millions.

Links per page

Each page has about 40 links, and about 10 of them are new.

It breaks in two ways. One process fetches a few pages a second, and we need 1,200. And it is rude. Most links on a page point to the same site, so the queue fills with long runs of one site’s URLs. Add a fleet of fetchers draining that queue, and they hit one small site from every machine at once. Soon an abuse email arrives: 300 requests in a minute to a small blog.

Step 2. A polite frontier and a fetcher fleet

The part that decides what to fetch next is called the frontier. Ours has two layers, from the Mercator crawler (Heydon and Najork, 1999):

Front queues decide priority. A new URL goes into one of a few queues by how important it is. A selector takes from them with a bias toward the important ones, so low-priority URLs still trickle through.
Back queues decide politeness. Each back queue holds URLs for exactly one host. A heap (a structure that always hands back the smallest item) orders hosts by the time each may next be fetched. A fetcher asking for work gets a URL from the host that is due soonest. That host then leaves the heap until its fetch finishes.

So politeness is built into the data structure. No fetcher can receive a URL for a host that isn’t due, and a busy host isn’t in the heap at all.

How long to wait. The largest of 1 second, ten times the last fetch time, and the site’s Crawl-delay if it sets one. So a server that takes 2 seconds to answer gets one request every 20 seconds. A “too many requests” (429) or “unavailable” (503) answer starts a backoff of a minute that doubles, up to an hour.

PolitenessScheduler.javapoliteness_scheduler.pyPolitenessScheduler.cspoliteness_scheduler.gopoliteness-scheduler.ts

// The back half of a Mercator-style frontier: one FIFO queue per host, and a heap ordered by
// the time each host may next be fetched. A fetcher only ever receives a URL whose host is due,
// so politeness is a property of the data structure, not something every fetcher must remember.
class PolitenessScheduler {
    private record Due(long at, String host) {}

    private final Supplier<Optional<String>> frontQueues; // the priority side: best URL next
    private final int maxHosts;  // about fetch rate x per-host gap; fewer and fetchers sit idle
    // One queue per host. A host is in the heap only while nobody is fetching it, which is what
    // stops two fetchers from ever hitting the same server at the same moment.
    private final Map<String, ArrayDeque<String>> backQueues = new HashMap<>();
    private final PriorityQueue<Due> heap = new PriorityQueue<>(Comparator.comparingLong(Due::at));
    // Kept after a host's queue empties, so a host that comes back is not hit early.
    private final Map<String, Long> earliest = new HashMap<>();
    private final Map<String, Long> backoff = new HashMap<>();

    static final long MIN_GAP_MS = 1_000;
    static final long FIRST_BACKOFF_MS = 60_000;
    static final long MAX_BACKOFF_MS = 3_600_000;

    PolitenessScheduler(Supplier<Optional<String>> frontQueues, int maxHosts) {
        this.frontQueues = frontQueues;
        this.maxHosts = maxHosts;
    }

    // Called by a fetcher that wants work. Empty means no host is due yet: wait, don't spin.
    synchronized Optional<String> next(long now) {
        refill(now);
        Due top = heap.peek();
        if (top == null || top.at() > now) return Optional.empty();
        heap.poll();  // the host is now busy until done() puts it back
        return Optional.of(backQueues.get(top.host()).poll());
    }

    // Called when a fetch finishes. The gap scales with how long the server took, so a slow,
    // struggling server automatically gets fewer requests (Mercator's 10x rule).
    synchronized void done(String host, long now, long fetchMs, int status, long crawlDelayMs) {
        long gap = Math.max(MIN_GAP_MS, Math.max(10 * fetchMs, crawlDelayMs));
        if (status == 429 || status == 503) {  // the server said slow down: double the penalty
            backoff.merge(host, FIRST_BACKOFF_MS, (old, first) -> Math.min(old * 2, MAX_BACKOFF_MS));
        } else if (status < 500) {
            backoff.remove(host);
        }
        long at = now + gap + backoff.getOrDefault(host, 0L);
        earliest.put(host, at);  // production bounds this map; it is per host, not per URL
        ArrayDeque<String> q = backQueues.get(host);
        if (q.isEmpty()) backQueues.remove(host);  // frees a slot for a new host
        else heap.add(new Due(at, host));
    }

    // Pull from the priority queues until every slot holds a host. A URL for a host that already
    // has a queue joins it, so a host's URLs keep their priority order.
    private void refill(long now) {
        while (backQueues.size() < maxHosts) {
            Optional<String> url = frontQueues.get();
            if (url.isEmpty()) return;
            String host = URI.create(url.get()).getHost();  // politeness by host; see the text on IPs
            ArrayDeque<String> q = backQueues.get(host);
            if (q != null) {
                q.add(url.get());
                continue;
            }
            q = new ArrayDeque<>();
            q.add(url.get());
            backQueues.put(host, q);
            heap.add(new Due(Math.max(now, earliest.getOrDefault(host, 0L)), host));
        }
    }
}

robots.txt comes first. A site’s robots.txt file says which pages crawlers may fetch. The first fetch from any host is that file, and its rules are cached for up to 24 hours. A missing file means no rules. A server error means “assume everything is off limits, and try later”.

Web crawler · architecture

Stage 2: A polite frontier and a fetcher fleet

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Pages fetched per second: 1,200

Stage 2 of 6

A polite frontier and a fetcher fleet

Why this stage

Politeness is a requirement: a FIFO of extracted links sends bursts at one host.

And at the 1,200 pages/s peak, one process is 12 times over.

What we add

A fleet of async fetchers, a frontier with priority queues in front and one queue per host behind, a robots.txt cache, and a local caching DNS resolver.

What it costs

The seen set is now a network call from every fetcher: about 48,000 checks/s against one node, and it holds every URL as a string.

At 1k pages fetched per second, URL seen set is 160% busy. Stage 3 is the fix.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One crawler process with blocking fetches and parsing handles about 100 pages a second.
One async fetcher server handles about 200 pages a second while it also parses, or 500 when it only fetches.
One parser server handles about 300 pages a second.
One frontier node hands out about 5,000 URLs a second and takes in 100,000.

Checking for seen links

A seen set that makes one network call per link handles about 30,000 checks a second.
Batched against a Bloom filter in memory, it handles millions.

Links per page

Each page has about 40 links, and about 10 of them are new.

Now the crawl is polite, and fetchers scale out. But each fetcher also parses pages and checks links, so slow parsing holds up fetching. And we still need to remember which URLs we’ve seen.

Go deeperQueue counts, shared servers and slow DNS1 min

How many back queues. At least the 12,000 hosts from the numbers, and about three times that, so slow hosts never leave fetchers idle. This number, not the fetcher count, sets throughput.

Hosts are not servers. One shared hosting address can serve thousands of sites. So the frontier adds a looser limit per IP address too. It also budgets per registered domain, so a million subdomains of one site count as one site.

DNS is a hidden bottleneck. Turning a host name into an address can take 200 ms, or seconds when a site’s name servers are slow. So each fetcher uses a local caching resolver, and looks up a host when its back queue is created. By the time the host is due, its address is ready.

Step 3. Parsing off the fetch path

Fetching mostly waits on the network. Parsing burns CPU. So they run on different machines, and scale separately. Fetchers publish each page to Kafka, and parser workers do the rest. They pull out links, check for copies, store the page and write its record. Kafka also means a crashed parser can replay pages instead of losing them.

Step 4. Remembering what we’ve seen

Every link is first normalized: written in one standard form, so two spellings of the same URL match. Then it is hashed to a 64-bit fingerprint. The question is how to remember 10 billion of them:

Option	Memory for 10 billion	When it is wrong
URL strings	About 800 GB	Never, but it doesn’t fit
Exact 8-byte fingerprints on SSD	About 160 GB	3 URLs in 10 billion; but a disk read per new URL
Bloom filter alone, 1% wrong	12 GB	1 in 100 new URLs is never crawled, permanently
Bloom filter in front of fingerprints	12 GB RAM + 160 GB SSD	Only the 3 fingerprint clashes: the pick

A Bloom filter is a compact bit array that can say “definitely not seen” or “maybe seen”. Its “no” is always right, so a new URL never touches the disk. A “maybe” is checked against the exact fingerprints on disk, so a wrong “maybe” costs one disk read, never a lost page. The first stress test sizes it.

Copied pages are caught after the fetch. An exact hash of the page text catches identical copies. A simhash catches pages that differ only in a date or an ad. It’s a fingerprint that changes only a little when a page changes a little. A copy is recorded as an alias of the first, and not stored again.

Web crawler · architecture

Stage 3: Parse and dedup off the fetch path

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Pages fetched per second: 1,200

Stage 3 of 6

Parse and dedup off the fetch path

Why this stage

At the peak the seen set takes 48,000 calls/s against about 30,000, and 10 billion URLs as strings are about 800 GB of RAM.

What we add

Kafka between fetchers and parsers, a seen set of 8 byte fingerprints behind a Bloom filter, content hashes for duplicate pages, WARC files on object storage, and a page metadata table.

What it costs

A page is parsed seconds after it is fetched instead of at once, and there are three more stores to run.

At 1k pages fetched per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One crawler process with blocking fetches and parsing handles about 100 pages a second.
One async fetcher server handles about 200 pages a second while it also parses, or 500 when it only fetches.
One parser server handles about 300 pages a second.
One frontier node hands out about 5,000 URLs a second and takes in 100,000.

Checking for seen links

A seen set that makes one network call per link handles about 30,000 checks a second.
Batched against a Bloom filter in memory, it handles millions.

Links per page

Each page has about 40 links, and about 10 of them are new.

Follow one fetch, and then one fetched page, through the design:

Web crawler · architecture

Trace a request: Fetch one page

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasionalHop in motionHops doneResponse

Fetch one page: step 1 of 6

URL frontier to Fetchers

A fetcher asks for work. The frontier pops its heap: the host whose next allowed time has passed. That host’s queue hands over its oldest URL, and the host is marked busy so no other fetcher can touch it.

1 ms of a 1000 ms budget

URL frontier → Fetchers1 ms
Fetchers → DNS resolver1 ms
Fetchers → Robots cache0 ms
Fetchers → Web servers550 ms
Fetchers → Kafka5 ms
Response

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

Step 5. Coming back for changes

So far each URL is fetched once. But the web keeps changing, and a crawl that never comes back goes stale within weeks.

Pages change at very different rates: a news front page every few minutes, an old forum thread never. A recrawl scheduler reads each page’s history and feeds due URLs into the front queues, beside new ones. Asking “has this changed since this version?” costs a tiny 304 Not Modified answer when nothing changed. About 60% of the budget goes to recrawls and 40% to new pages. The folded section at the end of the build explains how the interval is chosen.

Web crawler · architecture

Stage 4: Recrawl by change rate

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Pages fetched per second: 1,200

Stage 4 of 6

Recrawl by change rate

Why this stage

A requirement, not load: the index must stay fresh, and pages change at wildly different rates.

A one-shot crawl goes stale in weeks.

What we add

A recrawl scheduler that reads each page’s change history from the metadata table and feeds due URLs into the frontier with a priority.

What it costs

Recrawls compete with discovery for the same fetch budget, so the split between them becomes a tuning knob.

At 1k pages fetched per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One crawler process with blocking fetches and parsing handles about 100 pages a second.
One async fetcher server handles about 200 pages a second while it also parses, or 500 when it only fetches.
One parser server handles about 300 pages a second.
One frontier node hands out about 5,000 URLs a second and takes in 100,000.

Checking for seen links

A seen set that makes one network call per link handles about 30,000 checks a second.
Batched against a Bloom filter in memory, it handles millions.

Links per page

Each page has about 40 links, and about 10 of them are new.

This is enough for a mid-level answer. A frontier with per-host queues. robots.txt. A seen set that is honest about its errors. And recrawls on a schedule. The stress tests are what make it a senior answer.

Go deeperWhat a fetch sends, and what each answer means2 min

Each request names the bot and asks only for what changed:

GET /blog/2026/10/post.html HTTP/1.1
Host: example.com
User-Agent: ExampleBot/2.1 (+https://example.com/bot)
Accept-Encoding: gzip, br
If-None-Match: "a7f3c9"
If-Modified-Since: Tue, 06 Oct 2026 09:12:44 GMT

The User-Agent links a page explaining the bot and how to opt out. The last two headers come from the last fetch, so an unchanged page costs a 304 with no body.

Response	What the crawler does
`200`	Store, parse, record the version tags
`304`	Record “unchanged”, lengthen the recrawl interval; nothing to store
`301`, `308`	Queue the target as a new URL; mark the old one as an alias
`429`, `503`	Back off this host, honoring `Retry-After`; requeue the URL

Bodies are capped at 10 MB and fetches time out after 30 seconds, so a hostile server can’t hold a connection forever. The indexer gets one small Kafka event per stored page: the URL, fetch time and where the page sits in its WARC file.

Go deeperWhere the state lives1 min

What	Rate	Lives in
Next URL for a due host	1,200/s	Frontier, memory plus local disk
Is this URL new?	46,000/s	Seen set, memory plus SSD
Host rules and timers	Every fetch	Frontier memory, backed up
One record per URL	1,200/s	Cassandra, keyed by URL fingerprint
Page bodies	25 TB/month	WARC files on object storage

Pages are stored in WARC files of about 1 GB each, the archive format the Internet Archive uses. A billion separate objects a month would cost $5,000 in storage write requests alone. 25,000 large files cost almost nothing.

The URL record holds the last fetch time, version tags, content hash and simhash. It also holds where the page is stored, how many times it changed, and when it is next due. Cassandra suits 10 billion rows of point writes. Each write carries the fetch time, so a replayed old fetch never overwrites a newer one.

Go deeperA parser crash replays a page, never loses it2 min

A parser commits its Kafka position only after every write for the page has succeeded. So a crash means the page is processed again, never skipped:

A parser crash replays a page, never loses it

Scroll or pinch to zoom, drag to pan

Color key
Service
Queue or stream

Every write gives the same result if repeated. So the only trace of a replay is a duplicate record in a WARC file, which the indexer skips. The seen set and the frontier share one store, so “mark seen” and “queue it” are one write. Otherwise, a URL could be marked seen while its queueing failed, and it would never be crawled.

Go deeperWhat to fetch, and when to come back2 min

Which pages first. Priority decides which front queue a URL enters. We mix three signals: how important the site is (how many distinct sites link to it, computed daily), how deep the URL is inside its site, and, for a recrawl, how overdue it is. A small fixed share always goes to new sites, so the crawl keeps discovering.

How often to come back. A simple rule tracks each page’s change rate well enough: after a change, halve the interval. After no change, grow it by half. Keep it between an hour and 90 days. Then scale it by importance, and cap the total, so the crawl rate stays fixed however many URLs we know.

Other ways to order the crawl

Ordering	Strength	Weakness
Breadth-first	Simple, no extra data	Blind to quality; easy to spam
PageRank from the last crawl	Strong importance signal	Days old; nothing for new URLs
Importance passed along links as we crawl	Online and cheap	Noisy at first
Site budget plus page signals	Resists spam, works for new URLs	Needs a daily job for site importance

Counting observed changes underestimates fast pages, because two changes between visits look like one. Better estimators correct for that. Sitemaps and RSS feeds also announce changes before we look.

Stress it

The design is complete. Now we test it where crawling is hard. A seen set that must fit in memory. Ten times the pages. Sites that generate endless URLs. And copied pages. Only ten times the pages adds boxes.

Sizing the seen set

Interviewerminute 20

Walk me through the Bloom filter. How big is it, how many hash functions, and what happens when it’s wrong?

What they are testing

Whether you can work out the size from the count and the error rate. And whether you know that in a Bloom-only seen set, a false positive means that URL is never crawled. Treating it as a small random error is the red flag.

A Bloom filter is an array of m bits and k hash functions. Adding a URL sets k bits. A lookup says “maybe seen” if all k bits are set, and “not seen” otherwise, which is always right. For n URLs and a target error rate p, the best sizes are:

m = −n ln p / (ln 2)², about 9.6 bits per URL at 1%, and 14.4 at 0.1%
k = (m / n) ln 2, about 7 hash functions at 1%, and 10 at 0.1%

For 10 billion URLs, that is 12 GB at 1%. Each ten times fewer errors costs 4.8 more bits per URL. The k positions come from just two hashes combined, which works as well as k separate ones and is much cheaper.

BloomFilter.javabloom_filter.pyBloomFilter.csbloom_filter.gobloom-filter.ts

// The in-memory front of the URL-seen set. "No" is certain, so a new URL never needs a disk
// read; "maybe" goes on to the exact fingerprint store. Sized from the two numbers that matter:
// how many URLs it must hold, and the false-positive rate we accept.
class BloomFilter {
    private final long[] words;
    private final long m;  // bits
    private final int k;   // hash functions

    BloomFilter(long expected, double fpRate) {
        // m = -n ln p / (ln 2)^2 and k = (m / n) ln 2 minimize memory for a target rate:
        // 9.6 bits and 7 hashes a URL at 1%, 14.4 bits and 10 hashes at 0.1%.
        double ln2 = Math.log(2);
        m = (long) Math.ceil(-expected * Math.log(fpRate) / (ln2 * ln2));
        k = Math.max(1, (int) Math.round((double) m / expected * ln2));
        // Java arrays stop at 2^31 longs (16 GB): one filter per host partition stays far below.
        words = new long[(int) ((m + 63) / 64)];
    }

    // One call per extracted link: true means definitely new (and now recorded). Checking and
    // setting together halves the work, and the caller holds the partition's lock around it.
    boolean addIfAbsent(String normalizedUrl) {
        long h1 = fnv1a64(normalizedUrl.getBytes(StandardCharsets.UTF_8));
        long h2 = mix(h1) | 1;  // odd, so the k probes never collapse onto one bit
        boolean added = false;
        for (int i = 0; i < k; i++) {
            // Double hashing (Kirsch and Mitzenmacher): k positions from two hashes, as good as k
            // independent hashes for a Bloom filter and k times cheaper.
            long bit = Long.remainderUnsigned(h1 + i * h2, m);
            long mask = 1L << (bit & 63);
            int w = (int) (bit >>> 6);
            if ((words[w] & mask) == 0) {
                words[w] |= mask;
                added = true;
            }
        }
        return added;  // false: every bit was set, so "probably seen", ask the exact store
    }

    boolean mightContain(String normalizedUrl) {
        long h1 = fnv1a64(normalizedUrl.getBytes(StandardCharsets.UTF_8));
        long h2 = mix(h1) | 1;
        for (int i = 0; i < k; i++) {
            long bit = Long.remainderUnsigned(h1 + i * h2, m);
            if ((words[(int) (bit >>> 6)] & (1L << (bit & 63))) == 0) return false;
        }
        return true;
    }

    // FNV-1a keeps the example short. Production uses xxHash or Murmur3, which spread better.
    static long fnv1a64(byte[] data) {
        long h = 0xcbf29ce484222325L;
        for (byte b : data) {
            h ^= (b & 0xff);
            h *= 0x100000001b3L;
        }
        return h;
    }

    // The splitmix64 finalizer: turns h1 into an unrelated second hash.
    static long mix(long z) {
        z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L;
        z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL;
        return z ^ (z >>> 31);
    }
}

Go deeperWhy 3 clashes in 10 billion, and a filter that fills up1 min

Two different URLs can share a 64-bit fingerprint. The chance follows the birthday bound: 10 billion keys give about n² / 2⁶⁵ ≈ 3 clashes. So three URLs in 10 billion are wrongly treated as seen, which meets our promise.

The filter also gets worse as it fills. Sized for 10 billion and loaded with 20 billion, its 1% becomes about 16%. No URL is lost, since every “maybe” is checked, but one new URL in six now costs a disk read. So alert on how full it is, and rebuild it from the fingerprints in time.

Ten times the pages

The index team wants ten times the pages: 12,000 a second. What breaks first?

Fetchers and parsers just scale out. The frontier doesn’t: one node can’t hand out 12,000 URLs a second. So we split the frontier, the seen set and the DNS cache across nodes. The question is what to split by.

Split by	Politeness	Problem
Hash of the URL	Needs a lock across nodes for every host	Every fetch coordinates with other machines
Hash of the host	Local	A site with many subdomains spreads over many nodes
Hash of the registered domain	Local, including budgets and shared addresses	One huge site lives on one node, which politeness caps anyway

We split by site, the registered domain (example.com for blog.example.com). Each node owns its sites’ queues, timers, seen set slice and DNS cache. So politeness stays a local decision, with no coordination per fetch. Parsers send each new link to its owner through a Kafka topic keyed by site. Sites hash into 4,096 slots mapped to nodes, so adding a node moves slots, not URLs.

Web crawler · architecture

Stage 5: Partition the frontier by site

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Pages fetched per second: 1,200

Stage 5 of 6

Partition the frontier by site

Why this stage

At 10 times the load, 12,000 pages/s, one frontier node is 240% busy, and the seen set and DNS cache are heading the same way.

What we add

The frontier, seen set and DNS cache split into 16 partitions by a hash of the site (registered domain).

Each node owns its sites, so politeness stays a local decision.

What it costs

Links to sites another partition owns must be shipped there, and one huge site still lives on one partition.

At 1k pages fetched per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One crawler process with blocking fetches and parsing handles about 100 pages a second.
One async fetcher server handles about 200 pages a second while it also parses, or 500 when it only fetches.
One parser server handles about 300 pages a second.
One frontier node hands out about 5,000 URLs a second and takes in 100,000.

Checking for seen links

A seen set that makes one network call per link handles about 30,000 checks a second.
Batched against a Bloom filter in memory, it handles millions.

Links per page

Each page has about 40 links, and about 10 of them are new.

A giant site is not a hot spot, because politeness limits it to a few pages a second anyway. The cost is a few seconds of delay before a link to another site is queued.

Spider traps

A site has a calendar with a “next month” link on every page, and the crawler has fetched 4 million pages from it. What went wrong, and what stops it in general?

A spider trap is a site that generates URLs without end. Examples are endless calendars, session IDs in every link, and links that build ever-deeper paths like /a/b/a/b/.... Search filters and farms of generated subdomains are others. Some are accidents, and some are on purpose. The defenses come in layers:

Cheap limits on every URL: under 2,000 characters, a path under about 15 levels deep, and no part repeated three times.
A budget per site. Each site gets a page budget per crawl cycle that grows with how many other sites link to it. A million pages that only link to each other earn almost nothing.
Watch the yield. When most of a site’s recent pages are near-copies, cut its budget.

Go deeperWhich normalization rules are safe1 min

Normalization helps too. Some rules are always safe, like lowercasing the host or dropping the #fragment. Others, like dropping a query parameter, are learned per site. If removing it gives the same page on enough samples, it doesn’t matter for that site.

Rule	Safe?
Lowercase the scheme and host; drop the default port	Always
Resolve relative links and `.` and `..` parts	Always
Drop the `#fragment`	Always, for a crawler that doesn’t run scripts
Strip `utm_*` and other known tracking parameters	Almost always
Sort query parameters; drop session IDs; strip `index.html`	Per site: check the content hash is unchanged

Near-duplicate pages

Two pages are the same except for a timestamp and an ad, so a content hash says they differ. How do we catch them among 10 billion pages?

An exact hash changes completely when one byte changes. A simhash (Charikar, 2002) changes only a few bits when a few words change. Each word is hashed to 64 bits and votes on each bit position. The fingerprint has a 1 wherever the votes are positive. Google tested this on 8 billion pages and found that “3 bits or fewer differ” is a good test for near-copies.

Go deeperHow the lookup avoids comparing every page2 min

The lookup is the clever part. Split the 64 bits into 6 blocks. Two fingerprints within 3 bits differ in at most 3 blocks, so at least 3 blocks match exactly. Build one table for each choice of 3 blocks out of 6, which is 20 tables. A new page looks itself up in all 20, finds about 50 candidates in total, and checks each one fully.

SimHash.javaexample.pySimHash.csmain.goexample.ts

// Near-duplicate detection. A cryptographic hash changes completely when one byte changes, so it
// only finds exact copies. A simhash changes by a few bits when a few words change, so two pages
// that differ by a date or an ad land within a few bits of each other.
final class SimHash {
    static final int NEAR = 3;  // 3 of 64 bits: what Google found right for 8 billion pages

    // features: the page's words or word shingles, boilerplate stripped. A word that appears
    // often appears often in the list, which is how it gets more weight.
    static long of(List<String> features) {
        int[] votes = new int[64];
        for (String f : features) {
            long h = fnv1a64(f.getBytes(StandardCharsets.UTF_8));
            for (int i = 0; i < 64; i++) votes[i] += ((h >>> i) & 1) == 1 ? 1 : -1;
        }
        long fp = 0;
        for (int i = 0; i < 64; i++) if (votes[i] > 0) fp |= 1L << i;  // each bit is a majority vote
        return fp;
    }

    static boolean nearDuplicate(long a, long b) {
        return Long.bitCount(a ^ b) <= NEAR;
    }

    // Finding a match among 10 billion fingerprints without comparing against each one. Split
    // the 64 bits into 6 blocks. Two fingerprints within 3 bits differ in at most 3 blocks, so
    // at least 3 blocks match exactly. One table per choice of 3 blocks (20 tables), keyed by
    // those blocks: about 32 exact bits leave a couple of candidates per probe, not millions.
    static final int[] SIZES = {11, 11, 11, 11, 10, 10};
    static final int[] OFFSETS = {0, 11, 22, 33, 44, 54};

    static long[] tableKeys(long fp) {
        long[] keys = new long[20];
        int t = 0;
        for (int a = 0; a < 6; a++)
            for (int b = a + 1; b < 6; b++)
                for (int c = b + 1; c < 6; c++) {
                    long key = t;  // the table number keeps the 20 key spaces apart
                    for (int blk : new int[] {a, b, c})
                        key = (key << SIZES[blk]) | ((fp >>> OFFSETS[blk]) & ((1L << SIZES[blk]) - 1));
                    keys[t++] = key;
                }
        return keys;  // store the page under all 20; probe all 20, then check the full distance
    }

    // Any good 64 bit hash works; FNV-1a keeps the example short.
    static long fnv1a64(byte[] data) {
        long h = 0xcbf29ce484222325L;
        for (byte x : data) {
            h ^= (x & 0xff);
            h *= 0x100000001b3L;
        }
        return h;
    }
}

The 20 tables hold 20 copies of each fingerprint, about 1.6 TB for 10 billion pages. The exact hash is checked first, because it’s cheaper and settles most copies.

When things break

Interviewerminute 40

One of your 16 frontier nodes loses its disk. What did you lose, and how long until its sites are crawled again?

What they are testing

Whether you know which state is precious (queues and the seen set), which can be rebuilt, and how a takeover avoids two owners for one site.

Most failures may slow the crawl down. None may lose a page, or make us rude. The most important failure is a frontier node, because each one holds hundreds of millions of queued URLs. With 16 nodes, one fails every few weeks. Rebuilding its queues from the URL table would take hours. Instead:

Queues live on local SSD, in RocksDB, with only the ends in memory. The heap is rebuilt from the queues on start.
A checkpoint every 10 minutes. The node copies its new files to object storage, along with its position in the Kafka link topic.
One owner per partition. etcd gives each partition to one node with a lease, a claim that must be renewed. A node that can’t renew stops handing out URLs before its lease runs out. So two nodes never crawl one site at once.

These add the last boxes to the drawing: checkpoints in object storage, and leases in etcd.

Web crawler · architecture

Stage 6: Partitions that survive a crash

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Pages fetched per second: 1,200

Stage 6 of 6

Partitions that survive a crash

Why this stage

A failure domain, not load: with 16 frontier nodes, one dies every few weeks, and its partition holds hundreds of millions of queued URLs.

What we add

A coordinator that leases each partition to one node, and frontier checkpoints to object storage with a Kafka offset, so another node can take over.

What it costs

A takeover replays up to 10 minutes of links and refetches what the partition dispatched since its checkpoint.

The coordinator is one more consensus system to run.

At 1k pages fetched per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One crawler process with blocking fetches and parsing handles about 100 pages a second.
One async fetcher server handles about 200 pages a second while it also parses, or 500 when it only fetches.
One parser server handles about 300 pages a second.
One frontier node hands out about 5,000 URLs a second and takes in 100,000.

Checking for seen links

A seen set that makes one network call per link handles about 30,000 checks a second.
Batched against a Bloom filter in memory, it handles millions.

Links per page

Each page has about 40 links, and about 10 of them are new.

Another node takes over a dead partition

Scroll or pinch to zoom, drag to pan

Color key
Queue or stream
Database
Service

A takeover replays up to 10 minutes of links, and the seen set drops the ones already known. So nothing is lost. URLs handed out since the checkpoint are fetched again, about 45,000 pages, which is nothing in a billion a month. Every host restarts with a full gap, so recovery never bursts.

Never catch up by being rude. After any outage, every host restarts at its normal gap. The fleet has three times the needed capacity so that a backlog drains across more hosts, never with more requests per host.

Click any box to break it and see what happens:

Web crawler · architecture

Break it: what fails, who notices, what users see

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Break

Failure: click any box to break it

A frontier partition goes down

What breaks

Its hosts get no fetches, and links for them cannot be queued.

How we notice

Its lease is not renewed; the dispatch rate for the partition drops to zero.

What users see

One sixteenth of the crawl pauses for about a minute.

What we do

Another node takes the lease, loads the last checkpoint from S3 and replays Kafka from the offset in it.

URLs dispatched since the checkpoint, up to about 45,000, are fetched again.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

Go deeperEvery failure, and what happens2 min

Part	Failure	Impact	What we do
Frontier partition	Node or disk lost	One sixteenth of sites paused a minute or two	New owner loads the checkpoint and replays Kafka
Fetcher	Crash	A few hundred fetches redone	Busy hosts return to the heap after 60 s
etcd	Majority lost	Whole crawl pauses once leases run out	Five members survive two failures
Kafka	Down	Pages stop reaching parsers	Fetchers stop taking work; the frontier keeps every URL
Parser	Crash	Pages processed seconds later	Positions committed after writes; all writes repeatable
Page store	Uploads fail	WARC files queue on parser disks	Retry; positions not committed until the upload succeeds

If etcd itself loses its majority, every node stops when its lease runs out, and the whole crawl pauses. That sounds bad, but it’s the safe direction: a paused crawl annoys nobody, while a site with two owners gets twice the traffic.

What must be exact, and what needn’t be. Almost everything here is “at least once”. A link or a fetch may happen twice, and the seen set or the fetch time makes the repeat harmless. Exactly-once processing would be expensive, and buy nothing. The one strict rule is site ownership, because politeness rests on it. The lease gives it.

Go deeperRunning it: alerts and safety2 min

Wake someone up for:

any fetch inside a host’s gap, or two at once to one host
a fetch rate below 80% of plan for 30 minutes
fewer than 12,000 hosts ready in the heap (an early warning)
the most overdue top page being older than 36 hours
parsers more than 10 minutes behind

The crawler fetches URLs strangers wrote. A page can link to http://169.254.169.254/, the cloud’s internal metadata service. So resolve the address first, refuse private and local addresses, connect to the address you checked, and check again after every redirect. Cap both the download size and the unzipped size, because a small gzip file can expand a thousand times. Parse in a sandbox with time limits.

Make opting out easy. Publish the bot’s page, and apply a site owner’s block within a minute through the operator API.

Cost. Storage costs the most. By year five, 1.5 PB is about $30,000 a month on standard object storage. So older WARC files move to colder, cheaper tiers.

Wrap up

The whole design

Here is everything we built, in the order we built it. Use the buttons to step through it.

Web crawler · architecture

The full design, stage by stage

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Pages fetched per second: 1,200

Stage 6 of 6

Partitions that survive a crash

Why this stage

A failure domain, not load: with 16 frontier nodes, one dies every few weeks, and its partition holds hundreds of millions of queued URLs.

What we add

A coordinator that leases each partition to one node, and frontier checkpoints to object storage with a Kafka offset, so another node can take over.

What it costs

A takeover replays up to 10 minutes of links and refetches what the partition dispatched since its checkpoint.

The coordinator is one more consensus system to run.

At 1k pages fetched per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.The whole design. Step through it: one process, a polite frontier and fetchers, parsing and dedup, recrawls, a split by site, then partitions that survive a crash.

The numbers behind the busy bars

What one machine can do

One crawler process with blocking fetches and parsing handles about 100 pages a second.
One async fetcher server handles about 200 pages a second while it also parses, or 500 when it only fetches.
One parser server handles about 300 pages a second.
One frontier node hands out about 5,000 URLs a second and takes in 100,000.

Checking for seen links

A seen set that makes one network call per link handles about 30,000 checks a second.
Batched against a Bloom filter in memory, it handles millions.

Links per page

Each page has about 40 links, and about 10 of them are new.

The decisions, and what each one costs

Decision	We chose	We gave up	We’d choose differently if
Frontier	Priority queues in front, one queue per host	A simple distributed queue	We crawled a fixed list of a few sites
Seen set	Fingerprints behind a Bloom filter, batched	Links queued instantly	Losing 1% of pages were acceptable (Bloom only)
Copies	Exact hash, then simhash with 20 tables	1.6 TB of tables; some near-copies missed	We were an archive that keeps every copy
Recrawl	Adaptive intervals, weighted by importance	Catching a long-silent page’s first change	News needed minutes (feeds and a fast lane)
Splitting	By registered domain, 4,096 slots	Even load per node	Politeness didn’t matter, as for our own sites
Recovery	Leases, checkpoints every 10 minutes, replay	10 minutes of refetches per takeover	Partitions were small enough to rebuild quickly

How to spend 45 minutes

0 to 4. Purpose, scale, freshness, JavaScript or not. Politeness as a hard promise.
4 to 9. 390 a second, 1,200 in flight, 12,000 hosts, 1.5 PB, and the seen set three ways.
9 to 20. Build it: the two-layer frontier with robots.txt and DNS, parsing on Kafka, the seen set, recrawls. A mid-level answer can stop here.
20 to 28. The stress tests: the Bloom filter math, then splitting by site.
28 to 40. Traps, then near-copies or recrawl timing, whichever the interviewer leans toward.
40 to 45. A frontier node failing, then your own questions.

Never skip the per-host queues, the 12,000 hosts behind them, or what a false positive costs.

Follow-up questions

Interviewer asksNews search needs new articles within five minutes. Does this design do it?

Not through the normal recrawl. Add a fast lane. A few thousand news sites have their RSS feeds and sitemaps checked every minute or two. New article URLs go into the top front queue.

Interviewer asksA site changes robots.txt to block you. How fast do you stop?

Within 24 hours at worst, the cache limit the robots.txt standard allows. A site owner who contacts us gets a block through the operator API, which reaches the owning partition within a minute.

Go deeperMore follow-up questions2 min

What changes at 100 times the pages, 120,000 a second? Fetchers, parsers and partitions scale out as they are, to a few hundred partitions. The seen set reaches a trillion URLs, 16 TB of fingerprints, so checks become batched merges against a sorted file on disk, as IRLbot did. Bandwidth reaches 100 Gbit/s, so fetchers spread over regions, and 150 PB of storage forces keeping only the latest version of most pages.

Product wants JavaScript-rendered pages. What changes? A real browser costs 10 to 100 times the CPU of parsing. And every script and API call it makes counts against the host’s politeness. Add a render queue for pages whose HTML looks script-built. Cache scripts across pages. And give rendering its own budget.

Two frontier nodes both think they own a partition. What happens? The lease makes it rare. The old owner stops before its lease runs out, by a margin larger than the clock drift we allow. If it happens anyway, after a long pause, those sites see up to twice the rate for one lease period. Each fetch can also carry the lease number. Then a fetcher refuses work from an owner with an older one.

A site owner says you are slowing their server. What do you check? The politeness log for that host: gaps, connections at once, and whether several hosts share its address. If we were within limits, cap the site through the operator API. If not, it’s a politeness bug and an incident.

Design a web crawler

The answer in one minute

Scope it

The numbers that decide it

Build the design

Step 1. One crawler process

Stage 1: One crawler process

Why this stage

What we add

What it costs

Step 2. A polite frontier and a fetcher fleet

Stage 2: A polite frontier and a fetcher fleet

Why this stage

What we add

What it costs

Step 3. Parsing off the fetch path

Step 4. Remembering what we’ve seen

Stage 3: Parse and dedup off the fetch path

Why this stage

What we add

What it costs

Trace a request: Fetch one page

Step 5. Coming back for changes

Stage 4: Recrawl by change rate

Why this stage

What we add

What it costs

Other ways to order the crawl

Stress it

Sizing the seen set

Ten times the pages

Stage 5: Partition the frontier by site

Why this stage

What we add

What it costs

Spider traps

Near-duplicate pages

When things break

Stage 6: Partitions that survive a crash

Why this stage

What we add

What it costs

Break it: what fails, who notices, what users see

What breaks

How we notice

What users see

What we do

Wrap up

The whole design

The full design, stage by stage

Why this stage

What we add

What it costs

The decisions, and what each one costs

How to spend 45 minutes

Follow-up questions

Further reading

Keep reading

The designbeyondcode digest, every Saturday