Designing a Web Crawler: The Frontier, Politeness, and Dedup at Billions of Pages

On the whiteboard, a web crawler is ten lines: pop URL from queue, fetch, parse, push discovered links, repeat. Every complication comes from one fact the pseudocode hides — the graph is adversarial. Sites throttle you, trap you in infinite calendars, mirror each other's content, and go down mid-fetch. The interview is not "can you do BFS"; it is "do you know what the web does to BFS."

Requirements

Crawl ~1B pages/month (≈400 pages/sec sustained, thousands at peak); refresh pages on freshness-driven schedules; never overwhelm any host (politeness is a hard constraint — an impolite crawler gets your IP range blocked and makes headlines); dedupe near-identical content; resume cleanly after crashes.

The frontier: two-level queues, not one

The URL frontier — the "what to fetch next" structure — is the heart. A single FIFO fails twice: it ignores priority (a news homepage deserves refresh every 10 minutes; a 2009 blog comment page, yearly), and it ignores politeness (a thousand workers popping URLs will happily hit the same host a thousand times at once).

The classic Mercator design that production crawlers still echo — two levels:

front queues (by priority):  F1..Fk   <- refresh scheduler + new URLs enter here
       biased sampler pulls from front queues
back queues (by host):       B1..Bn   <- EACH maps to exactly one host
       worker pops only from a back queue whose host-timer is ready
host timer: next_allowed_fetch[host] = last_fetch + delay(host)

One back queue per host, one in-flight request per host, plus a per-host delay (from robots.txt Crawl-delay, or adaptive: a slow-responding host gets longer gaps — response time is a load signal). Politeness stops being a distributed-coordination nightmare because each host is owned by one queue; shard hosts across crawler nodes (hash(host) mod N) and ownership stays local — no cross-node locks. Priority lives entirely at the front level: importance (PageRank-ish, change frequency, site authority) decides what enters back queues; politeness decides when it leaves.

Fetch and parse: the boring-looking 60%

DNS resolution at 400/sec needs its own caching resolver (public resolvers will rate-limit you into mystery failures). Fetchers are async-IO workers (thousands of concurrent connections per node, most time spent waiting on slow servers), with per-fetch timeouts, size caps (a "page" that streams 2GB is an attack or a mistake — cut at ~10MB), and content-type filtering before download via HEAD or early abort. Respect robots.txt (cached per host with TTL, checked before every enqueue-to-back-queue, not at discovery time — rules change). Parsed links get normalized aggressively — lowercase host, strip fragments and default ports, resolve relative paths, sort/strip tracking params — because every distinct string that means the same page multiplies your frontier.

Dedup: seen URLs and seen content are different problems

URL-seen test: "have I enqueued this URL before?" — billions of entries, hit on every discovered link (~50 links/page × 400 pages/sec = 20K checks/sec). A Bloom filter in memory is the textbook answer, with its known bargain: false positives mean you skip a URL you never actually saw (~0.1% of the web silently unexplored — acceptable), zero false negatives means no duplicate fetches. Persist the authoritative set in a disk KV store; the Bloom filter is the fast front.

Content dedup is harder: mirrors, CDNs, ?session= variants, and scraped copies mean ~30% of fetched pages duplicate content you already have. Exact-dup via content hash is trivial; near-dup (same article, different boilerplate) needs locality-sensitive fingerprints — SimHash: 64-bit fingerprints where similar documents differ in ≤3 bits, and Hamming-neighbor lookup via permuted tables. Detecting near-dups saves storage, saves index pollution, and — the reason it belongs in the crawler rather than the indexer — saves you from wasting frontier budget on mirror farms: dedup feeds back into prioritization.

Traps, and the freshness loop

Crawler traps are graphs that generate infinite URLs — calendars with a "next month" link forever, faceted search with combinatorial filters, session-ID paths. Defenses are budget-based, not clever: per-host URL caps and depth caps, URL-pattern repetition detectors (the 4,000th /calendar/2043/07/ page), and diminishing returns per host — if the last 500 pages from a host were near-dups or low-value, throttle its frontier entry rate. A crawler's most precious resource is fetch budget; traps are budget attacks.

Recrawl scheduling closes the loop: for each page, estimate change frequency from observed history (fetch, compare fingerprint, update a per-page Poisson-ish rate estimate), then schedule next fetch to balance staleness cost against budget. Pages that never change decay to yearly; volatile pages climb toward their host's politeness ceiling. Storage-wise, everything downstream (parsed text → indexer, link graph → rank computation) consumes the crawl as an append-only stream — the crawler's output is a log, and index building is a fold over it.

Interview probe	Answer sketch
Coordinator dies?	Frontier is persistent (disk-backed queues + checkpointed host timers); fetch tasks idempotent — refetch is wasted work, not corruption
One host is 40% of your frontier?	That's the trap/skew signal — per-host budgets; frontier entry is prioritized globally, not FIFO
JavaScript-rendered pages?	Headless rendering costs 100× a plain fetch — a separate, budgeted rendering tier for pages that need it, chosen by heuristics/value
Why not one global rate limiter?	Politeness is per-host, and per-host ownership (queue-per-host, sharded by host) makes it coordination-free

The mental model to leave with: a crawler is a scheduler wearing a fetcher's clothes. Fetching is commodity async IO; the system is the frontier — priority in, politeness out, budgets everywhere.