Designing a Web Crawler

What you'll learn

• Requirements (What to Clarify)

  Functional Requirements: - Crawl billions of web pages starting from a set of seed URLs - Download and store pages for later indexing/processing - Handle link extraction and follow discovered URLs - Respect robots.txt and politeness cons…

• Scale Estimation

  | Metric | Value | |--------|-------| | Target pages | 15 Billion | | Crawl window | 4 weeks (28 days) | | Fetch rate required | ~6,200 pages/sec | | Avg page size | 100 KB | | Metadata per page | 500 bytes | | Raw storage | 15B × 100 KB…

• System Architecture

  | Component | Role | |-----------|------| | URL Frontier | Priority queue with per-hostname sub-queues for polite crawling | | HTTP Fetcher | Downloads pages, respects robots.txt, handles retries | | Document Input Stream (DIS) | Caches…

• Design Evolution & Trade-offs

  How this system grew from an MVP to what a production version looks like — and the choices you'd defend in an interview.

• Stage 1 — MVP: One box, one database

  The simplest thing that could possibly work for a web crawler. - A single crawler process (monolith) with an in-process FIFO queue. - A single relational database storing seen URLs and fetched pages. - One or two starting seed URLs, no d…

• Stage 2 — Scale-out: Multiple workers behind a shared queue

  - The monolith is split into stateless fetcher workers. - The queue moves out of process into a durable broker (SQS / RabbitMQ / Kafka). - Postgres remains the single URL dedup table — this is the "obvious wall" ahead. What breaks next.…

• Stage 3 — Bottleneck: Politeness at scale (per-host rate limiting)

  The problem. A polite crawler must never open more than 1 concurrent connection to a single host, and typically waits ~1s between requests to that host. But throughput must stay at 6,200 pages/sec — which means the crawler must be talkin…

• Stage 4 — Second bottleneck: URL & document deduplication at 15B scale

  The problem. The link extractor produces ~50 candidate URLs per fetched page — that is ~300K new candidate URLs per second, most of which have already been seen. A naive dedup check kills the crawler in two different ways: - Storage. 15B…

• Stage 5 — Mature architecture

  The full crawler after Stages 2–4 land, plus checkpointing and the indexer read-path. Fetch and parse are split across a queue so parsing logic can change without re-fetching, and the frontier is disk-backed so a 4-week crawl survives no…

• Cost vs Complexity — When to Pick What

  | Concern | MVP choice | Growth choice | Enterprise choice | |---------|-----------|---------------|-------------------| | Fetcher compute | Single VM, threaded | K8s deployment of stateless fetchers | Multi-region K8s, per-region host s…

• Migration Path (MVP → Enterprise)

  Ordered so each step is safe to ship and rollback independently. Depends-on notes make the ordering explicit. 1. Externalize the queue (in-process → SQS/RabbitMQ). No dependency. Unlocks horizontal fetcher scale and gives visibility time…

• The Core Insight: URL Frontier Architecture

  The URL Frontier is NOT a simple FIFO queue. It's a two-layer system that separates prioritization from politeness.

• Layer 1: Priority Queues (Front Queues)

  Priority signals: - PageRank / domain authority - Freshness (news sites re-crawled more often) - Content change frequency (see Adaptive Crawl Frequency below) - Manual boost (important domains)

• Layer 2: Per-Hostname Sub-Queues (Back Queues)

  Key rule: Each back queue is drained by exactly ONE thread. A hash function maps each hostname to a specific worker thread, guaranteeing: - Maximum 1 concurrent connection per host - Controlled crawl rate per domain (sleep between reques…

• Why This Two-Layer Design?

  ---

• Adaptive Crawl Frequency

  Re-crawling pages at the right interval is a balancing act: too frequent wastes bandwidth; too infrequent serves stale content. This handles the freshness-vs-load trade-off dynamically: - News home pages that change every few minutes → q…

• URL Canonicalization

  Before any deduplication check (URL or document), URLs must be canonicalized. Without normalization, the same page appears as multiple "different" URLs: Canonicalization happens immediately when a URL is discovered (before enqueueing int…

• Deduplication (Two Distinct Levels)

  The crawler performs dedup at two independent stages — confusing them is a common interview mistake: 1. URL dedup (before fetching): "Have we already enqueued this URL?" Uses 4-byte checksums of canonical URLs. Prevents redundant fetches…

• Document Deduplication

• Why Dedup Is Essential

• Checksum-Based Dedup

• Near-Duplicate Detection (SimHash)

  ---

• URL Deduplication with Bloom Filters

• The Problem

• Bloom Filter Trade-off

• Alternative: Checksum Set

• URL Dedup: Bloom Filter vs Redis vs RDBMS

  | Approach | Throughput | Consistency | Memory | |----------|-----------|-------------|--------| | Bloom Filter | Highest | Lowest (false positives) | ~50 GB for 15B URLs (1-in-1M FP rate) | | Redis | Medium | Medium | ~700 GB for 15B UR…

• HTTP Fetcher Details

• DNS Resolution Bottleneck

• robots.txt Handling

• Headless Browser Rendering (JavaScript-Heavy Pages)

• Document Input Stream (DIS)

  ---

• Traversal Strategy: BFS vs DFS

• BFS (Breadth-First) — Standard Approach

• DFS (Depth-First) — Situational Use

• Path-Ascending Crawling

  ---

• Crawler Traps and Defenses

• Common Traps

• Defenses

  ---

• Distributed Crawling

• Partitioning Strategy

• Coordination Between Crawl Servers

  ---

• Checkpointing and Fault Tolerance

• Why Checkpointing Is Critical

• What to Checkpoint

• Recovery Process

  ---

• Performance Optimizations

• Connection Reuse

• Parallel Processing Pipeline

• Two-Stage Separation (Fault Isolation)

  An advanced approach separates fetching from parsing into independent stages connected by a queue: Why separate? - If parsing logic changes (e.g., "include image alt text"), you don't need to re-fetch pages - Fetch failures don't block p…

• Message Queue Retry Semantics

  Using a queue (SQS-like) for the frontier provides built-in fault tolerance: | Mechanism | How It Helps | |-----------|-------------| | Visibility timeout | Message hidden from other consumers while being processed. If worker dies, messa…

• The Indexer (Read Path)

  The crawler handles the write path; the indexer handles the read path. Together they form the complete system.

• Indexer Architecture

  Write path of the indexer: 1. Store the URL and its extracted text in an object store (for cached copies when original is unavailable). If page text is large, store under a key that is the hash of the URL. 2. Maintain a reverse index map…

• Query Caching

  If the query API SLA requires tens of milliseconds at P90 and most queries repeat: - The 80/20 rule: ~80% of users query the same ~20% of phrases - Use an LRU cache (Redis) with TTL for common queries - Cache-aside strategy works well he…

• Operational Challenges (Interview Deep-Dive Points)

  These are the hard follow-up questions interviewers ask about production crawlers:

• 1. Throttling from the URL Store

  If too many crawlers simultaneously look up and write URLs to the NoSQL store, it may throttle. Problem cascade: If workers use exponential backoff on throttled requests, the visibility timeout on the queue message may expire, causing th…

• 2. Dead Links and Blacklisting

  Store domains/URLs that return 404 repeatedly in a blacklist. Workers check the blacklist before enqueueing discovered links. Blacklist storage: A NoSQL key-value store or Bloom filter. Include the domain + pattern (e.g., domain.com/) fo…

• 3. Temporarily Offline Sites

  If a worker connects to a site but it takes 40+ seconds to respond with 503, the visibility timeout may expire and release the same URL to another worker — which suffers the same fate. Mitigation: Use shorter connect timeouts (5-10s), an…

• 4. Per-Domain Rate Limiting (Advanced)

  Multiple workers crawling different pages of the same large site (like an encyclopedia) may collectively overwhelm it. Approaches: - Use a streaming queue (like Kafka) with domain name as partition key → all URLs for a domain go to one c…

• 5. Observability and Continuous Improvement

  Emit metrics for: - Rate-limit hits per domain - Latency of each operation (URL fetch, parsing, indexing) - Worker failures, timeout rates - Sites that return errors repeatedly Log analysis feeds back into: - Blacklist generation (machin…

• Scoping the Interview (Important Meta-Point)

  The scope of a web crawler system design is: design a distributed crawler using available infrastructure components (message queues, NoSQL stores, object stores) — NOT to design the internals of those components themselves. Ask upfront:…

• Key Architecture Decisions

  The "polite" crawler constraint is the single design force that drives the entire architecture. The requirement to never overwhelm any single host (at most one thread per hostname) is what forces the FIFO-sub-queue-per-hostname design. E…

• Key Numbers Summary

  | Metric | Value | |--------|-------| | Target pages | 15 Billion | | Crawl window | 4 weeks | | Fetch rate | ~6,200 pages/sec | | Avg page size | 100 KB | | Total storage | ~1.5 PB (2.14 PB at 70% capacity) | | Document dedup | 120 GB (…