The URL Frontier: Priority Queues Behind Per-Host Politeness

A crawler that has discovered ten million URLs has to answer one question ten million times: which one now. The naive answer, a single queue served first-in-first-out, is wrong in two independent ways. It ignores that some pages are worth fetching before others, and it ignores that the servers holding those pages will object to being asked too often. Fixing either problem alone produces a crawler that is visibly bad: a strict priority order concentrates all requests on whichever host happens to own the highest-ranked URL, and a strict round-robin over hosts throws away every signal about importance.

The standard resolution, described in the Mercator crawler and inherited in various forms by most large crawlers since, is to split the frontier into two stages. A front end orders URLs by priority. A back end orders URLs by host and time. The two stages communicate through an assignment table, and the whole design exists to keep the priority decision and the politeness decision from contaminating each other.

Two orderings that cannot live in one queue

Politeness is a per-host property. A crawler must leave a gap between successive requests to the same host, and the gap is measured in wall-clock time, not in queue positions. Priority is a global property, computed from link structure, update history, or a seed list, and it says nothing about which host a URL belongs to.

A single priority queue fails because the top of the queue is not uniformly distributed across hosts. If a site contributes a thousand high-priority URLs, the head of the queue is a thousand URLs from that site, and serving the queue in order means issuing a thousand requests back to back to one server. A single per-host round-robin queue fails because it treats the millionth-most-important page the same as the first, so the crawler spends its bandwidth on link farms and dead ends while the pages that would improve the index sit unfetched.

The two-stage frontier keeps a priority queue whose contents are cheap to reorder and a set of host queues whose contents are cheap to delay. Neither structure needs to know the other’s invariant.

The front end: prioritized queues with a random selector

The front end holds k FIFO queues, one per priority level. Every newly discovered URL is assigned a priority in the range 1 to k and appended to the corresponding queue. Assigning priority is a separate problem, covered under crawl order as resource allocation; the frontier only needs the resulting integer.

Fetching from the front end does not simply take from the highest non-empty queue. That policy would starve the low-priority queues completely and, worse, would hand the back end a burst of URLs from whichever host dominates the current top queue. Instead the selector picks among non-empty queues at random, with weights biased toward the higher priorities. A queue at priority i receives weight proportional to a decreasing function of i, so high-priority URLs are selected more often without any queue being unreachable.

The randomization does real work. Because URL discovery is itself bursty, consecutive draws from a biased selector tend to come from different sites, and the back end therefore receives a stream that already resembles a mix of hosts. The front end is not enforcing politeness, but it avoids manufacturing the pathological case in which one host monopolizes the head of the stream.

A subtle consequence: the selection is stochastic, so the frontier’s behaviour is not a strict priority order and cannot be described by one. Two runs over the same URL set can produce different fetch sequences. What is guaranteed is expected behaviour over many draws, not a deterministic sequence, and any test that asserts an exact order is testing the wrong property.

The back end: one queue per host, ordered by ready time

The back end maintains b queues, where b is a fixed bound on how many hosts the crawler can manage at once. Each queue is bound to exactly one host, and the binding is recorded in a host table. A back queue contains URLs for its host only, already ordered internally by priority, and carries a timestamp: the earliest moment at which the host may legally be contacted again.

The fetch loop takes the back queue whose timestamp has passed and whose next URL has the highest priority among all ready queues. After the fetch, the queue’s timestamp is advanced by the politeness interval for that host. When a queue becomes empty, its host is released from the host table, and the queue can be assigned to a different host that has pending URLs.

Assignment happens when the front end produces a URL whose host is not currently bound. If an unbound queue exists, the host takes it. If all b queues are bound, the frontier must decide which host to evict. Mercator’s approach is to reorder the heap of back queues: a host with many pending URLs should not be evicted merely because its next fetch is a few hundred milliseconds away, so the eviction decision weighs queue occupancy as well as ready time. Evicting the host with the longest current queue would be wrong for the opposite reason: it would discard exactly the host with the most work to do, then rediscover it immediately.

Each back queue should hold more than one URL whenever possible. With a single URL in the queue, the host goes idle the instant that URL is fetched, and the frontier must go back to the front end, resolve a host assignment, and reinsert — all before the next fetch is due. Keeping a small batch of URLs per host means the queue can advance immediately when its timestamp expires.

A minimal sketch of the two stages, omitting DNS and fetching:

import heapq, random

class Frontier:
    def __init__(self, priorities=8, hosts=256, delay=1.0):
        self.front = [[] for _ in range(priorities)]   # (url, host) per level
        self.weights = [priorities - i for i in range(priorities)]
        self.delay, self.capacity = delay, hosts
        self.back, self.bound = {}, {}   # host -> pending urls / earliest time
        self.ready, self.queued = [], set()   # heap of (time, host)

    def draw(self):
        live = [i for i in range(len(self.front)) if self.front[i]]
        if not live:
            return None
        i = random.choices(live, weights=[self.weights[j] for j in live], k=1)[0]
        return self.front[i].pop(0)

    def assign(self, url, host):
        if host not in self.back:
            if len(self.back) >= self.capacity:
                return False                  # caller must evict a host first
            self.back[host], self.bound[host] = [], 0.0
        self.back[host].append(url)
        if host not in self.queued:
            heapq.heappush(self.ready, (self.bound[host], host))
            self.queued.add(host)
        return True

    def next_url(self, now):
        if not self.ready or self.ready[0][0] > now:
            return None                       # no bound host is legal yet
        _, host = heapq.heappop(self.ready)
        self.queued.discard(host)
        url = self.back[host].pop(0)
        self.bound[host] = now + self.delay
        if self.back[host]:
            heapq.heappush(self.ready, (self.bound[host], host))
            self.queued.add(host)
        else:
            del self.back[host], self.bound[host]
        return url, host

The driver alternates between the two halves: while next_url returns nothing, it draws from the front end and calls assign; when it returns a URL, the fetch loop issues that request.

Two omissions in the sketch are deliberate. Eviction is not shown, because the choice of which host to displace is a policy decision that depends on how many URLs each queue holds. Nor is the persistence of pending URLs, which in a real frontier live outside memory. The separation is the design’s main virtue: the correctness of the front end does not depend on how a host gets a queue.

Why the split pays for itself

The front end costs k lists and one weighted draw per URL. The back end costs b host queues plus a heap ordered by timestamp and a host table mapping host strings to queue identifiers. Both are proportional to configuration parameters rather than to the number of pending URLs, so the structure scales to a frontier far larger than memory as long as the URL payloads live elsewhere.

The alternative designs are each simpler and each worse. A single priority queue with a per-host last-fetch map consulted at pop time requires searching past the queue head until a legal URL is found; with a thousand pending URLs from one host, that search is unbounded, and the queue becomes a linear scan. A single queue with rate-limited dequeue has the same problem in a different shape. The two-stage design makes the illegal-pop case structurally impossible: a URL is only offered to the fetch loop from a queue whose host is currently allowed to be contacted.

The cost is indirection. Every URL passes through the front end, then waits in the host table for assignment, then waits again in a back queue. Memory per pending URL is therefore larger than one pointer, and the bookkeeping per fetch includes a heap adjustment. For a crawl issuing thousands of requests per second, that overhead is small compared with the network round trip; for a crawl issuing a few per second, the structure is overkill and a plain queue with a per-host timestamp map is enough.

Failure modes that survive the design

The design bounds politeness but not throughput. If the frontier is bound to b hosts, at most b fetches can be in flight or waiting on a timer, so the aggregate rate is bounded by b divided by the per-host delay, ignoring latency. Raising b raises concurrency and memory; raising the delay lowers load on servers and lowers throughput proportionally. The relationship between these numbers, and the effect of running more than one connection per host, belongs to the per-host rate limits rather than to the queue structure.

Several failures are specific to the two-stage arrangement:

• Host identity errors. If the same server is reachable under two names, or under two schemes and default ports, it occupies two back queues and receives twice the intended request rate. Canonicalization before enqueueing is what prevents this, which is why URL normalization sits on the critical path of the frontier rather than after it.
• Host table thrash. If b is small relative to the number of active hosts, hosts are evicted before their queued URLs are fetched and reassigned repeatedly. Each reassignment re-reads the host’s URLs from storage, and the frontier spends its time shuffling rather than fetching.
• Timer starvation. A queue whose timestamp is always slightly in the future can be passed over indefinitely if the selection rule looks only at the most-ready queue and the arrival rate of new hosts is high. Ordering the ready heap by timestamp prevents this; ordering by priority alone reintroduces the starvation the random selector was meant to remove.
• Priority collapse at the back end. If back queues are ordered only by timestamp, a host holding a hundred low-priority URLs will be served as eagerly as one holding a hundred high-priority URLs, because both become ready at the same rate. The priority signal must survive the second stage, either by ordering URL selection within a queue or by preferring ready queues with higher-ranked heads.

The frontier also has to decide what happens to a URL whose host is unknown to DNS, whose robots rules forbid it, or which turns out to be a duplicate of something already fetched. Each of those decisions removes work from the queue, and the removal rate is what determines whether the crawler converges or the frontier grows without bound. Trap detection is the mechanism that keeps the second case from dominating.