36.6 How does the URL frontier work?

Step 5: Deep dives (10 minutes)

The frontier must answer two questions at once: what's most important to crawl next, and which hosts can we touch right now without being rude. The classic design (from the Mercator crawler) uses two layers:

Figure: priority on the way in, politeness on the way out.

• Front queues, by priority: important pages (popular sites, pages that change often, links from high-quality pages, new bestseller pages) go into higher-priority queues.
• Back queues, by host: each host has its own FIFO. A URL moves from a front queue to its host's back queue.
• A heap of "next allowed" times: a fetcher takes the host whose time has arrived, fetches one URL, and pushes that host's next time forward by its delay.

In the chapter's code, 1,000 URLs spread over 5 hosts with a 1-second delay per host take about 200 seconds, and no host is ever fetched more than once a second. A naive crawler doing 100 fetches a second would hit each of those hosts 20 times a second. And a high-priority URL jumps ahead of a low-priority one when both hosts are ready.

At scale, the frontier is too big for memory: keep the queues on disk or in a distributed queue, with in-memory buffers at the head of each queue.

Memory code: "Priority decides what; the host's clock decides when."