Design a Web Crawler

A web crawler starts from a set of seed URLs, downloads pages, extracts the links they contain, and repeats for the newly found URLs. Crawlers feed search engines, price monitors, archives, and training-data pipelines. The hard parts are scale (billions of pages), politeness (not overloading any one site), and robustness against malformed or adversarial pages.

Requirements

Functional

• Given seed URLs, discover and download pages by following links.
• Store page content for downstream indexing.
• Re-crawl pages periodically to detect changes.
• Respect robots.txt, a text file at the root of a host that lists paths crawlers may not fetch (Disallow) and sometimes a requested delay between requests (Crawl-delay, which not all crawlers honor).
• Support HTML first; extensible to other content types (PDF, images).

Non-functional

• Scalable: parallel across many machines.
• Polite: bound the request rate per host.
• Robust: survive slow servers, invalid HTML, redirect loops, and crawler traps.
• Extensible: new content processors can be added without changing the fetch path.
• Freshness matters more than completeness for popular pages.

Estimation

Assume the crawler must collect 1 billion pages per month.

• Rate: 1,000,000,000 / (30 x 86,400 s) = 1e9 / 2.59e6 ≈ 385 pages/s. Plan for peaks of about 2x, so roughly 800 pages/s.
• Average HTML page size (compressed transfer aside): assume 100 KB. Storage per month: 1e9 x 100 KB = 100 TB. Keeping 5 years of monthly snapshots gives about 6 PB, which needs object storage and compression.
• Bandwidth: 385 pages/s x 100 KB = 38.5 MB/s ≈ 308 Mbit/s average.
• URL set: if each URL takes about 100 bytes, 10 billion known URLs take about 1 TB. Too large for one machine's memory, so it is partitioned.
• Fetch concurrency: if a fetch takes about 500 ms including DNS, 385 pages/s needs about 385 x 0.5 ≈ 190 concurrent fetches. Well within a small cluster.

What the numbers imply

• Politeness, not raw throughput, limits the design. At 800 pages/s peak with a 2-second delay per host, at least 1,600 different hosts must be in flight at every moment, so the frontier must always supply diverse hosts. One host with 1 million pages at a 2-second delay takes about 23 days, so very large sites need a page budget and permission to crawl faster.
• Each page has roughly 50 outlinks, so 385 pages/s produces about 20,000 URL lookups/s. This is why a Bloom filter in memory in front of the exact store is required, and why lookups are batched.
• 100 TB/month of raw HTML compresses (gzip, assume 3 to 4x) to about 25 to 30 TB, and page metadata for 10 billion URLs at about 200 B is 2 TB. Both must be partitioned.
• 308 Mbit/s is small. The limits are DNS lookups, sockets, and per-host rate, not bandwidth.

API design

A crawler is mostly an internal pipeline, but it exposes a control interface.

Internal contracts:

• Frontier: enqueue(url, priority) and dequeue(worker_id) -> url.
• Fetcher output: an event {url, status, content_hash, blob_ref, fetched_at} to a queue for the parser.

Data model

Page metadata row: url_hash -> {url, last_crawled, etag, last_modified, content_hash, next_crawl_at, fail_count}.

High-level design

flowchart LR
    Seeds["Seed URLs"] --> Frontier["URL Frontier"]
    Frontier --> Fetchers["Fetcher workers"]
    Fetchers --> DNS["DNS resolver cache"]
    Fetchers --> Web(("Internet"))
    Fetchers --> Robots["robots.txt cache"]
    Fetchers --> Parser["Parser / link extractor"]
    Parser --> ContentDedup["Content dedup (hash)"]
    ContentDedup --> Store["Content store (object storage)"]
    Parser --> URLFilter["URL filter and normalizer"]
    URLFilter --> URLSeen["URL seen-set"]
    URLSeen --> Frontier
    Store --> Indexer["Downstream indexer"]

Component responsibilities:

• URL frontier: holds URLs to fetch, enforces priority and per-host politeness, and hands URLs to fetchers.
• Fetcher: resolves the host, checks robots.txt, downloads the page with timeouts and a size cap, and records status.
• DNS resolver cache: DNS lookups can take tens to hundreds of milliseconds and become a bottleneck, so the crawler keeps its own cache (see DNS resolution).
• Parser: validates and extracts text and links; handles malformed HTML.
• Content dedup: computes a hash of the page body and skips pages already stored.
• URL filter: normalizes URLs, drops disallowed schemes and blocklisted hosts, and applies depth limits.
• URL seen-set: drops URLs that were already discovered.

Crawl loop for one URL:

sequenceDiagram
    participant F as Frontier
    participant W as Fetcher
    participant R as robots.txt cache
    participant S as Site
    participant P as Parser
    participant U as URL seen-set
    F->>W: dequeue(url)
    W->>R: allowed(url)?
    R-->>W: yes, crawl-delay 2s
    W->>S: GET url (If-None-Match: etag)
    S-->>W: 200 body / 304 Not Modified
    W->>P: body
    P->>U: outlinks
    U->>F: enqueue only new URLs

Deep dive

URL frontier: priority and politeness

A single FIFO queue crawls in BFS order, but it fails two requirements: it ignores priority, and it may send thousands of consecutive requests to one host.

A common design (used in the Mercator crawler) has two layers:

1. Front queues (priority). URLs are assigned a priority (for example from page rank estimates, update frequency, or seed importance) and placed into one of F priority queues. A selector picks queues with bias toward high priority.
2. Back queues (politeness). Each back queue holds URLs from exactly one host. A mapping table records host -> back queue. A heap keyed by "earliest time this host may be fetched again" tells a worker which queue to serve. After a fetch, the host's next-allowed time is set to now plus its crawl delay.

Each fetcher thread takes a back queue, so at most one connection per host is in flight, and the delay between requests to the same host is enforced. When a back queue empties, it is refilled from the front queues.

Distribution: partition hosts across crawler nodes by hashing the hostname (see consistent hashing). One node then owns all URLs of a host, which makes per-host rate limiting a local operation. Links discovered by node A that belong to node B are forwarded to B's frontier.

URL deduplication

The web is heavily linked, so most extracted links are already known. Checking each against a database is too slow.

• Normalization first: lowercase the scheme and host, remove default ports and fragments (#...), resolve . and .., sort or strip tracking query parameters, and follow the canonical link when present. Without this, one page appears under many URLs.
• Bloom filter: a Bloom filter answers "definitely not seen" or "possibly seen". A false positive means a new URL is wrongly skipped, which is acceptable at a low rate. Memory is about 10 bits per element for a 1% false-positive rate, so 10 billion URLs need about 12.5 GB, which is partitioned across nodes.
• Exact store: for "possibly seen" hits that need certainty, or when no URL may be lost, check a sharded key-value store of URL fingerprints (for example 64-bit hashes).

Trade-off: Bloom filters cannot delete elements, so re-crawling a URL is driven by the metadata store's next_crawl_at, not by removing entries from the filter.

Content deduplication and near-duplicates

Different URLs often serve identical content (mirrors, session IDs in URLs). Exact duplicates are found by storing a cryptographic or 64-bit hash of the body and checking it before storing. Near-duplicates (same article with a different ad or timestamp) need similarity fingerprints. SimHash reduces the weighted features of a page (for example word shingles) to a short bit string in which similar pages differ in few bits, so pages whose fingerprints have a small Hamming distance (number of differing bits) are treated as near-duplicates. MinHash instead estimates the Jaccard similarity of two feature sets from a small sample of hashes. This adds compute cost and is optional.

Crawler traps and robustness

• Infinite spaces: calendars with next-month links, or URLs that append path segments forever. Mitigate with a maximum URL length, a maximum depth per host, a per-host page budget, and pattern detection on repeating path segments.
• Redirect loops: cap the number of redirects per fetch.
• Slow or huge responses: set connect and read timeouts, and a maximum body size.
• Spider-bait content: manual blocklists and per-host quality scoring.
• Politeness rules: fetch and cache robots.txt per host, honoring Disallow and Crawl-delay where present; refresh it periodically (for example daily). Identify the crawler with a User-Agent string.

Freshness and recrawling

Recrawling everything at the same rate wastes capacity. Schedule next_crawl_at per page from its observed change history: pages that changed on each visit are revisited sooner, pages that never changed back off. Use conditional requests (If-None-Match with the stored ETag, or If-Modified-Since); a 304 Not Modified response saves the body transfer and parse.

Sizing and thresholds

• Frontier layout. Use about 5 to 10 front (priority) queues. Mercator sizes back queues at about 3 times the number of fetcher threads so that threads rarely idle. Crawl delay is taken from Crawl-delay when present; otherwise use a default of 1 second or an adaptive delay of about 10 times the last fetch duration, so slow sites are hit less.
• Bloom filter sizing. For a 1% false-positive rate, use about 10 bits per element and 7 hash functions: 10 billion URLs need about 12.5 GB, or about 0.8 GB per node across 16 nodes partitioned by host, matching frontier ownership. A filter filled beyond its planned capacity raises the false-positive rate quickly, so monitor the fill ratio and add or rebuild filters at about 80%. The alternative, an exact set of 64-bit fingerprints, needs 80 GB plus overhead for 10 billion URLs, and is affordable when lost URLs are unacceptable.
• robots.txt policy. Cache for about 24 hours. A 4xx response means no restrictions; a 5xx or timeout means treat the site as fully disallowed for now and retry later, so a transient error does not cause disallowed crawling.
• Near-duplicates. Use a 64-bit SimHash and treat pages within Hamming distance of about 3 as near-duplicates. The alternative, MinHash with locality-sensitive hashing, gives a tunable Jaccard threshold but needs more storage per page. SimHash is chosen for its 8 bytes per page and its cheap lookup.
• Recrawl schedule. Start with a 1-day interval, double it when the content hash is unchanged (up to about 30 days), and halve it when it changed (down to about 1 hour for news pages).
• Consistency. Eventual and at-least-once. Checkpoint each frontier partition every few minutes; after a crash, at most that interval of dequeues is repeated, which costs duplicate fetches, not correctness.

Bottlenecks and scaling

• DNS: local caching in each node, plus asynchronous batched resolution.
• Frontier size: the frontier lives mostly on disk with in-memory head and tail buffers per queue.
• Fetch concurrency: use asynchronous I/O so one node holds thousands of connections. Fetching is I/O-bound; parsing is CPU-bound, so the two stages are separated by a queue (message queue) and scaled independently.
• Node failure: the frontier is periodically checkpointed. Because fetches are idempotent, an at-least-once redelivery of a URL only costs a duplicate fetch, which content dedup removes.
• Hot hosts: a very large site limited to one connection at a time crawls slowly. Raise its crawl rate only when the site permits it.
• Geographic placement: crawler nodes near the target sites reduce latency.

Failure modes

• Crawler node crash. Its hosts are reassigned by consistent hashing to other nodes, which reload the last frontier checkpoint. In-flight fetches are repeated (idempotent), and content dedup removes duplicates.
• At 10x scale. 3,850 pages/s needs at least 16,000 hosts in flight, 200,000 URL checks/s, about 125 GB of Bloom filters, and about 1 PB of raw content per month. Also rate-limit per IP address, because many hosts share one IP on shared hosting. Partition the frontier and seen-set by host across many more nodes, and use several DNS resolvers.

Trade-offs and follow-up questions

• BFS vs priority-driven crawling: BFS tends to reach well-linked pages early but ignores freshness needs.
• Bloom filter vs exact set: memory savings against a small permanent loss of URLs.
• How to crawl JavaScript-rendered pages? Requires a headless browser, which is much more expensive per page than plain HTTP fetching (it downloads scripts and subresources and executes them); restrict it to hosts that need it.
• How to detect that a site is blocking the crawler? Track per-host error and 403/429 rates and back off automatically.
• How to prioritize by page quality? Feed link-graph signals back to the frontier as priorities.
• How would DNS or the network fail? Retry with backoff, mark hosts unhealthy after repeated failures, and revisit later.
• How do you prioritize by page quality? Feed link-graph signals (in-links, previous page value) into the front-queue priority and update it on each crawl.