Design a Web Crawler

A web crawler starts from a set of seed URLs, downloads pages, extracts links, and keeps going. Search engines, archives and price trackers all run one. At scale the hard parts are being polite to websites, avoiding duplicate work, and keeping a frontier of billions of URLs moving.

Requirements#

• Crawl 1 billion pages a month of HTML.
• Respect robots.txt and never overload a single site.
• Skip duplicate URLs and duplicate content.
• Revisit pages based on how often they change.
• Store page content for an indexer downstream.

Estimates#

High-level design#

1. The frontier decides what to fetch next.
2. Fetchers resolve DNS, download the page and respect timeouts.
3. The parser extracts text and links, and checks whether the content is a duplicate.
4. New links that haven't been seen go back into the frontier.

The URL frontier#

The frontier does two jobs at once: priority (important pages first) and politeness (one host at a time).

• Front queues hold URLs by priority, scored by PageRank-like signals or how often the page changes.
• Back queues are one per host. Each fetcher thread pulls from a single host's queue and waits a delay between requests to that host.

This guarantees no site gets hammered even when it has millions of URLs in the frontier.

De-duplication#

• URLs: normalise them first (lowercase host, remove fragments, sort query parameters), then check a Bloom filter of seen URLs. A Bloom filter answers "definitely new" or "probably seen" in a few bits per URL.
• Content: many URLs serve the same page. Hash the content (or use SimHash for near-duplicates) and skip pages whose fingerprint is known.

Politeness and robots.txt#

• Fetch and cache each host's robots.txt before crawling it, and refresh it daily.
• Honour Crawl-delay, back off on 429 and 503 responses, and send a clear user agent with contact details.

Freshness#

Pages change at different rates: a news homepage changes every minute, an old blog post almost never. Track each page's change history and schedule revisits accordingly. Conditional requests with If-Modified-Since or ETag save bandwidth when nothing changed.

Robustness#

• Spider traps: infinite calendars or session IDs in URLs can generate endless links. Cap URL length and depth per host, and limit pages per domain.
• Fault tolerance: checkpoint the frontier to disk; fetchers are stateless and can restart anywhere.
• DNS: resolution can be slow, so run a local DNS cache.

Scaling out#

Partition the frontier and seen-set by host hash, so all URLs of a host live on one crawler node. That keeps politeness local (no cross-node coordination per host) and lets the cluster grow by adding nodes.