Case study: Web crawler

A search engine must first collect the pages it will search. A program that does this is a crawler. The interviewer says: "Design a web crawler that fetches 100 million pages a day."

A weak answer is one loop: take a URL from a queue, fetch it, add its links to the queue. It has no rule for how fast to visit one site, and it keeps every URL in one big set. A strong answer says that the speed limit is not the machines. The limit is how often one site may be visited. It also says how the crawler skips URLs it has seen, what that check costs, and what happens when sites fail.

At SDE-2 level you should draw the loop and do the numbers. At SDE-3 level you should explain how the crawler picks the next URL, the Bloom filter and the failures.

Imagine that you want a copy of the notices on every notice board in a big city. You go to one board, copy the notice, and write down the addresses of other boards that the notice names. Then you visit those boards. Three rules keep the board owners happy. Do not stand at one board all day. Skip a board that has a sign "do not copy". Never copy the same board twice.

A crawler follows the same rules.

What we build

A URL is a web address (lesson 7). The host is the site name inside it, for example shop.example.in. The crawler starts with a few seed URLs. It fetches a page, saves it, finds the links in it, and adds the new links to a list. The frontier is the list of URLs that are not fetched yet. The crawler only collects pages. Building the search index from them is lesson 80.

The requirements:

1. Fetch 100 million pages a day.
2. Be polite: never overload a site, and follow the site's rules.
3. Do not fetch the same URL twice.
4. A broken or slow site must never stop the crawl.
5. Fetch pages that change often again sooner.

The loop

1. The frontier gives the next URL.
2. The fetcher checks the rules of the host, looks up the host address (lesson 8, kept in a cache), and downloads the page.
3. The fetcher saves the page in object storage (lesson 24). It adds a message "page fetched" to a queue (lesson 58), keyed by host (lesson 59).
4. The parser reads the message, finds the links, and cleans each URL.
5. A check asks: "Have we seen this URL?" A new URL goes into the frontier.

The queue between steps 3 and 4 lets the two parts run at different speeds. Parsing is work for the CPU, and fetching is waiting for the network. The queue may give a message twice. This is harmless, because step 5 skips URLs it has seen.

Politeness

A site can answer only so many requests. If a crawler sends 50 requests a second to a small shop, the shop stops for its real customers. So the crawler needs two sets of rules.

The rules of the site. A site puts a file named robots.txt at its top address. It lists the paths that bots must not fetch. The standard is RFC 9309. A crawler should not keep a copy of the file for more than 24 hours. If the file is missing (a 4xx status), the crawler may fetch everything. If the server fails (a 5xx status), the crawler must assume that nothing is allowed until the file can be read. Some sites also write a Crawl-delay line. It is not part of the standard, and Google does not support it. We use it as a hint.

Our own gap. After each fetch from a host, wait at least max(1 second, 10 x the time of that fetch) before the next one. The factor of 10 is a rule from a well-known textbook. The 1 second is our choice. Open only one connection to a host at a time. If the host answers 429 or 503 (lesson 56, lesson 54), double the gap, and wait for the Retry-After time if it is given. The crawler also sends a User-Agent header with its name and a page where the site owner can complain.

The frontier

The frontier has two jobs: choose which URL is next, and make sure that no host is visited too fast. It has two layers.

• Front queues are for priority. We use 3 queues. A home page, or a page that changed at the last visit, goes to queue 1. Other pages go to queue 2 or 3. This rule is our choice.
• Back queues are for politeness. There is one queue for each host. A table holds the next allowed time of each host. A min-heap is a structure that always gives the smallest value first, so a heap of these times gives the host that is ready first.

A fetcher takes the host with the earliest time. If that time has not come, it waits. It takes one URL from the queue of that host, and fetches it. Then it sets the next time of the host to now + gap. When a host queue is empty, it is filled again from the front queues.

To scale, split the hosts over many frontier machines by a hash of the host (lesson 43). Use the ring of lesson 44, so that a new machine takes only a few hosts. Each host lives on one machine, so that machine alone controls the gap. The URLs are kept on disk, and only the first few URLs of each queue stay in memory.

The frontier never runs empty. The web gives more links than we can fetch. So the frontier has a size limit, and it drops the lowest priority URLs first.

Not fetching twice

First, normalise the URL, so that equal addresses look equal. Make the host lower case. Remove the # part. Remove the default port. Sort the query parameters. Remove tracking parameters such as utm_source.

Then ask "seen?". With billions of URLs, one way is to keep an 8-byte hash of every URL in memory. Another way is a Bloom filter (lesson 46): it answers "definitely not seen" or "maybe seen". It never says "not seen" for a URL that was added. We put every URL that we add to the frontier into the filter.

The answer "maybe" can be wrong for a new URL. The crawler then skips a page that it has never fetched. That page is skipped again every time, because the same URL sets the same bits. For a crawler this loss is acceptable, if it is small. Two more facts from lesson 46 matter. You cannot remove a URL from a filter. The false positive rate grows if you add more URLs than the size was planned for.

Split the filter by the hash of the host, like the frontier. Then each frontier machine checks its own URLs and holds its own part of the filter.

Same page, different URLs. Copy sites show the same text under different URLs. So the crawler also takes a hash of the page text, called a content fingerprint, and keeps it in a table. If it is already there, the page is not stored or parsed again. This finds only exact copies.

Traps. A calendar page may link to "next day" forever. This is a crawler trap. Set limits. Use a maximum URL length and a maximum link depth from the seed. Use a maximum queue size and a maximum number of pages each day for each host.

When fetches fail

• Timeouts (lesson 54). Give a connection 5 seconds to open and a page 20 seconds to arrive. Stop reading a page after 5 MB.
• Retries. A site that is down will not return in milliseconds. Put the URL back in its host queue to try again after 1 hour, then 6 hours, then 24 hours. After 3 failures, mark it dead for a week. A host that fails often gets a longer gap.
• Redirects. Follow at most 5. The new address goes through the clean-up and the "seen?" check like any other URL.

Keeping pages fresh

Each URL has a next fetch time. If a page is the same as at the last visit (same fingerprint), double the wait, up to 30 days. If it changed, halve the wait, down to 1 hour. This rule is our choice. To save the download, the crawler can ask for the page only if it changed. The site answers 304 Not Modified with no body when nothing changed.

A crawler fetches 100 million pages a day.

Assumptions (made up to teach with, not real data):

• An average fetch takes 0.5 seconds. An average page is 100 KB, and is stored compressed at 25 KB.
• A page has 50 links. 20% of the links lead to a URL that we have not seen.
• One fetcher machine keeps 100 connections open, and we plan for 70%: 70.
• The Bloom filter is planned for 10 billion URLs, with 10 bits for each URL and 7 hash functions. The frontier is split over 8 machines.
• The crawl touches 5 million different hosts in a day.
• 5% of the fetches go to hosts that are down.

Step 1: the rate. 100,000,000 / 86,400 = 1,157 pages per second.

Step 2: machines and storage. Fetches in progress = 1,157 x 0.5 seconds = 579. Machines = 579 / 70 = 8.3, so 9. The bandwidth is 1,157 x 100 KB = 115,700 KB per second, about 116 MB per second, which is 926 megabits per second. Over 9 machines that is 103 megabits each. The storage is 100,000,000 x 25 KB = 2,500,000,000 KB = 2.5 TB a day.

Step 3: politeness. The gap is max(1, 10 x 0.5) = 5 seconds. One fetch and one gap take 0.5 + 5 = 5.5 seconds. So one host gives 1 / 5.5 = 0.18 pages per second. For the big site of 20 million pages: 20,000,000 x 5.5 = 110,000,000 seconds, which is 1,273 days, or about 3.5 years. This answers the predict box. More machines do not help. To reach 1,157 pages per second, the crawler needs 1,157 x 5.5 = 6,366 hosts being served at the same moment. So the frontier must always hold thousands of hosts that are ready. For a big site we fetch only the pages with the highest priority.

Step 4: links and the frontier. 100,000,000 x 50 = 5,000,000,000 links a day. That is 5,000,000,000 / 86,400 = 57,870 "seen?" checks per second, and 57,870 / 8 = 7,234 for each machine. New URLs: 20% x 5,000,000,000 = 1,000,000,000 a day. We fetch only 100,000,000 a day, so the frontier grows by 900,000,000 a day. At 80 bytes for a URL, the new URLs are 80 GB a day on disk. The frontier needs a size limit.

Step 5: the filter. 10,000,000,000 x 10 bits = 100,000,000,000 bits = 12.5 GB. That is 1.56 GB on each of 8 machines. A set of 8-byte hashes needs 10,000,000,000 x 8 = 80 GB, which is 6.4 times more. At 10 bits and 7 hashes, the false positive rate is 0.82% (lesson 46). The crawler wrongly skips 0.82% x 1,000,000,000 = 8.2 million new URLs a day. The filter reaches 10 billion URLs after 10 days (1,000,000,000 a day). Suppose the same filter held 20 billion URLs. The rate would be (1 - e to the power of -1.4) to the power of 7 = 13.8%. So build a bigger filter before it fills.

Step 6: robots.txt. 5,000,000 hosts / 86,400 = 58 fetches of robots.txt per second, with a 24-hour cache. That is 58 / 1,157 = 5% of the page rate.

Step 7: dead hosts. 5% of the fetches wait for the full timeout. Suppose we used one 20-second timeout for everything. The average fetch takes 0.95 x 0.5 + 0.05 x 20 = 1.475 seconds. In progress: 1,157 x 1.475 = 1,707, which needs 1,707 / 70 = 24.4, so 25 machines. With our 5-second limit to open a connection, the average is 0.95 x 0.5 + 0.05 x 5 = 0.725 seconds. In progress: 1,157 x 0.725 = 839, which needs 12 machines. Marking a host dead after 3 failures cuts this more.

• A queue for each host, with a gap, solves the overload of sites and keeps site owners from blocking the crawler. It costs speed for each site (0.18 pages per second) and a frontier that is harder to build. It needs thousands of hosts in parallel. I would raise the gap for one host only when its owner agrees.
• A Bloom filter solves memory: 12.5 GB against 80 GB. It costs 0.82% of new URLs skipped for good, no removal, and a size that must be planned. I would use an exact table when each URL matters, for example for home pages.
• A queue between fetch and parse solves different speeds. It costs a delay, and messages that can repeat. I would keep it, because the parser is safe to repeat.
• Long timeouts solve nothing for a crawler. They cost machines: 25 against 12. I would keep timeouts short and slow down a failing host.

"More fetcher machines make a crawl faster." The limit is the gap for each host. The big site needed 3.5 years however many machines we had. Only more hosts at the same time help.

"A Bloom filter that says 'seen' is always right." It says "maybe seen". At 10 billion URLs it wrongly skipped 8.2 million new URLs a day, and the same URLs stay skipped.

"If robots.txt gives an error, I can fetch the whole site." Only for a 4xx status. For a 5xx status the standard says to assume that nothing is allowed. Also, robots.txt is a request to good crawlers. It is not a lock.

1. Why does the frontier have one queue for each host? What does a Bloom filter answer?
2. A crawler fetches 50,000,000 pages a day. A fetch takes 0.4 seconds, and the gap is max(1 second, 10 x the fetch time). (a) How many pages per second? (b) How many hosts must be served at the same moment? (c) How much memory does a Bloom filter need for 2,000,000,000 URLs at 10 bits each?
3. After a week, one host has 300 million URLs in its queue, all like /calendar/2031/05/12. Its real pages are about 50,000. What is this? Why does the gap not stop it? What do you change?