Case study

Design a Web Crawler

Crawl billions of web pages with politeness, deduplication, and distributed worker coordination.

BFSdeduppoliteness

Requirements

Functional: discover and fetch URLs; parse HTML; extract links; store content
Respect robots.txt and crawl-delay per domain
Prioritize important pages (PageRank, freshness)
Non-functional: 1B pages crawled/month; politeness ≥ 1 sec between requests per domain
Detect duplicate content (near-duplicate via simhash)

Back-of-envelope Estimation

Metric	Calculation	Result
Pages/month	1B	Given
Fetch QPS	1B / (30 × 86,400)	~400/sec average sustained
Avg page size	50 KB HTML	50 TB/month raw HTML
URL frontier	10B unique URLs discovered	Bloom filter ~ 12 GB @ 1% FP
Domains	100M unique	Per-domain queues essential for politeness

Internal API Design

Component	Interface
Seed API	POST /seeds { urls[], priority } — bootstrap frontier
Fetcher	pull(url) → html, headers, status
Parser	parse(html, baseUrl) → { links[], text, title }
Robots cache	getPolicy(domain) → { allowed paths, crawl-delay }

Data Model

Store	Purpose
URL frontier	Priority queue per domain shard (Kafka/Redis)
visited_bloom	Probabilistic dedup of canonical URLs
url_metadata	url_hash, last_crawled, etag, content_hash — Cassandra
page_store	Raw HTML + parsed text — S3/HDFS
robots_cache	domain → robots.txt parsed rules — Redis TTL 24h

High-level Design

Crawler fleet

Coordinator ──► Domain Shards (hash domain → queue)
                      │
              Fetcher Workers (pull when politeness window open)
                      │
              Parser ──► extract links ──► normalize URL ──► dedup ──► re-enqueue
                      │
              Page Store (S3) + Index pipeline (downstream search index)

Deep Dive: Politeness & Scheduling

Each domain has a last_fetch timestamp and crawl-delay (from robots.txt, default 1s). Worker can fetch only if now − last_fetch ≥ delay. Priority within domain by PageRank estimate and freshness (last_crawled age).

Canonicalize URLs: lowercase host, strip fragments, resolve relative paths
DNS cache per worker; respect max redirects (3)
Rate limit per IP block to avoid bans

Deep Dive: Dedup at Scale

Layer	Mechanism
URL dedup	Bloom filter + DB confirm on positive
Content dedup	SHA-256 of normalized text; skip if seen
Near-duplicate	Simhash with Hamming distance ≤ 3

Failure Modes & Monitoring

Metric	Alert
Fetch success rate	< 90% (exclude 404/403)
Frontier lag per domain	> 7 days for high-priority
Parser crash rate	> 0.1%
Robots violations	Any — critical

System Design