Design a web crawler

For this problem, we'll design a crawler that collects about 1 billion HTML pages and keeps them reasonably fresh, for a search engine that indexes them later. We'll stop at "raw pages and links are stored"; indexing and ranking are the next system downstream (see How Google Search works). Interviewers like this question because the happy path is a simple loop, yet every box in it hides a real constraint: politeness towards other people's servers, duplicates everywhere, traps that never end, and a queue of billions of URLs that must survive crashes.

01Requirements

Here's the scope I'd agree on in the first five minutes.

Functional

• The system should take a list of seed URLs and crawl outward by following links.
• The system should download HTML pages and store the raw content for an indexer.
• The system should extract links from each page and add new, allowed URLs to the crawl.
• The system should obey robots.txt and limit how often it hits any single host.
• The system should recrawl pages over time, more often for pages that change often or matter more.

Non-functional

• Scale: about 1 billion pages per crawl cycle of roughly a month (assumption, confirm it).
• Politeness: by default no more than one open connection per host and a gap of seconds between requests to it; back off when a site returns 429 or 5xx.
• Robustness: survive malformed HTML, slow servers, crawler traps and our own machines failing, without losing the frontier.
• Freshness: important pages recrawled within days; the long tail within the cycle.
• Extensibility: new content types (PDF, images) and new parsers can plug in later.

At this point, ask your interviewer: "What is the crawl for (search, archive, price monitoring)? How many pages and how fresh? Only HTML? Do we render JavaScript? Do we need to respect a single region's legal rules?" A price tracker that hits 10,000 known pages hourly is a very different system from a broad web crawl.

02Core entities and API

The crawler is an internal system, so its "API" is mostly how stages talk to each other. The entities:

• URL record: normalised URL, host, priority, status, last fetch time, next due time, content checksum, SimHash, and the blob key of the latest copy.
• Host record: robots.txt rules and when they were fetched, resolved IP and when it expires, the next time we're allowed to hit the host, and recent error counts.
• Page blob: raw bytes plus response headers, stored in a blob store under a key like pages/<url-hash>/<fetch-time>.
• Link: source URL, target URL and anchor text, emitted by the parser for the indexer and for the frontier.

POST /v1/seeds                         (operators add starting points)
{ "urls": ["https://example.org/"], "priority": "high" }

POST /v1/frontier/lease                (a fetcher asks for work)
{ "worker": "fetch-17", "max": 50 }
200 { "lease_id": "l-9f2", "expires_in_s": 300,
      "urls": [ { "url": "https://example.org/a", "etag": "\"abc\"" } ] }

POST /v1/frontier/complete             (report results, release the lease)
{ "lease_id": "l-9f2",
  "results": [ { "url": "https://example.org/a", "status": 200,
                 "blob": "pages/7c1e.../2026-10-20T02:00Z", "checksum": "sha256:..." } ] }

The lease is the important design choice. A fetcher that dies simply lets its lease expire, and those URLs go back to the frontier. We'll come back to that under failures.

03Back-of-envelope estimates

All inputs are assumptions to confirm with your interviewer. The arithmetic is ours and rounded.

Two numbers drive the design. 400 pages a second is modest, so throughput isn't the hard part. Politeness is: at one request per host every couple of seconds, sustaining 400 pages a second needs at least ~800 hosts in rotation at any moment. The frontier must spread work across many hosts, and that shapes everything below.

04High-level design

Let's start with the version that fits on a laptop: a queue of URLs, one loop that pops a URL, downloads it, saves it and pushes its links. Then we make each step safe at scale.

To crawl outward from seeds, operators load seed URLs into the URL frontier, the to-do list of the crawl. Fetchers lease batches of URLs from it.

To download pages, fetchers run asynchronous HTTP clients with strict timeouts and size limits. Before a fetch, they look up the host in a DNS cache and in a robots.txt cache. DNS is a well-known crawler bottleneck: a lookup can take seconds and standard library resolvers are generally synchronous, so crawlers usually run their own caching resolver (IIR, DNS resolution).

To store raw content, a fetched page passes a content dedup check, then goes to a blob store (S3 or similar) and its URL record is updated in the URL metadata store, a sharded key-value table keyed by URL hash. Big immutable blobs go to object storage, small mutable state to a database (see Blob storage (S3)).

To discover new URLs, a parser extracts links and text. A URL filter normalises each link, applies trap rules and scope rules, and asks "have we seen this URL?". New URLs go back to the frontier.

To stay polite and fresh, the frontier enforces per-host pacing, and a scheduler feeds URLs whose "next due" time has passed back into it (deep dives 1 and 3).

Between stages I'd put durable queues (Kafka topics for "fetched pages" and "discovered links"), so a slow parser never blocks fetchers and a crash in one stage doesn't lose work. See Queues and event streams.

05Deep dives

1) The URL frontier: priority and politeness

Bad: one FIFO queue (plain breadth-first search). The 5,000 links from one site land next to each other, and your 400 threads all fetch from that one host at once. That's a denial-of-service attack with extra steps, and it treats spam and a news home page with the same urgency.

Good: a priority queue plus a per-host lock. Priority fixes "what first". The lock stops parallel hits on one host, but threads still grab that host's next URL the instant the lock frees, and they pile up waiting on the busy host.

Great: front queues for priority, back queues for politeness. This is the classic Mercator design, described clearly in Introduction to Information Retrieval (The URL frontier):

1. A prioritiser gives each URL a priority from its importance and how often it changes, and appends it to one of a few front queues.
2. A selector, biased towards high priority, moves URLs into back queues. Each back queue only ever holds URLs of one host.
3. A min-heap stores, per back queue, the earliest time that host may be contacted again.
4. A fetcher thread pops the heap root, waits if needed, fetches one URL from that host's queue, then pushes the host back with a new time.

IIR states the goals as one connection per host at a time, a wait of a few seconds between requests to a host, and high priority first. Its heuristics: make the gap about ten times the last fetch duration (slow server, longer gap), and keep about three times as many back queues as crawler threads so threads always have a ready host. Google says Googlebot shouldn't hit most sites more than once every few seconds on average (Googlebot), which is a good default to quote.

Adaptive back-off. Google lowers its crawl rate when a site responds slowly or with 5xx or 429 errors (crawl budget, HTTP errors). Do the same: on 429 or 5xx, double that host's gap up to a cap and slowly shrink it again after successes. This is rate limiting applied to ourselves; see Rate limiting.

robots.txt. Fetch /robots.txt once per host and cache it. RFC 9309 says crawlers SHOULD NOT use a cached copy for more than 24 hours unless the file is unreachable, MUST parse at least 500 KiB, treat a 4xx as "no rules" (crawl anything), and treat a 5xx or network failure as a complete disallow (RFC 9309). The most specific (longest) matching rule wins:

User-agent: *
Disallow: /search
Allow: /search/about      # longer match, so /search/about is allowed
Disallow: /cart
Sitemap: https://example.org/sitemap.xml

robots.txt manages crawler traffic; Google notes it "is not a mechanism for keeping a web page out of Google" (robots.txt intro).

Distributing the frontier. Partition by host, not by URL: hash(host) % N picks the crawler node. All of a host's URLs, its robots rules, its DNS entry and its politeness timer then live on one node, so politeness needs no cross-node coordination. When a parser finds a link to a host owned by another node, it forwards the URL there. More in Sharding and partitioning.

At a billion URLs the frontier won't fit in RAM, so keep the head of each queue in memory and the rest on disk, refilling as it drains (IIR describes this too).

My default: Mercator-style frontier, partitioned by host, with adaptive per-host gaps and robots.txt cached for at most 24 hours.

2) Dedup: the same URL, the same content

There are two different problems here, and you need both.

Same URL. Normalise first: lowercase the scheme and host, drop the default port and #fragment, resolve .. segments, and strip known tracking parameters. Then ask "seen before?".

• Exact hash set: store an 8-byte hash per URL. About 40 GB for 5 billion URLs, sharded with the frontier. No mistakes (ignoring hash collisions), but it's a lot of RAM.
• Bloom filter: a bit array with a few hash functions that answers "definitely not seen" or "maybe seen" (Bloom, 1970). RocksDB's numbers: about 9.9 bits per key gives roughly a 1% false-positive rate. At ~6 GB it fits comfortably in memory per partition. A false positive means we skip a URL we never crawled, which costs coverage, not correctness, and important pages usually get rediscovered through other links or sitemaps.

Same content. Mirrors, ?sessionid= variants, print views and syndicated articles give you the same page under many URLs.

• Exact duplicates: a checksum (for example SHA-256) of the normalised body, looked up in a table of checksums. Identical bytes, one copy.
• Near duplicates: pages that differ only by an ad, a counter or a timestamp. Google's WWW 2007 paper showed that Charikar's SimHash works here: each page becomes a 64-bit fingerprint where similar pages differ in only a few bits, and for a repository of 8 billion pages, 64-bit fingerprints with a threshold of k = 3 differing bits were reasonable (Manku, Jain and Das Sarma). The paper also argues for ignoring a near-duplicate's outgoing links, since they probably lead to near-duplicates too.

My default: Bloom filter for URLs, checksum for exact content, SimHash for near duplicates, all partitioned by host.

3) Recrawl scheduling and freshness

A crawl is never finished. Pages change, and a stale copy is worse than none for some uses. The question is which URL to fetch again, and when.

Bad: recrawl everything every cycle. Simple, but a news front page and a years-old archive page get the same effort.

Good: fixed tiers. Important hosts daily, everything else monthly. Better, but a quiet page in a "daily" tier still wastes fetches.

Great: an adaptive interval per URL. IIR's guidance is that priority should combine change rate and quality, because spam pages change on every fetch. Google describes its own crawl demand in the same terms: more popular URLs are crawled more often, and its systems want to recrawl often enough to pick up changes (crawl budget). A simple rule (our heuristic, not Google's): after each fetch, if the content changed, halve the interval; if not, grow it by half; clamp it between an hour and a few months; multiply by an importance factor.

Two cheap signals help a lot:

• Conditional requests. Send If-None-Match with the stored ETag or If-Modified-Since. An unchanged page comes back as 304 Not Modified with no body (MDN: 304), which saves bandwidth for us and for the site.
• Sitemaps. Sites can list URLs with a <lastmod> date (sitemaps.org protocol). Treat it as a hint and check it against what you observe.

The scheduler feeds URLs whose next_due has passed into the front queues, so recrawls and fresh discoveries compete in one frontier and the priority function decides the balance.

My default: an adaptive per-URL interval weighted by importance, conditional GETs on every recrawl, and sitemaps as hints.

4) Crawler traps and failures

Traps are URL spaces that never end: a calendar with a "next month" link forever, faceted filters that combine into millions of URLs, session IDs appended to every link, or symlink loops producing /a/a/a/a/.... Defences, all cheap:

• Cap URL length, path depth and query parameters; drop URLs with repeating path segments.
• Cap pages per host per cycle, scaled by the host's importance.
• Treat near-duplicate pages as dead ends (deep dive 2).
• Alert when a host's discovered URLs explode while its new content stays flat: that's probably a trap.

Failures will happen every day at this scale. The question is how much work one failure costs.

• Bad: in-memory state only. A crashed frontier node forgets its queues and its seen-set, and you restart that partition's crawl from the seeds.
• Good: periodic checkpoints. Every few minutes, snapshot the frontier queues, Bloom filter and offsets to blob storage. A replacement node restores the last snapshot and replays the discovered-links topic from the saved offset. You lose minutes, and dedup absorbs the URLs fetched twice.
• Great: checkpoints plus leases and idempotent writes. Fetchers lease URLs with a timeout; a dead fetcher's lease expires and the URLs return to the frontier. Results are written keyed by URL hash and fetch time, so a repeated fetch overwrites rather than duplicates. A parser that crashes on odd HTML leaves the page in Kafka; after a few retries it moves to a dead-letter topic and the crawl keeps going. Timeouts and a maximum page size stop one slow host from tying up threads.

My default: host-level trap caps, plus leases, idempotent writes and checkpoints every few minutes.

06What interviewers look for

Green flags: saying that throughput is easy and politeness is hard, partitioning by host, explaining what a Bloom filter false positive costs, catching near duplicates, having a story for every failure.

Red flags: one global FIFO, "we'll just respect robots.txt" with no caching or error semantics, deduping only URLs, storing pages in a relational database, no answer for traps.

07Follow-up questions

What if many sites need JavaScript to show their content?

Add a rendering tier: a pool of headless browsers that runs only for pages whose raw HTML looks empty or for hosts known to need it. Google renders pages with a recent Chrome (how Search works), but running a browser per page is much heavier than a plain HTTP fetch, so keep it a second, separately budgeted queue.

What if we need 10 billion pages in a week instead?

That's roughly 16,500 pages a second, about 40 times more (our arithmetic). The design holds because it's partitioned by host: add frontier and fetcher nodes, and the Bloom filters and metadata shards grow with them. The new limit is politeness: you need tens of thousands of hosts in rotation at once, so discovery breadth and DNS caching matter even more.

What if a site owner complains that we're hammering them?

Their robots.txt changes apply within 24 hours, and an override in the host record lowers our rate immediately. Publish a user-agent with a contact URL and back off on 429 and 503. Google doesn't support the crawl-delay field (robots.txt spec); honouring it anyway is the polite choice.

What if the Bloom filter fills up and false positives climb?

A Bloom filter can't grow in place. Size it with headroom, partition it by host so each piece stays small, and rebuild a bigger one from the metadata store between cycles. If coverage matters more than memory, use an exact hash set for hot partitions.

What if breaking news must be crawled within minutes?

Give news hosts a top-priority front queue, short recrawl intervals and frequent sitemap polling. Links found on those pages inherit high priority, so a new article is fetched within minutes.

What if the indexer needs to know which pages are new?

The fetch stage publishes a "page stored" event (URL, blob key, checksum) to Kafka. The indexer consumes it, reads the blob and updates the index, so it never scans the blob store. It's the same change-feed pattern a catalogue uses to keep its search index current in Design product search.

08How to say it in the interview