Design a Web Crawler
A search company wants to keep a copy of the public web fresh. The crawler is handed addresses to visit, must skip pages it has already seen, must not overload any single website, downloads each page, stores it, and pulls out the links that lead to more pages. If the memory of already-seen addresses is lost, the crawler must not turn that into a flood of duplicate downloads on other people's servers.
Constraints
- Accept and schedule about 4,000 addresses per second
- About 45% of addresses are ones already seen, so even a perfect lookup removes no more than that
- Every download passes a politeness limit so no site is overloaded
- Pages come from the open web, which your plan limits to 5,000 requests per second
- Stored pages go to cheap bulk storage; link extraction is helpful but optional
- Old pages are refreshed by a background job
- Keep infrastructure under $10,000 a month
Scenarios to survive
Typical rate
Steady scheduling at the usual rate.
Interviewer asks: Why does skipping duplicates early matter more than making downloads faster?
A huge seed list (2x)
A big list of new addresses doubles the rate for a few minutes.
Interviewer asks: Where does the extra work queue up, and what stops you exceeding the web plan's limit?
The seen-address memory is lost
The fast lookup that remembers visited addresses goes away.
Interviewer asks: The duplicate check is gone. What happens to downloads and to other people's sites, and how do you defend them?
Download workers fail
Whatever runs downloads loses an instance.
Interviewer asks: A downloader dies mid-page. How do you avoid losing the address or fetching it twice?
What a good design must do
- Addresses are accepted within the latency target at the usual rate
- The huge seed list passes
- Total monthly cost stays within $10,000
- The design has a duplicate lookup, a queue, a politeness limit and bulk storage
- Something downloads pages, politely, from the open web
- Something saves pages
- Something refreshes old pages
- Losing the duplicate lookup does not overload the web plan or the crawler
- Losing a downloader does not stop the crawl
- The design explains how a single website is protected