Crawl Order as Resource Allocation Under a Fixed Budget

Every crawling decision so far has assumed the crawler has a URL and asks whether it may fetch it. The harder question is which URL to consider at all. A crawl runs against a deadline, a bandwidth allowance, or a politeness budget, and the number of URLs it could fetch is larger than the number it will fetch. The ordering rule therefore determines what the index contains, and it does so before any of the mechanisms discussed elsewhere (robots compliance, delay, trap detection) have a chance to influence the outcome.

Framing this as a resource allocation problem is more useful than framing it as a ranking problem, because it forces the question of what a fetch is worth. A fetch costs one politeness slot on one host plus the bandwidth of the response. It returns a document that may be new, may be an updated version of something held, or may be worthless. The ordering rule’s job is to maximize the total value returned per unit of cost, and the value function is the part that cannot be derived from the crawler’s own data.

The two demands that compete for one request

A fetched URL can serve two purposes, and they are usually in conflict.

Coverage means the index contains documents it did not contain before. The marginal value of a fetch is high when the document is new, important, and not already represented by a near-duplicate. Discovery of new URLs is the engine of coverage: a page with many unseen outlinks is worth more than a page with none, because the links are the only way the crawl grows.

Freshness means the index reflects the current state of documents it already holds. The marginal value is high when a held document has changed since it was last fetched, which is more likely for documents fetched long ago and for documents with high change rates.

Every request spent on a new URL is a request not spent revalidating an old one, and vice versa. The two are not commensurable in the abstract: a new document adds a row to the index, while a revalidated document keeps an existing row accurate. Which matters more depends on how stale the index already is and how much of the web the index is trying to cover, which is a property of the application rather than of the crawler. The frontier’s priority levels are where this ordering reaches the scheduler.

The common structure is a two-tier schedule: a steady allocation to discovery and a remainder to refresh, with the split set by policy. Within each tier the ordering is separate, and the interesting design work is in the ordering rules rather than in the split.

Ordering by link evidence

The earliest systematic answer to “which URL first” used the link graph. A URL’s importance can be estimated from how many already-fetched pages link to it, on the reasoning that a page many people point at is more likely to be worth having than one nobody points at. This is a breadth-first approximation of importance, and it is cheap: the count comes from pages the crawler has already parsed, so no extra fetching is required.

The refinement is to weight the links. An incoming link from a page that is itself well-linked counts more than one from an obscure page, which is the idea behind PageRank and its many variants. Computing the full stationary distribution over the known graph requires iterating over all known pages and all known links, which is affordable at the scale of a crawl’s frontier but not per-decision. In practice the crawler maintains an approximate score per URL, updates it incrementally as new links arrive, and uses the current approximation to order the queue.

Two properties of link-based ordering matter more than the specific formula.

First, it is self-reinforcing. Pages that are already well-linked attract links, and a crawler that follows link counts will keep finding the same popular cluster. That is the desired behaviour for coverage of the head of the web and the wrong behaviour for coverage of the tail, where the pages are individually unimportant but collectively most of the content. A pure link-count ordering leaves the tail permanently unfetched, and the index is then a mirror of the popular web rather than a sample of the web.

Second, link evidence is only available for URLs that have been discovered, and discovery is itself ordered. A crawler cannot rank a URL it has not seen, so the ordering rule operates on a frontier that is already biased by earlier ordering decisions. The bias compounds: an ordering rule that prefers hubs discovers more hubs, which reinforces the preference. This is the same self-conditioning problem that affects change-rate estimation, and it has the same remedy — an explicit allocation to unexplored regions rather than an implicit one.

Ordering by expected yield

The alternative to link-based ordering is to estimate what a fetch will return. Three signals are available before the fetch.

The URL itself carries structural information. Depth in the path, the presence of query parameters, the extension, and the path’s similarity to URLs already known to be productive all predict something about whether the target is a document. A URL ending in a common image or archive extension is unlikely to be an indexable page; a URL one segment below a known directory index is likely to be a sibling of a productive page. These are heuristics, and they are cheap enough to compute for every candidate.

The site’s history carries more. A host that has yielded a high fraction of new, non-duplicate documents from its last thousand fetches is likely to continue doing so, and a host that has yielded almost nothing is likely to continue yielding nothing. This is the same yield accounting that detects traps, used prospectively rather than as a cutoff. Allocating the next request to the host with the highest recent yield is a bandit problem, and the standard tension applies: always exploiting the best-known host starves the hosts that have not been sampled enough to know.

The document’s change rate carries the freshness side. A URL already in the index with an estimated rate λ and a time since last fetch t has a probability 1 − exp(−λt) of having changed, which is the same quantity the change-rate estimator produces from observed fetches. That probability, multiplied by the document’s importance, is the expected value of a revalidation, and it is directly comparable across URLs because both factors are on a common scale.

The allocation rule

Combining these into a single priority means putting coverage value and freshness value on one scale, and the honest way to do that is to express both as expected gain in an index quality measure per fetch. That measure is not the crawler’s to choose alone; it belongs to whoever evaluates the index.

import math

REFRESH_WEIGHT = 0.6     # relative value of keeping a held page current
DISCOVERY_WEIGHT = 0.4   # relative value of links a new page may yield

def priority(url, now):
    if url.in_index:
        # freshness side: expected staleness recovered per fetch
        p_change = 1.0 - math.exp(-url.rate * (now - url.last_fetch))
        return url.importance * p_change * REFRESH_WEIGHT
    # coverage side: expected new-document value
    novelty = 1.0 - url.duplicate_probability   # from URL shape and site history
    discovery = url.outlink_estimate            # links it may yield
    return url.importance * novelty * (1.0 + DISCOVERY_WEIGHT * discovery)

The weights are policy, not physics. What the formula enforces is that no URL’s priority is unbounded: a page with unknown importance and unknown novelty starts at a moderate value rather than at zero, so it is eventually fetched. That property, no permanent starvation, is what separates a working ordering rule from one that converges on a narrow slice of the web and stays there.

A second property is that priority decays or grows with time in a controlled way. On the freshness side it grows, because staleness accumulates, which guarantees revalidation eventually. On the coverage side it should decay, because a URL that has been waiting in the frontier for a long time is either less relevant than it was or evidence that the crawl is not going to reach it; decaying its priority lets the frontier shed old work rather than accumulating it indefinitely.

The decay interacts badly with the trap budget if implemented carelessly. A host that contributes a million low-priority URLs will see them all decay to the floor, and the floor is what determines whether they are ever fetched. A floor at zero means they are never fetched, which is the intended outcome; a floor that keeps them just above the shed threshold means the frontier carries them forever without fetching them. Frontier size, not just priority, has to be bounded.

What ordering cannot promise

The ordering rule is a heuristic over incomplete information, and three of its limitations are structural rather than fixable.

Importance is estimated from a biased sample. Link counts come from fetched pages, and fetched pages were chosen by earlier orderings. A page that is important but poorly linked is invisible to link-based scoring until something else causes it to be fetched. The only correction is explicit exploration: a fraction of the budget spent on URLs chosen without regard to their score, which lowers average quality and raises the chance of finding the unlinked important pages.

Novelty estimates are circular. A URL’s duplicate probability is estimated from its similarity to documents already held, and what is held was determined by previous ordering. A cluster that was never crawled looks novel when it is finally sampled, and one that was crawled exhaustively looks duplicate. The estimate is a measure of the crawl’s own history as much as of the web.

The value function is not observable. Whether a fetch improved the index depends on queries the index will later serve, and those are not known at crawl time. Every weighting between coverage and freshness is a guess about future query mix. A crawl tuned for freshness serves users who search for current events; one tuned for coverage serves users who search for obscure material. Both are defensible, and the choice cannot be validated from crawl data alone.

Where the budget actually binds

The mechanisms described across the crawl stack each consume part of the budget in ways that are easy to overlook when reasoning about ordering. Politeness delay caps the rate per host, so the effective cost of a fetch depends on which host it goes to: a request to a host with a thirty-second delay costs thirty seconds of that host’s capacity, and the same request to a fast host costs a fraction of a second. Ordering by value per fetch without dividing by the host’s delay will systematically over-fetch slow hosts, because their URLs look as valuable as anyone’s while costing far more.

The correct denominator is the marginal cost in the scarce resource, and the scarce resource differs by crawl. For a crawl bounded by its own bandwidth, the cost of a fetch is the response size. For a crawl bounded by politeness, it is the delay on the host. For a crawl bounded by the indexer’s throughput, it is the number of documents the indexer can absorb. A single priority formula cannot serve all three, and a crawler that does not know which constraint binds will optimize the wrong denominator. When the crawl is spread over several machines, the denominator also depends on which partition owns the host, since partitioning by host makes each machine’s capacity a separate constraint.

The last consideration is termination. A crawl that orders by value and never stops will keep finding low-value URLs at the margin forever, because the web is effectively infinite in the tail. The stopping rule is therefore part of the allocation: a budget, a deadline, or a marginal-value threshold below which a fetch is not worth its cost. All three produce a crawl that ends, and the choice among them determines what the index looks like when it does.