Mercator’s two-stage frontier: priority front queues, one-host back queues, and a heap of the times each host may be contacted again.
What you will learn
Explain why one FIFOqueue fails at both priority and politeness.
Follow Mercator's two-stage frontier: front queues by priority, back queues by host, and a heap of next-allowed times.
Split the frontier across machines by host.
What the frontier must balance
The URL frontier decides the crawl's download order. It must balance two things:
Priority: fetch important or frequently changing pages first.
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 FIFOqueue 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 queues: one FIFOqueue per priority level. A pluggable prioritizer gives each new URL a priority from 1 to kwhat its symbols mean, 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 queues: 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 is added to 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 crawlerthread:
removes the heap root, waiting if its time has not come yet;
downloads the head URL of that back queue;
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 DNScache and seen-URL set are partitioned the same way.
To assign hosts, hash the host name. With Nwhat its symbols meancrawler processes, a plain hash(host)modN reassigns almost every host whenever N changes. Consistent hashing (chapter 4) moves only about 1/N of them.
A polite, prioritizing URL frontier
Front queues order by priority; each back queue holds one host; a crawler takes the host that may be contacted soonest, then that host waits 10 times its download time.
Clock: 0 ms
Front queue, priority 1
wiki.example
Front queue, priority 2
empty
Front queue, priority 3
blog.example
shop.example
news.example
Back queue 1: news.example
3 URLs
host may be contacted at 0 ms
heap root: next to be fetched
Back queue 2: shop.example
1 URL
host may be contacted at 0 ms
Back queue 3: wiki.example
1 URL
host may be contacted at 0 ms
Fetches
None yet.
New URLs1× instancePrioritizer1× instanceFront queues (one perpriority)1× instanceBack queues (onehost each)1× instanceHeap of next allowedtimes1× instanceCrawler threads1× instanceNew URLs1× instancePrioritizer1× instanceFront queues (one perpriority)1× instanceBack queues (onehost each)1× instanceHeap of next allowedtimes1× instanceCrawler threads1× instance
Figure 2
Mercator’s two-stage frontier: front queues by priority, back queues by host, and a heap of the times each host may be contacted again.
These are the parts of one crawling process, not separate servers, so each is drawn once. Follow a URL in: the prioritizer gives it a priority and puts it in that priority’s front queue. When a back queue empties, it is refilled from the front queues, chosen at random with a bias to the high priorities; a URL goes to the back queue that holds its host. Now follow a crawler thread: it takes the heap’s root, the back queue whose host may be contacted soonest, waits until that time, downloads the URL at the head of that queue, and puts the queue back in the heap with its host’s next allowed time, 10 times the download’s duration later. Mercator kept 3 times as many back queues as threads.
New URLs: 1 × Users
Prioritizer: 1 × App server
Front queues (one per priority): 1 × Queue
Back queues (one host each): 1 × Queue
Heap of next allowed times: 1 × Cache
Crawler threads: 1 × App server
New URLs sends requests to Prioritizer
Prioritizer sends requests to Front queues (one per priority)
Front queues (one per priority) sends requests to Back queues (one host each)
Crawler threads sends requests to Heap of next allowed times
Crawler threads sends requests to Back queues (one host each)
Key takeaways
The front end orders URLs by priority; each back queue holds one host's URLs, so only one thread at a time fetches from a host.
A heap of each host's next allowed time spaces requests out; Mercator waited 10 times the last download's duration before contacting the host again.
Assign hosts to crawler processes by consistent hashing, so a host's URLs live in one frontier and adding a machine moves only about 1/Nwhat its symbols mean of them.