Hedged Requests and the Arithmetic of Tail Latency

A request that fans out to twenty shards completes when the slowest of the twenty completes. If each shard responds within 100 milliseconds at the 99th percentile, the probability that at least one of the twenty exceeds 100 milliseconds is 1 - 0.99^20, which is about 18 percent. The aggregate p99 is not the shard p99; the aggregate’s median is somewhere near the shard’s p80.

That multiplication is the reason tail latency in a fan-out system is a different quantity from tail latency in a single service, and it is the reason the techniques that address it look nothing like the ones that address mean latency.

The maximum of many draws

For independent draws from a distribution with CDF F, the maximum of n draws has CDF F(x)^n. The percentile that was p for one draw becomes, for the maximum, the value at which F(x)^n = p, i.e. F(x) = p^(1/n).

At n = 20 and p = 0.99, the required per-shard percentile is 0.99^(1/20) ≈ 0.9995. A shard’s p99.95 becomes the fan-out’s p99. The gap between those two percentiles is where the expensive engineering lives.

Independence is an assumption, and it fails in a specific way. When the shards share a rack, a switch, a runtime, or a garbage collector behaviour, the tails correlate, and F(x)^n understates the aggregate tail. The true behaviour is closer to the maximum of a much smaller effective number of independent draws plus a common component that affects all of them at once. Correlation is why fan-out latency has a floor that no per-shard improvement can move: the shared component sets it.

Hedging as a bet on the tail

A hedged request sends a second copy of the request to a different replica after a delay, without cancelling the first, and takes whichever answer arrives first. The delay is the parameter: it is chosen so that most requests have already completed by the time the hedge fires, which means the extra load is proportional to the fraction of requests that are slow rather than to all of them.

If the hedge fires at the 95th percentile of the latency distribution, roughly five percent of requests generate a second request. The extra load is five percent. The latency of the aggregate becomes the minimum of two draws, conditional on at least one of them having been issued before the hedge.

The minimum of k draws has CDF 1 - (1 - F(x))^k. Hedging at a delay d means the second draw is offset by d, so the completion time is min(T₁, T₂ + d). For the requests that were going to be slow, the second attempt starts at d and completes at d + T₂, and if T₂ is typical the result is roughly d plus a typical latency instead of the original slow latency.

The arithmetic that makes this work is the shape of the tail, not its magnitude. A latency distribution with a heavy tail has the property that a slow request is slow because of an uncommon event, and a second independent attempt is unlikely to encounter the same event. If the tail is heavy because of a shared resource, the second attempt encounters it too, and the hedge doubles the load without improving the latency. Distinguishing those two cases is the entire question of whether hedging is appropriate for a given dependency.

Choosing the delay

The delay trades load against latency reduction, and the exchange rate is steep at first and flattens.

Hedging at the median means half the requests are duplicated, and the aggregate latency approaches the minimum of two draws, which is a large improvement for a hundred percent load increase. Hedging at the 99th percentile duplicates one percent of requests and improves the requests that were already past the 99th percentile, which is a small population. The useful region is somewhere between, and the choice depends on the cost of the extra load and the value of the tail improvement.

The delay also has to exceed the point where the two attempts would collide in the dependency’s own queue. Two copies of the same request arriving at the same backend within microseconds do not diversify anything; they queue behind each other. Hedging at a delay shorter than the dependency’s service time is nearly useless, because the second copy reaches the backend while the first is still being served and waits behind it.

func hedged(ctx context.Context, delay time.Duration, urls []string) (*http.Response, error) {
	type result struct {
		resp *http.Response
		err  error
	}
	ch := make(chan result, len(urls)) // buffered: losers must not block
	for i, u := range urls {
		go func(i int, u string) {
			if i > 0 {
				select {
				case <-time.After(time.Duration(i) * delay): // stagger, do not fire together
				case <-ctx.Done():
					return
				}
			}
			req, err := http.NewRequestWithContext(ctx, http.MethodGet, u, nil)
			if err != nil {
				ch <- result{nil, err}
				return
			}
			resp, err := http.DefaultClient.Do(req)
			ch <- result{resp, err}
		}(i, u)
	}
	res := <-ch
	return res.resp, res.err
}

The channel is buffered so a losing goroutine does not block forever on a send that nobody reads. That detail is not cosmetic: an unbuffered channel here leaks a goroutine per hedge until the context is cancelled, and if the context is not cancelled the leak is permanent. The losing responses are also never read, so their bodies are never closed and their connections are never returned to the pool; a real implementation drains and closes them, which costs a read of whatever has already arrived.

Cancelling the loser, and the work that survives

Cancelling the losing attempt is the obvious optimisation and it is only partly effective. Cancellation propagates through the transport to the second replica, which stops the handler if it checks its context. It does not undo anything the handler already did. A hedge against a write endpoint can produce two writes unless the endpoint is idempotent on a request key, and the window in which both are in progress is exactly the delay plus the service time.

The consequence is that hedging is safe for reads and requires idempotency for writes. For a write, the second attempt has to carry the same idempotency key as the first, so that whichever replica processes it second either returns the first result or is rejected as a duplicate. Cancellation Propagation and the Work That Outlives Its Caller describes why cancellation is a signal and not a rollback.

There is also a resource asymmetry. A hedged request occupies two concurrency slots for the duration of the overlap, so a service that limits its own in-flight count must count hedges against that limit. A hedge that ignores the limit is an unaccounted doubling of load at exactly the moment the limit is trying to constrain it. The limit described in Concurrency Limits Derived from Little’s Law has to be sized with the hedge rate in mind, or the hedge has to be suppressed when the limit is at its ceiling.

Request-level versus queue-level remedies

Hedging attacks the tail at the client. The alternative is to reduce the tail at the source, and the two have different costs.

Queue-level remedies reduce the probability of a slow response by removing the mechanisms that produce it: shorter queues so a request cannot wait behind many others, smaller work units so a request cannot be stuck behind a long one, and priority so a latency-sensitive request is not queued behind a batch job. These reduce the tail for everyone and require changes at the server. The techniques in Bounded Queues and Load Shedding at the Admission Boundary belong to this family.

Client-level remedies accept the tail and route around it. Hedging is the main one, and it requires only that the client has alternative replicas and can tolerate the extra load. It also degrades gracefully: when the dependency is healthy, the extra load is proportional to the tail probability; when the dependency is failing broadly, hedges fail too, and the correct response is to stop hedging rather than to hedge harder.

The failure mode of client-level remedies is that they are invisible to the server. A dependency receiving hedged traffic sees more requests without any indication of which ones are duplicates, so its own capacity planning counts them as real demand. A server that could serve 1000 real requests per second and receives 1050 with hedging is at 105 percent of its intended load, and the extra five percent is the first thing to push it past the knee.

Percentiles are not additive

A hedge reduces the tail of a single call. A fan-out combines many calls by maximum. The two compose, and the composition is the reason fan-out latency is so hard to move.

If each of twenty shards is hedged and each hedge reduces the per-shard p99 from 100 to 40 milliseconds, the fan-out p99 becomes the maximum of twenty draws from the improved distribution, which is close to the improved p99.95. The hedge has to improve the extreme percentile, not the p99, because the fan-out is sampling the extreme. A hedge tuned to fire at the p95 improves the p99 and leaves the p99.9 where it was, which is the percentile the fan-out actually uses.

The measurement problem compounds this. Percentiles are not averages, and they do not combine across services: a request that passes through three services has a latency that is the sum of three draws, and the p99 of the sum is not the sum of the p99s. It is usually lower, because the three draws are unlikely to all be at their p99 simultaneously, and occasionally much higher, when they are. Any argument of the form “the first service’s p99 is 50 and the second’s is 40, so the total p99 is 90” is wrong in both directions, and it is wrong often enough that latency budgets built that way are unreliable.

When not to hedge

Hedging requires spare capacity, and its purpose is to use capacity that would otherwise be idle to reduce latency. A dependency at ninety percent utilization has no spare capacity; a hedge there takes a slot from a request that needed it and gives it to a duplicate. The correct precondition is measured headroom, and the correct behaviour when headroom disappears is to disable hedging, which means the hedge rate has to be a runtime parameter rather than a constant.

Hedging also requires that the replicas be genuinely independent in their failure modes. Two replicas on the same host, or behind the same load balancer that is the actual bottleneck, share the tail and the hedge does nothing. Verifying independence is harder than assuming it, and the assumption is usually wrong in exactly the cases where the tail matters.

The residual case is the dependency whose tail comes from a source the client cannot influence and cannot route around: a shared lock, a global cache, a single leader. Hedging against a single leader is pure duplication, and the only remedies are reducing the work or reducing the contention, neither of which is a client-side technique.