Web crawling

A recipe search engine crawls 40,000 cooking sites, from large publishers to one-person baking blogs on shared hosting. It knows about 200 million URLs and wants every page refreshed within a week. The core is the same loop every crawler runs:

Run naively, the loop goes wrong in predictable ways. Relative links mean a page's links mostly point to the same host, so a simple first-in, first-out queue sends bursts of requests to one server. The same page is reachable under many URLs. Some sites generate pages without end. And once everything has been fetched, it starts going stale:

Before fetching anything from a host, a crawler reads its robots.txt, a file of allow and disallow rules per crawler, standardized as RFC 9309. The rules that matter in practice:

• The most specific rule wins: the matching rule with the longest path; on a tie, allow beats disallow.
• A 4xx response (no file) means everything may be crawled.
• A 5xx response or a network error means nothing may be crawled until it is fixed.
• Cache it for at most 24 hours, and parse at least the first 500 KiB.
• It isn't access control: anyone can ignore it, so it can't protect private pages.

Then the crawler limits its own pace for each host. A crawl that only kept one request at a time per server still drew complaints, because pages arrived back to back with no pause. The Mercator crawler waited 10 times as long as the last download took before contacting the same host again; the Heritrix crawler has the same setting as a multiple of the last fetch time, with a minimum and maximum:

Server errors are a signal, not just a failure. Google lowers its crawl rate for a site that returns 5xx errors or 429 (too many requests), in proportion to how many URLs fail, and raises it again gradually once the site responds normally. The Crawl-delay line some robots.txt files contain isn't part of the standard, and Google ignores it.

Politeness reshapes the frontier. Mercator's design splits it in two. A front end holds URLs in a few queues by priority. A back end keeps many first-in, first-out queues, each holding URLs of a single host, and a heap of those queues ordered by the time each host may next be contacted. A fetching thread takes the queue at the top of the heap, waits if its time hasn't come, fetches one URL, and puts the queue back with its next allowed time.

The arithmetic shows why there must be far more host queues than threads:

The total rate is easy; one host is the limit. A publisher with 500,000 recipe pages needs 500,000 × 3.3 s ≈ 19 days at that pace, so its pages can't all be refreshed weekly, and the crawler has to choose which ones to fetch. Mercator ran three times as many host queues as threads to keep every thread busy, and kept most of each queue on disk, because a large frontier outgrows any machine's memory.

Priorities decide what gets fetched first. A site's crawl demand is driven by popularity, staleness, and how many of the site's known URLs are worth fetching at all. Sites can help with a sitemap, a file listing their URLs, at most 50,000 URLs or 50 MB per file; Google uses a page's last-modified date from it only when the dates prove accurate, and ignores the priority and change-frequency fields.

A link is checked against everything already seen before it enters the frontier. First it is normalized, so that equivalent spellings compare equal. The URL standard (RFC 3986) lists safe rules: lowercase the scheme and host, drop a default port such as :80, turn an empty path into /, decode needlessly percent-encoded characters, and resolve . and .. segments. The #fragment part is dropped too, because it is never sent to the server. A site's own redirects and rel="canonical" links point to its preferred URL for duplicates.

Then comes the seen test, which must be fast for hundreds of millions of URLs. Mercator stored an 8-byte fingerprint of each URL instead of the URL itself. A Bloom filter (Bloom filters) is smaller still: Heritrix's default holds 125 million URLs in about 495 MB with a false-positive chance of 1 in 4 million. The recipe engine has discovered about 500 million distinct URLs over time, of which 200 million are worth fetching, and the seen set must hold all of them:

A Bloom filter's error is one-sided, and for a crawler that decides which way it fails. It never says "new" for a URL already seen, so nothing is fetched twice because of it. It sometimes says "seen" for a URL that is new, and that page is silently never crawled. At 1 in 100, that is 1 page in every 100 new URLs; at 1 in 4 million, a few hundred out of a billion.

Different URLs often return the same page: print versions, tracking parameters, mirrored sites. Mercator ran a content-seen test after each download, comparing a fingerprint of the content with those already stored, and stopped processing exact copies. Many more pages are near-duplicates, the same recipe with a different ad or timestamp. Simhash, a 64-bit fingerprint in which similar pages differ in only a few bits, catches them: treating pages within 3 differing bits as duplicates works at the scale of 8 billion pages.

A near-duplicate's outgoing links are probably near-duplicates too, so the crawler can skip them as well. That matters most for crawler traps: sites whose URLs never run out. A recipe site's filters (cuisine, diet, time, sort order) combine into more URLs than the site has recipes, and calendars or scripts that link to "next" forever do the same. Filter-based navigation can generate infinite URL spaces and lead crawlers to fetch huge numbers of useless pages.

The third row comes from a research crawler that fetched 6.3 billion pages from a single server in 41 days. Spam sites can create unlimited pages and subdomains, but not unlimited links from other domains, so it gave each domain a page budget in proportion to those links.

A crawl is never finished: the recipe engine's index is only as fresh as its last visit to each page. Pages change at very different rates. A site's home page and its newest recipes change daily; a recipe from 2014 may never change again. Staleness and popularity drive how often a page is recrawled, and Mercator's prioritizer used each URL's download history, such as whether it had changed since the last fetch.

A recrawl of an unchanged page can cost the site almost nothing. The crawler sends back the page's last ETag or Last-Modified value, and if nothing changed the server answers 304 Not Modified with no body:

Google's crawlers support both headers; ETag is the less error-prone of the two. Few sites make use of it: only about 0.017% of Google's fetches could be served from cache, down from 0.026% ten years earlier. So the crawler should also learn from what it sees: a page that came back unchanged several times in a row can wait longer before the next visit.

When one machine isn't enough, split the crawl by host. In Mercator's distributed version each process owned a set of host names, and its frontier, seen set and DNS cache held only those hosts; a link to another process's host was sent there in batches. Because about 80% of links are relative, most links never left the process that found them, and per-host politeness stays in one place (Consistent hashing keeps the assignment stable as machines join).

DNS deserves its own attention. In Mercator, resolving host names took 70% of each thread's time, because the system resolver handled one uncached lookup at a time; a resolver that sent many queries in parallel to a local name server cut that to 14%. The checklist for the recipe engine: