A single machine running the crawler architecture described earlier can fetch a few hundred pages a second. At that rate, fetching ten billion pages once would take about a year, and a search engine must also revisit pages to keep them fresh. Web-scale crawling is therefore distributed across many machines, often in several data centers. This article describes how the work is divided, and then the connectivity server, which stores the link structure the crawl discovers.
Dividing the work
The natural unit of division is the host. Each crawler node is made responsible for a set of hosts, and it fetches every URL on those hosts and no others. Assigning by host, rather than by individual URL, has two advantages. Politeness stays local, since all requests to a host come from one node, which can enforce the delay between them without consulting the others. Caches stay effective, since the node that crawls a host also holds its robots.txt rules and DNS results.
A simple assignment hashes the host name and takes the result modulo the number of nodes. Simple modular hashing reassigns almost every host when a node is added or fails. UbiCrawler (Boldi, Codenotti, Santini, and Vigna, 2004) used consistent hashing instead, which moves only the hosts of a node that leaves, or the hosts taken over by a node that joins. Geographic distribution can refine the assignment, giving each data center the hosts that are close to it on the network.
Why modular hashing moves almost everything
Suppose a host name hashes to the integer $h$, and the crawl grows from 4 nodes to 5. The host stays where it was only if $h \bmod 4 = h \bmod 5$. Both remainders are determined by $h \bmod 20$, and of the 20 possible values of $h \bmod 20$, only 0, 1, 2 and 3 give equal remainders. So a fraction $4/20 = 1/5$ of hosts stay and $4/5$ move. In general, going from $n$ to $n+1$ nodes moves a fraction $n/(n+1)$ of all hosts, which approaches all of them as the crawl grows. A move is expensive: the new node has no robots.txt rules or DNS results cached for the host, no record of when the host was last contacted, and none of the host's URLs in its frontier, which must all be sent over. Yet only $1/5$ of the hosts need to move to give the new node an equal share.
Consistent hashing
Consistent hashing, introduced by Karger, Lehman, Leighton, Levine, Lewin, and Panigrahy (1997) for distributing web caches, is a hash function that "changes minimally as the range of the function changes", in their words. The usual construction places both nodes and hosts on a circle:
- Hash each node's name to a point on a circle, for example a 32-bit value read as a fraction of a full turn.
- Hash each host name to a point on the same circle.
- Assign each host to the first node found by moving clockwise from the host's point.
Each node owns the arc that ends at its own point. When a node joins, it takes over only part of one arc, the hosts between its point and the previous node's point, and every other host stays put. When a node leaves, only its own hosts move, to the next node clockwise.
The figure also shows a weakness of the basic construction. With one point per node, the arcs have very unequal lengths: node A's arc is so short that it owns none of the twelve hosts, while D owns five. The standard remedy is to give each node many points on the circle, called virtual nodes, so that each node's share is the sum of many short arcs and evens out. A simulation with 100,000 synthetic host names, over 30 random placements of the nodes, gives:
| Points per node | Hosts moved, 4 to 5 nodes | Load of the busiest of 4 nodes |
|---|---|---|
| 1 | 0.182 (0.066 to 0.327) | 2.10 (1.88 to 2.84) times an even share |
| 100 | 0.204 (0.187 to 0.212) | 1.08 (1.06 to 1.11) times an even share |
| Modular hashing | 0.801 | 1.005 times an even share |
Each entry is the median over the 30 placements, with the middle half of the placements in parentheses (rounded to three places, or two for loads). Both forms of consistent hashing move about the ideal fifth of the hosts, but with one point per node the amount moved and the load per node vary widely with the placement. With 100 points per node the busiest node carries only about 8 percent more than its share. Modular hashing balances load almost perfectly and moves four fifths of the hosts. In every run, every host that moved under consistent hashing moved to the new node, as the construction guarantees.
Exchanging URLs
A node parsing a page finds links to hosts it is not responsible for. Manning, Raghavan, and Schütze (2008, §20.2.1) add a host splitter to the crawler, after the URL filter: each link is sent to the node that owns its host, and links received from other nodes enter the local duplicate URL elimination and frontier like any others.
The exchange would be expensive if every link were sent separately, but two properties keep it manageable. Most links point to pages on the same host, so most links found by a node are its own. In the crawl of this site, only 34 of 1,640 links pointed elsewhere, though a single site is an extreme case. The links that must be sent can also be batched, and links to very popular pages, which appear on many hosts, can be filtered locally with a cache of URLs known to be already seen, so they are not sent repeatedly.
Duplicate content across nodes
Duplicate URL elimination partitions naturally by host, since a URL belongs to one host. The "content seen?" test does not. Two copies of a page can live on different hosts, and so on different nodes. The fingerprints of fetched pages are therefore partitioned by the fingerprint itself, not by host: each node sends the fingerprint of every page it fetches to the node responsible for that fingerprint, chosen for example by taking the fingerprint modulo the number of nodes, which answers whether it has been seen before (Manning, Raghavan, and Schütze, 2008, §20.2.1). Most of these tests are therefore remote calls, though lookups can be batched. For near-duplicates, the sketch values can be partitioned the same way.
From crawl to index
A distributed crawl produces its pages spread across many machines, and indexing them is distributed too. Index construction describes building an inverted index with MapReduce, in which parsers process splits of the collection and inverters gather the postings for ranges of terms. The finished index is then partitioned for searching, almost always by document, as search at scale explains.
Connectivity servers
A crawl discovers not only pages but the links between them, and the link graph is valuable in itself. PageRank and other link analysis methods are computed from it, anchor text is gathered along it, and link patterns help detect spam. Many applications need two kinds of query answered quickly:
- out-links: which pages does page $p$ link to?
- in-links: which pages link to page $p$?
A connectivity server answers them (Bharat, Broder, Henzinger, Kumar, and Venkatasubramanian, 1998). It stores two adjacency lists for every page, its out-links and its in-links, with each page identified by an integer rather than its URL. The difficulty is size. A web of four billion pages with an average of ten links each, storing both ends of each link as 32-bit page identifiers, needs $4 \times 10^9 \times 10 \times 8$ bytes, about 320 gigabytes (Manning, Raghavan, and Schütze, 2008, §20.4). The lists should fit in memory for fast access, so they must be compressed.
Compressing the link graph
The compression methods exploit regularities of the web graph (Manning, Raghavan, and Schütze, 2008, §20.4):
- Locality. Most links point to pages on the same host. If pages are numbered in lexicographic order of their URLs, pages on the same host receive nearby numbers, and a page's out-links are mostly close to its own number.
- Gaps. As with postings lists in index compression, a sorted adjacency list can be stored as the differences between successive identifiers, which are small and encode in few bits.
- Similarity. Pages on the same host often have nearly identical link lists, since they share navigation menus. A list can be encoded as a reference to a similar, earlier list plus the differences.
A small example shows the first two working together. Suppose pages are numbered in URL order and page 1001 links to pages 1000, 1002, 1003, 1010, 1011, 1050 and 2040, most of them on its own host and so numbered nearby. Stored as 32-bit identifiers, the list takes $7 \times 4 = 28$ bytes. Stored as the first identifier followed by the gaps between successive ones, it is
$$1000,\ 2,\ 1,\ 7,\ 1,\ 39,\ 990.$$
With variable-byte encoding, which uses 7 bits of each byte for the number, every value below 128 fits in one byte and values up to 16,383 in two. The gaps 2, 1, 7, 1 and 39 take one byte each and 1000 and 990 take two, 9 bytes in all, about a third of the original. Locality is what makes the gaps small: without it, a page's links would point to random identifiers among billions, and the gaps would be nearly as large as the identifiers. The third idea goes further. If another page on the same host links to the same pages except 1050, and also to 1012, its list can be stored as a reference to page 1001's list, a note that one entry is dropped, and one extra entry.
The Link Database (Randall, Stata, Wickremesinghe, and Wiener, 2002) and the WebGraph framework (Boldi and Vigna, 2004) combined these ideas and reduced large crawled web graphs to a few bits per link, small enough to hold billions of links in the memory of one machine.
This site's link graph showed the same regularities on a small scale. When the site had 82 pages, of the 1,115 distinct links among them, 162 point to just two pages, the home page and the Academics page, which are linked from every page's navigation menu, and another 78 pointed to the CSC 790 course page. Every wiki article's out-link list contained the same few entries, exactly the redundancy that reference compression removes.
References
- Bharat, K., Broder, A., Henzinger, M., Kumar, P., and Venkatasubramanian, S. (1998). The connectivity server: Fast access to linkage information on the web. In Proceedings of the Seventh International World Wide Web Conference (WWW7), 469–477.
- Boldi, P., Codenotti, B., Santini, M., and Vigna, S. (2004). UbiCrawler: A scalable fully distributed web crawler. Software: Practice and Experience, 34(8), 711–726.
- Boldi, P., and Vigna, S. (2004). The WebGraph framework I: Compression techniques. In Proceedings of WWW 2004, 595–602.
- Karger, D., Lehman, E., Leighton, T., Levine, M., Lewin, D., and Panigrahy, R. (1997). Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the 29th ACM Symposium on Theory of Computing (STOC 1997), 654–663.
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, sections 20.2.1 and 20.4. Cambridge University Press.
- Randall, K. H., Stata, R., Wickremesinghe, R. G., and Wiener, J. L. (2002). The Link Database: Fast access to graphs of the web. In Proceedings of the Data Compression Conference (DCC 2002), 122–131.