Design a web crawler

Design a web crawler for a search engine: start from seed URLs, download pages, extract their links and keep going, collecting a billion pages a month. It must be polite to websites and never get stuck.

1. Clarify the requirements

Before drawing anything, ask questions. These are the answers an interviewer would typically give:

What is it for?

Search engine indexing.

How many pages?

1 billion pages a month.

Which content types?

HTML only. Images, PDFs and video are out of scope.

New and edited pages?

Yes: re-crawl so new and edited pages are picked up.

Do we store the pages?

Yes, keep the HTML for 5 years.

Duplicate pages?

Pages with duplicate content should be ignored.

2. Estimate the scale

Assumptions: 1 billion pages a month, 500 KB per page on average, kept for 5 years.

• Pages per second: about 400 pages/s1 billion ÷ 30 days ÷ 86,400 s ≈ 400 pages/s.
• Peak pages per second: about 800 pages/sPeak ≈ 2 × average = 800 pages/s.
• Storage per month: about 500 TB1 billion × 500 KB = 500 TB a month.
• Storage for 5 years: about 30 PB500 TB × 12 × 5 = 30 PB.

3. The high-level design

1. Seeds start the frontierThe crawl starts from seed URLs. The URL frontier holds every URL still to download and decides the order: priority first, and one queue per host for politeness.
2. Downloaders fetch and parseMany downloaders, partitioned by host with consistent hashing, fetch pages (respecting robots.txt), parse the HTML and extract links: breadth-first search over the web.
3. Cache DNSDNS lookups take 10–200 ms and block the downloader, so resolved addresses are cached and refreshed in the background.
4. Store pages, skip what you've seenPages go to storage. A hash of each page's content drops duplicates, and a Bloom filter of visited URLs means only new links go back into the frontier.
5. Watch it in productionMetrics and alerts close the loop: pages per second, fetch errors per host and frontier size. Cap URL length and depth so spider traps can't eat the crawl.

4. The components and what each one does

Seed URLs Client (web)

Popular sites by country and topic.

URL frontier Message queue

Prioritizer → front queues; politeness router → one back queue per host, with a delay between requests. Mostly on disk, buffered in memory.

Downloaders & link extractors Workers

Fetch pages (respecting robots.txt), parse HTML, extract links. Partitioned by host with consistent hashing; BFS.

DNS cache Cache

Resolved IP addresses, refreshed periodically.

Page storage Object storage

Raw HTML, kept 5 years (about 500 TB a month).

Content & URL seen NoSQL / KV store

Content hashes (duplicates dropped) and a Bloom filter of visited URLs: only new links go back to the frontier. Sharded by host; replicas with failover.

Metrics & alerts Metrics & alerts

Dashboards and alerts on p99 latency, error rate, queue depth and cache hit ratio, so a bottleneck shows up before it becomes an outage.

5. Deep dive: the url frontier: politeness and priority

How does the URL frontier decide which URL to download next? How do you avoid hammering one website, and still crawl important pages first?

• Politeness: one queue per host, one downloader thread per queue, and a delay between two requests to the same host.
• Priority: a prioritizer scores URLs (PageRank, traffic, update frequency) into front queues; a selector picks high-priority queues more often.
• Most of the frontier lives on disk; in-memory buffers keep enqueue and dequeue fast.

6. What interviewers listen for

• Breadth-first search over the web graphThe web is a graph; BFS (not DFS, which can go very deep) is the usual traversal, with a frontier queue.
• Politeness: per-host queues, delays and robots.txtSending many requests to one host looks like a DoS attack. Map each host to one queue and wait between requests.
• Prioritize important pagesThere are too many pages: crawl the valuable ones first.
• Detect duplicate content with a hashAbout 30% of the web is duplicates: compare page hashes instead of whole pages.
• Avoid spider traps and junkSome sites generate infinite URLs: cap URL length and depth, and filter spam.
• Spread the crawl over many servers by hostPartition URLs by host (consistent hashing) so each host is crawled by one server, politely.
• Re-crawl to keep pages freshRe-crawl based on how often a page changes, and crawl important pages more often.
• Database replication and failoverA single database is a single point of failure. Replicas give redundancy and read capacity; failover promotes a replica when the primary dies.
• Partition (shard) data as it growsOne machine eventually can't hold the data or the write load. Say how you'd split it and by which key.

7. Follow-up questions

1. A small website complains your crawler takes it down every night. What's wrong, and what do you change?
2. Your crawler has been downloading pages from one site for 6 hours: www.site.com/foo/bar/foo/bar/... What happened, and how do you prevent it?
3. Profiling shows downloaders spend most of their time waiting on DNS. How do you fix that?
4. A crawl server crashes halfway through its queue. What's lost, and how do you recover?

The design in a nutshell

• Seed URLs → URL frontier (prioritizer → front queues; politeness router → one back queue per host, on disk with memory buffers).
• HTML downloaders (many, partitioned by host with consistent hashing) use a DNS cache and robots.txt cache, then hand pages to the content parser.
• Content seen? (hash) drops duplicates; pages go to content storage; the link extractor and URL filter find new URLs; URL seen? (Bloom filter) keeps only new ones, which go back into the frontier.
• Robustness: cap URL length/depth against traps, save crawl state, retry with backoff, monitor pages/s and error rates.

Related lessons: The URL frontier: politeness, priority, freshness · DFS vs BFS