Crawler Architecture

The crawl loop is short: take a URL, fetch it, extract links, add them to the list. A crawler that must run for months, fetch hundreds of pages a second, and stay polite to every host divides that loop into modules, each solving one problem. This article follows the architecture in Manning, Raghavan, and Schütze (2008, §20.2), which is based on the Mercator crawler (Heydon and Najork, 1999; Najork and Heydon, 2002), and then shows the same steps in a small crawl of this site. Olston and Najork (2010) survey the field more broadly.

The modules

A URL passes through these stages:

1. URL frontier. Holds the URLs waiting to be fetched and decides which comes next.
2. DNS resolution. Converts the URL's host name to an IP address.
3. Fetch. Downloads the page with HTTP.
4. Parse. Extracts the text and the links.
5. Content seen? Checks whether this content has already been fetched under another URL.
6. URL filter. Applies robots.txt and other rules to each extracted link.
7. Duplicate URL elimination. Drops links already in the frontier or already fetched.

Links that survive enter the frontier, and the cycle repeats. Many threads run it at once, so that while one waits on a slow server, others are fetching.

The three tests run at different rates. The content test runs once per page, while the URL filter and duplicate elimination run once per link, and a page has dozens of links. In the crawl of this site described below, more than nine in ten links were to URLs already seen, so duplicate elimination discards most links and only a small fraction ever reach the frontier.

One link, followed through the modules

Suppose the crawler fetches http://Example.COM:80/a/b.html and the parser finds the link ../c.html#sec2 in it.

1. Normalization. Resolved against the page, the link becomes http://Example.COM:80/c.html#sec2. Lowercasing the host, dropping the default port and dropping the fragment give http://example.com/c.html, as the first row of the table under URL normalization below shows.
2. URL filter. The crawler looks up example.com in its robots.txt cache. If the cached rules disallow /c.html, the link is dropped here.
3. Duplicate URL elimination. The crawler computes a fingerprint of the normalized URL and looks it up in the set of URLs seen. If another page linked to the same URL earlier, the link is dropped.
4. Frontier. Otherwise the URL is added to the seen set and to the frontier, with a priority.
5. Later, at fetch time. When the frontier releases the URL, the crawler resolves example.com (probably from its DNS cache, since it fetched from that host recently), checks robots.txt again, and fetches the page. If the page's content fingerprint matches one already stored, the page is not indexed and its links are not followed.

DNS resolution

Every new host requires a DNS lookup, which can take a second or more, and the standard lookup functions in many libraries block the thread that calls them. At hundreds of fetches a second, DNS becomes a bottleneck. Large crawlers run their own asynchronous resolvers and keep a cache of recent results, since links in a page usually point to hosts seen recently (Manning, Raghavan, and Schütze, 2008, §20.2.2).

Fetching and parsing

The fetcher sends an HTTP request and handles what comes back: redirects, errors, timeouts, and responses of the wrong type. It should check the Content-Type header, and the size, before reading a whole response. The parser then extracts the text for the indexer and the targets of the page's links. HTML found on the web is often malformed, so parsers must be forgiving.

Content seen?

Much of the web is copied. If a page's content has been fetched before under another URL, there is no point indexing it again or following its links. The crawler computes a fingerprint of each page's content, such as a 64-bit hash, and checks it against those of pages already fetched. Exact fingerprints catch only identical copies. Near-duplicate detection covers shingling, which also catches copies that differ slightly.

URL normalization

Before a link can be checked for duplicates, it must be reduced to a canonical form, since many strings name the same page. The safe steps, which follow from the URL standard, are:

• resolve relative links against the URL of the page they appear on;
• lowercase the scheme and host, which are case-insensitive;
• remove the port when it is the default for the scheme (80 for http, 443 for https);
• remove the fragment, which is never sent to the server;
• give an empty path the value /.

Further steps are tempting but depend on the site. Removing a trailing slash, sorting query parameters, dropping session identifiers, or ignoring the case of the path can merge URLs that a particular server treats differently. Many pages also declare a preferred URL for themselves with a <link rel="canonical"> element, which a crawler can use as a hint.

URL filter and duplicate elimination

The URL filter discards links the crawler should not fetch: those disallowed by the host's robots.txt, which the filter caches for each host, and those excluded by the crawler's own rules, such as other domains in a focused crawl, file types it cannot use, or URLs that are suspiciously long or deep. Since a URL may wait in the frontier for days while the host's robots.txt changes, Manning, Raghavan, and Schütze (2008, §20.2.1) repeat the robots.txt check immediately before the fetch. Duplicate URL elimination then checks each surviving link against the set of URLs already seen. On a large crawl this set holds billions of URLs, so it is stored as fingerprints of URLs, sorted and kept largely on disk, with a cache in memory (Heydon and Najork, 1999).

The URL frontier

The frontier decides the order of the crawl, and it has two competing jobs. It should fetch important pages first and revisit pages that change often. It must also never send two requests to the same host at once and must wait between requests to a host. Mercator's frontier separates the two jobs into two sets of queues (Najork and Heydon, 2002; Manning, Raghavan, and Schütze, 2008, §20.2.3).

• Front queues handle priority. Each new URL is given a priority from 1 to $F$, based on signals such as its estimated quality or how often its page has changed, and placed in the front queue for that priority. When a back queue needs refilling, a selector picks a front queue, favoring the high-priority ones but taking from all of them.
• Back queues handle politeness. Each back queue holds URLs from a single host, and a table records which host each queue serves. URLs taken from the front queues are routed to the back queue of their host, and when a back queue empties, it is assigned a new host.
• A heap schedules the hosts. Each back queue has an entry in a heap, keyed by the earliest time its host may be contacted again. A thread takes the back queue at the top of the heap, waits if that time has not yet arrived, fetches one URL, and puts the queue back with a new time, set by the delay rules of politeness.

With this design, priority decides which URLs reach the back queues and politeness decides when each host is visited. Mercator's designers used about three times as many back queues as crawler threads, so that threads rarely wait for a host to become available.

A frontier traced step by step

The rules are easier to follow on a small example, with every time computed. The frontier below has two front queues and three back queues, and one crawler thread. Nine URLs on four hosts have arrived with priorities: a.com/1, b.org/1, a.com/2, c.net/1 and a.com/3 in the high-priority queue, and d.edu/1, b.org/2, c.net/2 and d.edu/2 in the low one. To make the trace repeatable, the selector takes from the front queues in the fixed pattern 1, 1, 2, 1, 1, 2, and so on (the real selector chooses at random with a bias toward high priority), skipping a queue that is empty. Each host answers in a fixed time, 0.2 seconds for a.com, 0.5 for b.org, 0.1 for c.net and 0.3 for d.edu, and after each fetch the host may not be contacted again for 10 times that long.

At the start, each empty back queue is filled. Back queue 1 takes the first URL selected, a.com/1, and is assigned the host a.com. Back queue 2 takes b.org/1. The third selection comes from front queue 2, d.edu/1, and back queue 3 is assigned d.edu. All three are available at time 0.

The thread then repeats: take the back queue with the earliest time from the heap (the lower queue number on a tie), wait for that time if necessary, fetch one URL, and put the queue back with its next allowed time. When a queue empties, it is refilled from the front queues: a URL for a host that already has a back queue is appended to that queue, and the first URL for a new host claims the empty queue. A refilled queue for a host fetched before must still wait out that host's delay.

Between the fetches, the queues are refilled as follows:

• Step 1. Queue 1 empties and takes a.com/2, so it keeps a.com; it is due at 2.2, not at once, because a.com was just fetched.
• Step 2. Queue 2 empties and is assigned c.net, with c.net/1.
• Step 3. Queue 3 empties and is assigned b.org, with b.org/2; it is due at 5.7.
• Step 4. Queue 2 empties. The selector first draws a.com/3, which joins queue 1 because a.com already has a queue, then c.net/2, which goes back into queue 2, due at 2.1.
• Step 5. Before it, the thread is idle from 1.1 to 2.1: no host is due. Afterward, queue 2 is assigned d.edu with d.edu/2, due at 4.0, and the front queues are empty.
• Steps 6 to 9. No more refills are possible. The thread is idle from 2.4 to 4.0, from 4.3 to 4.4, and from 4.6 to 5.7, waiting for the next host to come due.

Every host is contacted exactly when its delay allows and never sooner: a.com at 0.0, 2.2 and 4.4, two seconds after each 0.2-second fetch ends. Priority shows in the order: the high-priority a.com and b.org URLs reached the back queues first. The cost of politeness shows too. The thread was busy for 2.4 of the 6.2 seconds, 39 percent, because with only four hosts it often had nothing it was allowed to fetch. With thousands of hosts in the back queues, some host is almost always due, which is why a real frontier keeps several times more back queues than threads.

The trace is produced by tools/experiments/crawling/frontier_sim.py in the site repository, and the demo implements the same rules.

A crawl of this site

To see these steps on real pages, a small crawler was run against a copy of this site served on the local machine, never against an outside server. It used a first-in, first-out frontier, the URL normalization above, robots.txt checking, a 0.1-second delay between requests, and a restriction to the site's own host. The crawl was made while the site had 77 wiki articles, before this topic was written. The site has no robots.txt, and the request for it, not counted in the table, returned 404, which under RFC 9309 means everything may be fetched. The script treats a server error on robots.txt as disallowing everything, as the RFC requires, but relies on Python's parser for matching rules, with the limits of its older versions described in politeness and robots.txt.

Starting from the home page, the crawl reached 1 page at depth 1, 3 at depth 2, 11 at depth 3, and 66 at depth 4, so every page the crawl reached is within four links of the home page. More than nine in ten links pointed to URLs already seen, which is why duplicate URL elimination has to be fast. Each wiki page links to the navigation pages and to related articles, so the same few URLs appear on nearly every page.

The 24 discarded files show a simple inefficiency. The crawler wanted only HTML, but it learned each file's type from the response, after downloading it in full. Checking the URL's extension first, or reading the headers and closing the connection before the body arrives, would have saved most of that transfer. On a large crawl, decisions like this one determine how much bandwidth goes to pages that will actually be indexed.

The same crawl's pages are used in near-duplicate detection. The script is tools/experiments/crawling/sitecrawl.py in the site repository.

References

• Heydon, A., and Najork, M. (1999). Mercator: A scalable, extensible web crawler. World Wide Web, 2(4), 219–229.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 20.2. Cambridge University Press.
• Najork, M., and Heydon, A. (2002). High-performance web crawling. In J. Abello, P. M. Pardalos, and M. G. C. Resende (Eds.), Handbook of Massive Data Sets, 25–45. Kluwer Academic Publishers.
• Olston, C., and Najork, M. (2010). Web crawling. Foundations and Trends in Information Retrieval, 4(3), 175–246.