Design a Web Crawler at Scale

1. Problem Statement & Scope Clarification

System Mission

Design a distributed, fault-tolerant, planetary-scale web crawler (similar to Googlebot, Bingbot, and Common Crawl) capable of crawling 1 Billion web pages per month, respecting domain politeness and robots.txt specifications, eliminating duplicate URLs and near-duplicate content, and persisting raw web snapshots into Amazon S3 for downstream search indexing and LLM training pipelines.

Functional Requirements

1. Scalable Distributed Crawling: Crawl billions of web pages starting from a curated set of seed URLs, traversing outbound hyperlinks up to a bounded depth.
2. Politeness & robots.txt Compliance: Respect domain crawl-delays, disallow directives, and cap request rates to a maximum of 1 request per second per target host.
3. URL & Content Deduplication:
   • URL Deduplication: Avoid re-fetching visited URLs within a 30-day freshness window.
   • Near-Duplicate Content Detection: Detect identical or template-modified mirror pages using 64-bit SimHash fingerprints.
4. HTML Parsing & Link Extraction: Extract canonical URLs, page titles, text content, and outbound links, normalizing relative paths to absolute URI standards.
5. Durable Web Archive Storage: Persist raw HTML and WARC (Web ARChive) formatted files into Amazon S3 Standard-IA.

Non-Functional Requirements (SLAs & SLOs)

• Scale: 1 Billion pages/month ($\approx 400\text{ pages/sec}$ sustained, Peak: $1,200\text{ pages/sec}$).
• Fault-Tolerance: 100% resilient to worker container termination via AWS EC2 Spot Instances ($70-90\%$ compute cost reduction).
• Extensibility: Modular architecture supporting pluggable media downloaders and headless browser rendering (Playwright) for JavaScript-heavy single-page applications.

2. Capacity & Scale Estimation (Back-of-the-Envelope Math)

Ingestion & Throughput Derivations

• Monthly Target: $1,000,000,000\text{ pages/month}$ (1 Billion pages/month).
• Average Crawl Rate: $\text{Sustained Crawl Rate} = \frac{10^9\text{ pages}}{30\text{ days} \times 86,400\text{ sec}} \approx \mathbf{386\text{ pages/sec}}$
• Peak Crawl Rate ($3\times$ multiplier): $\text{Peak Crawl Rate} = 386 \times 3 \approx \mathbf{1,200\text{ pages/sec}}$
• Average Page Payload: $500\text{ KB}$ (HTML + metadata).
• Peak Ingress Network Bandwidth: $\text{Bandwidth} = 1,200\text{ pages/sec} \times 500\text{ KB} = 600\text{ MB/sec} \approx \mathbf{4.8\text{ Gbps}}$

Storage Footprint (Annual Accumulation)

• Monthly Raw Storage: $10^9\text{ pages} \times 500\text{ KB} = \mathbf{500\text{ TB/month}}$
• Annual Storage Footprint (Compressed Zstandard): $\text{Annual Storage} = 500\text{ TB/month} \times 12\text{ months} \times 0.35\text{ compression} \approx \mathbf{2.1\text{ PB/year}}$

Memory Sizing for URL Deduplication (Bloom Filter)

• Tracking 5 Billion discovered URLs with a false positive rate $p = 0.001$ ($0.1\%$): $m = -\frac{n \ln p}{(\ln 2)^2} = -\frac{5 \times 10^9 \times \ln(0.001)}{(0.6931)^2} \approx 71.9 \times 10^9\text{ bits} \approx \mathbf{8.98\text{ GB RAM}}$ A modest Amazon ElastiCache Redis Cluster easily hosts this Bloom filter in memory.

3. High-Level Architecture & AWS Component Mapping

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

4. URL Frontier Architecture (The Mercator Model)

To solve the dual challenges of Priority (crawling high-quality pages first) and Politeness (never overloading a single target web server), the crawler implements the Mercator Two-Tier Queue System:

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

Politeness Heap Algorithm

1. Each host queue maintains a state record: (hostname, last_access_timestamp, crawl_delay_ms).
2. When a worker requests a URL, the coordinator inspects the Min-Heap.
3. If $T_{\text{now}} \ge \text{next\_fetch\_time}$, the worker pops the next URL for that host, fetches the page, and reschedules the host in the heap for $T_{\text{now}} + \text{crawl\_delay\_ms}$ (minimum 1,000ms).
4. This mathematically guarantees that no single web server ever receives concurrent or rapid-fire hits.

5. Storage Engine & Near-Duplicate SimHash Algorithms

1. 64-Bit SimHash Near-Duplicate Detection Algorithm

To prevent storing millions of mirror pages or template variations:

1. Tokenize HTML body text into word shingles (e.g. 3-word n-grams).
2. Compute 64-bit cryptographic hash for each shingle.
3. Initialize a 64-element weight vector $V = [0, 0, \dots, 0]$.
4. For each shingle hash, add $+1$ to $V[i]$ if bit $i=1$, else $-1$.
5. Form the final 64-bit fingerprint: bit $i=1$ if $V[i] > 0$, else $0$.
6. Hamming Distance Match: If $\text{HammingDistance}(\text{SimHash}_A, \text{SimHash}_B) \le 3$, the pages are near-duplicates; the crawler drops the redundant payload and only records canonical metadata.

2. DynamoDB Crawl State Schema (CrawlStateTable)