Skip to content

00. Design a Web Crawler

~20 min read · Level: advanced · Part 1 of 4 (Overview → HLD → LLD → Q&A)

Problem

A web crawler starts from a set of seed URLs, fetches each page, extracts the links inside it, and follows those links outward until it has walked as much of the web as it can afford to. This is the machine behind Googlebot, Bingbot, and the crawlers feeding every search index, price-comparison site, and large-scale training corpus. The output is a growing store of fetched pages plus the link graph that connects them, kept fresh enough that a search over it reflects the web as it is today, not as it was last month.

From the outside it reads like a loop: fetch a page, parse links, enqueue them, repeat. What turns it into a hard system-design problem is everything that loop ignores. The same page is reachable by thousands of paths, so without deduplication you crawl it thousands of times. Every fetch lands on someone else's server, so crawling too fast is indistinguishable from a denial-of-service attack. Pages change at wildly different rates — a news homepage every few minutes, a 2011 blog post never — so a fixed re-crawl schedule is wrong for almost every page. And the frontier of URLs-still-to-fetch grows faster than you can drain it, so what you crawl next is a prioritization decision, not a queue pop.

Thread one scenario through the whole design: crawl 10 billion pages for a fresh index while re-crawling roughly 10,000 news domains every hour, and never fetch from any single domain faster than politeness allows — a default of one request per domain per second unless that domain's robots.txt says otherwise. That target contains the whole tension of the problem in one line: 10 billion pages demands enormous aggregate throughput, hourly news refresh demands tight per-page timing, and the politeness cap forbids getting either by simply hammering a server harder. Every decision below is judged against it.

Functional requirements

  • Fetch: given a URL, download the page over HTTP(S), following a bounded number of redirects, honoring timeouts.
  • Parse and extract: pull out links (and for an index, text and metadata) from fetched HTML, normalizing relative links to absolute URLs.
  • Frontier management: maintain the set of URLs still to crawl, decide which to fetch next, and enforce per-domain politeness while doing so.
  • Deduplication: never re-crawl a URL already seen, and detect near-duplicate content across different URLs (mirrors, print pages, session-id variants).
  • Freshness / re-crawl: revisit already-crawled pages on a schedule tuned to how often each one actually changes, so news stays hourly-fresh without wasting fetches on static pages.
  • Politeness: obey robots.txt, respect Crawl-delay, cap per-domain request rate, and back off on errors.

De-scoped for this round, and worth naming so the interviewer hears it as a choice: rendering JavaScript-heavy pages in a headless browser (we assume server-rendered HTML; JS rendering is a separate, far heavier fetch tier), building the inverted search index over crawled content, ranking/PageRank computation, and anti-cloaking / spam-detection. These sit downstream of or beside the crawl loop and do not change its core shape.

Non-functional requirements

The single dominant constraint is sustained aggregate throughput under a hard per-domain politeness cap. We are not throughput-limited by our own CPUs or bandwidth; we are limited by a rule that says we may only touch each domain slowly, so hitting 10 billion pages means spreading fetches across a very large number of domains concurrently while a scheduler keeps every one of them under its rate limit. That constraint shapes the frontier, the fetcher fleet, and the failure modes more than anything else.

  • Throughput: sustain the fetch rate needed to cover 10B pages on the target cadence (computed below) — on the order of thousands of pages per second, aggregate.
  • Politeness (a correctness constraint, not a nicety): never exceed the allowed per-domain rate. Violating it gets your crawler IP-banned, which is a worse outage than crawling slowly.
  • Freshness: re-crawl interval per page should track that page's real change rate; the news-hourly target is the tightest deadline in the system.
  • Scalability of the frontier: the set of discovered-but-uncrawled URLs runs to tens of billions and must live mostly on disk, not in RAM.
  • Fault tolerance: fetchers, parsers, and frontier shards die constantly at this scale; no single failure may lose queued URLs or crawl the same page twice.
  • Resistance to traps: infinite calendars, session-id URL explosions, and redirect loops must not be able to consume the crawler.

Scale estimation

Take the scenario's 10 billion pages and a baseline full-web refresh cadence of 30 days. The average fetch rate is 10e9 / (30 × 86,400 s) = 10e9 / 2.59e6 ≈ 3,860 pages/second. Real traffic is bursty and some capacity is lost to retries and errors, so design the fetch fleet for a peak of ~10,000 pages/second. That is the number the whole fetch tier is sized against.

The hourly news refresh is a small but tight slice of that. Ten thousand news domains, refreshing on the order of 100 changed/important pages each per hour, is 10,000 × 100 = 1,000,000 fetches/hour ≈ 280 pages/second. Only ~3% of total throughput — but it is the highest-priority, most deadline-sensitive 3%, and it competes for the same fetcher slots as the 10B-page discovery crawl.

Now the politeness constraint bites. At a default of 1 fetch/domain/second, sustaining 10,000 pages/second requires at least 10,000 distinct domains being actively fetched at any instant. The web has hundreds of millions of registered domains, so there is no shortage — but it means the frontier must be organized by host, able to hold ten-thousand-plus domains "in flight" simultaneously, each metered independently. A crawler that queued URLs in one big FIFO would either violate politeness or sit idle waiting out a delay; the per-host structure is forced by this arithmetic.

Storage: an average HTML page is ~100 KB raw, ~30 KB gzip-compressed. Storing raw compressed content for 10B pages is 10e9 × 30 KB = 3e14 bytes ≈ 300 TB per full snapshot. Keep a few historical versions for change detection and it is low petabytes — a distributed blob store, not a database. Bandwidth to ingest at peak is 10,000 × 100 KB = 1 GB/second ≈ 8 Gbps sustained inbound, plus DNS and TLS overhead.

The metadata that matters most for sizing is the seen-set — every URL ever discovered, needed to answer "have I already queued this?" Discovered URLs outnumber crawled pages roughly 10:1 (filtered, disallowed, duplicate, or not-yet-reached), so budget for ~100 billion URLs in the seen-set. Storing them exactly as 64-bit fingerprints costs 100e9 × 8 bytes = 800 GB; a Bloom filter at a 0.1% false-positive rate costs 100e9 × 14.4 bits / 8 ≈ 180 GB. That gap — 800 GB exact versus 180 GB probabilistic — is one of the defining tradeoffs, developed below and pinned down in the LLD.

API sketch

A crawler's contracts are mostly internal service boundaries rather than a public REST surface.

# Frontier — the scheduler the fetchers pull from
frontier.get_next(fetcher_id) -> { url, host, scheduled_at }   # respects politeness; may block
frontier.add(url, priority, discovered_from)                   # enqueue if unseen & allowed
frontier.ack(url, outcome)                                     # fetched | retry | dead

# Seen-set — dedup membership
seen.contains(url_fingerprint) -> bool                         # Bloom check, then exact confirm
seen.add(url_fingerprint)

# Fetch result → downstream
POST /internal/fetched
  body: { url, status, fetched_at, content_ref, links[], content_hash }

# Seed / admin
POST /api/v1/seeds        body: { urls[], priority }
POST /api/v1/recrawl      body: { host, interval }             # e.g. news → 1h

Solutioning

Start from the dominant constraint and the shape falls out. Because we may only fetch each domain slowly, throughput comes from breadth — many domains in flight — which means the URL frontier cannot be one queue; it must be sharded by host, with a per-host politeness gate in front of every one. The canonical structure (Mercator's) is two-layered: a set of front queues that encode priority (news and high-value pages jump ahead), feeding a large set of back queues, one per active host, each releasing at most one URL per politeness interval. The memory hook: a web crawler is not a fetching problem, it's a scheduling problem — the hard part is choosing what to fetch next and when, under the politeness cap, not the fetching itself.

The second defining tradeoff is freshness versus politeness/load, and the news target makes it concrete. A news domain with 5,000 pages, refreshed at the polite 1 fetch/second, takes 5,000 s ≈ 83 minutes for a full sweep — already past the 60-minute deadline, and that is if we spend the entire hour on that one domain. Push politeness to 3 fetches/second and a sweep is ~28 minutes, comfortably hourly — but 3/sec may exceed what a mid-size news server tolerates, and the reward for over-crawling is a wave of 429 Too Many Requests and eventually an IP ban. The resolution is not a global speed knob; it is to refresh a prioritized subset (homepage, section pages, newly-linked articles) rather than all 5,000 pages, plus adaptive per-page scheduling that learns each page's change rate so fetch budget flows to pages that actually change. Freshness is bought by fetching smarter, not harder, precisely because fetching harder is forbidden.

The third tradeoff is dedup memory versus accuracy. The seen-set must answer "have I queued this URL?" 100 billion times over, fast, and it dominates RAM. An exact fingerprint set (800 GB) never makes a mistake but must be sharded across many machines' memory or pushed to SSD, adding a network or disk hop to the hottest check in the system. A Bloom filter (180 GB, fits in the fleet's RAM) answers in nanoseconds but at a 0.1% false-positive rate will wrongly declare ~0.1% of genuinely new URLs "already seen" and silently drop them — on a 10B crawl that is ~10 million pages never fetched. The resolution is two-tier: a Bloom filter as the in-memory fast-reject, backed by an exact fingerprint store on SSD consulted only when Bloom says "possibly new," so the common "definitely seen" case stays in RAM and the rare "maybe new" case pays for exactness. The dropped-page cost is further softened because a genuinely important page is linked from many places and gets rediscovered.

Two smaller decisions complete the picture. Content-level deduplication is separate from URL dedup: different URLs (mirrors, print/session variants) can serve identical or near-identical bodies, so we also fingerprint the content (a checksum for exact dupes, a SimHash for near-dupes) to avoid indexing the same article twenty times. And DNS resolution — easy to forget — becomes a bottleneck at 10,000 fetches/second against distinct hosts, so an aggressive DNS cache and a dedicated resolver fleet sit on the fetch path. The result is a system whose center of gravity is the frontier scheduler, whose throughput comes from host-breadth under a politeness gate, whose dedup trades a sliver of accuracy for a fit-in-RAM seen-set, and whose freshness comes from adaptive scheduling rather than raw speed. The next files take these to components (HLD) and then to schemas, algorithms, and edge cases (LLD).