The probe
The web crawler question tests distributed systems breadth: politeness (don’t hammer a single server), deduplication (don’t re-crawl the same URL twice), scheduling (recrawl priority), and parsing at scale. The interesting distributed systems problem is managing a frontier of billions of URLs across a cluster of crawlers without duplication.
Step 1 — Clarify
- Target scale: crawl the whole web (~50B pages) or a specific domain subset? - Recrawl frequency: how often to revisit pages? (Dynamic pages: hourly. Static: weekly.) - What to extract: HTML only, or also images, PDFs, structured data?
- Politeness: respect robots.txt? Rate limit per domain?
- SLO: crawl 1B pages within 24 hours (requires ~12K pages/sec)
Step 2 — Estimate
- 50B pages × 500KB average = 25 PB total web
- Crawl rate needed: 1B pages/day = ~12K pages/sec
- 12K pages/sec × 500KB = 6 GB/sec download bandwidth — requires hundreds of crawler nodes
- URL frontier size: 50B URLs × 50 bytes/URL = 2.5 TB — too large for RAM, needs disk-backed priority queue
Step 3 — Key Components
URL Frontier: A distributed priority queue of URLs to crawl. Priority based on: page importance (PageRank estimate), content freshness, recrawl deadline. Implemented as a two-level structure: an in-memory heap of high-priority URLs, backed by a disk-based queue (Kafka or a custom LSM-tree store) for the full frontier.
Deduplication: Before adding a URL to the frontier, check if it’s already been crawled. Use a Bloom filter (fast, probabilistic, O(1) membership check) to catch already-seen URLs. False positives acceptable (skip a valid URL) but false negatives not (avoid re-crawling). Secondary deduplication: content hash of the fetched page to detect mirror pages.
Politeness policy: Per-domain rate limiting. Maintain a domain_last_crawled map. Enforce minimum interval between requests to the same domain (e.g., 1 request/sec per domain). Respect robots.txt — fetch and cache per domain on first visit.
DNS pre-resolution: DNS lookup adds latency to every fetch. Pre-resolve and cache DNS for all domains in the frontier. TTL-matched to DNS record TTL.
Preparing for a distributed systems interview?
→Download the free Interview Pack
→ Subscribe now to access source code repository - 200 + coding lessons
