Design a Web Crawler

The core loop is simple: take a set of URLs, download each page, pull out the links, and add unseen links to the to-do list. What makes it a design problem is scale and hostility. Crawlers power search indexing, web archiving, data mining, and copyright monitoring, and each purpose changes what gets crawled and how often.

Assume a search-engine crawler that fetches about one billion HTML pages per month, keeps them for five years, and ignores duplicate content. Four qualities matter. Scalability means the work parallelises across many machines. Robustness means bad HTML, unresponsive servers, crashes, and malicious traps never stop the crawl. Politeness means you never hammer one website with too many requests. Extensibility means new content types, such as images or PDFs, can be added as plug-in modules without redesigning the pipeline.

One billion pages a month is 1,000,000,000 / (30 × 86,400) ≈ 1,000,000,000 / 2,592,000 ≈ 386 pages per second, so plan for about 400 QPS average and roughly 800 at peak.

With an average page of 500 KB, monthly storage is 10^9 × 500 KB = 500 TB. Over five years that is 500 TB × 12 × 5 = 30 PB. Check by another route: 400 pages/s × 500 KB = 200 MB/s, × 2.6 million seconds ≈ 520 TB per month, which agrees. Bandwidth of about 200 MB/s (1.6 Gbps) inbound is significant but ordinary for a cluster.

Crawling begins from seed URLs. A good seed set spreads coverage, for instance by picking popular sites per country or per topic. URLs waiting to be fetched live in the URL frontier, a smart queue. The HTML downloader fetches pages, using a DNS resolver to turn hostnames into IP addresses. The content parser validates and parses each page, discarding malformed ones so they do not waste storage.

Next, a content-seen check compares the page against already stored content; studies have found that a large fraction of web pages are duplicates. New pages go to content storage. The URL extractor pulls links and normalises relative paths into absolute URLs. A URL filter drops blacklisted sites, unwanted file types, and error links. Finally, a URL-seen check skips anything already visited or queued, and genuinely new URLs return to the frontier. The traversal is essentially breadth-first search, because depth-first search can dive endlessly into one deep site.

Plain BFS with a single FIFO queue has two flaws. Most links on a page point back to the same host, so a naive crawler would fire hundreds of parallel requests at one site, which is impolite and can look like a denial-of-service attack. And a FIFO treats every page as equally important, when a news homepage clearly deserves more attention than a forgotten forum thread.

The frontier fixes both with two layers of queues. Front queues handle priority: a prioritiser scores each URL using signals like PageRank, traffic, and update frequency, and places it into one of several queues by priority; a selector picks from higher-priority queues more often. Back queues handle politeness: a router maps each host to exactly one back queue using a host-to-queue table, and each back queue has a single worker thread that downloads one URL at a time with a delay between requests. Freshness comes from recrawling pages based on how often they change and how important they are.

Before fetching from a site, the downloader reads its robots.txt, which states which paths crawlers may visit. Fetching it before every page would double the traffic, so results are cached and refreshed periodically.

Performance comes from several techniques. Crawl jobs are distributed across many servers, each running many threads. DNS resolution is surprisingly slow, often tens to hundreds of milliseconds, and many resolvers are synchronous, so the crawler keeps its own DNS cache refreshed by a background job. Locality places crawl servers near the hosts they fetch to cut network time. Short timeouts stop a slow server from tying up a worker forever.

Comparing pages character by character is far too slow at billions of documents. Instead, compute a hash or fingerprint of each page and compare fingerprints. Exact hashes catch identical copies; techniques like SimHash can detect near-duplicates whose small differences, such as timestamps or ads, would otherwise defeat an exact match.

URL-seen checks run for every extracted link, so they must be cheap. A Bloom filter fits billions of URLs into modest memory and answers 'definitely new' or 'probably seen'. The occasional false positive means a genuinely new URL is skipped, which is an acceptable loss for a crawler. A plain hash table keyed by normalised URL is the exact alternative when memory allows.

Use consistent hashing to spread work across downloader servers so nodes can join or leave without reshuffling everything. Persist crawl state and frontier contents regularly so a crash restarts from a checkpoint rather than from scratch. Catch exceptions per page so one bad document never kills the process, and validate data to avoid storing garbage.

Watch for spider traps, pages that generate infinite link structures such as endless calendar pages or deeply nested paths. Capping URL length and depth helps, but some traps need manual blacklisting. Filter data noise like ads, spam pages, and code snippets that add no value. Many sites build links with JavaScript, so a crawler that only parses raw HTML will miss them; server-side rendering (dynamic rendering) of pages before parsing recovers those links at extra CPU cost.

Most of the important choices are trade-offs between coverage and cost. A larger frontier and more aggressive recrawling improve freshness but cost bandwidth and annoy site owners. Bloom filters save memory but lose a small fraction of URLs. Rendering JavaScript finds more links but multiplies CPU per page. BFS gives broad coverage; DFS would get stuck. Extensibility is achieved by plugging new modules, such as a PNG downloader or a web monitor for copyright infringement, into the same pipeline after the parser.

Good closing points include horizontal scaling of every stage, database replication and sharding for content storage, keeping the stages stateless where possible, and adding analytics on crawl rate, error rate, and freshness so the operators can tune priorities over time.