Design a Web Crawler at Scale

1. Problem Statement & Scope Clarification

System Mission

Design a planetary-scale, distributed, fault-tolerant Web Crawler (similar to Googlebot, Bingbot, or Common Crawl) capable of crawling $1\text{ Billion}$ web pages per month, strictly adhering to domain politeness policies and robots.txt protocols, eliminating duplicate URLs and near-duplicate content, and persisting standardized Web ARChive (WARC ISO 28500) datasets into Amazon S3 for downstream search engine indexing and LLM pre-training pipelines.

Functional Requirements

1. Planetary-Scale Distributed Crawling: Crawl billions of web pages starting from a curated set of high-authority seed URLs, traversing outbound hyperlinks up to a bounded depth.
2. Politeness & robots.txt Compliance: Respect target website rate limits, crawl-delays, and disallow directives. Restrict crawl velocity to at most 1 request per second per target host unless explicit crawl-delay specifies otherwise.
3. Multi-Stage Deduplication:
   • URL Deduplication: Prevent re-crawling visited URLs within a 30-day freshness horizon using high-speed in-memory Bloom filters.
   • Near-Duplicate Content Detection: Identify duplicate or template-generated mirror pages using 64-bit SimHash Hamming distance ($\le 3$ bit differences).
4. HTML Parsing & Link Extraction: Extract canonical URLs, page titles, text content, and outbound links, converting relative links to absolute, canonicalized URI representations.
5. Standardized Web Archive Persistence: Package raw HTTP request/response payloads, headers, and metadata into compressed WARC files and stream them to Amazon S3 Standard-Infrequent Access (S3-IA).

Non-Functional Requirements (SLAs & SLOs)

• Throughput & Scale: Ingest $1\text{ Billion pages/month}$ ($\approx 386\text{ pages/sec}$ sustained average, Peak: $1,200\text{ pages/sec}$).
• Politeness SLA: $0$ DDoS incidents against target websites; strict per-domain throttling.
• Compute Cost Efficiency: Resilient to sudden instance terminations using AWS EC2 Spot Fleets with automated state checkpointing ($70-90\%$ compute cost reduction).
• Extensibility: Pluggable architecture supporting headless browser rendering (Playwright/Puppeteer) for JavaScript-heavy Single-Page Applications (SPAs).

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

Ingestion & Crawl Throughput Derivations

• Monthly Crawling Target: $1,000,000,000\text{ pages/month}$ (1 Billion pages).
• Average Crawl Rate: $\text{Sustained Crawl Rate} = \frac{10^9\text{ pages}}{30\text{ days} \times 86,400\text{ sec/day}} = \frac{10^9}{2,592,000\text{ sec}} \approx \mathbf{386\text{ pages/sec}}$
• Peak Crawl Rate ($3\times$ burst multiplier for high-bandwidth domains): $\text{Peak Crawl Rate} = 386 \times 3 \approx \mathbf{1,200\text{ pages/sec}}$
• Average HTML Page Payload: $500\text{ KB}$ (HTML text, stylesheets, embedded headers).
• Peak Ingress Network Bandwidth: $\text{Peak Ingress} = 1,200\text{ pages/sec} \times 500\text{ KB} = 600\text{ MB/sec} = \mathbf{4.8\text{ Gbps}}$

Storage Footprint (Raw vs Compressed WARC Archive)

• Monthly Raw Web Ingestion: $\text{Raw Monthly Volume} = 10^9\text{ pages} \times 500\text{ KB} = 500\text{ TB/month}$
• Compressed Archive (Zstandard compression ratio $\approx 0.35$): $\text{Monthly Compressed Volume} = 500\text{ TB} \times 0.35 = \mathbf{175\text{ TB/month}}$
• Annual Storage Accumulation: $\text{Annual Storage} = 175\text{ TB/month} \times 12\text{ months} = \mathbf{2.1\text{ PB/year}}$ Stored in Amazon S3 Standard-IA with lifecycle transition to S3 Glacier Deep Archive after 90 days.

Memory Sizing for URL Deduplication (Redis Bloom Filter)

To prevent re-crawling, we track $n = 5,000,000,000$ ($5\text{ Billion}$) discovered URLs over a 30-day window with a false positive probability $p = 0.005$ ($0.5\%$):

• Optimal Bit Array Size ($m$): $m = -\frac{n \ln p}{(\ln 2)^2} = -\frac{5 \times 10^9 \times \ln(0.005)}{(0.69315)^2} = -\frac{5 \times 10^9 \times (-5.2983)}{0.48045} \approx \frac{26.49 \times 10^9}{0.48045} \approx \mathbf{55.14 \times 10^9\text{ bits}}$ $\text{RAM Required} = \frac{55.14 \times 10^9\text{ bits}}{8 \times 1024^3\text{ bytes/GB}} \approx \mathbf{6.42\text{ GB RAM}}$
• Optimal Number of Hash Functions ($k$): $k = \frac{m}{n} \ln 2 = \frac{55.14 \times 10^9}{5 \times 10^9} \times 0.69315 \approx 11.03 \times 0.69315 \approx \mathbf{8\text{ hash functions}}$ Using MurmurHash3 double-hashing ($g_i(x) = h_1(x) + i \cdot h_2(x) \pmod m$), an Amazon ElastiCache Redis Cluster with $16\text{ GB RAM}$ handles this deduplication dataset with room for growth.

EC2 Spot Crawler Fleet Sizing

• Average fetch latency per page (DNS + TCP/TLS Handshake + HTTP Stream): $t_{\text{fetch}} \approx 1.5\text{ seconds}$.
• Concurrently active HTTP socket connections needed for $1,200\text{ pages/sec}$: $\text{Concurrent Connections} = 1,200\text{ pages/sec} \times 1.5\text{ sec} = \mathbf{1,800\text{ concurrent streams}}$
• Using c6i.2xlarge Spot instances (8 vCPUs, 16 GB RAM, 12.5 Gbps network) capable of sustaining 150 concurrent non-blocking async HTTP worker coroutines: $\text{Fleet Size} = \frac{1,800\text{ streams}}{150\text{ streams/instance}} = \mathbf{12\text{ Spot Instances}}$ We provision a minimum of 16 Spot instances across 3 Availability Zones for N+4 redundancy.

3. High-Level Architecture & AWS Component Mapping

Synthesizing vector architecture diagram...

Data Flow Walkthrough

1. Frontier Enqueue & Deduplication: Discovered links are submitted to the Frontier Coordinator. The URL is canonicalized (lowercased, default ports stripped, query params normalized). It tests the Redis Bloom Filter; if present, the link is discarded immediately ($< 0.1\text{ ms}$).
2. Priority Classification: Unvisited URLs are categorized by domain authority into Priority SQS FIFO queues ($F_1..F_n$).
3. Politeness Dispatching: The Politeness Router pulls URLs from priority queues using biased lottery scheduling and routes them into a single SQS FIFO politeness queue with MessageGroupId = host_<domain>. SQS FIFO delivers the messages of one group to only one consumer at a time and in order, so the queue itself serialises each host; millions of hosts become millions of groups inside one queue, not millions of queues (SQS has no practical way to create or poll a queue per domain). A Redis lease (SET lease:host:<domain> PX 1000 NX) then spaces consecutive fetches to the same host at least 1 second apart, since group ordering alone says nothing about timing.
4. Optimized Network Fetching: The Crawler Worker queries its local Unbound DNS Cache (avoiding external DNS network round trips) and initiates an asynchronous HTTP/2 GET. The worker parses robots.txt directives cached in memory.
5. SimHash Verification & Archival: The downloaded HTML is fingerprinted using a 64-bit SimHash. If Hamming distance to any known page on the domain is $\le 3$, it is flagged as a near-duplicate and skipped. Otherwise, the raw payload is written into an open WARC container in Amazon S3, and newly extracted outbound URLs are looped back to step 1.

Concrete Step-by-Step Request Walkthrough: Tracing a Discovered URL Crawl

4. API Interface Design & Control Protocol

Internal Crawler Worker Job Message Protocol (SQS FIFO Message Body)

jsonCopy
{
  "message_id": "msg_984f1a2b-3c4d-5e6f-7a8b-9c0d1e2f3a4b",
  "crawl_job_id": "job_2026_09_crawl",
  "target_url": "https://en.wikipedia.org/wiki/Distributed_computing",
  "canonical_url": "https://en.wikipedia.org/wiki/Distributed_computing",
  "host": "en.wikipedia.org",
  "depth": 3,
  "max_depth": 8,
  "priority_score": 92.5,
  "retry_count": 0,
  "parent_url": "https://en.wikipedia.org/wiki/Computer_science",
  "scheduled_at_epoch_ms": 1767225600000
}

Crawl Result Event (Emitted to Kinesis Ingestion Pipeline)

jsonCopy
{
  "url": "https://en.wikipedia.org/wiki/Distributed_computing",
  "http_status": 200,
  "content_type": "text/html; charset=UTF-8",
  "content_length_bytes": 430080,
  "fetch_duration_ms": 312,
  "simhash_fingerprint": "0x8f9a2b1c4d3e5f60",
  "discovered_links_count": 84,
  "warc_file_s3_uri": "s3://crawler-warc-lake/2026-09-16/chunk_104.warc.zst",
  "warc_record_offset": 41943040,
  "warc_record_length": 143360,
  "crawled_at": "2026-09-16T12:00:00.000Z"
}

5. Data Models & Storage Architecture

1. DynamoDB Visited URLs & SimHash Registry (VisitedUrlsRegistryTable)

2. S3 Web Archive (WARC ISO 28500) Storage Standard

Files are packaged into standardized $1\text{ GB}$ chunks compressed with Zstandard (.warc.zst) partitioned by crawl date and target domain cluster: