Design a web crawler
A crawler is a breadth first search over a graph with no map. The nodes are servers owned by people who did not ask you to visit. Some of the edges are traps built 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.
Step 1: Understand the problem#
"Crawl the web" is not a requirement. These six answers turn it into one, and two of them are about being a guest on other people's servers rather than about scale.
| You ask | They say | What it settles |
|---|---|---|
| How many pages, and in what time? | A billion pages a month, refreshed continuously. | About 400 fetches a second sustained, which sounds small until you remember it has to be spread politely across millions of hosts. |
| Do we obey robots.txt and per host rate limits? | Always. Getting blocked is worse than being slow. | The frontier design. Politeness is per host, so the queue cannot be a single queue, and this is the answer that forces the whole structure. |
| HTML only, or JavaScript rendered pages too? | HTML for now. | A fetcher stays cheap. Rendering needs a headless browser per page, which is roughly a hundred times the CPU, and it would change the machine count by two orders of magnitude. |
| How fresh do already crawled pages have to be? | News in minutes, most pages in weeks. | Recrawl is a priority problem, not a loop. It also justifies keeping etags and content hashes so an unchanged page costs a 304 rather than a download. |
| What do we do with what we fetch? | Store the raw page and hand it to an indexing pipeline. | The crawler writes to object storage and a queue, and owns nothing downstream. Say this or you will end up designing a search engine by accident. |
| How do we know we have seen a page before? | By URL, and by content, since the same page has many URLs. | Two separate filters. URL dedupe stops the loop, content dedupe stops you storing the same article forty times under forty tracking parameters. |
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.
Back of the envelope#
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.
Step 2: Propose the high level design#
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. |
The whole system on one whiteboard#
Walking Figure 1:
- Seeds and sitemaps prime the frontier. After the first hour they contribute almost nothing, because the crawl feeds itself.
- A fetcher asks for work and gets a URL whose host is due. It never picks its own work, which is what makes politeness possible across 500 machines.
- Before the fetch: robots.txt from a per host cache, and DNS from your own resolver. Both matter more than they look. Uncached DNS at 400 lookups a second will get you throttled by your resolver before the web ever notices you.
- The raw page goes to object storage exactly once, and a pointer goes to the indexing queue. The crawler's job ends there.
- The parser pulls links out.
- Every extracted URL is normalised and checked against the seen filter, and the page body is checked against the near duplicate filter. Whatever survives updates the URL state table with an etag and a crawl time.
- New URLs go back to the frontier and the loop closes.
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.
Step 2 says a fetcher never picks its own work. What goes wrong if all 500 machines just take the next URL off one shared queue?
Step 3: Design deep dive#
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.
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.
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.
Break it#
Read every step as text
- polite · Healthy. One fetch per host per second, robots.txt cached and respected, 400 pages a second across hundreds of thousands of hosts. Nobody notices you, which is the goal.
- no per host limit · Down. Take URLs from one shared queue and 500 fetchers can land on one host together. To that site you are a denial of service attack. You get rate limited, then blocked by IP, then blocked by user agent, and eventually you are in a blocklist other sites subscribe to.
- trap · Down. A calendar with an infinite next month. The frontier fills with millions of URLs from one host that all differ by one parameter and contain nothing. Your crawl is now spending its whole budget generating URLs for itself.
- filter saturated · Degraded. The bloom filter was sized for the URLs you expected. Past that, the false positive rate climbs and you silently start skipping pages you have never crawled. Nothing errors. Size it for the target and monitor the fill ratio.
- bounded · Healthy. Per host scheduling, a depth cap, a per host URL cap, and a filter sized with headroom. The crawl is slower than it theoretically could be, and it can run for years without anyone blocking it or it eating itself.
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 billion pages a month is about 400 fetches a second, spread politely across millions of hosts.
- Politeness is per host. That one fact is why the frontier is many queues rather than one.
- A 64 bit URL hash plus a Bloom filter answers "seen it?" without touching a database.
- A conditional request that returns 304 is the cheapest recrawl there is. Spend your fetch budget on pages that move.
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.