system-design

Design a Web Crawler

Difficulty: Tier 2 Asked at: Google, Amazon, Systems Ltd, Arbisoft Time budget: 45 min

A web crawler downloads the internet, one page at a time, forever. The interesting part isn’t fetching a page — it’s doing it at the scale of billions of pages: not re-fetching what you’ve seen, being polite to servers, prioritizing what matters, and never getting stuck. It’s a beautiful showcase for queues, deduplication (Bloom filters!), and politeness — a producer/consumer system at planetary scale.

Prerequisites: Message Queues, Bloom Filters, Object Storage

1. Requirements

Functional:

Non-functional:

Out of scope: the search index itself (that’s google-search), ranking.

2. Estimation

3. Components

flowchart LR
    Seed[Seed URLs] --> Frontier[[URL Frontier<br/>priority + politeness queues]]
    Frontier --> Fetcher[Fetcher workers]
    Fetcher --> DNS[DNS resolver cache]
    Fetcher --> Robots[robots.txt cache]
    Fetcher --> Parser[Parser: extract links + text]
    Parser --> Dedup{Seen before?<br/>Bloom filter}
    Dedup -- no --> Frontier
    Dedup -- content dup? --> Drop[Drop]
    Parser --> Store[(Content store<br/>object storage)]

The heart is the URL frontier — the smart queue that decides what to crawl next and when, honoring priority and politeness.

4. Deep dives

4a. The URL frontier (priority + politeness)

🚨 This is the core of the question. Two competing needs:

A common design: a front set of priority queues feeds a back set of per-host queues; a worker is assigned a host queue and paces its requests. This decouples “what’s important” from “who’s allowed to fetch now.”

4b. Deduplication — have we seen this URL / content?

Two dedup problems:

4c. Politeness & robots.txt

Fetch and cache each domain’s robots.txt; obey disallowed paths and crawl-delay. Cache DNS resolutions (DNS lookups are slow and would dominate latency otherwise). Rate-limit per host in the frontier. Set a descriptive User-Agent. 🚨 A crawler that ignores politeness gets your IP banned and can DoS small sites — name this.

4d. Traps & robustness

4e. Freshness / re-crawling

Pages change at different rates (a news homepage vs an archived doc). Track each page’s change history and re-crawl frequently-changing, important pages more often — an adaptive re-crawl schedule. Re-insert URLs into the frontier with a due-time.

4f. Distributed coordination

Partition the frontier and workers by domain hash so all URLs for a host go to the same worker/shard — this makes politeness easy (one place enforces per-host pacing) and keeps DNS/robots caches warm. Workers are stateless and horizontally scalable; the frontier and seen-set are the shared state.

5. Bottlenecks & scaling further

  1. Fetch throughput → add fetcher workers; they’re stateless and network-bound.
  2. DNS → a caching DNS layer (DNS is a classic hidden bottleneck).
  3. Frontier size → the seen-set is billions of URLs → Bloom filter in memory + durable backing store.
  4. Politeness vs speed → per-host queues limit per-domain rate; parallelism comes from crawling many domains at once, not one domain fast.
  5. Storage → object storage scales; compress content.

6. Trade-off summary

Decision Chosen Alternative Why
URL dedup Bloom filter Exact hash set Billions of URLs won’t fit; false positives tolerable
Frontier Priority + per-host queues Single FIFO queue Needs both importance and politeness
Partitioning By domain hash By URL hash Keeps politeness/DNS/robots per-host in one place
Content dup Content hash / SimHash Ignore Mirrors and traps waste crawl budget
Storage Object storage, compressed Database Cheap, scalable for 100 TB of blobs

7. Follow-up questions

Why a Bloom filter for the seen-set and what's the risk? Because tracking billions of already-seen URLs in an exact hash set would need hundreds of GB of RAM, whereas a Bloom filter represents the same set in a small fraction of that memory by allowing a controlled false-positive rate. Its answers are "definitely not seen" (safe to crawl) or "probably seen." The risk is a false positive: it says "seen" for a URL we actually haven't crawled, so we skip a real page. At web scale that's acceptable — we'll still crawl billions of pages, and for high-value URLs we can double-check against a durable store. There are no false negatives, so we never re-crawl something the filter says is new when it isn't, meaning we never accidentally lose the dedup guarantee in the dangerous direction.
How do you stay polite without crawling slowly overall? Politeness is per-host, throughput is aggregate. You cap the request rate to any single domain (per-host queue with a crawl-delay, one worker draining it), but you crawl thousands of *different* domains simultaneously. So no individual server is overwhelmed, yet total throughput is huge because it's the sum across many hosts. The trick is partitioning by domain so per-host pacing is enforced in one place while parallelism comes from breadth across domains, not depth into one.
How do you avoid crawler traps and infinite loops? Several layers: content-hash dedup catches pages that are identical despite different URLs (common in traps); a max crawl depth and a per-domain URL budget bound how far you'll descend; URL-pattern heuristics detect obviously-generated infinite spaces (endless calendar dates, session IDs); and the seen-set stops re-crawling the same URL. Together these cap the damage a malicious or accidental infinite URL space can do to your crawl budget.
How do you keep the crawl fresh? Track how often each page actually changes and re-crawl adaptively: pages that change frequently and matter (news, popular sites) get re-queued with short intervals; static or unimportant pages get long intervals. URLs carry a due-time and re-enter the frontier when due. This spends limited crawl budget where change is happening instead of re-fetching everything uniformly.

8. What junior / mid / senior answers look like

Further reading

This site is open source. Improve this page.