Web Crawler

1. Requirements

Functional

• Discover URLs (seeds + extracted links), fetch pages, extract content + outlinks.
• Respect robots.txt and per-host crawl-delay; identify via user-agent.
• Deduplicate URLs (exact) and content (near-duplicate).
• Refresh: re-crawl important/changed pages on a schedule (minutes for news, weeks for docs).
• Store page snapshots (content-addressed) for the indexer.
• Operator controls: seed management, per-domain throttle overrides, blocklist.

Non-functional

• Politeness: ≤ configured req/s per host (default ~1/s), obey Retry-After/429.
• Throughput: billions of pages/month with bounded bandwidth.
• Fault tolerance: worker/region death loses no frontier state.
• Freshness: important pages re-fetched within their change window.
• Cost: bandwidth + storage dominate; dedup before storing anything.

Out of scope

• Index ranking, rendering JavaScript at scale (headless fleet noted only), search serving.

2. Capacity Estimation

Derivations:

• Fetch rate: 10 B / (30 × 86,400) ≈ 3.9 k pages/s.
• Bandwidth: 3.9 k × 50 KB ≈ 195 MB/s ≈ 1.6 Gbps sustained fetch — plus DNS/TLS overhead; budget ~2–3 Gbps with retries.
• Frontier breadth needed: at 1 req/s/host, sustaining 3.9 k fetches/s needs ≥ ~4 k distinct fetchable hosts at all times — trivially true on the web, but the scheduler must never let one host dominate a worker (per-host queues + global interleaving).
• Storage: 10 B × 50 KB = 500 TB per snapshot before dedup/compression; with ~30% near-dup collapse + compression (~5×) ⇒ ~70 TB retained per generation in object storage.
• Seen-URL set: 10 B URLs × ~100 B (hash + metadata) = 1 TB — partitioned KV; the Bloom prefilter (§6B) keeps 99% of lookups out of it.

3. API Design

Mostly internal service APIs + operator surface:

# Frontier (internal gRPC)
PopAssignment { worker_id, capacity } -> { urls[] (host-sharded, politeness-ready) }
ReportFetch { url, status, fetch_ms, content_hash, simhash, outlinks[], robots_hit }
Requeue { url, not_before_ts, reason }   # politeness backoff, 429, 5xx

# Page store
PUT /internal/pages { content_hash, bytes, url, fetched_at }  # idempotent by hash
GET /internal/pages/{content_hash}

# Host metadata (cached)
GET /internal/hosts/{host} -> { robots_rules, crawl_delay_ms, next_allowed_ts, dns_ttl }

# Operator
POST /admin/seeds { urls[], priority }
POST /admin/throttles { host_pattern, req_per_s }
GET  /admin/crawl/status?host=… -> { queued, fetched_24h, error_rate, last_fetch }

Key point: fetch results are reported with content hashes so the frontier can dedup before the indexer ever sees bytes.

4. Data Model & Storage

5. High-Level Design

Flow: seeds → frontier (prioritize) → fetch workers (DNS cache → robots check → polite fetch) → parse (links back to frontier, content hash → dedup) → page store + indexer; refresh scheduler re-injects stale important URLs; coordinator owns host→worker assignment.

Workers are stateless-ish: all assignment and cursor state lives in the coordinator + frontier, so workers scale horizontally and die freely.

6. Deep Dives

A. Frontier and politeness

• Structure: per-host FIFO queues (priority-ordered within host) fronted by a global min-heap keyed by next_allowed_ts. A worker pops the host whose time has come, fetches one URL, and pushes the host back with next = now + max(crawl_delay, 1/rate_limit). This single structure yields max throughput subject to politeness — no host is ever over-fetched, no worker ever idles while fetchable URLs exist.
• Prioritization: score = importance (link-graph rank, inlink velocity) × staleness (now − last_fetch)/change_interval. News homepages (change interval: minutes) naturally outrank static docs (weeks). Fresh discoveries from high-importance pages inherit a fraction of parent priority (focused crawling).
• Backpressure signals: 429/Retry-After ⇒ multiplicative decrease of that host's rate; timeouts ⇒ host quarantine with exponential backoff; robots fetch failures ⇒ fail closed (don't crawl) for that host until robots succeeds.

B. Dedup via Bloom and SimHash

• Exact URL dedup: canonicalize first (lowercase host, strip tracking params, sort query keys, resolve relative URLs) — canonicalization kills ~20–30% of dupes before any structure is touched. Then Bloom filter: for n = 10 B URLs at p = 1%: m = −n·ln(p)/(ln 2)² ≈ 9.6·n bits ≈ 12 GB — shardable across workers (1.2 GB per 10 shards), kept in memory. Bloom "seen" ⇒ confirm against KV ground truth (kills false positives); Bloom "new" ⇒ definitely new, insert.
• Near-dup content: 64-bit SimHash of page text; Hamming distance ≤ 3 ⇒ near-duplicate (templates, mirrors, printer-friendly variants). Pairwise comparison is avoided via banding/bucketing on hash prefixes; only survivors reach the index. Freshness nuance: same SimHash + newer timestamp ⇒ refresh the index entry, don't store twice.
• Content-addressed storage makes the whole pipeline idempotent: re-fetching stores nothing new, just updates pointers.

C. DNS caching and distributed coordination

• DNS: uncached DNS adds ~20–100 ms per fetch — at 3.9 k fetches/s that's 80–400 s of aggregate stall per second. Cache resolutions honoring TTL (floor ~60 s, cap ~10 min), share per worker-host, prefetch DNS for queued hosts. Same for robots.txt (cache 24 h unless the site signals otherwise) and TLS sessions (resumption across fetches to the same host).
• Coordination: hosts map to workers via consistent hashing (see Consistent hashing) — one host is ever owned by one worker, so politeness holds globally without cross-worker locking. Membership/liveness via a coordinator (etcd/ZooKeeper); on worker death, its host ranges move and cursors resume from frontier checkpoints.
• Failure semantics: at-least-once fetching (a crashed fetch may repeat) + idempotent stores (content hash keys) = exactly-once effects. Checkpoint frontier cursors every N pops so reassignment replays at most N URLs.

7. Bottlenecks, Trade-offs & Monitoring

Bottlenecks: politeness-limited hosts (more distinct hosts in rotation, not more threads); DNS storms on new-host discovery (prefetch + shared cache); frontier hot shards for mega-hosts (split giant hosts across sub-queues); parse CPU on JS-heavy pages (separate headless fleet with tight budget).

Monitoring: fetches/s, per-host rate adherence (violations = 0), queue depth by priority, Bloom FP rate, SimHash collapse ratio, robots-failure rate, DNS hit ratio, worker rebalance events, freshness SLO (% important pages within change window).

Interview one-liners

• Q: How do you avoid hammering one site? A: Per-host queues + next-fetch-time heap; politeness falls out of the data structure.
• Q: Bloom filter size for 10 B URLs? A: ~12 GB at 1% FP — derive it live: m ≈ 9.6·n bits.
• Q: Exact vs near duplicates? A: Canonicalize + Bloom for URLs; SimHash Hamming ≤ 3 for content.
• Q: Worker dies mid-crawl? A: Consistent-hash reassignment + checkpointed cursors; idempotent stores make replay safe.

Related

• Consistent hashing — host→worker assignment
• Rebalancing — host-range failover
• Message queues — frontier queue substrate
• cache-aside — DNS/robots caching discipline
• Object storage — content-addressed snapshots
• Stream Processing — crawl-log analytics and refresh scoring