Design a web crawler
A crawler is a breadth first search over a graph with no map, where the nodes are servers owned by people who did not ask you to visit, some of the edges are traps designed to keep you walking forever, and the graph is larger than your storage.
It is also the design question most likely to reveal whether someone thinks about being a good citizen on shared infrastructure, which is why interviewers like it.
You have 500 crawler machines and a queue of URLs. What goes wrong if each machine simply takes the next URL and fetches it?
What you are building
- Fetch pages starting from a seed list and follow links. Breadth first, so shallow pages are found before deep ones.
- Never overload a single site. Politeness is a hard requirement, not an optimisation.
- Avoid fetching the same content twice. Both the same URL and the same content under different URLs.
- Recrawl pages as they change. A crawl that runs once is a snapshot, not a crawler.
- One billion pages a month.
- Respect robots.txt and a per host rate limit at all times.
- Survive a machine dying without losing or re-fetching its work.
- Storage grows for years, so the design has to assume it never all fits in memory.
- Ranking and the search index. This produces the raw pages, and building the inverted index is its own question.
- JavaScript rendering. Worth one sentence: a headless browser is roughly two orders of magnitude more expensive per page, so it runs as a separate tier for a small subset of URLs.
- Parsing quality, boilerplate removal and language detection.
The numbers
Politeness caps you at 1 fetch per second per host, so hitting 386 pages a second means having roughly 386 different hosts in flight simultaneously. That is why the frontier is organised by host rather than as one big queue: the constraint is per host, so the data structure has to be per host too.
That last line is the whole insight. Everyone starts by imagining one queue of URLs. The politeness rule makes that structure wrong before you write any code.
The design
The loop is the design: fetch, store, extract, filter, enqueue. Everything hard lives in two of those boxes, the frontier and the seen filter, and the rest is plumbing.
Deep dive one: the frontier
Two properties have to hold at once, and they pull against each other. Politeness says never fetch from one host too quickly. Priority says important pages should be crawled sooner. A single queue gives you neither.
The frontier does not fit in memory. A billion URLs at a couple of hundred bytes is hundreds of gigabytes, so host queues live on disk with only the heads cached, which is a normal and boring thing to say out loud.
robots.txt can specify a crawl delay, and it must be fetched and cached per host before
anything else on that host. Sites also vary enormously in what they can take: a large
site may be fine with ten requests a second while a small one on shared hosting is hurt
by one. Adapting the rate from observed response times and error rates is what separates
a crawler people tolerate from one that gets blocked.
Deep dive two: not fetching the same thing twice
There are two different duplicate problems and they need different tools.
The same URL. A billion URLs is far too many to keep in a set in memory. Hash each URL to 64 bits and keep it in a bloom filter, which answers “definitely new” or “probably seen” in constant space. False positives mean occasionally skipping a page you have not crawled, which for a crawler is an acceptable loss. False negatives do not happen, which is the property that matters.
The same content under different URLs. Session ids in query strings, print versions, trailing slashes, and the same article on five country domains. URL normalisation catches the mechanical cases: lowercase the host, drop the fragment, sort query parameters, strip known tracking parameters. For genuinely duplicated content, hash the document with a similarity preserving hash such as simhash, so near duplicates collide and not just exact ones.
Crawler traps. An infinite calendar that always has a next month. A faceted search with every filter combination as a URL. These are not malicious, just infinite. Cap depth, cap URLs per host, and watch for hosts producing large numbers of near identical pages.
Deep dive three: sharding the work
Partition the frontier by host, not by URL. This falls out of politeness: all URLs for one host must be handled by one worker, or two workers will hit that host simultaneously and no rate limiter will save you.
Switch to the last one and note that it has the best numbers. That is the point: the metric you would naturally optimise says the wrong design is better.
The data model
| url_hash | bigint | PK | 64 bit hash of the normalised URL. Storing the URL itself as the key wastes a lot at this scale. |
| host | varchar(255) | IDX | Partition key. Everything for one host lives together because one worker owns it. |
| last_crawled | timestamp | Drives recrawl scheduling. | |
| content_hash | bigint | Simhash of the last body. If it has not changed, back off and recrawl less often. | |
| etag | varchar(128) | Sent back as If-None-Match. A 304 costs almost nothing and is the cheapest recrawl there is. | |
| fail_count | int | Consecutive failures. Past a threshold, stop trying and stop wasting fetches. |
Break it
Trade-offs
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| Frontier partitioned by host | Politeness is structural, since only one worker can ever fetch a given host. | A very large site becomes a slow partition that more workers cannot speed up. | Always. Any other partitioning makes politeness a race you will eventually lose. |
| Bloom filter for seen URLs | A billion URLs in a couple of gigabytes with constant time checks. | False positives silently skip pages, and it fills up, at which point the rate climbs quietly. | Any set too large for memory where missing a small fraction is acceptable. |
| Conditional requests with etags | Recrawling an unchanged page costs a 304 rather than a full body. | Storing an etag and last modified per URL, and trusting servers to implement them properly. | Any recrawl strategy. This is where most of the saving on a mature crawl comes from. |
| Skipping JavaScript rendering | Two orders of magnitude cheaper per page, so vastly more coverage for the same budget. | Sites that render entirely on the client look empty. | The default, with a separate rendering tier for a curated subset of URLs. |
Interview replay
Checkpoint
1. Why partition the frontier by host rather than by URL, when partitioning by URL balances better?
2. Your bloom filter reports a URL as seen when it has never been crawled. What is the consequence?
3. A site returns a 304 Not Modified for most of your recrawls. Is that a problem?
A crawler is a breadth first traversal where the binding constraint is politeness, so the frontier is not one queue, it is a queue per host with one owner each and a schedule holding the earliest time each host may next be contacted. That structure makes it impossible for two workers to hit a host at once, which a shared queue plus a rate limiter cannot guarantee. Deduplication is two problems: the same URL, handled by normalising and then a bloom filter over the hash, where false positives just mean occasionally skipping a page, and the same content under different URLs, handled by a similarity preserving hash of the body. I would cap depth and URLs per host to survive infinite calendars and faceted search, which are not malicious, just endless. Recrawl is driven by observed change using etags and content hashes, backing off pages that never move, because change rates on the web span orders of magnitude and any fixed interval is wrong for nearly every page.
