System Design Interview
Web crawler in the style of the Mercator design used by search engines: a durable URL frontier, per-host politeness queues with robots.txt and DNS caches, distributed fetchers, Bloom-filter URL deduplication, SimHash content deduplication, and change-based recrawl scheduling. A teaching design.
See why one loop over one list can't crawl the web, politely or otherwise.
What was missing: Nothing yet.
Why that's risky: It fetches one page at a time (each waits hundreds of milliseconds), revisits the same URLs endlessly, and hammers whatever site it is on.
What gets added: One crawler that takes the next URL, fetches it, saves the page and appends every link to its list.
Trade-offs: Simple breadth-first crawling, with no notion of priority, politeness or duplicates.
Keep the list of URLs durable and fetch many pages in parallel.
What was missing: One process held the URL list in memory and fetched one page at a time.
Why that's risky: Fetchers ignore robots.txt and crawl delays, and resolve DNS for every page.
What gets added: A frontier service and store that hold URLs to crawl per host with priority, per-host fetch queues, a fleet of fetchers, and a page store in object storage.
Trade-offs: Grouping by host gives politeness a natural home, at the cost of slower progress on very large single sites.
Crawl fast overall while never overloading any single site.
What was missing: No respect for robots.txt or crawl delays, and a DNS lookup per page.
Why that's risky: The same URL is still queued again every time another page links to it, and mirrored content is stored many times.
What gets added: A robots.txt cache checked before every fetch, a politeness limiter enforcing each host's crawl delay, and a DNS cache.
Trade-offs: Politeness caps how fast any one site is crawled; overall speed comes from crawling many sites at once.
Discover new URLs without re-queueing known ones, and skip duplicate content.
What was missing: Links went straight back to the frontier, duplicates included.
Why that's risky: Every page is crawled once and never refreshed, and nothing measures crawl health.
What gets added: A link extractor that parses pages, normalizes links and compares SimHash content fingerprints to skip near-duplicates; a URL filter that checks a seen-URL Bloom filter before adding URLs to the frontier store.
Trade-offs: The Bloom filter's 1% false positives mean a few new URLs are skipped, in exchange for checking billions of URLs in memory.
Keep the crawl fresh, feed the search index, and watch crawl health.
What was missing: Pages were never revisited, nothing was indexed, and the crawl was unobserved.
Why that's risky: Remaining risk is spider traps (infinite generated URLs); per-host URL caps and depth limits contain them.
What gets added: A recrawl scheduler that estimates how often each page changes and schedules its next visit, a search index of crawled text, and monitoring of throughput, errors per host, frontier size and duplicate ratio.
Trade-offs: Fresh pages get crawl budget at the expense of rarely changing ones.
You're in the middle of an interview session. Leaving now will end your current attempt.
Explore concept overviews, real-system examples, key tradeoffs, and interview talking points for each roadmap section.
You've conquered this phase. These are the skills you now own:
