Design a Distributed Web Crawler

A distributed web crawler systematically navigates the World Wide Web to download, index, and archive billions of web pages for search engines, price monitors, or AI model datasets.

Functional Requirements

1. Scalable Web Crawling: Ingest seed URLs and recursively discover, fetch, and parse billions of hyperlinks.
2. Politeness & robots.txt Compliance: Strictly respect robots.txt exclusion standards, crawl delays, and never overwhelm any individual domain with rapid-fire requests.
3. URL & Content Deduplication: Detect and discard duplicate URLs and near-duplicate HTML content (e.g., identical content with different tracking parameters).
4. JavaScript SPA Rendering: Support headless browser rendering (Puppeteer/Playwright) for dynamic single-page applications.

Non-Functional Requirements

• Massive Scalability: Crawl 1 billion web pages per month (~ 400 pages/sec).
• Extensibility & Modularity: Modular architecture to support adding new protocols (FTP, sitemaps) and media parsers (PDF, image indexing).
• Spider Trap Resilience: Detect and terminate infinite looping URL traps (e.g., dynamic calendar links: /calendar?month=12&year=2099).

Crawling Scale

• Monthly Crawl Target: 1 billion web pages.
• Crawling Throughput:

Pages per second = \frac{1,000,000,000}{30 × 86,400} ≈ 386 pages/sec (Peak: 1,000 pages/sec)

Storage & Bandwidth Estimation

• Average HTML Page Size: 100 KB (after gzip compression: ~ 30 KB).
• Monthly Storage Footprint:

1B pages × 30 KB = 30 Terabytes (TB)/month \implies 360 TB/year

• Ingress Network Bandwidth:

Peak Bandwidth = 1,000 pages/sec × 100 KB = 100 MB/sec = 800 Mbps (Megabits/sec)

The URL Frontier is the brain of the crawler. It stores unvisited URLs and schedules when and where each URL is dispatched.

The Two-Tier Queue Design (Mercator Model):

1. Priority Queues (Importance / Quality Filter):

   • URLs are scored based on PageRank, domain authority, and update frequency.
   • High-priority pages (Wikipedia, major news outlets) are placed into top priority queues (F_1, F_2) to be crawled first; low-authority blogs enter lower queues (F_k).
   • A Prioritizer Worker pulls probabilistically from higher queues.

2. Politeness Queues (Domain Rate-Limiting):

   • An aggressive crawler must never trigger Denial of Service (DoS) on a website.
   • The Queue Selector routes URLs from priority queues into dedicated per-domain Politeness Queues (B_1, B_2, \dots, B_m).
   • Rule: A worker thread assigned to domain example.com fetches one page, downloads the content, and enforces a politeness delay (e.g., 1,000 ms) before pulling the next URL for example.com.

Over 30\% of the internet consists of duplicate or near-duplicate web pages. Crawling duplicates wastes petabytes of storage and network bandwidth.

1. URL Deduplication: In-Memory Bloom Filter

• Storing 10 billion URL strings in RAM requires hundreds of gigabytes.
• A Bloom Filter provides an O(1) space-efficient probabilistic set representation:
  • If Bloom Filter returns False: The URL has definitely never been seen \implies Proceed to crawl!
  • If Bloom Filter returns True: The URL is likely already crawled \implies Check persistent DB or discard.
  • With 10 hash functions and 10 bits per entry, a 1-billion-URL Bloom filter consumes only ~ 1.2 GB of RAM with a false positive rate < 1\%.

2. Content Deduplication: SimHash (Near-Duplicate Fingerprinting)

Web pages often contain identical content with minor variations (e.g., copyright year changed from 2025 to 2026, or different dynamic session IDs).

• SimHash Algorithm:
  1. Tokenize HTML body into word tokens and assign weights.
  2. Compute 64-bit cryptographic hashes for each token.
  3. Combine weighted hash bits into a single 64-bit SimHash fingerprint.
  4. Compare new page fingerprints using Hamming Distance (number of differing bits).
  5. If Hamming Distance ≤ 3, pages are flagged as near-duplicates and dropped from indexing.

End-to-End Crawl Cycle:

1. Dequeue URL: Worker pulls polite URL from the frontier.
2. DNS Resolution & robots.txt Check:
   • Lookup domain IP from local in-memory DNS cache to avoid exhausting public DNS servers.
   • Fetch and cache robots.txt rules for the host.
3. HTTP Fetch: Download HTML over HTTP/2 with gzip compression and timeouts (< 5s).
4. Content Fingerprint: Calculate SimHash; if already seen, discard.
5. Store Document: Save raw HTML in S3 (WARC format) and metadata in Cassandra/HBase.
6. Link Extraction & Normalization: Extract <a href="..."> tags, convert relative paths to canonical absolute URLs, and feed through the Bloom Filter before enqueuing back to the URL Frontier.

Avoiding Spider Traps

Spider traps are infinite dynamic loops (e.g., dynamic calendar pages, nested directory structures: /dir/dir/dir/...).

• Mitigations:
  • Maximum Crawl Depth: Cap recursion depth (e.g., max 15 hops from seed).
  • URL Length Limit: Drop URLs exceeding 255 characters.
  • Per-Domain Page Limit: Cap total crawled pages per domain to 100,000 pages per cycle.

Fault Tolerance & State Checkpointing

• Workers are stateless and report heartbeats. If a worker crashes mid-download, the URL is re-queued.
• URL Frontier queue states are snapshotted to distributed disk (RocksDB/Kafka) every 10 minutes to resume immediately after cluster reboots.