Hedged Requests, Tied Requests, and the Cost of Buying Back the Tail

Tail latency is resistant to the usual optimizations because it is not caused by the same thing as the mean. Speeding up the common path moves the median and leaves the tail roughly where it was. A different class of techniques accepts the distribution as given and instead reduces the probability that a user request waits on a member of the tail: it issues the work more than once and takes whichever copy finishes first.

That is a purchase, and like any purchase it has a price. The price is extra work, extra load, and extra state that has to be resolved when the copies disagree or when both succeed. Whether the purchase is worth making depends on the shape of the latency distribution and on how close the system is to saturation, and the accounting is what turns an appealing idea into a defensible one.

The condition under which duplication pays

Hedging reduces latency only if the slow part of the distribution is a minority of requests and the requests are independent. With independent draws from a distribution whose $p$-th percentile is $T$, the probability that a single copy exceeds $T$ is $1-p$; for two copies it is $(1-p)^2$. A p99 of one second becomes a p99.99 of one second, in the sense that the fraction exceeding one second falls from one percent to one ten-thousandth.

The gain is largest where the distribution’s tail is far from its median, which is the normal situation for the systems where hedging is used. A service with a median of 10 milliseconds and a p99 of 1 second has a tail that is 100 times its median, and a second copy makes a substantial difference to that tail. A service with a median of 10 milliseconds and a p99 of 15 has almost nothing to gain, because the second copy is nearly certain to be drawn from the same narrow range and the best of two draws saves only a fraction of the spread.

The independence assumption is the one that fails most often, because correlated slowness is what large systems actually experience: a link that is congested, a shared dependency that is degraded, or a host that is running a background job affects both copies. Correlated slowness does not merely reduce the gain; it can invert it, since both copies then occupy capacity that could have served other requests. The practical implication is that the copies must be routed through paths that fail independently, which is a property of the routing layer rather than of the client, and a hedge issued to the same replica set as the original is not a hedge.

Deriving the hedge delay

Issuing both copies simultaneously halves the expected latency but doubles the work rate immediately. The alternative is to issue the second copy only after a delay, so that the copies overlap for the duration of the original’s overshoot rather than for its whole duration.

The right delay is around the high percentile of the distribution, not the median. If the delay is set at the median, half of all requests get a second copy, which doubles the work rate; if it is set at the p95, then five percent of requests trigger a hedge, and the average work multiplier is 1.05 while the requests that were slowest get the benefit. Setting the delay slightly above the p95 is the common choice, and moving it up or down trades work for tail reduction continuously.

The multiplier has a simple form. Let the delay be the $q$-th percentile of service time. Then a fraction $1-q$ of requests trigger a second copy, so the offered work rate is $1 + (1-q)$ times the request rate, before accounting for cancelled copies. A p99 delay gives a work multiplier of about 1.01; a p50 delay gives 1.5. The measured multiplier is lower than that when the second copy is cancelled as soon as the first completes, which is the next piece of the mechanism.

import concurrent.futures, time

def hedged(call, delay_s, timeout_s, pool):
    """Issue a copy; if it has not returned after delay_s, issue a second and
    take the first result. Both copies are cancelled once one completes."""
    first = pool.submit(call)
    time.sleep(delay_s)
    if first.done():
        return first.result(timeout=0)        # fast path: no duplicate issued
    second = pool.submit(call)
    done, _ = concurrent.futures.wait(
        (first, second), timeout=timeout_s,
        return_when=concurrent.futures.FIRST_COMPLETED)
    for f in (first, second):
        if not f.done():
            f.cancel()                        # the losing copy stops here
    if not done:
        raise TimeoutError("both copies exceeded the timeout")
    return next(iter(done)).result()

The cancel call only stops work that has not started; a copy already executing continues until it observes the cancellation, which is why the saving depends on how co-operatively the callable checks for it.

Cancellation makes the losing copy cheap, not free

When the first copy returns, the second is no longer needed. Cancelling it stops the remaining work and releases the capacity it would have consumed. The saving is real, and its size depends on when the cancellation is delivered relative to the remaining work: a copy that has been running for 900 milliseconds of a one-second operation saves about a tenth of the work, while a copy cancelled immediately saves nearly all of it.

Cancellation is not instantaneous, and it has three costs that are easy to overlook. The signal has to travel, so a copy executing on a remote host continues until the signal arrives; the interval is at least a round trip and can be much longer if the work does not check for the cancellation flag. The cancellation must propagate to any work the copy started downstream, or the abandoned copy continues to occupy resources at lower tiers where the saving was expected. And the work must be safe to abandon, which excludes anything that has already committed a side effect.

Idempotence determines how much of this is available. Reads can be cancelled freely. Writes that are idempotent can be cancelled as long as the mechanism for detecting duplicates is in place, because the retry and the original will produce the same result. Non-idempotent writes, such as a counter increment or a message publish, cannot be hedged without an explicit deduplication token that the target uses to reject the second copy.

Tied requests and the round trip they cost

A different problem arises when the work is stateful and the two copies would both attempt to perform it. Sending the same write to two replicas of a stateful service risks applying it twice, and applying it once requires that the replicas agree about which one performs it.

Tying solves this by sending the request to a small set of replicas and having each of them inform the others of the time at which it received the request. The replica whose arrival time is earliest wins and performs the work; the others wait for the outcome rather than executing it. The mechanism converts the duplicate execution into a duplicate notification, which is much cheaper.

The cost is a communication step before execution: each replica must hear from the others before it can decide, so the request’s latency floor becomes at least one cross-replica round trip in the worst case. In a system where a round trip is a few hundred microseconds within a datacenter, that is a real but modest addition to a request that would otherwise take milliseconds. Across regions it is tens of milliseconds, which exceeds the tail it was meant to remove.

The variant that avoids the extra round trip has the replicas start executing provisionally and coordinate only over whether to commit. The coordination still requires a round trip, but it overlaps with the work rather than preceding it, so the latency cost is hidden rather than avoided. The price is that both replicas may perform the work before one is told to discard its result, which brings back the duplicate-execution cost that tying was designed to eliminate.

Hedging under saturation

Every hedging scheme adds work in proportion to the request rate, and work is exactly the resource that is scarce when a system is near capacity. The extra work raises utilization, and utilization raises queueing delay for all requests, including those that are not hedged. If the utilization curve is steep, the increase in the mean can exceed the reduction in the tail.

This is the reason hedging belongs with admission control rather than instead of it. A hedged request issued into a saturated system delays the original request that is already in the queue and everything behind it, and the reduction in the tail of the hedged request’s own latency is purchased from the tail of other requests. In the language of queueing, hedging is a transfer, and the transfer is favourable only when the system is below the knee of its utilization curve.

The measurement that makes the decision defensible is the work multiplier alongside the end-to-end tail. If the hedged tail falls while the multiplier stays near one, the copies are being issued rarely and cancelled cheaply. If the multiplier rises toward the delay percentile’s complement and the tail does not improve, the second copies are arriving into a saturated path where they do not win races, and the configuration is adding load for nothing.

A useful safety property follows: hedging should be disabled when the service’s own queue depth or latency already exceeds its normal band. The signal is available locally, since the service knows whether it is behind, and it is the same signal that drives the shedding policy described in Bounded Queues, Backpressure, and What to Drop Under Overload. A hedge issued by a client into a queue that is already over its target is not reducing latency; it is adding to the queue.

Where the technique does not apply

Hedging requires the copies to be interchangeable, which means the operation must be free of ordering constraints with respect to other operations and must produce the same result regardless of which copy wins. Operations on shared mutable state with a strict order, such as appending to a log, do not qualify without a mechanism that serializes them.

It requires that the extra work be cheap relative to the tail it removes. For an operation whose service time is dominated by a shared, fixed cost, such as a large scan or a lock held across the operation, the second copy does not shorten the critical section; it contends for it. The gain from duplication comes from variance in the copies’ durations, and where the duration is set by a shared bottleneck, variance is not what limits the request.

It requires a client that can wait for the best of several results without amplifying error. A hedged request that fails on one copy and succeeds on the other is a success, but the accounting has to treat it as one, or the failure counters will double-count and the retry logic may issue a third copy on top of the hedge.

Finally, hedging reduces the tail of the latency distribution without changing the underlying straggler rate. The stragglers still occupy capacity and still delay whatever shares their queue, which is why the technique is complementary to reducing the sources of variance: the shorter the tail, the less there is to hedge, and the cost of hedging falls with it. The variance reduction that makes the tail shorter is the same $C_s^2$ term that governs queueing delay, described in Utilization and the Nonlinear Growth of Waiting Time; the two techniques act on the same quantity from opposite directions.