A crawler is a scheduler plus a polite HTTP client. The interview tests whether you find the per-host serialization constraint, and whether the frontier survives restarts.
Requirements and capacity
Crawl 1B URLs, re-crawl weekly → 1B/(7 × 86,400) ≈ 1,650 pages/s sustained. Average page ~100KB → 165MB/s → ~14TB/day raw, ~4.7TB/day compressed into object storage. The crawl is throughput-bound in theory and politeness-bound in practice.
Components
- Frontier: the crawl's memory — per-host priority queues, persisted in RocksDB. An in-memory frontier dies with the process and takes the crawl's position with it; persistence is non-negotiable.
- Politeness scheduler: the binding constraint. One outstanding fetch per host, minimum 1–2s between fetches to the same host. Math: 1B URLs over ~50M hosts ≈ 20 URLs/host → one fetcher serving a host with a 2s delay yields ~0.5 pages/s. Sustaining 1,650 pages/s needs ~3,300 fetchers in flight — a fetcher pool sized by politeness, not by network bandwidth. That arithmetic is the heart of the interview.
- Fetcher pool: HTTP GET, 30s timeout, stream the body to blob storage so RAM stays flat. Cache DNS aggressively (it is a real bottleneck at this QPS) and cache robots.txt per host with a TTL — a crawler that ignores robots gets IP-blocked, which is a throughput loss orders of magnitude worse than the cache miss.
- Parser + link extractor: new URLs → normalize (scheme, host casing, fragment removal, relative resolution) → dedup → frontier.
- Dedup: Bloom filter over seen URLs: 1B URLs × 10 bits ≈ 1.25GB in RAM, ~1% false positives. A "seen" false positive means a page is skipped forever — acceptable when the alternative is a 40GB+ hash set. State the trade explicitly: you are buying 32x memory savings at 1% recall loss.
Data model
url_table(url_hash PK, url, host, status, fetch_time, next_fetch_time, priority, robots_ok); frontier = RocksDB queues keyed by host; content in object storage keyed by url_hash + fetch_time — immutable snapshots, re-crawls add versions, never overwrite.
Re-crawl prioritization
Score = (change likelihood × importance) − freshness. High-priority queues drain first; a daily newspaper gets crawled more often than a static README. This is a scheduling policy, not an afterthought.
Failure handling
Per-host error tracking: flaky hosts back off exponentially, and a host whose error rate trips a threshold gets circuit-opened — retries flow back through the normal queue, never a parallel firehose (health-checks-and-observability, queue-burst-trace). One misbehaving retry loop can otherwise consume the whole frontier.
Bottlenecks
Per-host serialization (the throughput cap), DNS, duplicate discovery, robots re-fetches, storage growth, and burst absorption in the frontier when a large site is discovered at once. Order them by impact and you've passed.