Design a Web Crawler: Frontier, Politeness, and Dedup at Scale

A web crawler is a graph traversal that never terminates. Start from a seed set of URLs, fetch each page, extract the links, add the new ones to a queue, repeat. The whole design problem is what happens when that queue holds ten billion URLs, the graph spans two hundred million hosts, and you are legally and ethically bound not to knock any of them offline.

Interviewers love this problem because the naive version — a while loop over a queue — is something a first-year student can write, yet every constraint you add (politeness, dedup, freshness, fault tolerance, JS rendering) forces a real distributed-systems decision. The gap between toy and production is the entire interview.

What are we actually building?#

Pin the scope before drawing boxes. A general-purpose search-engine crawler has these functional requirements:

• Given a seed set of URLs, fetch the reachable web and store raw pages plus extracted text.
• Extract outbound links from each page and feed them back into the system.
• Respect robots.txt and per-host rate limits — never overload a domain.
• Deduplicate URLs and near-duplicate content so you don't store the same page a thousand times.
• Recrawl pages so the index stays fresh as content changes.

The non-functional requirements are where the scale lives:

Capacity estimation: what does 1B pages/day cost?#

Do this math out loud — it drives every hardware decision that follows.

Request rate. 1B pages ÷ 86,400 seconds ≈ 11,500 pages/sec sustained. Budget 30–40K/sec at peak.

Bandwidth. At an average page size of 100 KB, that's 1B × 100 KB = 100 TB/day inbound, roughly 10 Gbps sustained.

Storage. Raw HTML compresses about 3×, so ~33 TB/day — ~12 PB/year before replication, tens of petabytes at 3× replication. That's why raw pages go to cold object storage, not a hot database.

Compute. One fetcher core sustains ~50 pages/sec (it's I/O-bound, mostly waiting on network), so ~250 cores cover fetching alone. Parsing, link extraction, JavaScript rendering, and retries typically add 5–10× more compute on top of that.

The takeaway that lands in interviews: a crawler is not one homogeneous fleet. It's tiered — a hot frontier (fast key-value store), cold raw-page storage (object store), and a parsed-text index — each scaled independently.

The URL frontier is the heart of the system#

Every meaningful decision routes through one component: the frontier, the store of URLs discovered but not yet fetched.

Model the crawl as BFS, not DFS. BFS pulls the top pages of each site first and spreads fetches across many hosts; DFS would drill straight down into one domain and hammer it. The frontier is therefore a set of queues, keyed for dedup and annotated with priority, last-seen timestamp, and target host.

It has to be durable. Ten billion URLs won't fit in memory, and a crash must not vaporize the queue, so the frontier is backed by a persistent store — RocksDB for the seen-set, Kafka or a similar durable log for the work stream.

How do you crawl politely without going slow?#

Politeness and parallelism sound contradictory — one requests slowly, the other requests fast. The resolution is that the constraint is per host, not global. You throttle each domain to 1 req/sec while keeping thousands of domains in flight at once.

Partition the frontier by host. Each host gets its own queue and a last_fetch timestamp; a scheduler only pops a URL from hosts whose last fetch is older than the configured delay. Workers pull from a pool of "ready" hosts rather than one global queue, so thousands of hosts can each be served once per second simultaneously, none of them overloaded.

Layer on the courtesies that keep you off blocklists:

• Fetch and cache each host's robots.txt; honor its Crawl-delay directive when present.
• Back off exponentially on 429 Too Many Requests and 503.
• Cap URLs fetched per host per day so one giant site can't starve the rest.

Deduplication: URLs and content#

With billions of URLs, duplicates are the default, not the exception. Two independent dedup layers handle it.

URL dedup. Before anything else, canonicalize: lowercase the host, strip tracking params (utm_, sessionid, jsessionid), resolve ./ and ../. Hash the canonical URL (MD5 or xxHash folded to 64 bits) and test it against a giant "seen" set, with a Bloom filter sitting in front of a persistent hash table so the common case is answered in memory with zero disk I/O. False positives are possible (skip a few genuinely new pages) but false negatives never happen, an acceptable trade at this scale.

Content dedup. Different URLs often serve identical or near-identical content — mirrors, syndicated articles, print-vs-web versions, session-id variants that slip past canonicalization. Compute a shingled fingerprint (simhash or minhash) over the visible text; pages within a small Hamming distance collapse to one canonical URL. This is what stops the index from storing the same wire story five hundred times.

Keeping the index fresh without wasting bandwidth#

A one-time crawl is stale within hours. But blindly recrawling everything every night wastes most of your bandwidth on pages that never change.

Estimate a change frequency per URL from historical diffs, exponentially weighted so recent behavior dominates. Set the next-crawl time to roughly 1 / change_rate, bounded by the page's importance (PageRank or observed traffic):

The frontier's priority queue then interleaves new-discovery URLs with due recrawls, and a per-tier staleness SLO (e.g., top-1M pages under 1 hour stale) drives how much fetcher capacity you provision.

The hard parts interviewers push on#

JavaScript-heavy sites. Plenty of pages render their real content client-side, so a plain HTTP fetch returns an empty shell. Run a headless-browser pool (Chromium via Puppeteer or Playwright) as a separate, expensive tier — the cheap static fetcher tries plain HTTP first and only escalates when heuristics fire (empty body, no links, a known SPA framework). Rendered pages cost 10–50× more, so cache them with a longer TTL and cap the rendered fraction at a few percent of total volume.

Fault tolerance. Treat the frontier as the single source of truth in a durable log with at-least-once delivery. A worker marks a URL fetched only after the page is written and its links enqueued, so a crash-and-replay refetches at most a handful of in-flight URLs — idempotency comes free from the URL dedup filter. Per-host locks are held as leases with TTLs, so a dead worker's hosts free up automatically once the lease expires.

Crawler traps. Infinite calendars, session-id URLs, and faceted-search pages can generate unbounded distinct URLs. Defend with a max URL depth per host, a per-host daily URL cap, and aggressive query-param stripping. Heuristically detect traps: if a host keeps emitting new URLs whose content is near-duplicate (caught by simhash), demote or blacklist the pattern.

How this shows up in interviews#

The opening question is almost always "walk me through a basic crawler." The fast path to a strong signal: say BFS over a durable frontier in the first minute, then name the two constraints that make it hard — politeness and dedup. Interviewers listen for whether you know the frontier is a set of per-host queues, not one global queue; that single detail resolves the politeness-vs-parallelism tension and shows you've thought past the toy.

From there the interview branches into the deep dives above. The strongest answers keep returning to the frontier as the coordination point rather than sprinkling fixes ad hoc.

Further learning#

• System Design: Distributed Web Crawler — Tech Dummies walks the distributed architecture end to end, including frontier partitioning and dedup.
• Design an Autocomplete System — the read side of search, where the crawler's index becomes type-ahead suggestions.
• Design a Unique ID Generator — how to assign stable identifiers to billions of fetched documents.
• Design a Task Scheduler — the same "due work in a priority queue" pattern that drives recrawl scheduling.
• Design a Leaderboard — another ranking-at-scale problem, useful contrast for how importance scores get maintained.

You can also practice this topic on YeetCode with the interactive roadmap.

FAQ#

Why does a web crawler use BFS instead of DFS?#

DFS chases one link chain to the bottom of a single site — a burst of consecutive requests hitting one server, exactly the denial-of-service risk politeness rules exist to prevent. BFS fans out level by level, touching many hosts before it goes deep into any one of them, and surfaces the most-linked pages first as a side effect.

Why is politeness enforced per host instead of as one global rate limit?#

A single global cap would either throttle the whole crawl to the speed of one domain or let a handful of large sites absorb most of the budget. Keying the limit to the host means thousands of independent "clocks" tick in parallel — one site being rate-limited has zero effect on how fast a different domain gets crawled, so throughput scales with the number of hosts in flight, not with how patient any one server is.

What's actually stored in the Bloom filter, and why not skip straight to the hash table?#

A compact bit array, not the URLs themselves, so billions of entries fit in memory rather than needing a disk seek. Its only job is answering "definitely new" instantly for the vast majority of lookups; the hash table is the source of truth only for the minority it can't rule out. Skip it and every check becomes a disk round-trip — the difference between a feasible system and one that can't keep up with its own fetch rate.

How is deciding when to recrawl a page different from deciding whether a URL is a duplicate?#

Dedup is a one-time gate at discovery — a URL either enters the system or it doesn't. Recrawl scheduling runs continuously on URLs already inside it, and it's a bet about the future rather than a fact about the past: a guess at how likely a page changed since last seen, willing to be wrong sometimes because fetching every page hourly to be certain isn't affordable at this scale.

If a worker crashes mid-fetch, what stops its in-progress URLs from being lost or fetched twice by another worker?#

Nothing marks a URL done until its page is written and links enqueued, so an interrupted fetch just looks unfinished and gets picked up again — that's what prevents loss. Duplicate fetches are bounded, not eliminated: the crash window is small, and the dedup filter absorbs any URL processed twice, so a crash costs a handful of redundant fetches, not a correctness bug.