System Design

Design Web Crawler

Distributed crawl frontier, robots.txt politeness, deduplication, and storing billions of web pages.

Interview tip BFS frontier in priority queue, robots.txt cache, Bloom filter for seen URLs, separate fetcher vs parser workers. Per-domain rate limiting is critical.

① Functional requirements

Start from seed URLs; discover new URLs by parsing HTML links
Fetch page content (HTML); follow redirects (max 5 hops)
Extract and normalize URLs (canonical form)
Respect robots.txt and crawl-delay per domain
Deduplicate URLs — never fetch same URL twice
Store raw HTML + metadata (URL, fetch time, status code, checksum)
Priority queue: important domains/pages crawled first

Out of scope (state in interview)

JavaScript rendering (headless browser — mention as extension)
Full-text search index building
Image/binary file crawling
Authentication / login walls

② Non-functional requirements

Crawl 1B pages/day (~11.5K pages/sec sustained)
Politeness: default 1 request/sec per domain
Fault tolerant — failed fetches retried with backoff
Horizontally scalable fetcher workers
Detect and avoid spider traps (infinite URL spaces)

③ Back-of-the-envelope scale

Assumptions

1B pages/day → ~11.5K fetches/sec average, ~50K/sec peak
Avg page 50KB HTML → 50GB/sec raw bandwidth at peak
Storage: 1B × 50KB × 365 ≈ 18 PB/year
URL frontier: ~10B unique URLs discovered; Bloom filter 10B @ 1% FP ≈ 12 GB
100M domains → robots.txt cache ~5 GB
DNS lookups: 11.5K/sec → dedicated DNS resolver pool

Per-domain queues are the key scaling unit — 100M domain queues managed by consistent hashing to scheduler shards. Bloom filter gives O(1) "probably seen" check; exact dedup DB for confirmation on Bloom positive.

④ High-level architecture

Distributed Web Crawler

Seed URL Injector

URL Frontier (priority queues per domain)

Scheduler / Coordinator

Fetcher Pool (10K workers)

Robots.txt Cache

Parser + Link Extractor

URL Dedup (Bloom + DB)

Document Store (HDFS/S3)

URL Metadata DB

Dequeue URL→Check robots.txt→HTTP fetch→Parse + store

Scheduler assigns URLs to fetchers respecting per-domain rate limits. Fetchers are stateless — pull work from domain-specific Kafka topics. Parser is CPU-bound, separate pool from network-bound fetchers.

⑤ Data flow & execution path

End-to-end execution flow

① Client→② API / LB→③ Core services→④ Cache + DB→⑤ Message queue→⑥ Async workers

Sync path: validate → authorize → read/write primary store
Async path: publish domain events → consumers (email, analytics, search index)
Read-heavy path: CDN / edge cache → regional cache → DB replica
Failure path: retry with backoff, DLQ, idempotent handlers

In interviews, trace one user action through this diagram. State what is synchronous (user waits) vs asynchronous (background), and where you enforce idempotency.

⑥ API & interfaces

Endpoint / flow	Purpose	Notes
Internal: enqueue(url, priority)	Add URL to frontier	Normalize; Bloom check; assign to domain queue
Internal: fetch(url)	HTTP GET	Returns {status, headers, body, redirect_chain}
Internal: parse(html, base_url)	Extract links	Returns normalized absolute URLs[]
GET /crawl/status/{domain}	Ops dashboard	Queue depth, last fetch time, error rate per domain
POST /crawl/seeds	Inject seed URLs	Bootstrap or recrawl specific domains

⑦ Data model & storage

url_metadata: url_hash (PK), canonical_url, first_seen, last_crawled, status_code, content_hash, priority

domain_state: domain, last_fetch_ts, crawl_delay_ms, robots_txt, queue_depth

documents (object store): path = /{yyyy}/{mm}/{dd}/{url_hash}.html

Store	What	Why
Kafka (per-domain topics)	URL frontier queues	Backpressure; replay on failure
Redis + Bloom filter	URL deduplication	Bloom in-memory per scheduler shard; Redis for exact check
HDFS / S3	Raw HTML documents	Cheap bulk storage; immutable append
PostgreSQL	URL metadata + domain state	Robots.txt cache; crawl history

⑧ Deep dive — core components

URL frontier & politeness

Each domain has a priority queue in Kafka (topic = domain hash). Scheduler tracks last_fetch_ts per domain — won't dequeue until crawl_delay elapsed (from robots.txt or default 1s). High-priority domains (news, gov) get dedicated fetcher capacity.

Consistent hash domains to scheduler shards — each shard manages ~1M domains. On scheduler failure, Kafka retains unconsumed URLs.

URL normalization & deduplication

Normalize: lowercase host, remove default port, resolve relative paths, strip fragments (#), sort query params, remove tracking params (utm_*). Canonical URL hash (SHA256) as dedup key.

Two-stage dedup: (1) Bloom filter — if "not seen", definitely new. (2) If "maybe seen", check URL metadata DB. False positive rate 1% acceptable — occasional re-fetch wastes bandwidth but not correctness.

Spider trap prevention

Detect: same domain queue depth > 100K; URL path depth > 20; calendar/archive pattern generating infinite dates. Action: cap URLs per domain per day; skip URLs matching trap patterns; alert ops.

robots.txt Disallow paths honored before fetch. Max redirect chain = 5. Reject non-HTTP(S) schemes.

Fetcher design & fault tolerance

Fetcher pool: stateless workers, connection pooling per domain (respect Keep-Alive). Timeout: connect 5s, read 30s. Retry: 3 attempts with exponential backoff for 5xx/timeout. 4xx (except 429): don't retry, log and skip.

DNS caching per fetcher (TTL 300s). User-Agent string identifies crawler. Handle 429 with Retry-After header — requeue with delay.

⑨ Trade-offs & alternatives

Decision	Option A	Option B	Pick when
Dedup	Bloom filter	Exact DB only	Bloom + DB confirm; DB-only too slow at 11K/sec
Frontier	Kafka per domain	Central priority queue	Kafka scales; central queue bottleneck
Politeness	Strict 1 req/sec	Adaptive rate	Strict default; adaptive for trusted domains
Storage	Raw HTML	Extracted text only	Raw for reprocessing; text saves 80% storage
Priority	PageRank-style	FIFO per domain	PageRank for important pages first

⑩ 45-minute interview script

0–5 min: Clarify crawl goals, politeness, dedup, storage
5–12 min: Scale — pages/day, bandwidth, storage PB
12–22 min: Architecture — frontier, fetcher, parser, store
22–30 min: Per-domain rate limiting and robots.txt
30–36 min: URL normalization and Bloom filter dedup
36–42 min: Spider trap detection
42–45 min: Priority crawling for news vs static sites

⑪ Likely follow-up questions

Question	Short answer
JavaScript-rendered pages?	Headless browser pool (Puppeteer) — 10× slower; only for whitelisted domains
How to recrawl changed pages?	Store content_hash; recrawl based on Last-Modified header or periodic schedule by PageRank
Crawler banned by domain?	Backoff crawl rate; rotate IP (ethical gray area); respect 403 as stop signal
Duplicate content different URLs?	Canonical link tag parsing; content_hash dedup across URLs
Distributed robots.txt fetch?	Cache robots.txt 24h per domain; refresh on 404/expiry
How to crawl 10× more tomorrow?	Add fetcher workers linearly; Kafka partitions scale; Bloom filter sharded

⑫ Revision checklist

BFS/priority URL frontier explained
Per-domain rate limiting (robots.txt)
URL normalization rules listed
Bloom filter + exact dedup two-stage
Separate fetcher and parser workers
Spider trap detection mentioned
1B pages/day bandwidth math
Fault tolerance: retry, Kafka replay
Document store on HDFS/S3
DNS caching and connection pooling

crawlerdistributedBloom filterpolitenessBFS