Worked Example 15.12 · 12 of 15

Design a web crawler

📖 3 min read · 8 sections · May 2026

Asked at: Google Microsoft Bing Amazon

The setup

"Design a web crawler. Goal: crawl the entire indexable web (~50 billion pages). Goal latency: complete a full pass every 30 days. Politeness: don't hit any single site more than once per second."

Capacity estimation

Rate: 50B pages / (30 days × 86400 sec) = ~20K pages/sec
Each fetch: avg ~500ms (varies wildly by site)
Concurrent fetches needed: 20K × 0.5 = 10K parallel fetchers
Storage per page: ~100KB compressed
Total: 50B × 100KB = ~5 PB storage

The core loop

┌────────────────────┐
│  Frontier (URLs    │ ← distributed priority queue
│  to crawl)         │
└──────────┬─────────┘
           │
           ↓ pick high-priority URLs (politeness-respecting)
┌────────────────────┐
│  Fetcher pool      │ ← parallel HTTP fetches
└──────────┬─────────┘
           │
           ↓ fetched HTML
┌────────────────────┐
│  Parser            │ ← extract links, content, metadata
└──────────┬─────────┘
           │
        ┌──┴──┐
        ↓     ↓
   ┌────────┐ ┌────────────────┐
   │Storage │ │ Discovery: add │
   │        │ │ new URLs to    │
   │        │ │ Frontier       │
   └────────┘ └────────────────┘

Design Decision 1: the Frontier — distributed priority queue

The frontier holds billions of URLs to crawl. Must be:

Distributed (can't fit on one machine)
Prioritised (high-value sites crawled more often than long-tail)
Politeness-aware (don't hit same host too often)
Resumable (worker crashes don't lose state)

Implementation: per-priority queues stored in distributed system (Kafka, custom). Each URL has metadata: priority score, host, last-crawled-at.

Priority tier	Examples	Re-crawl frequency
P0 — Critical	Wikipedia, news sites, social	Hourly
P1 — High	Mid-popularity sites, blogs	Daily
P2 — Standard	Long-tail	Monthly
P3 — Low	Rarely linked-to	Quarterly

PageRank-style signals determine priority: a URL is more important if it has many incoming links from high-priority sites. Feedback loop: crawled content → analyze links → update URL priorities.

Design Decision 2: politeness — per-host rate limiting

Interviewer: A small site can't handle being crawled at 20K rps. How do you respect politeness?

Workers respect per-host rate limits. The scheduler groups URLs by host before assigning to workers; each host has a "next-crawl-time" timestamp. Workers won't fetch from a host before that time. After fetching, update next-crawl-time = now + politeness_delay (default 1 sec; configurable per robots.txt's crawl-delay directive). For high-volume hosts (Wikipedia), multiple worker queues per host with internal scheduling — but never exceed declared politeness.

Design Decision 3: deduplication

Interviewer: 50B URLs but many redirect to the same content (mirrors, URL parameter variations). Don't re-crawl identical content.

Two levels of dedup. (1) URL normalization: strip query params that don't affect content, canonical hostname, etc. Bloom filter of "URLs seen" — billions of URLs but compact storage; "have we seen this URL?" answered in O(1). (2) Content dedup: after fetching, hash the content. Bloom filter of content hashes. If duplicate content, record the URL → content_hash mapping but don't re-store the content.

Cross-examination round 1: scale of the frontier

Interviewer: 50B URLs in the frontier. How much storage?

URL ~100 bytes avg + metadata (priority score 4 bytes, last-crawled 8 bytes, host 32 bytes etc): ~200 bytes/URL. 50B × 200 = 10 TB. Distributed across many shards (by URL hash). Per-host queues are smaller (millions of URLs per host max); fit in subordinate workers.

Takeaway

Web crawlers are a fascinating exercise in scale and politeness. The hardest parts are not technical primitives but operational: politeness contracts with hosts, content deduplication at petabyte scale, and prioritising the right URLs with finite resources. The deeper insight: at large scale, the priority of what to crawl matters more than the throughput of crawling. Google's original PageRank insight was that you can use the crawl graph itself to decide what's worth crawling more often. That feedback loop — crawl shapes priorities shapes crawl — is what distinguishes great crawlers.