Design a web crawler

Why did a partner’s website go down on Sunday night?

The delivery service now works with 2,000 partner kitchens. Most of them keep their menus on small websites of their own, and a few list them on one big city food directory. Customers want to search every partner’s dishes inside the app.

One Saturday somebody wrote a crawler: start from the list of partner sites, download each page, follow its links, save everything. Fifty threads, so it would finish quickly. It was started before dinner.

On Monday morning a partner cook phoned. She runs her kitchen’s website on the cheapest hosting plan she could find, and it had been down all Sunday evening. Her hosting company said one visitor made forty requests a second for an hour. It called itself DabbaBot.

The crawler’s logs explain it. Her site has twelve pages. The crawler had fetched them more than four thousand times, under addresses that differed only in a tracking tag or a sort order. Another site had a calendar with a “next month” link, and the crawler had followed it into the year 2400. The big directory had blocked the crawler’s IP address after an hour.

Do the sum before reading on. Two thousand kitchens with about 40 pages each is 80,000 pages. The crawler stored three million, and still had no menu from the directory. Ten more machines would crawl faster, and faster is what knocked the cook’s site over.

No partner objects to the crawler reading its menu. What they object to is forty requests a second. How can a crawler visit two thousand sites every day without overloading any of them?

That is the web crawler, a design every search engine and price comparison site depends on. The fetching is the easy part. The hard parts are deciding what to fetch next, never fetching the same thing twice, never getting lost in pages that generate endless new addresses, and sending requests gently enough that no site minds them.

Pause and predict Twelve pages were fetched more than four thousand times. What would have stopped most of that?

What must never go wrong?

The crawler is its own system. The partner team gives it seed sites; kitchen owners publish menus; the ordering platform reads the menus it extracts.

Two rules come first. No partner’s site should ever slow down because of the crawler. And a price shown in the app must come from a page fetched recently, and the app must show when it was fetched.

Core entities, in two minutes

A Site (one host, its robots.txt rules and its politeness state), the URLs on it (each normalised, with when it was last fetched and when it is next due), the Page content itself (stored once per distinct content), and the Menu extracted from a page for one kitchen.

The estimate that changes the design

One page a second is nothing: one small machine fetches that. The estimate removes one worry and adds another. Throughput will never be the problem here. Time per site is. At ten times today’s partners, the directory alone needs 36.7 hours of polite fetching, more than a day, so “refresh every page every day” cannot work by fetching harder. The design must fetch only what changed: conditional requests, sitemaps that list when pages changed, and a schedule per page. That is a requirement the estimate created.

The obvious version, and how it breaks

The weekend crawler is the version in every tutorial: a queue of URLs, a set of URLs already seen, and threads that take the next URL, download it, and add the links they find.

Pause and predict Pages link mostly within their own site, so twelve pages of one small site reach the head of the queue in a row. Fifty threads are free. How many requests reach that site at once?

• It overloaded sites. Pages link mostly within their own site, so links arrive in runs: twelve pages of one site in a row at the head of the queue. Fifty threads took them all at once. Nothing in the design knows what a site is.
• It could not tell two addresses of one page apart. /menu?utm_source=wa and /menu?sort=price were new URLs to the seen set, so the same twelve pages were fetched thousands of times.
• It got lost. The calendar trap generates a new URL on every page, forever. A crawler with no limits follows it until it runs out of disk.
• It forgot everything on restart. The queue and the seen set lived in one process’s memory, and a crash on Sunday night started the crawl again from the seeds.

And one failure that is not a bug: pages were stored in PostgreSQL as text. Three million bodies is a job for object storage (lesson 1.3), with only their addresses in the database.

A mental model

URL frontier

The crawler’s to-do list: every URL discovered but not yet fetched, and the rules for which one goes next.

For example: One queue per site and a heap of times: “cook.example ready at 12:04:07, directory ready at 12:04:05”. A free fetcher takes the directory.

Seen this way, a crawler is a scheduler more than a downloader. Its quality is decided by what it fetches next and what it refuses to fetch. Underneath, the web is a graph: pages are nodes, links are edges, and a crawl is a traversal from the seeds much like breadth-first search, with a seen set so no node is visited twice.

A fixed wait, or one that adapts?

How long should the crawler wait between two requests to the same site? Two goals compete: one rule for everyone that is easy to promise, or a wait that follows each site’s health.

A fixed wait is honest and easy to promise, and many crawlers start there. But it treats a struggling shared host and the directory’s large servers the same, when politeness means going easier on the site that is struggling. The ten-times rule of thumb is the one Manning, Raghavan and Schütze describe; the floor and the cap keep the promise that no partner feels the crawler.

What to remember

1. A crawler is a scheduler: its quality is decided by what it fetches next and what it refuses to fetch.
2. Politeness needs structure: a queue per site and a heap of ready times, so no site gets two fetches at once and no fetcher waits behind one busy site.
3. With politeness, speed comes from how many sites have work, and the biggest site sets the finishing time. Fetch less from big sites, with conditional requests and sitemaps.
4. Normalise URLs before the seen test, hash content to catch the rest, and cap every site with a budget so traps cost little.
5. Obey robots.txt (cache it at most 24 hours; a 5xx means disallow everything), identify yourself, and back off a site that slows down.

One request in flight per site, a wait that follows the site’s response time, and fetch only what changed.

In the real world

Real crawlers add what this toy leaves out. Search engines keep frontiers of billions of URLs on disk, rank them by importance and by how often each page has changed before, render JavaScript for sites that need it in a separate, slower pipeline, and detect near-duplicate pages as well as exact copies. Mercator found DNS lookups were 87% of each thread’s elapsed time until it built its own resolver, which brought it to 25%: the bottleneck is often not where you look.

The partner crawler is far smaller. The same frontier, the same seen tests and the same manners serve two thousand sites or two billion; the estimate decides how many machines, and politeness decides how fast.