Design a web crawler

In 2 minutes

I would build the crawler around a URL frontier. Seeds go into the frontier, which keeps priority queues in front and one queue per host behind, with a heap of when each host may next be hit. That gives importance ordering and politeness at once. Each host is owned by one fetcher machine, chosen by hashing its name, so the delay is a local timer. Before it first visits a host, a fetcher reads and caches that host's robots.txt. At about 400 pages a second, with half a second per fetch, roughly 200 fetches are in flight at any time, so a few dozen machines are enough. Pages go to a parser that stores the content with a text fingerprint and extracts links. Links are normalised and checked against a Bloom filter, which holds 10 billion URLs in about 12 GB with a 1 percent false positive rate. Only new URLs go back to the frontier. Traps are handled with URL length, depth and per-host budgets. Revisit intervals double when a page is unchanged and halve when it changes, using conditional requests to save bandwidth. In-flight URLs have timeouts, so crashes lose nothing.

The question

Clarifying questions

• What is the crawl for: a search index, a price tracker, or a one-off archive? The purpose sets which pages matter, how often to revisit them, and what to keep from each page.
• How many pages a month, and what is the average page size? Together they give the fetch rate, the bandwidth and the storage, which size the whole fleet.
• Do we need to run JavaScript to see a page, or is the HTML enough? Rendering in a browser is many times more expensive than plain download, so it can only be used on a few pages.
• How fresh must pages be? News needs revisits every few minutes. Most pages change rarely, so one schedule for everything wastes work.
• Do we follow robots.txt and any crawl-delay hints? A well-behaved crawler must, and that rule changes the shape of the queue: it becomes one queue per site.

Requirements

Functional

• Start from seed URLs, download pages and extract the links they contain.
• Follow each site's robots.txt rules and never overload a single site.
• Skip pages already seen, including duplicates under different URLs.
• Revisit pages on a schedule, more often when they change more often.

Non-functional

• Throughput: about 400 pages a second sustained, which is 1 billion pages a month.
• Politeness: at most 1 request a second to any one host unless it allows more.
• Fault tolerance: a crashed fetcher loses at most the URLs it was fetching, and they are retried.
• Extensible: new content types or a new parser can be added without touching the fetcher.

Back-of-the-envelope estimates

Assumptions for this exercise:

• These numbers are assumptions for the exercise, not facts about any real crawler.
• 1 billion pages a month, an average of 100 KB of HTML each, and a fetch takes 0.5 seconds including DNS.
• The crawler knows about 10 billion distinct URLs. Pages are stored compressed at about 4 to 1.
• Politeness allows one request a second to each host.

The arithmetic:

• Pages per second: 1B ÷ (30 days × 86,400 s = 2.59M s) ≈ 386 → ≈ 390/s, or about 39 MB/s of downloads (≈ 310 Mbit/s)
• Fetches in flight: 390 pages/s × 0.5 s per fetch (rate × time) → ≈ 200 at any moment, so a few dozen machines
• Storage per month: 1B × 100 KB = 100 TB raw ÷ 4 for compression → ≈ 25 TB a month
• Seen-URL memory: Bloom filter at 1% false positives needs about 9.6 bits per URL: 10B × 9.6 bits = 96 Gbit. An exact set of 8-byte hashes: 10B × 8 bytes → 12 GB against 80 GB
• One very large site: 10M pages ÷ 1 request a second = 10M s ÷ 86,400 → ≈ 116 days, so big sites must be spread over time and prioritised

High-level design

Crawling is a loop. The Seed list gives the first URLs to the URL frontier, a set of queues that decides which URL is fetched next. The frontier keeps one queue per host, so it can enforce a delay between two requests to the same site.

A Fetcher takes a URL when its host is due, checks the cached robots.txt rules, and downloads the page from the Web servers. It hands the page to the Parser, which saves the content and a fingerprint in the Content store and extracts the links.

Links go through the URL filter. It normalises each URL and asks the Seen set, a Bloom filter, whether the URL is already known. New URLs go to the New-URL queue, which a scheduler feeds back into the frontier. That feedback arrow is the loop, and it is the part not drawn.

How a request flows

Crawl one page

1. A fetcher takes the next URL whose host has waited long enough since the last request to it.
2. It checks the cached robots.txt rules for that host and goes on only if the path is allowed.
3. It downloads the page, with a time limit so one slow site cannot hold a fetcher.
4. The site returns the HTML, or an error that the fetcher will retry later with a longer delay.
5. The fetcher passes the page to the parser.
6. The parser stores the page and a fingerprint of its text, so duplicate content can be spotted.
7. It also extracts the links and sends them to the URL filter.
8. Links that survive the filter are queued as new URLs for the frontier.

Filter new links

1. A page with 200 links arrives at the URL filter from the parser.
2. The filter normalises each URL, then asks the Bloom filter whether it was seen before.
3. The answer is either probably seen, or definitely new. The filter drops the first kind.
4. Definitely new URLs go to the queue. A scheduler files each one in its host's queue in the frontier.

Start a crawl

1. An operator adds seed URLs, and the frontier files each one in the queue for its host.
2. A fetcher takes a URL once the host's politeness delay has passed.
3. The robots.txt cache has nothing for this new host yet.
4. So the fetcher first requests the site's robots.txt file and reads the rules.
5. It stores the rules in the cache for about a day, then fetches the real page.

Deep dive: the URL frontier and politeness

A plain first-in, first-out queue would be a disaster. A big site contributes thousands of links in a row, and the crawler would hit it with thousands of requests at once. The frontier needs two ideas: importance and politeness.

Importance. A set of front queues holds URLs by priority. Priority can come from how many pages link to a URL, how often it changes, or the quality of the site. A selector picks from the high-priority queues more often than from the low ones.

Politeness. Behind them sit back queues, one for each host. A small heap orders hosts by the time they are next allowed a request. A fetcher takes the host that is due first, pops one URL, and sets that host's next due time to now plus a delay. One second is a good default. A better delay scales with how slowly the site answers, for example ten times the last response time, so a struggling server gets a rest.

Give each host to exactly one fetcher machine, chosen by hashing the host name. Then politeness is a local rule on that machine and needs no shared counter.

robots.txt. Before the first request to a host, fetch its robots.txt file and cache the parsed rules for about a day. Skip any path it disallows. If the file is missing (a 404), the site has set no limits. If the server errors (a 5xx), be careful and pause the host, not crawl it freely.

The frontier is too large for memory, since it holds billions of URLs. Keep it on disk, with small in-memory buffers at the head of each queue. Mark each handed-out URL as in flight with a timeout, so if a fetcher crashes the URL goes back in the queue.

Deep dive: dedupe: URLs and content

Duplicates come in two kinds: the same URL written in different ways, and different URLs with the same content.

Normalise first. Lowercase the scheme and host, drop the default port, resolve '..' segments, remove the fragment after '#', sort query parameters, and apply one rule for a trailing slash. Strip parameters that only track visitors, but be careful, because some parameters really change the page.

Remember what was seen. Storing every URL exactly is costly: our estimate says 80 GB for 10 billion 8-byte hashes. A Bloom filter is a long array of bits plus a few hash functions. To add a URL, set the bits its hashes point to. To check one, see if all of them are set. It never forgets a URL it has seen. It sometimes wrongly says 'seen' for a new one, about 1 time in 100 at 9.6 bits per URL, which takes 12 GB in all. Losing 1 percent of new links is fine, because most pages are linked from several places.

A Bloom filter cannot delete. Rebuild it periodically from the URL list, or keep a separate record of crawl state per URL for scheduling.

Same content, different URLs. Mirrors, print views and session IDs in URLs create pages that are the same. Hash the main text of each page after stripping scripts and menus. An equal hash means an exact copy. For near copies, use a similarity fingerprint such as SimHash, where similar texts get fingerprints that differ in only a few bits. Do not index a duplicate, and count duplicates per host, because a host full of them may be a trap.

Deep dive: traps and re-crawl scheduling

A spider trap is a set of pages that never ends. An online calendar links to the next month forever. A link adds a session ID, so every visit shows a new URL. A relative link bug builds paths like /a/a/a/a. Defences are blunt but effective:

• A maximum URL length, for example 2,000 characters, and a maximum path depth.
• A page budget for each host per day, so no single site can consume the crawl.
• A limit on how many query parameters one URL may have.
• A duplicate-content alarm. If most pages from a host are copies, lower its priority.
• Detection of repeated path segments in a URL.

Re-crawling. Pages change at very different speeds. A news front page changes by the minute, and a contact page may not change for years. Use an adaptive schedule per URL. If the page changed since the last visit, halve the interval. If not, double it, within bounds such as one hour to ninety days. Priority also depends on importance, so busy pages are checked more often.

Make revisits cheap with a conditional request. Send the ETag or the last-modified date from the last visit. If the page has not changed, the server replies 304 Not Modified with no body, which saves bandwidth for both sides.

Handle failures with care. Retry temporary errors with growing delays. After several failures, mark the URL dead and check it again rarely. A permanent redirect (301) means the URL should be replaced by the new one. A page that disappears (404 or 410) is removed from the index after a second confirmation.

Trade-offs

• Remembering seen URLs: A Bloom filter over An exact set of URL hashes. It needs 12 GB rather than 80 GB. The cost is that about 1 in 100 new URLs is skipped by mistake, and entries cannot be removed.
• Frontier shape: Priority queues in front, one queue per host behind over A single FIFO queue. Important pages go first and no host gets hammered. The cost is a more complex structure that must live mostly on disk.
• Who talks to a host: One fetcher machine per host, by hashing the name over Any fetcher may take any URL. Politeness becomes a local timer. The cost is uneven load when one host is huge, and a fetcher failure pauses its hosts until they are reassigned.
• Revisit schedule: Adaptive interval per URL over Re-crawl everything every month. Fast-changing pages stay fresh and static ones cost almost nothing. The cost is a change history to store for each URL.

Common follow-up questions

How would you crawl pages that need JavaScript?
Run a separate pool that renders pages in a headless browser. It is many times slower and costlier than a plain download, so use it only for pages whose plain HTML has almost no text. Everything else stays on the cheap path.

What happens when a fetcher crashes in the middle of a crawl?
Each URL handed to a fetcher is marked in flight with a timeout. If no result arrives in time, the frontier puts the URL back in its queue. Because storing a page and queueing its links are idempotent, a repeat does no harm.

How do you behave as a good citizen on the web?
Identify the crawler with a clear user agent and a contact page. Obey robots.txt, back off on 429 and 503 replies, and keep delays proportional to how slow the site is. Provide a way for site owners to ask you to slow down or stop.

How would you scale the crawler by ten times?
Add fetcher shards and spread hosts across them by hash. Watch for DNS lookups, which become a bottleneck, and run a caching resolver. Keep the frontier sharded by host as well, so each shard stays small enough to manage.