Back to Notes

Design a Web Crawler

1. Problem & Real-World Context

Design a system that systematically downloads web pages, extracts links, and crawls those links recursively, at the scale of the entire web (billions of pages). The defining challenges are not downloading a page — that's a single HTTP GET — they are: not crawling the same URL twice (dedup at massive scale), not hammering any one site into the ground (politeness), and deciding what to crawl next out of a queue that grows faster than it shrinks (prioritization).

2. Requirements

Functional: given seed URLs, fetch each page, extract outbound links, add new links to the crawl queue, store fetched content; respect robots.txt; avoid re-crawling unchanged pages unnecessarily.

Non-functional: politeness — never overwhelm a single domain's servers with concurrent requests (a real ethical and legal constraint, not just an engineering nicety); scalable to billions of URLs; extensible crawl priority (freshness for news sites vs. one-time discovery for static content); fault-tolerant (a crawler worker crashing shouldn't lose queued work).

3. Capacity Estimation

  • Crawling 1 billion pages/month ÷ (30 × 86,400s) ≈ ~385 pages/sec average fetch rate — modest in isolation, but the queue of discovered-but-not-yet-crawled URLs grows much faster than this, since each page yields on average 10+ outbound links, most of them new.
  • URL frontier size: at steady state, potentially billions of discovered URLs waiting to be crawled — this alone rules out an in-memory queue; the frontier needs to be a persisted, distributed structure (§6).
  • Dedup set size: tracking "have we seen this URL/content before" across billions of entries needs a memory-efficient structure — a plain hash set of billions of full URLs would cost hundreds of GB; this is exactly the case for a Bloom filter (§7).
  • Storage: 1B pages × ~500KB average (HTML + assets metadata) ≈ ~500TB — squarely a job for [[Blob & Object Storage]], with a separate metadata index (URL, fetch time, content hash) in a horizontally-scaled store.

4. High-Level Architecture

flowchart LR
    Seeds[Seed URLs] --> Frontier[URL Frontier<br/>priority queue, per-host]
    Frontier --> Fetcher[Fetcher Workers]
    Fetcher --> DNS[DNS Resolver<br/>+ cache]
    Fetcher --> Robots[robots.txt<br/>Cache]
    Fetcher --> Store[(Content Store<br/>blob storage)]
    Fetcher --> Extractor[Link Extractor]
    Extractor --> Dedup{Seen before?<br/>Bloom filter}
    Dedup -->|no| Frontier
    Dedup -->|yes| Discard[Discard]
    Extractor --> Meta[(URL Metadata DB)]

Walking a crawl cycle: a fetcher worker pulls the next URL from the frontier (respecting per-host politeness, §8) → resolves DNS (cached — DNS lookups are slow and repetitive across many URLs on the same host) → checks the cached robots.txt for that host to confirm the path is crawlable → fetches the page → stores raw content in blob storage → extracts outbound links → each extracted link passes through the dedup check (§7) → new, not-yet-seen URLs are added back into the frontier.

5. The URL Frontier

Not a simple FIFO queue — it needs to balance two competing needs: politeness (don't send 1000 concurrent requests to the same host) and priority (a news homepage should be recrawled far more often than a static personal blog).

flowchart TD
    F[URL Frontier] --> FQ[Front Queues<br/>priority-based]
    FQ --> BQ[Back Queues<br/>one per host]
    BQ --> W[Fetcher Worker<br/>pulls, respecting<br/>per-host delay]

A common two-tier design (used conceptually by Mercator, an influential real crawler architecture worth naming): front queues hold URLs bucketed by priority (crawl frequency/importance score); a router pulls from front queues based on priority weighting and pushes into back queues, each dedicated to a single host — this is what makes enforcing "only one in-flight request per host at a time" simple: a worker only ever pulls from one back queue's head, and a back queue is only refilled from the front once its current URL is dispatched.

6. Frontier Persistence & Distribution

Given the frontier's scale (§3), it can't live in one process's memory:

  • Persisted, typically in a distributed KV store or a partitioned queue system, so a crawler process crash doesn't lose the discovered-but-uncrawled backlog.
  • Partitioned by host across multiple frontier-manager instances — since politeness is inherently per-host, sharding by hash(host) naturally keeps all of one host's queued URLs together on the same partition, avoiding cross-partition coordination just to enforce a single host's rate limit (same reasoning as [[Consistent Hashing]]'s partition-locality principle).

7. Deduplication: Bloom Filters

URL-level dedup — has this exact URL been queued/crawled before? At billions of URLs, an exact hash set costs too much memory; a Bloom filter trades a small, tunable false-positive rate for massive memory savings (a single bit array + K hash functions, no stored keys at all).

import hashlib

class BloomFilter:
    def __init__(self, size: int = 1 << 30, num_hashes: int = 7):
        self.size = size
        self.num_hashes = num_hashes
        self.bits = bytearray(size // 8)

    def _hashes(self, item: str) -> list[int]:
        return [
            int(hashlib.sha256(f"{item}:{i}".encode()).hexdigest(), 16) % self.size
            for i in range(self.num_hashes)
        ]

    def add(self, item: str) -> None:
        for h in self._hashes(item):
            self.bits[h // 8] |= (1 << (h % 8))

    def might_contain(self, item: str) -> bool:
        return all(self.bits[h // 8] & (1 << (h % 8)) for h in self._hashes(item))

Why "might contain," never "definitely contains": a Bloom filter can have false positives (says "seen" for a URL never actually added, due to hash collisions across bits) but never false negatives — this asymmetry is exactly right for crawling: occasionally, rarely, skipping a genuinely-new URL because of a false positive is an acceptable cost; a false negative (re-crawling something already done) would be a correctness failure the Bloom filter must never produce, and structurally can't. State this asymmetry explicitly — it's the whole reason a Bloom filter is the correct structure here rather than "an approximate hash set" waved away vaguely.

Content-level dedup (near-duplicate detection) — the same content can exist at multiple URLs (mirrors, tracking-parameter variants of the same page). A content hash (SHA-256 of normalized body) catches exact duplicates cheaply; SimHash (a locality-sensitive hash where similar documents produce similar hash values, differing in few bits) is the standard answer for catching near-duplicates — worth naming by name as the upgrade path if asked "what about pages that are 95% the same but not byte-identical."

8. Politeness

Real websites' servers can be overwhelmed by an aggressive crawler — politeness is a hard constraint, not a nice-to-have.

  • Per-host rate limiting: enforced by the back-queue design in §5 — a worker only pulls the next URL for a given host after a minimum delay since the last request to that same host. This is conceptually the same token-bucket idea as [[Rate Limiter]], applied per-host instead of per-client.
  • robots.txt compliance: fetched and cached per host (it rarely changes, and re-fetching it before every single page request would itself be impolite); parsed to exclude disallowed paths before a URL is even added to the frontier.
  • Respecting Crawl-delay directives when a site specifies one, overriding the crawler's own default politeness interval for that host.

9. Storage & Metadata

  • Content store: raw fetched HTML/assets in [[Blob & Object Storage]] — large, opaque, not queried directly.
  • URL metadata: a separate record per URL — last-crawled timestamp, content hash, HTTP status, discovered-from (parent URL) — in a horizontally-scaled store keyed by URL (see [[SQL vs NoSQL]]); this is what a recrawl-scheduling job queries to decide "which pages are due for a freshness check," not the blob content itself.

10. Deep Dives / Follow-ups

  • Crawl traps: infinite URL spaces (calendar pages that generate a "next month" link forever, session-ID-in-URL patterns creating infinite distinct-looking URLs for the same content) — mitigated by a max-depth-per-host cap, normalization (stripping known tracking/session parameters before hashing for dedup), and per-host URL-count ceilings.
  • Freshness/recrawl scheduling: pages don't all change at the same rate — a news homepage might warrant hourly recrawl, a static reference page yearly. A recrawl priority score (based on observed historical change frequency) feeds back into the front-queue prioritization from §5, rather than every URL being crawled exactly once and forgotten.
  • Distributed coordination across crawler instances: multiple fetcher fleets need to avoid two different instances claiming the same host's back queue simultaneously — typically solved with the same partition-ownership pattern as [[Consistent Hashing]] (each host consistently maps to one owning instance) rather than a global lock per host.

11. Interview Drill Questions

  1. Why a Bloom filter instead of a regular hash set for URL dedup? — At billions of URLs, an exact hash set's memory cost becomes prohibitive; a Bloom filter trades a small, tunable false-positive rate (occasionally re-crawling, or rarely, mistakenly skipping a genuinely new URL) for a large constant-factor memory reduction — and critically, it never produces false negatives, so it can never cause a "definitely already crawled" URL to be wrongly re-added.
  2. How do you prevent the crawler from hammering one popular domain with thousands of concurrent requests? — Partition the frontier by host into per-host back queues (§5), with each worker enforcing a minimum delay between requests to the same host — the politeness constraint is structural (built into the queue design), not an afterthought bolted onto the fetcher.
  3. The crawler discovers a calendar page that links to "next month" infinitely. How do you avoid crawling forever down that path? — This is a crawler trap; mitigate with a maximum crawl depth per host/path pattern and a per-host URL-count ceiling, so a single pathological site can't consume unbounded frontier capacity.
  4. Two different URLs (with different tracking parameters) serve identical content. How do you avoid storing/crawling both as if they were different pages? — URL normalization (strip known tracking/session query parameters before the dedup check) catches the easy case; for content that's identical but reached via genuinely different URL structures, a content-hash check after fetch catches it at the storage layer even if the URL-level dedup didn't.
  5. How would you prioritize which URLs to crawl first out of billions queued? — Feed a priority score per URL into the front-queue tier (§5) — based on signals like domain authority, historical change frequency, or explicit seed importance — rather than treating the frontier as a plain FIFO; this is what makes "recrawl a news homepage hourly, a static blog yearly" possible within the same overall system.

Cross-links

[[Rate Limiter]] · [[Consistent Hashing]] · [[Blob & Object Storage]] · [[SQL vs NoSQL]] · [[Database Replication & Sharding]]