Interview Case Studies
Design a Web Crawler
Fetching a billion pages a month without overloading anyone's server, fetching the same page twice, or getting lost in an infinite calendar.
Medium15 min read
By the end of this chapter
- Design a URL frontier that balances priority against per-host politeness
- Deduplicate URLs and content at billion scale with bounded memory
- Schedule recrawls so freshness tracks how often pages actually change
Clarify the requirements
- Functional: start from seed URLs, fetch pages, extract links, and keep crawling.
- Functional: store fetched HTML for a downstream indexer.
- Functional: revisit pages to keep the stored copy reasonably fresh.
- Out of scope: rendering JavaScript-heavy pages, images and video, the indexer itself.
- Non-functional: polite. Never overload a site; obey robots.txt.
- Non-functional: robust against malformed pages, slow servers and crawler traps.
- Non-functional: scales by adding machines.
Estimate
| Quantity | Assumption |
|---|
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inYou’ve reached the end
What this chapter was for:
- The frontier is the heart of a crawler: priority queues decide what next, per-host queues decide when.
- Politeness is a hard requirement, not a courtesy. One connection per host, delays between requests, and robots.txt obeyed.
- A Bloom filter holds a billion seen URLs in about a gigabyte, at the cost of occasionally skipping a page it has not actually seen.
- Recrawl adaptively: pages that change often are revisited often, and conditional requests make unchanged pages cheap.