Hedged Requests and the Economics of Tail Tolerance

A tail latency problem has two possible responses. The first is to make the slow requests fast, which means finding the mechanism that makes them slow and removing it: variance reduction, contention removal, or capacity. The second is to accept that some requests will be slow and to stop waiting for them, by issuing the same request to a second backend and taking whichever answers first. The second response does not fix anything; it converts a latency problem into a load problem, and the conversion is favourable only under conditions that can be stated precisely.

The technique is hedging, and its arithmetic is the arithmetic of the minimum of two random variables. If one backend’s response time exceeds a threshold with probability p, two independent backends both exceed it with probability p². The tail shrinks quadratically in probability, which means the latency at a fixed percentile falls steeply for the upper percentiles. The cost is that every request for which the hedge fires generates a second request, and the second request consumes backend capacity whether or not its response is used.

The delay is the whole design

A hedge that fires immediately is just a duplicate request: it doubles load and halves nothing, because both copies race and the loser’s work is discarded. The hedge must fire after the point at which the original has become suspiciously slow, so that the common case, a fast response, never triggers a duplicate. The firing delay is therefore the parameter that determines both the benefit and the cost.

Set the delay at the distribution’s median and half of all requests are hedged, which is untenable load. Set it at the ninety-fifth percentile and about five percent are hedged, which is affordable, and the effect is on the tail beyond the ninety-fifth percentile: a request that would have taken the ninety-ninth percentile time now completes at roughly the delay plus the second backend’s service time, which is close to the median. The tail beyond the delay is compressed toward the delay itself.

The choice of delay is thus a choice of which percentile to sacrifice to gain the ones above it. The hedged requests’ latency is bounded below by the delay, because a hedge cannot complete before it fires, so the technique raises the floor of the tail while lowering its ceiling. A delay set too low raises the floor for many requests and buys a ceiling that was already acceptable; a delay set too high leaves the tail intact.

// Hedge after d: first response wins, the loser is cancelled.
func hedged(ctx context.Context, d time.Duration, call func(context.Context) (*Resp, error)) (*Resp, error) {
    ctx, cancel := context.WithCancel(ctx)
    defer cancel()
    type result struct{ r *Resp; err error }
    ch := make(chan result, 2)
    go func() { r, err := call(ctx); ch <- result{r, err} }()
    select {
    case res := <-ch:
        return res.r, res.err            // fast path: no hedge issued
    case <-time.After(d):
    }
    go func() { r, err := call(ctx); ch <- result{r, err} }()
    res := <-ch
    cancel()                              // tell the loser to stop
    return res.r, res.err
}

The cancel is not cosmetic. Without it the losing request continues to completion, holding a connection and consuming backend capacity for a result nobody reads. Cancellation propagation is what makes the load cost proportional to the duration of the hedge rather than to the full service time, and it requires the backend to notice the cancellation, which for a request already queued or in the middle of a database query it often cannot.

The load arithmetic

Suppose a fraction h of requests are hedged, and each hedge adds one more request to the backend. The backend’s offered load becomes (1 + h) times the client-visible rate. With h = 0.05, the increase is five percent, which is small. With h = 0.2, it is twenty percent, which is a capacity decision.

The subtlety is that h is not a constant. It is the probability that the original request exceeds the delay, and that probability rises when the backend slows. A backend at 70 percent utilization has a small fraction above a high percentile; the same backend at 90 percent utilization has a much larger fraction, because the whole distribution has shifted right. So hedging fires more often exactly when the backend is least able to absorb the extra load, which is a positive feedback loop of the same shape as retries.

This is the central hazard. Hedging is safe when the backend has headroom and dangerous when it does not, and the transition between the two is not visible to the hedger. A hedge delay chosen against a healthy distribution becomes an amplifier during degradation: the first slow responses trigger duplicates, the duplicates raise load, load raises latency, latency triggers more duplicates. The mechanism is identical to the retry storm, with the difference that a hedge fires on slowness rather than on failure, so it can start before any error is visible.

The defence is a budget. Limit the fraction of requests that may be hedged at any moment, measured as a rate rather than as a probability, and stop hedging when the budget is exhausted. That converts the feedback loop into a bounded amplifier: hedging can add at most the budgeted rate of extra requests, regardless of how slow the backend becomes. A budget expressed as a fraction of the primary rate is easier to reason about than one expressed as an absolute count, because it scales with traffic.

Which requests may be hedged at all

A hedge is a duplicate execution, and duplicate execution is only safe for operations that are idempotent. An idempotent operation produces the same effect whether executed once or several times; a non-idempotent one such as an insert without a unique constraint, an increment, or an append, produces a different state when the duplicate lands. HTTP’s notion of idempotent methods makes the distinction explicit for requests: the methods defined as idempotent can be repeated without changing the intended effect, and others cannot.

The practical difficulty is that the losing request may have already taken effect before it is cancelled. Cancellation is a request to stop, not a guarantee that nothing happened; a backend that has already written to storage will not undo the write because the client went away. Hedging a non-idempotent operation therefore risks applying it twice, and the risk is highest exactly when the hedge fires, since that is when the original was slow, plausibly because it was doing the work.

Three mitigations exist and none is complete. Restrict hedging to reads and to writes with a client-supplied idempotency key that the backend uses to deduplicate. Make the write path’s first step a reservation that is idempotent by key, so a duplicate reservation is a no-op. Or accept the duplication and make the operation’s semantics tolerate it, which is only possible for operations whose effect is naturally idempotent, such as setting a value to a fixed result.

The information asymmetry between the two copies

A hedged request’s two copies are not equivalent, because the second one is issued later and knows more. The hedger knows the original has not completed by the delay, which is evidence that the original is slow, which is evidence that should inform where the duplicate goes. Sending the duplicate to a backend chosen at random ignores that evidence; sending it to a backend that the original did not use, chosen by the load signal described in power of two choices and the cost of a random probe, uses it.

The evidence also argues against sending the duplicate to the same backend. If the original is slow because that backend is slow from a garbage collection pause, a lock wait, or a saturated disk, the duplicate will be slow too, and the hedge buys nothing while costing a full request. If the original is slow because of a network path or a queue in front of the backend, a duplicate to the same backend may still help, because the second request may take a different path through the queue. The distinction requires knowing where the slowness lives, which is what per-request tracing provides.

A further asymmetry: the original request’s client-visible latency includes the delay, so a hedged request’s latency is never below the delay even when the original was about to complete. That is the floor mentioned above, and it is why the technique is applied to the upper percentiles rather than to the distribution as a whole.

Interaction with fan-out

Hedging is most valuable where fan-out has already amplified the tail, since a fan-out request waits for its slowest component and the hedge targets exactly that component. The combination has an arithmetic of its own: a fan-out of width w, each component hedged with probability h, generates up to w(1 + h) requests, and the probability that a fan-out request contains at least one hedge is 1 − (1 − h)^w, which approaches one quickly. A hedge probability of five percent across a fan-out of twenty means most fan-out requests contain a hedge, and the load increase is not five percent of the fan-out’s load but closer to the full five percent per component, summed.

The amplification described in fan-out and the amplification of tail latency therefore compounds with hedging’s own amplification. A design that applies both must account for the product, and the accounting is easiest when the hedge budget is expressed at the fan-out request level rather than at the component level: a request may hedge at most one of its components, so the total extra load is bounded by the fraction of requests that hedge rather than by the width.

What the tail looks like afterwards

A hedged service’s latency distribution has a distinctive shape. Below the delay it is the original distribution, unchanged, because no hedge fired. At the delay there is a discontinuity: requests that were about to complete just after the delay are now more likely to complete at the delay plus a second backend’s service time, which may be shorter or longer. Above the delay the distribution is compressed, because a request that would have taken ten times the median now takes the delay plus roughly the median.

The compression has a limit. If both copies are slow because the slowness is in a shared dependency or in the caller, the hedge does nothing, and the tail remains. Hedging works on independent slowness, the same independence assumption that the fan-out arithmetic rests on, and it fails on correlated slowness. A service whose tail is caused by a shared database will not be fixed by hedging; it will be made worse, because the duplicate adds load to the shared dependency.

Measuring the result requires care, because the hedged requests’ latency is the minimum of two completion times and the unhedged requests’ latency is a single completion. A histogram that mixes them describes a mixture whose shape depends on the hedge rate, which varies with load. Reporting the hedged and unhedged populations separately, and reporting the hedge rate alongside the latency, keeps the distribution interpretable. Without that separation, the measured improvement looks larger than it is, because the hedged population’s improvement is attributed to the whole.

When not to hedge

Hedging is the wrong instrument in four situations, and each is recognizable.

When the tail is caused by a shared resource, hedging adds load to that resource and makes the tail worse. When the operation is not idempotent and cannot be made so, the duplicate risks a second effect. When the backend is near saturation, the added load pushes it further along the utilization curve described in queueing delay and the cost of service-time variance, and the hedge’s benefit is swamped by the load’s cost. And when the tail is small enough that the delay would have to be set below the median to catch it, the hedge fires on most requests and the load doubles for a marginal gain.

The situations where it is the right instrument share a structure: the tail is caused by independent, transient slowness at individual backends, the operation is idempotent, and there is capacity headroom to absorb a bounded increase in load. Those conditions describe a service whose tail is a statistical artefact of many independent components rather than a symptom of a saturated dependency, and hedging is precisely the tool for that case: a way of buying the tail down with capacity that is otherwise idle.

The measurement discipline from coordinated omission in latency measurement applies with full force here. A hedge changes the relationship between offered load and observed latency, and a closed-loop measurement of a hedged service will report the improvement while hiding the load increase that paid for it. The two numbers, latency and the extra request rate, have to be reported together, or the technique looks free when it is not.