01. Web Crawler — High-Level Design¶

~15 min read · Part 2 of 4 (Overview → HLD → LLD → Q&A)

This file turns the solutioning narrative into concrete boxes and the flows between them. Read the architecture top to bottom, follow one URL through a full crawl-and-rediscover cycle, then look at what breaks when a piece fails.

Architecture¶

   seeds ─┐
          ▼
   ┌───────────────┐        ┌──────────────────┐      ┌───────────────┐
   │  URL Frontier │◀──────▶│  Seen-set         │      │ robots.txt    │
   │  ───────────  │  dedup │  Bloom + exact FP │      │ cache         │
   │  front queues │        └──────────────────┘      └───────┬───────┘
   │  (priority)   │                                          │ allow?
   │       │       │                                          │
   │       ▼       │        ┌──────────────────┐              │
   │  back queues  │◀──────▶│  DNS resolver     │              │
   │  (per-host,   │  resolve  cache            │              │
   │   politeness) │        └──────────────────┘              │
   └──────┬────────┘                                          │
          │ get_next (politeness-gated)                       │
          ▼                                                   │
   ┌───────────────┐   fetch    ┌──────────────┐              │
   │  Fetcher      │───────────▶│  the Internet │              │
   │  fleet        │◀───────────│  (web servers)│              │
   └──────┬────────┘   HTML     └──────────────┘              │
          │ raw page                                          │
          ▼                                                   │
   ┌───────────────┐     ┌────────────────┐                   │
   │  Content store│◀────│  Parser /      │                   │
   │  (blob, comp.)│     │  Link extractor│───extracted links─┘
   └───────────────┘     └───────┬────────┘   (normalize → add to frontier)
          │                      │
          ▼                      ▼
   ┌───────────────┐     ┌────────────────┐
   │ Content dedup │     │  Scheduler /   │  sets next-crawl time
   │ (hash/SimHash)│     │  freshness svc │  per page (news → +1h)
   └───────────────┘     └────────────────┘

Read it as a cycle. Seeds enter the frontier, which is the scheduling heart: front queues rank URLs by priority and feed per-host back queues that release one URL per politeness interval. A fetcher pulls the next allowed URL, resolves its host through the DNS cache, checks the robots.txt cache for permission, downloads the page, and writes the raw body to the content store. The parser extracts links, normalizes them, and hands each candidate to the seen-set; unseen and allowed links flow back into the frontier, closing the loop. Meanwhile the content-dedup stage drops near-duplicate bodies before they reach the index, and the freshness scheduler records how the page changed and sets when it should be re-crawled — which for a news page is one hour out.

Components¶

URL Frontier. The scheduler and the center of the design. It holds every discovered-but-uncrawled URL, decides crawl order via priority front queues, and enforces politeness via per-host back queues, each gated so no host is fetched faster than allowed. It exists because throughput under a per-domain cap is fundamentally a scheduling problem, not a queue.

Seen-set (dedup). A two-tier membership structure: an in-RAM Bloom filter as the fast-reject front line, backed by an exact fingerprint store on SSD for confirming the rare "possibly new" answers. It answers "have I already discovered this URL?" and stops the crawl from re-queuing the same page along its thousands of reachable paths.

DNS resolver + cache. At 10,000 fetches/second against distinct hosts, uncached DNS becomes a bottleneck and an external dependency that can throttle you. A dedicated resolver fleet with an aggressive cache turns most host lookups into a memory hit and keeps the fetch path from stalling on someone else's DNS.

robots.txt cache. Before fetching from a host, the crawler must consult that host's robots.txt for disallowed paths and any Crawl-delay. Fetched once per host and cached (with its own refresh interval), so permission checks are local and one robots.txt fetch covers thousands of subsequent page fetches.

Fetcher fleet. Stateless, horizontally scaled downloaders. Each pulls a politeness-cleared URL from the frontier, performs the HTTP(S) fetch with strict timeouts and redirect limits, and streams the body to the content store. Statelessness lets us scale throughput by adding fetchers — up to the ceiling the politeness cap imposes.

Parser / link extractor. Parses HTML, extracts anchors and metadata, and normalizes relative and messy URLs to a canonical absolute form (covered in the LLD) so that /a and https://host/a dedup as one. Feeds canonical links to the seen-set and, if new, to the frontier.

Content store. A distributed blob store holding compressed raw page bodies, keyed by URL fingerprint (and version). Append-mostly, read by downstream indexing and by change-detection. It is a blob store, not a database, because the access pattern is "write once, read by key, keep versions."

Content-dedup. Computes an exact content hash and a SimHash for near-duplicate detection, so mirror sites, print-view pages, and session-id URL variants that serve the same body are collapsed to one logical document instead of being indexed repeatedly.

Freshness / scheduler service. Observes each page's change history and sets its next-crawl time to track its real change rate — hourly for a live news homepage, monthly-or-slower for a static archive page. It is what turns re-crawl budget from evenly-spread waste into targeted freshness.

Primary write path (discover and fetch a new URL)¶

A URL arrives at the frontier — either a seed or a link the parser just extracted.
The frontier asks the seen-set: Bloom check first; if "definitely new" it proceeds, if "possibly seen" it confirms against the exact fingerprint store. Already-seen URLs are dropped here.
The URL is normalized and checked against the host's cached robots.txt; disallowed paths are dropped and recorded.
The URL is placed in a front queue by priority, then routed to that host's back queue. Its fingerprint is added to the seen-set.
A fetcher calls get_next; the frontier returns a URL only from a back queue whose host is now past its politeness delay, so the fetch is guaranteed polite.
The fetcher resolves the host via the DNS cache, downloads the page with a timeout, and writes the compressed body to the content store.
The parser extracts links (looping back to step 1 for each) and the content-dedup stage fingerprints the body; the scheduler records the outcome and sets the next-crawl time. The fetcher acks the URL as fetched.

Primary read path (re-crawl an already-known page)¶

The scheduler wakes URLs whose next-crawl time has arrived — the news homepage every hour, a static page every few weeks.
Each due URL is re-injected into the frontier's front queues, usually at higher priority than fresh discovery, because a stale news page is more costly than an undiscovered obscure one.
It flows through the same per-host back-queue politeness gate — a re-crawl is not exempt from politeness — and is fetched.
The new body's content hash is compared to the stored version. Unchanged: the scheduler lengthens the interval (the page is calmer than we thought). Changed: it shortens the interval (the page is livelier), and the new version is stored.
Newly-appeared links on the re-crawled page (a fresh news article linked from the homepage) enter the write path as new discoveries.

Storage choices¶

Content store: distributed blob store, compressed. Bodies are large, written once, read by key, and versioned — a blob/object store (GFS/Colossus, HDFS, or S3-class) fits far better than a database. Compression takes the 100 KB average page to ~30 KB, turning a 300 TB snapshot into something a cluster holds comfortably and cheaply.
Seen-set: Bloom filter in RAM + exact fingerprints on SSD. The membership check is the hottest metadata operation in the system, so the common case must be an in-memory bit test. The exact tier on SSD (sharded by fingerprint) backs the Bloom filter's "maybe" answers without inflating RAM 4×.
Frontier: sharded on-disk queues with in-memory heads. Tens of billions of URLs cannot live in RAM; the bulk of each queue is on disk, with only the queue heads and the per-host next-fetch-time heap kept in memory. Sharded by host so politeness state for a host lives on one node.
robots.txt + DNS: in-memory caches with TTLs. Small, hot, host-keyed lookups; cached aggressively so they never sit on the fetch path.
Freshness metadata: key-value store keyed by URL fingerprint. Holds last-crawled time, last content hash, observed change interval, and next-crawl time — a point-lookup workload, ideal for a KV store.

Scaling¶

Fetch throughput. Fetchers are stateless, so raw capacity scales by adding boxes — but the real ceiling is the politeness cap. To go from 5,000 to 10,000 pages/second you do not primarily add fetchers; you must have 10,000 distinct hosts with URLs ready in their back queues at any instant, because 1 fetch/host/second times 10,000 hosts is the throughput. Scaling throughput therefore means scaling host breadth in the frontier, and only then adding fetchers to service those hosts.

Frontier. Partition by host: all of a host's back-queue state (its politeness timer, its pending URLs) lives on one shard, so politeness is enforced locally with no cross-shard coordination. Adding frontier shards spreads hosts across more machines and grows how many can be in flight — which is exactly what raises the throughput ceiling above.

Seen-set. Shard the Bloom filter and fingerprint store by URL-fingerprint prefix. Growing from 100B to 200B tracked URLs is +180 GB of Bloom bits (or a modestly higher false-positive rate at the same size), spread across the shards' RAM.

Hot / huge domains. A single domain with, say, 10 million pages cannot be drained fast: at 1 fetch/second it is 10e6 s ≈ 116 days for a full pass. That is inherent to politeness, so the lever is prioritization within the domain (crawl its high-value and changed pages first) rather than trying to fetch it faster, which would only earn a ban.

Operational signals¶

The healthy signal is effective fetch rate versus polite-capacity — pages/second actually fetched as a fraction of what politeness would allow given the hosts currently ready; a healthy crawl runs near its polite ceiling with fetchers busy. The first metric to degrade under trouble is frontier back-pressure / queue growth: when discovery outpaces fetching, the frontier's on-disk size climbs and the oldest-URL age rises, the early sign that the crawl is falling behind. The misleading metric is aggregate fetcher CPU or bandwidth utilization — it can sit low and calm while the crawl is badly behind, because the bottleneck is politeness scheduling and host-breadth, not fetcher horsepower; a candidate who "scales up fetchers" is reading this misleading gauge. The graph an experienced operator opens first during a freshness incident is the news re-crawl deadline-miss rate — the fraction of the 10,000 news domains whose hourly refresh completed within the hour — because it collapses freshness, politeness, and scheduling health into one line that maps directly to the product promise.

Failure modes and resilience¶

News hourly deadline miss (the threaded scenario). During a breaking-news surge, one large news domain publishes a flood of new articles; its back queue swells, and at the polite 1 fetch/second a full sweep of its now-5,000 pages needs ~83 minutes — past the hourly deadline. Left alone, discovery of those thousands of new URLs also starves other news domains' slots. Mitigations: cap how many URLs any one host may hold in the front-of-line priority band so no single domain monopolizes fetch slots; refresh a prioritized subset (homepage + section pages + newly-linked articles) instead of all pages; and, where a site's robots.txt permits a shorter Crawl-delay, let that domain safely run a few fetches/second to bring a sweep to ~28 minutes. Freshness is recovered by fetching smarter and fairer, never by breaking politeness.
Fetcher crash mid-fetch. In-flight URLs are lost from that fetcher. Mitigation: the frontier hands out URLs on a lease with a visibility timeout; an unacked URL is re-queued after the timeout, so a crashed fetch is retried, not lost — and idempotent by fingerprint so a page is not double-stored.
Frontier shard loss. The hosts on that shard stall. Mitigation: persist queue state (it is on disk anyway) and replicate the per-host heap; a standby takes over the shard's hosts. Because URLs are re-discoverable via links, a brief stall degrades coverage rather than corrupting it.
Crawler traps (infinite spaces). A dynamic calendar or session-id URLs generate unbounded distinct links, ballooning the frontier. Mitigations: cap crawl depth and per-host URL budgets, detect low-value URL patterns, and let content-dedup collapse the identical bodies these traps usually serve.
Getting rate-limited / banned by a domain. Over-crawling earns 429/503 and eventually an IP ban — a real outage for that domain's coverage. Mitigation: honor Retry-After, back off exponentially on 429/5xx, and treat sustained errors as a signal to lower that host's rate, not retry harder.
DNS provider throttling. A spike of cache misses can overwhelm the resolver or get the crawler throttled by upstream DNS. Mitigation: large DNS cache with long TTLs, a dedicated resolver fleet, and pre-resolution of hosts before their URLs reach the fetchers.

Where this shows up in production¶

Googlebot — schedules re-crawl by observed change rate, spending crawl budget on pages that actually change (news often, archives rarely), the freshness-scheduling idea at web scale.
Google's Mercator-lineage frontier — the front-queue/back-queue split (priority in front, per-host politeness in back) is the canonical frontier design this study follows.
Internet Archive / Heritrix — an open-source archival crawler whose politeness and frontier configuration make the scheduling-not-fetching lesson concrete and inspectable.
Common Crawl — publishes multi-petabyte monthly web snapshots, showing the blob-store-of-compressed-pages storage profile at the exact scale estimated here.
Bingbot — publishes crawl-rate controls in Bing Webmaster Tools, exposing the politeness cap as a first-class, per-site negotiated setting.
Ahrefs / SEMrush crawlers — commercial link-graph crawlers that live or die on frontier prioritization, deciding which of billions of known URLs to spend a limited fetch budget on.
Bloom filters in Chrome / Bitcoin / Cassandra — the same "cheap probabilistic membership, accept a small false-positive rate to fit in memory" pattern the seen-set uses, in unrelated domains.
CDN and search robots.txt/Crawl-delay handling — the per-host cached-permission-plus-delay contract that every well-behaved crawler implements exactly as described here.