Adaptive Per-Host Rate Control from Latency and Error Signals

A fixed delay is safe and wasteful. It is safe because it never asks a server for more than a known amount, and wasteful because most servers can absorb more than the floor a cautious crawler chooses, and the crawl therefore takes longer than it needs to. Adaptive control tries to recover that waste by treating the request rate as a variable to be adjusted from evidence: fast responses and clean status codes permit a higher rate, slow responses and rejections force a lower one.

The evidence available to a crawler is much poorer than the evidence available to a transport protocol. A crawler sees one request at a time per host, so it has no packet-level signal, no acknowledgement stream, and no way to distinguish a server that is busy from a path that is congested. What it has is a sequence of response latencies and status codes, and a strong prior that a server which starts rejecting requests is telling the truth about its capacity. Building a controller from that is possible, but the loop has properties that make naive versions oscillate.

The signals and what each one means

Response latency is the primary continuous signal. For a given host, the time from request start to the first byte of the response includes DNS resolution (usually cached), connection setup (usually pooled), the request, and the server’s queueing and processing. Only the last of those responds to load in the way a controller wants: a server under pressure queues requests, so latency rises before anything else fails.

The confound is that latency also rises for reasons unrelated to load — a slow origin behind a CDN, a large response body, a long database query on one particular page. A controller that treats every latency increase as a capacity signal will throttle a host for serving a big page. The standard mitigation is to use a low quantile of latency rather than the mean: the tenth or twentieth percentile of recent response times reflects the floor cost of contacting the host, and a page-specific slow query does not move it. When the floor itself rises, the host is under load.

Status codes are the discrete signal. A 429 or a 503 with Retry-After is an explicit instruction and should dominate any inference. A 503 without Retry-After still says the server is unavailable, and a crawler should back off by a bounded amount rather than guess a duration. A 500 says something failed, which may be the crawler’s fault (a malformed request) or the server’s; treating it as a load signal is a guess. A rising share of connection timeouts and resets is the strongest negative signal available and the one most likely to be caused by the crawler itself.

A useful separation is between signals that are authoritative and signals that are inferred. Authoritative signals are instructions from the server: Retry-After, Crawl-delay, a 429. They set a hard floor on the interval. Inferred signals — latency percentiles, timeout rates — may only move the rate within the range the authoritative signals permit. Conflating them produces a controller that argues with a server’s explicit instruction because its own measurements look fine.

An additive-increase, multiplicative-decrease loop

The shape that works is borrowed from transport congestion control because the constraints are similar: increase cautiously, decrease sharply, and never increase faster than the evidence supports.

Each host carries a state: a current interval between request starts, a threshold recording the interval at which the host last objected, and a baseline latency. The loop runs after every response.

class HostRate:
    def __init__(self, floor=0.5, ceiling=30.0):
        self.floor = floor          # minimum seconds between starts
        self.ceiling = ceiling      # maximum, when backing off hard
        self.interval = 1.0
        self.ssthresh = 4.0         # interval at which the host last objected

    def on_response(self, status, latency, baseline):
        if status in (429, 503):
            # authoritative: double the interval, then honour Retry-After
            self.interval = min(self.ceiling, self.interval * 2.0)
            self.ssthresh = self.interval
            return
        if status >= 500 or latency > 3.0 * baseline:
            self.interval = min(self.ceiling, self.interval * 1.5)
            return
        if self.interval > self.ssthresh:
            # far below the last known limit: probe multiplicatively
            self.interval = max(self.floor, self.interval * 0.9)
        else:
            # near the limit: approach additively, small overshoot
            self.interval = max(self.floor, self.interval - 0.05)

The asymmetry is the important part. Shrinking the interval by a factor on success would double the rate every round trip, which reaches an unsafe rate in a handful of requests and does so before the server has had a chance to signal that it is unhappy. Increasing the interval by a fixed increment on failure is equally wrong in the other direction: it takes many failures to undo one optimistic increase, and the crawler keeps hammering a host that has already said stop.

The two-phase increase deserves explanation. While the interval is well above the threshold, meaning the rate is far below where the host last complained, it shrinks multiplicatively and the rate climbs quickly. Once the interval falls to or below the threshold, the shrink becomes additive, so the approach to the limit is slow and the overshoot is small. The threshold is set from the last observed failure, which is the controller’s memory of where the host last complained.

The floor is a hard constraint and it is not negotiable by the controller. A host that responds in one millisecond does not license a hundred requests per second; the floor encodes the crawler’s own politeness commitment, and the adaptive loop operates entirely above it. This is the structural difference between a crawler’s controller and a transport’s: the transport is trying to fill a pipe, and the crawler is trying to stay under a social limit that it cannot measure.

Why the loop needs damping

Three feedback paths make the naive loop unstable.

The first is measurement lag. A rate increase takes effect on subsequent requests, and those requests’ latencies reflect the server’s state some time after the increase. If the loop reacts to each response immediately, it can increase several times before the first increase’s effect appears, then decrease several times in response to a backlog that its own earlier increases created. The result is a sawtooth that spends much of its time at the wrong rate.

Damping helps: update the rate at most once per k responses, or once per interval of wall-clock time, so the loop’s bandwidth is below the plant’s response time. Choosing k is the same problem as choosing a control period anywhere else, and the honest answer is that it depends on the host’s latency distribution, which the crawler is measuring anyway.

The second path is that per-host rates are not independent. A crawler running many hosts at once shares its own uplink, its own DNS resolver, and its own connection pool. When the aggregate rate saturates any of those, every host’s latency rises, every controller backs off, the aggregate rate falls, latencies recover, and every controller speeds up again. The oscillation is global and has nothing to do with any individual server’s capacity. The remedy is a global rate limit that the per-host loops operate beneath, so that shared-resource contention is attributed to the shared resource rather than to the hosts.

The third path is heterogeneity within a host. A single authority may serve some URLs from a cache and others from an origin, so latency alternates between two populations. A controller keyed on the mean sees a rate-dependent average and adjusts to it; one keyed on a low quantile sees the cache latency and concludes the host is idle even while the origin is saturated. Keying on a low quantile is still the better choice, but it should be paired with a separate check on the fraction of requests exceeding a threshold, so that a bimodal distribution is visible rather than averaged away.

What the controller cannot know

The controller infers capacity from behaviour, and behaviour is confounded by everything else on the server. A host that is slow because it is serving other clients is not slow because of the crawler, and backing off does not help it; it only makes the crawl longer. There is no signal in an HTTP response that distinguishes a server busy with its own traffic from a server that considers the crawler’s rate excessive. The 429 status is the closest thing to an explicit statement, and it is voluntary.

This is why the authoritative signals must dominate. A server that publishes a Crawl-delay has told the crawler what it wants; a controller that overrides that with its own measurements is substituting inference for instruction. A server that returns 429 has said stop; the interval doubling is not a heuristic but a compliance action.

The second thing the controller cannot know is whether its own probing caused harm. A rate increase that triggers a 503 may have caused an outage on a fragile server, and the fact that the crawler backed off afterwards does not undo it. Because the cost is asymmetric — a longer crawl versus a broken site — the probing phase should be slow and the floor should be conservative. A controller that spends most of its time near the floor is behaving correctly for a crawler; one that spends most of its time probing upward is optimizing the wrong objective.

Where adaptivity belongs in the stack

The controller sits above the frontier’s per-host queue and below the global scheduler. Its output is the timestamp advance after each fetch, replacing the constant delay that a fixed policy would use. Everything upstream — priority, host assignment, trap budgets — is unaffected, which is what makes the mechanism safe to add to an existing frontier: the queue contract is unchanged, and only the interval computation differs.

Its interaction with the freshness model is indirect but real. A shorter interval means more fetches per unit time from a host, which means the same politeness budget buys more revalidations, which changes the marginal value of a fetch from that host. A scheduler that assumes a fixed per-host cost will over-fetch hosts whose controller has driven the interval down and under-fetch the rest. Keeping the two mechanisms’ cost models consistent is a bookkeeping requirement rather than an algorithmic one, and it is the kind of inconsistency that produces a crawl which looks healthy in every individual component and distributes its effort wrongly overall — a failure that shows up as poor crawl order economics rather than as a rate-control bug.