Design a web crawler

A web crawler starts from a few URLs, downloads each page, extracts its links and repeats, until it has fetched a meaningful slice of the web. Search engines, archives, price monitors and the datasets behind language models all depend on one. The loop is ten lines of code; the hard part is running it over billions of pages without overloading websites, refetching the same content endlessly or getting stuck in infinite link mazes. This lesson designs a crawler for a search engine.

#Requirements

Functional:

• Given seed URLs, discover and download HTML pages across the public web.
• Store each page's content and metadata for the indexing system downstream.
• Recrawl pages so the stored copy stays reasonably fresh: news front pages within minutes, most pages within weeks.
• Out of scope: rendering JavaScript-heavy pages (discussed at the end), images and video, and the search index itself.

Non-functional:

• Politeness: never overload a website. Respect robots.txt and limit requests per host.
• Scale: billions of pages; the system must scale horizontally by adding machines.
• Robustness: the web is hostile and broken: malformed HTML, endless redirects, slow servers, deliberate traps.
• Efficiency: don't download the same content twice when it hasn't changed.

#Numbers

target:               5 billion pages, refreshed on average every 30 days
fetch rate:           5e9 / (30 × 86,400 s) ≈ 2,000 pages/s steady; plan for 5,000/s
average page:         ~100 KB of HTML (compressed in transit to ~25 KB)
download bandwidth:   5,000/s × 25 KB ≈ 125 MB/s ≈ 1 Gbit/s
storage:              5e9 × 100 KB = 500 TB raw; ~100 TB compressed, per snapshot
URLs known:           ~10× pages fetched → tens of billions of URLs in the frontier and seen-set

The fetch rate itself is modest for a fleet of machines. The difficulty is the bookkeeping: tens of billions of URLs, each with a priority and a next-fetch time, organised so that no host is hit too often.

#The crawl loop

Each box is a separately scaled tier. Fetchers are I/O-bound (thousands of concurrent connections per machine); parsers are CPU-bound; the frontier is a large, carefully structured queue. Content goes to object storage, and an event per stored page tells the indexer.

#The URL frontier: priority and politeness

The frontier holds URLs waiting to be fetched. A plain FIFO queue fails in two ways: it fetches unimportant pages before important ones, and when a popular site's links pile up in the queue, the crawler hammers that one site with hundreds of requests a second.

The classic design has two layers:

1. Front queues for priority. Each URL gets a score: a page's importance (for example a link-based score), how often it changes, how long since it was last fetched. URLs go into one of several priority queues; selection favours higher queues without starving lower ones.
2. Back queues for politeness. Each back queue holds URLs for one host, and each host has a "next allowed fetch time". A heap ordered by that time tells fetchers which host is ready next. After fetching from a host, set its next time to now + delay, where the delay respects the site's Crawl-delay if set, and otherwise scales with how long the server took to respond (a slow server gets more breathing room).

Fetchers ask the frontier for "a URL from a host whose turn it is", so politeness is enforced by construction rather than by every fetcher remembering it.

At tens of billions of URLs, the frontier can't live in one process's memory. Partition by host: hash the hostname to pick a frontier shard, so all URLs of one host, and its politeness timer, live on one shard. New links extracted anywhere are routed to the shard that owns their host. Each shard keeps the head of each queue in memory and the rest on disk.

#robots.txt and DNS

Before fetching from a host, the crawler fetches its /robots.txt, which says which paths crawlers may visit:

User-agent: *
Disallow: /cart/
Disallow: /search
Crawl-delay: 5

User-agent: ExampleBot
Disallow: /

Cache it per host (for about a day) and check every URL against it before fetching. Identify your crawler honestly in the User-Agent header with a URL explaining what it is and how to contact you; site owners need to be able to block or complain.

DNS is a surprisingly common bottleneck: every new host needs a lookup, standard resolvers are slow and rate-limited, and a crawler talks to millions of hosts. Run a dedicated caching resolver close to the fetchers, cache aggressively, and resolve asynchronously so a slow DNS answer doesn't block a fetcher thread.

#Not doing the same work twice

The web repeats itself constantly, and the crawler must notice at three levels.

The same URL. Links come in many spellings: HTTP://Example.com:80/a/../b?utm_source=x#top is the same page as http://example.com/b. Normalise before anything else: lowercase scheme and host, drop default ports and fragments, resolve .., sort query parameters, strip known tracking parameters. Respect <link rel="canonical"> when a page declares its canonical URL.

URLs already seen. Before adding a URL to the frontier, check whether it's been seen. With tens of billions of URLs, an exact set costs hundreds of gigabytes; a Bloom filter per shard answers "definitely not seen" or "probably seen" in a fraction of the memory. A false positive means occasionally skipping a new URL, which is acceptable for a crawler. Exact records of fetched URLs (with last fetch time and content hash) live in a key-value store for recrawl scheduling.

The same content at different URLs. Mirrors, session IDs in URLs and printer-friendly versions serve identical or near-identical pages. Store a hash of each page's normalised content: an exact match means a duplicate. Near-duplicates (the same article with a different ad block) are caught with similarity fingerprints such as SimHash, where similar documents get fingerprints that differ in only a few bits.

#Recrawling: freshness on a budget

Fetching every page every day is impossible, and unnecessary: most pages rarely change. Schedule each URL's next fetch from evidence:

• Change rate: if the last five fetches all returned the same content hash, double the interval (up to a cap); if it changed, shorten it. News front pages converge to minutes, an old documentation page to months.
• Importance: popular pages are worth fetching more often, because stale results there are seen by more users.
• Cheap revalidation: send If-None-Match with the stored ETag or If-Modified-Since with the last date. A 304 Not Modified costs the site and you almost nothing.
• Sitemaps (sitemap.xml, often listed in robots.txt) give lastmod dates; trust them in proportion to how accurate they've proven for that site.

#Traps and failures

The web contains structures, some accidental and some deliberate, that can consume a naive crawler forever:

• Infinite spaces: a calendar whose "next month" link goes on forever, or faceted search producing endless combinations of filters. Cap URLs per host, the depth of path segments and URL length, and deprioritise URLs with many query parameters.
• Redirect loops and chains: follow at most 5 redirects per fetch.
• Huge or endless responses: cap the response size (say 10 MB) and the total fetch time.
• Slow servers: set connect and read timeouts, and treat repeated timeouts as a signal to slow down for that host.
• Spam and link farms: thousands of generated hosts linking to each other. Per-domain budgets (not just per host) and quality scores keep them from eating the crawl.

Fetchers should treat every response as untrusted input: parse HTML with a robust, memory-bounded parser, and run parsers in isolated processes so a pathological page can only crash one worker.

#Practice

The search team asks for two changes:

1. Many important sites are now single-page apps whose HTML is an empty shell until JavaScript runs. The crawler must index their content.
2. A large news site complains that your crawler sent it 800 requests per second, even though politeness is enforced per host.

How do you handle each?

#Key takeaways

• A crawler is a loop of frontier, fetch, store and parse; each stage scales independently.
• The frontier combines priority queues with per-host back queues and next-fetch times, so politeness is built into what fetchers are given.
• Partition the frontier by host, cache robots.txt and DNS, and identify your crawler honestly.
• Normalise URLs, use Bloom filters for the seen-set, and fingerprint content to skip duplicates and near-duplicates.
• Schedule recrawls by observed change rate and importance, revalidate with conditional requests, and defend against traps with caps on depth, size, redirects and URLs per site.