System design interview question

Design a web crawler

Every search engine starts with one: “design a web crawler” asks you to download a meaningful part of the web, keep it fresh, never hammer anyone's site, and survive machines dying mid-crawl. It is a question about work lists, parallelism and politeness at scale. Here is how to walk into it, and then how to practise it until the answer is yours.

Practise Web Crawler

Multiple choicePick the design from four
Fill the gapsFill the gaps in one drawn for you
Build from scratchBuild it on a blank canvas

Practise it on a canvas

Free with an account.

The question, as an interviewer would set it

A search company needs to download a billion web pages a month and keep them fresh, starting from a list of known sites and following the links it finds. The same page is often reachable through many different links, and fetching it twice wastes a great deal of work. Sites must be treated politely: never more than one request every few seconds to the same site, or the crawler gets blocked. Fetching is slow and unpredictable, since some sites answer in milliseconds and others time out, so hundreds of machines work in parallel, and a machine that crashes must not lose the pages it was about to fetch. The downloaded pages are large and kept for later processing.

What it is really testing

Every phrase that matters in the brief is a requirement in disguise. Spot them before you draw a single box.

“fetching it twice wastes a great deal of work”
A record of every address already seen, checked before queuing.
“never more than one request every few seconds to the same site”
A per-site limit checked before every fetch.
“hundreds of machines work in parallel”
A fleet of fetchers taking work from one shared list.
“a machine that crashes must not lose the pages it was about to fetch”
A list that keeps each address until a fetcher confirms it.
“The downloaded pages are large and kept for later processing”

Back of the envelope

Pages: 1 billion a month → ~400 a secondAn assumption to say out loud. If the interviewer has a number in mind, they will give it to you.
Page size: ~500 KB each → ~500 TB a monthKept for processing later, so storage has to be cheap.
Addresses seen: ~10 billion discovered × ~100 bytes → ~1 TBJust the record of what has been seen, checked before every new link is added.
Politeness: One request per site every 5 seconds → a site of 1 million pages takes ~2 monthsSo the crawl must spread across thousands of sites at once, and never go faster on any one of them.

Questions to ask first

How many pages, how often, and how fresh must they stay?
HTML only, or images, PDFs and other files too?
Must the crawler obey robots.txt and each site's crawl-delay?
Where does the crawl start, and does it follow links to any site?
What happens to pages after download — is indexing in scope?

The trade-offs you will be pushed on

1.How do hundreds of machines share one list of addresses without two fetching the same page?
2.A machine crashes halfway through its share. What happens to the addresses it had taken?
3.How do you keep to one request every few seconds per site and still keep every machine busy?
4.

Now answer it

The same design always gets the same score, with the reason behind every requirement — then defend it against the trade-offs above.