Design a Web Crawler (Googlebot-style)

TL;DR. A web crawler is a scheduling problem first and a fetching problem second. At 1 billion pages per day, the URL frontier holds 10 TB of state¹, per-host politeness demands at most one in-flight request per hostname across the entire fleet, and duplicate detection requires two complementary layers: Bloom filters for URL dedup (~120 GB for 100B URLs at 1% FPR²) and SimHash for content dedup (64-bit fingerprints, Hamming-3 threshold³). Mercator’s 1999 reference architecture¹ established the component decomposition every major crawler since has reused. The pivotal trade-off: crawl rate versus politeness compliance.

Learning Objectives

After this module, you will be able to:

• Design a URL frontier that enforces per-domain politeness at millions of domains in parallel
• Size Bloom filters for 100-billion-URL dedup and explain the Bloom + exact-store production pattern
• Separate URL dedup from content dedup and justify why both layers are necessary
• Implement RFC 9309-compliant robots.txt parsing and articulate why it is a hard constraint
• Estimate capacity for a billion-page-per-day crawl system using back-of-envelope math
• Justify frontier sharding by hostname hash for global politeness enforcement

Intuition

A web crawler looks trivial: fetch a page, extract links, repeat. A while loop with a queue and a set handles 100 pages. At 1 billion pages per day it collapses, and the reason is not bandwidth or CPU. It is scheduling.

The naive approach (one big FIFO queue) fails immediately. If the next 10,000 URLs in the queue all belong to example.com, you hammer that server with 10,000 concurrent requests. The site goes down. You get blocked. Your IP range gets flagged by Cloudflare, and since July 2025 all sites on Cloudflare block AI crawlers by default unless explicit permission is granted⁴.

The insight that unlocks the design: the crawler is a distributed rate limiter running from the client side. Every architectural decision, from frontier partitioning to DNS caching to WARC storage, flows from one invariant: at most one in-flight request per hostname, globally, across every fetcher you own. Once you internalize that constraint, the Mercator two-level frontier, the host-hash sharding, and the politeness gate all follow naturally.

Requirements

Clarifying Questions

• Q: What is the target crawl scale? Assume: 1 billion pages per day (~11,500 pages/sec average, 30K-50K peak). Comparable to Common Crawl’s monthly 2-3B pages⁵.

• Q: Must we render JavaScript? Assume: HTML-only for the bulk path. Selective headless-Chrome rendering for high-priority SPA pages (estimated 100-1000x cost per page⁶).

• Q: What politeness guarantees? Assume: At most 1 request per second per host. Honor robots.txt per RFC 9309⁷. Honor Crawl-delay as a de facto convention.

• Q: How do we store crawled content? Assume: WARC format (ISO 28500) in object storage (S3/GCS). Compressed 3-5x⁵⁸.

• Q: What is the active frontier size? Assume: 100 billion URLs in the pending pool. At ~100 bytes per URL (URL + metadata), that is 10 TB of frontier state¹.

• Q: Multi-region or single cluster? Assume: Single cluster with geographically distributed fetcher pods for latency. Frontier is centralized (sharded).

Functional Requirements

• Discover new pages by recursively following links from seed URLs
• Fetch pages over HTTP/1.1 and HTTP/2, respecting robots.txt and Crawl-delay
• Deduplicate URLs (canonicalization + Bloom filter) and content (SimHash)
• Store raw responses in WARC format with metadata (timestamp, digest, status)
• Prioritize URLs by importance (OPIC/PageRank) and freshness (change-rate scheduling)
• Provide a re-crawl loop: pages with high change rates get revisited more frequently

Non-functional Requirements

• Throughput: 1B pages/day sustained; 30K-50K pages/sec peak
• Politeness: <=1 req/sec per host; 99%+ robots.txt compliance
• Dedup accuracy: URL dedup at 1% FPR (Bloom), content dedup at Hamming-3 threshold (SimHash)
• Storage: ~500 TB/day raw (100 TB compressed); 5-year retention
• Availability: frontier and dedup services at 99.9%; fetcher fleet tolerates individual node failure
• Latency: not user-facing; optimize for throughput, not p99

Capacity Estimation

Key ratios:

• Read:write on the frontier is roughly 1:1 (every fetch produces new URLs to enqueue)
• Bloom filter hit rate: ~60-70% of candidate URLs are duplicates (seen before)
• Content dedup rate: an estimated ~25-30% of fetched pages are near-duplicates of existing content³
• Hosts per crawl: Common Crawl reports 43-46 million hosts per monthly crawl⁵

API and Data Model

API Design

The crawler is not user-facing, but the frontier exposes a gRPC API (following the Crawler-Commons URL Frontier specification⁹):

POST   /frontier/v1/urls          # Inject seed URLs or discovered URLs
GET    /frontier/v1/next           # Pull next ready host + URL batch
PUT    /frontier/v1/urls/{id}      # Update URL state (fetched, failed, blocked)
PUT    /frontier/v1/hosts/{host}/rate  # Set per-host crawl rate
GET    /frontier/v1/hosts          # List active hosts with queue depth
GET    /frontier/v1/stats          # Frontier health: queue depth, throughput, FPR

The dedup service exposes:

POST   /dedup/v1/url/check         # Bloom + exact-store URL lookup
POST   /dedup/v1/content/check     # SimHash fingerprint comparison

Data Model

-- URL frontier state (sharded by host_hash)
table frontier_urls (
  host_hash       int,          -- partition key (consistent hash of hostname)
  url_id          uuid,         -- clustering key
  url             text,
  priority        float,        -- OPIC score
  state           enum,         -- queued, fetching, parsed, blocked, retired
  last_fetch_at   timestamp,
  retry_count     int,
  crawl_delay_ms  int           -- from robots.txt
)

-- Content fingerprints (for SimHash dedup)
table content_fingerprints (
  fingerprint_block  bigint,    -- 16-bit prefix block (partition key)
  fingerprint        bigint,    -- full 64-bit SimHash
  url_id             uuid,
  fetched_at         timestamp
)

-- WARC metadata index
table warc_records (
  url_id          uuid,
  warc_file       text,         -- S3 key
  offset          bigint,       -- byte offset within WARC file
  content_length  int,
  content_digest  text,         -- SHA-256
  fetch_status    int,
  fetched_at      timestamp
)

High-Level Architecture

flowchart LR
    Seeds[Seed URLs] --> Frontier[URL Frontier<br/>per-host queues<br/>sharded by host hash]
    Frontier --> Fetchers[Fetcher Pool<br/>DNS cache, HTTP/2<br/>conn pool]
    Fetchers --> Parser[Parser<br/>link extraction<br/>canonicalization]
    Parser --> URLDedup{Bloom filter<br/>+ exact store}
    URLDedup -- new --> Frontier
    URLDedup -- seen --> Drop1[Drop]
    Parser --> ContentDedup{SimHash<br/>64-bit fingerprint}
    ContentDedup -- near-dup --> Drop2[Drop]
    ContentDedup -- fresh --> WARC[WARC Writer<br/>S3 / GCS]
    WARC --> Index[Indexing Pipeline]
    Index --> Scorer[OPIC Priority Scorer]
    Scorer -. priority feedback .-> Frontier
    Robots[robots.txt Cache<br/>24h TTL per RFC 9309] -.-> Fetchers
    ZK[ZooKeeper<br/>shard assignment<br/>leader election] -.-> Frontier

The write path: a fetcher pulls a ready host from the frontier, resolves DNS (cached), checks the politeness gate (last fetch timestamp + Crawl-delay), fetches the page over HTTP/2, passes the response to the parser. The parser extracts links, canonicalizes them, and submits them to the URL dedup service. Fresh URLs re-enter the frontier. The raw response goes through SimHash content dedup; if fresh, it is written to a WARC file in S3.

The feedback path: the indexing pipeline computes OPIC scores (an online approximation of PageRank¹⁰) and updates priority weights in the frontier. High-priority pages get re-crawled sooner.

ZooKeeper manages frontier shard assignment and leader election. When a frontier node fails, its host-hash range is reassigned to surviving nodes via consistent hashing with virtual nodes.

Deep Dives

Deep dive 1: URL frontier and politeness scheduler

The frontier is the hardest component. It must satisfy three constraints simultaneously: (1) per-host rate limiting across the entire fleet, (2) global priority ordering so important pages get crawled first, and (3) durability so a multi-week crawl survives node failures.

Mercator’s two-level design¹ solves this with per-host back queues and a global front queue. URLs are assigned to a back queue by hostname. A worker pulls a ready host from the front queue (selected by priority), fetches a batch of URLs from that host’s back queue, then parks the host on a delay timer. The host becomes eligible again only after Crawl-delay seconds elapse.

Heritrix implements this as BdbFrontier with per-host work queues that move between several collections: inProcessQueues, readyClassQueues, snoozedClassQueues (plus a snoozedOverflow map for extreme situations), inactiveQueuesByPrecedence, and retiredQueues¹¹. The classKey is the hostname. Berkeley DB JE provides disk-backed durability with deferred-write mode for short-lived URLs that never hit disk.

Adaptive revisit scheduling. Not all pages change at the same rate. OPIC (Adaptive On-Line Page Importance Computation, Abiteboul et al. 2003) distributes “cash” from each crawled page to its outlinks; accumulated cash approximates PageRank without the full link matrix in memory¹⁰. Combine OPIC priority with observed change rate: pages that changed on the last N visits get shorter re-crawl intervals.

Why BFS fails at scale. Breadth-first traversal from seeds fans out uniformly. Without per-host gating, it creates DNS stampedes (millions of uncached resolutions saturating upstream resolvers¹) and accidental DDoS on small sites. Mercator’s per-host queue is the fix.

sequenceDiagram
    participant W as Worker
    participant F as Frontier
    participant D as DNS Cache
    participant P as Politeness Gate
    participant H as Host Server
    participant S as WARC Storage
    W->>F: getNext(ready host)
    F-->>W: host=nytimes.com, batch=[/article/1, /article/2]
    W->>D: resolve nytimes.com
    D-->>W: 151.101.1.164 (cached, TTL 1h)
    W->>P: canFetch(nytimes.com)?
    P-->>W: yes (last fetch 1.2s ago, delay=1s)
    W->>H: GET /article/1 (HTTP/2, reuse conn)
    H-->>W: 200 OK, 45KB HTML
    W->>S: write WARC record
    W->>F: enqueue extracted links (post-dedup)
    W->>F: snooze(nytimes.com, 1000ms)

Deep dive 2: Content dedup at scale (SimHash + URL canonicalization)

Two dedup layers attack duplicates from different angles:

URL canonicalization catches syntactic duplicates: http://A.com/ vs http://a.com, trailing slashes, session IDs (?PHPSESSID=abc), tracking parameters (?utm_source=twitter), and protocol normalization. This is cheap (string manipulation) and eliminates 30-40% of candidate URLs before the Bloom filter.

SimHash catches semantic duplicates: the same article republished at a different URL, or a page with minor boilerplate changes (ads, timestamps, navigation). Charikar’s 2002 locality-sensitive hash¹² maps documents to 64-bit fingerprints where cosine similarity is preserved as Hamming distance. Manku et al. at Google (2007) showed that a Hamming threshold of 3 bits on 64-bit fingerprints yields good precision and recall for web pages³.

The construction:

1. Tokenize the document into overlapping 3-word shingles
2. Hash each shingle to 64 bits
3. For each bit position, accumulate +1 (bit=1) or -1 (bit=0) across all shingles
4. Final fingerprint: sign of each accumulator

Sublinear candidate lookup. Scanning all fingerprints for Hamming distance is O(N). The permutation-table trick: split 64 bits into B blocks. For two fingerprints to differ by at most 3 bits, at least B-3 blocks must match exactly. Index by each block permutation. Manku et al. used 4 tables at ~150 MB each per billion fingerprints³.

The Bloom + exact-store pattern for URL dedup:

flowchart TD
    URL[Candidate URL] --> Canon[Canonicalize<br/>lowercase, strip params<br/>normalize path]
    Canon --> Bloom{Bloom filter<br/>120 GB across cluster<br/>possibly seen?}
    Bloom -- definitely not seen --> Enqueue[Add to Bloom<br/>enqueue for fetch]
    Bloom -- possibly seen --> Exact{Exact store lookup<br/>Cassandra / HBase}
    Exact -- not found --> Enqueue
    Exact -- found --> Skip[Drop as duplicate]

Deep dive 3: Distributed coordination and frontier sharding

The invariant: all URLs for one hostname must live on the same frontier shard. This is non-negotiable. If two shards independently schedule fetches for nytimes.com, politeness breaks.

Host-hash partitioning. Hash the hostname (not the full URL) to determine the frontier shard. All URLs for nytimes.com land on shard 7 (for example). Within shard 7, the two-level scheduler enforces local politeness. Since no other shard holds nytimes.com URLs, local politeness equals global politeness¹³.

Consistent hashing with virtual nodes. When a shard fails, its host-hash range must be reassigned. With virtual nodes, only 1/N of the key space moves. At 10 TB of frontier state, moving 1/N is still expensive (hundreds of GB), so the system must checkpoint frequently and minimize in-flight state.

The Crawler-Commons URL Frontier gRPC API⁹ decouples fetchers from the frontier service. Fetchers call getNext to pull work and update to report results. This lets the fetcher pool and the frontier scale independently. StormCrawler uses Apache Storm spouts as fetchers with a shared URL-Frontier service¹⁴.

ZooKeeper’s role: shard assignment (which frontier node owns which hash range), leader election (one coordinator distributes config changes), and robots.txt rule distribution (blocked domains, custom Crawl-delay overrides). Failure detection must be fast: a dead shard strands all URLs for its hosts until reassigned.

Cross-shard priority. OPIC scores are computed per-shard (each shard knows the cash for its hosts). Global priority requires a lightweight gossip protocol between shards to surface the highest-priority hosts across the cluster. In practice, per-shard priority is sufficient: the top-priority hosts within any shard are likely globally important¹⁰.

Real-World Example

Common Crawl: the only public, auditable web-scale crawler.

Common Crawl’s April 2026 crawl archived 2.19 billion pages across 43.2 million hosts and 35.4 million registered domains, totaling 379.2 TiB uncompressed⁵. Each monthly crawl discovers approximately 600-660 million new URLs not seen in prior crawls⁵¹⁵. The cumulative archive exceeds 10 PB since 2008¹⁶.

CCBot is Nutch-based (Apache Nutch over Hadoop). Map-Reduce processes the crawl database and extracts candidates, sorted by host and distributed to crawler servers¹³. HTTP/1.1 and HTTP/2 over TLS are supported. No JavaScript execution. Raw content is stored in WARC format (ISO 28500)⁸. Files land in S3 on AWS, with a columnar Parquet index queryable via Athena without bulk download.

Key engineering decisions that differentiate Common Crawl from a naive implementation:

• Adaptive back-off on 429/5xx rather than static per-host rate limits. CCBot slows to any host that signals overload¹³. This is more robust than configuration-driven politeness.
• WARC over custom format. Interoperability with Heritrix and IIPC tooling outweighs compression savings from a bespoke format⁸.
• Published, reverse-DNS-verifiable IP ranges. Site operators can distinguish real CCBot from spoofed User-Agents¹³. Googlebot uses the same verification pattern¹⁷.
• No JavaScript rendering. At 3B pages/crawl, headless Chrome at an estimated 100-1000x cost per page⁶ would require a fleet 1000x larger. CCBot accepts missing SPA content.

flowchart TB
    subgraph Common Crawl Pipeline
        MR[Map-Reduce<br/>candidate extraction] --> Sort[Sort by host]
        Sort --> Dist[Distribute to<br/>crawler servers]
        Dist --> Fetch[CCBot fetchers<br/>HTTP/2, adaptive backoff]
        Fetch --> WARC2[WARC Writer]
        WARC2 --> S3Store[S3<br/>340-400 TiB/month]
        S3Store --> Parquet[Parquet Index<br/>Athena-queryable]
    end
    RobotsTxt[robots.txt<br/>RFC 9309 compliant] -.-> Fetch
    CDX[CDX API<br/>rate-limited] --> S3Store

Trade-offs

The biggest meta-decision: crawl rate versus politeness. Google resolves it with dynamic per-hostname budgets that increase when the site responds fast and decrease on 5xx¹⁸. Common Crawl resolves it with adaptive back-off on any overload signal¹³. Both approaches treat the host’s response as the ground truth for acceptable load.

Scaling and Failure Modes

At 10x (10B pages/day):

• Frontier state grows to 100 TB. Disk-backed frontier (Berkeley DB or RocksDB) becomes the bottleneck. Mitigation: tiered storage with hot partitions in NVMe, cold in HDD.
• Bloom filter grows to 1.2 TB. Mitigation: shard across 10+ dedup nodes or switch to scalable Bloom filters that chain additional filters on saturation².

At 100x (100B pages/day):

• Fetcher fleet must sustain 500K QPS. Mitigation: geographically distributed fetcher pods to reduce RTT. HTTP/2 multiplexing over persistent connections.
• DNS cache must hold 500M+ entries. Mitigation: dedicated recursive resolver cluster with aggressive TTL extension.

At 1000x (the entire web, continuously):

• Architectural rewrite: move from batch-oriented (Nutch/Hadoop) to streaming (Flink/Kafka). The frontier becomes a distributed log. Priority is computed incrementally via streaming OPIC.

Failure modes:

• Frontier shard failure. All hosts assigned to that shard are stranded. Detection: ZooKeeper session timeout (seconds). Recovery: consistent-hash reassignment moves 1/N of hosts to surviving nodes. Data loss bounded by last checkpoint interval.
• Bloom filter node failure. Dedup degrades to exact-store-only (slower but correct). No data loss since the exact store is the source of truth. Bloom can be rebuilt from the exact store.
• Fetcher pod failure. In-flight URLs return to queued state after timeout. No data loss. The frontier re-issues them to another fetcher on the next scheduling round.

Common Pitfalls

Follow-up Questions

1. How do you handle JavaScript rendering for SPA-heavy sites?

Two-phase indexing (Google’s model⁶). HTML-only fetch feeds the pipeline immediately. High-priority pages (detected by empty <body> or known SPA frameworks) enter a separate render queue running headless Chromium. Render is estimated at 100-1000x the cost of plain fetch, so budget it at <1% of total crawl volume. Timeout aggressively (5-10 seconds per render).

2. How do you handle LLM-crawler blocks (GPTBot, ClaudeBot, CCBot)?

Respect User-agent: GPTBot / Disallow: / in robots.txt per RFC 9309⁷. Since July 2025, Cloudflare blocks AI crawlers by default across all sites on its platform unless publishers opt in or are compensated⁴. Publish verifiable IP ranges and a clear opt-out mechanism. The legal landscape is active: Reddit sued Anthropic in June 2025 over unauthorized scraping²⁰, following the NYT v. OpenAI precedent. Compliance is not optional.

3. How do you implement incremental re-crawl freshness?

Track per-URL change rate (did the content hash change on the last N visits?). High-change-rate pages (news homepages, stock tickers) get re-crawled hourly. Low-change-rate pages (about pages, documentation) get re-crawled weekly or monthly. OPIC priority combined with change-rate scheduling gives a two-dimensional priority: importance x freshness.

4. How do you partition the URL frontier across data centers?

Hash by hostname, not by URL. All URLs for one host land on one shard. This preserves the politeness invariant without cross-shard coordination. Use consistent hashing with virtual nodes for rebalancing on failure. Do not split by geography unless fetcher-to-host latency is the bottleneck (rare; most hosts are behind CDNs).

5. What is the difference between near-duplicate and exact-duplicate detection?

Exact dedup uses content hash (SHA-256 of the response body). Near-dedup uses SimHash with Hamming-3 threshold³. Exact dedup catches byte-identical mirrors. Near-dedup catches the same article with different ads, timestamps, or navigation chrome. You need both: exact dedup is cheap (one hash comparison), near-dedup is expensive (permutation-table lookup) but catches an estimated 25-30% more duplicates.

6. How do you extract main content from a page (boilerplate removal)?

Algorithms like Readability, Dragnet, or Trafilatura strip navigation, ads, and boilerplate to extract the “main content” block. This improves SimHash accuracy (fingerprinting only main content reduces false negatives from boilerplate variation) and reduces storage (store extracted text alongside raw WARC for downstream consumers).

Exercise

Exercise 1: Bloom filter sizing

Your crawler has discovered 50 billion unique URLs so far and expects to reach 200 billion over 3 years. Design the Bloom filter layer: how much RAM do you need today, how much at capacity, and when should you trigger a filter rebuild?

Key Takeaways

• The frontier is a scheduler, not a queue. Per-domain fairness via Mercator’s two-level design is the hard part; every production crawler since 1999 reuses it¹.

• Politeness is the load-bearing constraint. At most one in-flight request per host, globally. This single invariant dictates frontier sharding, fetcher assignment, and DNS caching.

• Two dedup layers are mandatory. URL canonicalization + Bloom catches syntactic duplicates; SimHash catches semantic duplicates. Neither alone is sufficient³.

• Bloom + exact store, never Bloom alone. A false positive means a lost page. The exact store eliminates false positives on the 1% slow path².

• robots.txt is legally binding. RFC 9309 formalized it in 2022⁷, Cloudflare enforces it commercially with default-block since July 2025⁴, and courts are adjudicating violations²⁰.

• Common Crawl’s numbers are your benchmark. 2-3B pages, 350-425 TiB, 43-46M hosts per monthly crawl⁵. Use these for capacity estimation in interviews.

Further Reading

• Mercator: A Scalable, Extensible Web Crawler (Heydon and Najork, 1999). The reference architecture that established per-host queues and the component decomposition every modern crawler reuses.
• Detecting Near-Duplicates for Web Crawling (Manku, Jain, Das Sarma, WWW 2007). The production-scale SimHash paper; 64-bit fingerprints, Hamming-3 threshold, permutation-table trick for sublinear lookup.
• RFC 9309: Robots Exclusion Protocol (IETF, 2022). The formal standardization of robots.txt with ABNF grammar, longest-match semantics, and the 500 KiB parser budget.
• Common Crawl FAQ. The only public, auditable web-scale crawler; documents CCBot behavior, IP ranges, WARC format, and opt-out mechanisms.
• Google Crawl Budget documentation. The canonical description of crawl capacity limit vs crawl demand and per-hostname budgeting.
• Bloom Filters: Network Applications Survey (Broder and Mitzenmacher, 2005). The canonical math reference for sizing Bloom filters; source for the 9.6 bits-per-element formula.
• WARC 1.1 specification (ISO 28500). The standard archive format for web crawls; essential for building the storage layer.
• Cloudflare: Content Independence Day (2025). The commercial reframe of crawler etiquette; documents default-block for AI crawlers and pay-per-crawl across all Cloudflare-protected sites.

Flashcards

References