What a Web Crawler Does

A web crawler, also called a spider or robot, is a program that finds and downloads web pages automatically. For a search engine, it is the first stage of the pipeline described in search engine architecture: the crawler gathers pages, the indexer builds an inverted index from them, and the query processor searches that index. A search engine can only return pages its crawler has fetched, and only in the form in which it last fetched them. The goal of a crawler is to gather as many useful pages as possible, quickly and efficiently, together with the link structure that connects them (Manning, Raghavan, and Schütze, 2008, §20.1).

URLs

Every page is identified by a Uniform Resource Locator. A URL such as

https://www.example.edu/graduate/courses.html?term=fall#csc790

has a scheme (https), which names the protocol, a host (www.example.edu), which names the server, a path (/graduate/courses.html), which names the resource on that server, an optional query (term=fall), which passes parameters to a program on the server, and an optional fragment (csc790), which points to a place within the page and is never sent to the server. The crawler resolves the host to an IP address through the Domain Name System, connects to that server, and requests the path and query with HTTP.

Many different URLs can name the same page. The host is case-insensitive, the default port can be written or omitted, relative links must be resolved against the page they appear on, and the fragment changes nothing. Reducing URLs to one canonical form, called URL normalization, is described in crawler architecture.

The crawl loop

The basic operation is the same for any crawler (Manning, Raghavan, and Schütze, 2008, §20.2):

1. Start from seeds. The crawl begins with a set of seed URLs, typically well-known, well-connected pages.
2. Choose a URL. The crawler takes a URL from the URL frontier, its list of URLs discovered but not yet fetched.
3. Fetch. It downloads the page over HTTP, following redirects and handling errors.
4. Parse. It extracts the page's text, for the indexer, and its links.
5. Add new URLs. Each extracted link is normalized, checked against the URLs already seen, filtered by rules such as robots.txt, and, if it passes, added to the frontier.
6. Repeat until the frontier is empty, which on the web never happens, or until the crawl's budget runs out.

If the frontier is a first-in, first-out queue, the crawl is a breadth-first traversal of the web graph from the seeds. Breadth-first order has a useful property beyond simplicity. Important pages tend to have many incoming links, so they are reached early from many directions. Najork and Wiener (2001) found, on a crawl of 328 million pages, that breadth-first crawling discovered pages with high PageRank early. Production crawlers replace the simple queue with a prioritized frontier, but breadth-first order is a sound baseline.

A small crawl, step by step

The loop fits in a few lines. Leaving out fetching and parsing, which a later article covers, the bookkeeping is a queue of URLs to fetch and a set of URLs already seen:

frontier = deque([seed])        # URLs discovered but not yet fetched, first in, first out
seen = {seed}                   # every URL ever added to the frontier
while frontier:
    url = frontier.popleft()
    for link in links_on(url):  # fetch and parse
        if link not in seen and allowed(link):
            seen.add(link)
            frontier.append(link)

A URL is marked as seen when it is added to the frontier, not when it is fetched, so that a page linked from many places enters the queue only once.

Consider a toy web of six pages on two hosts, a university (uni.edu) and a library (lib.org), plus a calendar on cal.org whose page for each month links to the next month, so that it has no last page. The university's news page links to the calendar. The crawler starts from uni.edu/ and, as a defense against spider traps like the calendar (described under robustness below), admits at most 4 URLs per host to the frontier. In the table, "added" lists the links that entered the frontier; links to URLs already seen are not listed.

The trace shows three things. Breadth-first order finished every page at depth 1 before any at depth 2, so the six pages of real content were all fetched within the first seven steps. The calendar, by contrast, contributed a new page at every level, and without the limit the crawl would never end: run without it, the same crawl is still descending the calendar after 12 steps, at depth 7. And the limit is blunt. A limit of 3 URLs per host would also have stopped the trap, but it would have refused uni.edu/csc790, a real page, because uni.edu reached its quota first. Every defense against traps is a trade between the pages it saves fetching and the pages it misses. The trace is computed by tools/experiments/crawling/crawl_trace.py in the site repository.

Features a crawler must provide

Manning, Raghavan, and Schütze (2008, §20.1.1) name two features that any crawler on the open web must have.

Robustness

The web contains spider traps: parts of sites that generate an unbounded number of distinct URLs. A calendar with a "next month" link on every page has no last page. A site that puts a session identifier in every URL makes each visit's links look new. A misconfigured server that returns the same page, with the same relative links, for any path under a directory can be crawled at /a/, /a/a/, /a/a/a/, and so on. Some traps are deliberate, built by spammers to fill a search engine's index with their pages or to waste the resources of crawlers that ignore the site's rules (Olston and Najork, 2010, §6.2).

A crawler has no general way to tell that a site is infinite, so it defends itself with limits and checks:

• limits on the number of pages fetched from each host, and on the depth of paths and length of URLs;
• duplicate detection, so that pages whose content has been seen before are not mined for more links;
• URL normalization, so that trivially different URLs are recognized as one;
• timeouts and size limits on every fetch, so that one slow or enormous response cannot stall the crawler.

Robustness also means surviving the ordinary mess of the web: malformed HTML, wrong character encodings, servers that time out, and responses that claim one content type and contain another.

Politeness

Every request consumes the server's bandwidth and processing time. A crawler fetching from one server as fast as its connection allows can degrade that server for its human users, and to the server's operator it looks like an attack. Servers have both explicit policies, published in a file called robots.txt, and implicit ones, such as not sending many requests at once. A crawler must respect both. Politeness and robots.txt describes how.

Features a crawler should provide

Beyond the two essentials, a crawler serving a search engine should have several further qualities (Manning, Raghavan, and Schütze, 2008, §20.1.2):

• Quality. Much of the web is spam, duplicates, or of little use. The crawler should be biased toward useful pages, fetching them first and revisiting them more often.
• Scalability. Adding machines or bandwidth should increase the crawl rate roughly in proportion.
• Performance and efficiency. The crawler should make good use of processors, storage, and network bandwidth. A machine waiting on a slow server should be fetching from others in the meantime.
• Distributed operation. A crawl of the web is too large to finish quickly on one machine, so the crawler should be able to run on many machines, possibly in several locations, as described in distributed crawling.
• Freshness. Pages change and disappear. The crawler should run continuously and revisit each page at a rate suited to how often it changes, a problem treated in freshness and recrawling.
• Extensibility. New formats, protocols, and kinds of content keep appearing. A modular design lets one part of the crawler change without rebuilding the rest.

What a crawler cannot reach

Following links reaches only pages that some other reachable page links to. Pages behind logins, pages generated in response to form submissions, and content that appears only after a script runs in the browser are not reached this way. Together they make up the deep web, which Bergman (2001) estimated to be hundreds of times larger than the part search engines index.

A small instance of the same limit appeared when this site was crawled for crawler architecture. The crawler found every one of the 77 wiki articles the site had at the time, because every article is linked from a topic page or from another article. It did not find the wiki's index page at /wiki/, because no page links to it. A page that exists but is not linked is invisible to a crawler, unless the site lists it in a sitemap or someone submits it directly.

References

• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, sections 20.1–20.2. Cambridge University Press.
• Bergman, M. K. (2001). The deep web: Surfacing hidden value. Journal of Electronic Publishing, 7(1).
• Najork, M., and Wiener, J. L. (2001). Breadth-first search crawling yields high-quality pages. In Proceedings of the Tenth International World Wide Web Conference (WWW10), 114–118.
• Olston, C., and Najork, M. (2010). Web crawling. Foundations and Trends in Information Retrieval, 4(3), 175–246.