The URL frontier and politeness

What the frontier must balance

The URL frontier decides the crawl's download order. It must balance two things:

1. Priority: fetch important or frequently changing pages first.
2. Politeness: do not overload any web server. Najork and Heydon put it this way: "a web crawler should not attempt to download multiple pages from the same web server simultaneously; better, it should impose a limit on the portion of a web server's resources it consumes."

A single FIFO queue fails at both. A page with thousands of links to one site would put thousands of consecutive requests to that site at the head of the queue.

Mercator's first frontier guaranteed only that one thread at a time contacted a given server, which they called the weak politeness guarantee. It still drew complaints from administrators, because it "does not prevent a stream of requests from being issued to the same host without any pauses between them".

Mercator's two-stage frontier

Najork and Heydon's best design (2001) has a front end for priority and a back end for politeness:

Front end: one FIFO queue per priority level. A pluggable prioritizer gives each new URL a priority from 1 to $k$, based on the URL and its download history (for example, whether the page changed since the last visit). It then puts the URL in that priority's queue. URLs leave the front end through a "random queue chooser with bias to high-priority queues"; the paper leaves the bias to configuration. In the visual, each level is chosen half as often as the one above it.

Back end: many FIFO queues, each holding URLs of exactly one host. A host-to-queue table records which queue serves which host. When a back queue empties, it is refilled from the front end. A URL whose host already has a back queue joins that queue. The first URL with a new host claims the empty queue.

A heap with one entry per back queue, holding the earliest time that queue's host may be contacted again. A crawler thread:

1. removes the heap root, waiting if its time has not come yet;
2. downloads the head URL of that back queue;
3. sets the host's next allowed time and puts the entry back in the heap.

The paper's production settings: "3 times as many back-end queues as crawling threads", and "we wait 10 times as long as it took us to download a URL from a host before contacting that host again". These values were "sufficient to keep all threads busy and to keep the rate of complaints to a bare minimum". Scaling the wait to the download time slows the crawler down automatically on hosts that are already slow.

The frontier soon outgrows memory, so each FIFO queue keeps most of its URLs on disk and buffers only its head and tail in memory.

Splitting the frontier across machines

Mercator's distributed "hive" gives each crawling process a subset of host names. A host splitter sends every discovered URL to the process that owns its host. All of a host's URLs then live in one frontier, so politeness is enforced in one place. The DNS cache and seen-URL set are partitioned the same way.

To assign hosts, hash the host name. A plain $\text{hash}(\text{host}) \bmod N$ reassigns almost every host whenever $N$ changes. Consistent hashing (chapter 4) moves only about $1/N$ of them.