Skip to content

Hedging Requests to Cut Tail Latency

Retries fire after a failure. Hedging fires after a delay: if the first attempt has not answered within the time a healthy call normally takes, send a second one and use whichever answers first. When the slow case is caused by something specific to one attempt — an unlucky node, a garbage-collection pause, a cold cache, a queue behind a single connection — the second attempt is an independent draw from the same distribution, and the caller's latency becomes the minimum of two samples instead of one. Measured on 400 calls against an upstream that is fast 90% of the time and slow 10% of the time, hedging after 50 ms cut p99 from 576.5 ms to 125.5 ms for 14% extra upstream calls.

Prerequisites

  • Python 3.11+. The implementation uses asyncio.wait with FIRST_COMPLETED and a timeout.
  • Retry classification from classifying retryable errors — hedging is only safe for idempotent requests, always.
  • Amplification control from retry budgets; hedges are amplification and should draw on the same budget.
What a hedged call looks like 4 lanes over time. What a hedged call looks like attempt 1 slow: still running cancelled hedge delay p95 of normal latency attempt 2 answers first caller waiting result returned time → The caller sees the faster of the two; the loser is cancelled, not awaited.

1. Implement the hedge

The whole mechanism is asyncio.wait with a timeout equal to the hedge delay: if nothing has completed, start another attempt and wait on both.

async def hedged(operation, *, delay: float, max_hedges: int = 1):
    tasks = {asyncio.create_task(operation())}
    try:
        for _ in range(max_hedges):
            done, _ = await asyncio.wait(tasks, timeout=delay,
                                         return_when=asyncio.FIRST_COMPLETED)
            if done:
                return done.pop().result()             # the first answer wins
            tasks.add(asyncio.create_task(operation())) # still nothing: hedge
        done, _ = await asyncio.wait(tasks, return_when=asyncio.FIRST_COMPLETED)
        return done.pop().result()
    finally:
        for task in tasks:
            if not task.done():
                task.cancel()                          # release the losers

The finally is not optional. Without it, every hedged call leaves a task running against the upstream, which converts a latency optimisation into a load leak — and, for a client with a connection pool, into pool exhaustion. Cancellation must reach the underlying request too, as covered in propagating cancellation through callback APIs; a cancelled task whose HTTP library keeps going has not released anything.

Verify: after a hedged call returns, no extra tasks remain and the client's active-connection count returns to baseline.

2. Measure the effect before believing it

Across the same 400 calls, with the hedge delay as the only variable:

policy p50 p95 p99 upstream calls
no hedging 32.2 ms 462.5 ms 576.5 ms 1.00x
hedge after 150 ms 32.2 ms 185.7 ms 325.7 ms 1.14x
hedge after 80 ms 32.2 ms 115.4 ms 186.0 ms 1.14x
hedge after 50 ms 32.2 ms 85.8 ms 125.5 ms 1.14x

Three things stand out. p50 does not move, because the median request finishes long before the hedge delay — hedging is a tail treatment and nothing else. The tail improves roughly in proportion to how early you hedge. And the cost is set by the fraction of slow requests, not by the delay: at every delay above p90, only the same 10% of calls get duplicated, so the amplification is identical.

Allowing a second hedge changed nothing measurable here (p99 125.7 ms versus 125.5 ms), because one hedge almost always lands. Extra hedges pay off only when the slow fraction is large — at which point the upstream probably has a problem that hedging is the wrong tool for.

Verify: compare p50, p95 and p99 with and without hedging on your own traffic; if p99 does not move, the slow case is not independent.

p99 latency by hedge delay 4 bars comparing no hedging with the others. p99 latency by hedge delay no hedging 576.5 ms hedge after 150 ms 325.7 ms hedge after 80 ms 186.0 ms hedge after 50 ms 125.5 ms 400 calls against an upstream that is fast 90% of the time and slow 10% of the time. The earlier the hedge, the shorter the tail — and the more duplicate load.

3. Pick the delay from your own latency distribution

The delay is the only tuning knob, and the rule is to set it near p95 of the normal distribution:

  • Below p50 — you duplicate most traffic for a tail you could have fixed by other means. That is a 2x load multiplier, not a hedge.
  • Around p95 — about 5% of requests are duplicated, the amplification is small, and the tail collapses. This is the standard choice.
  • Above p99 — you are hedging so rarely that the tail is barely affected; the 150 ms row above still left p99 at 325.7 ms.
delay = percentile(recent_latencies, 95)               # recomputed periodically

Deriving it from a live histogram rather than a constant keeps it correct as the upstream changes, and automatically disables hedging when the upstream slows down generally — because p95 rises with everything else, and a hedge that fires later duplicates less.

Verify: the configured delay sits between p90 and p99 of the last hour's latencies for that upstream.

4. Know when hedging makes things worse

Hedging converts spare capacity into lower latency. When there is no spare capacity, it converts a slowdown into an outage — every slow request becomes two, which makes more requests slow, which produces more hedges.

  • The upstream is overloaded. Hedging adds load precisely when load is the problem. A circuit breaker or a rising p95-derived delay should switch hedging off.
  • The work itself is slow. If the slow 10% are slow because the query is expensive, the hedge is equally slow and you have doubled the cost for nothing.
  • The request is not idempotent. A hedge is a deliberate duplicate request. Without an idempotency key, it is a duplicate side effect.
  • The hedge shares the bottleneck. A second request over the same connection, to the same pool-limited host, or into the same saturated queue is not an independent draw. Hedge to a different instance where you can.
Is hedging appropriate here? A decision on Why is the slow case slow with 3 outcomes. Is hedging appropriate here? Why is the slow case slow? an unlucky node or GC pause hedge a second try is independent the upstream is overloaded do not hedge you would add load the work itself is slow do not hedge every attempt is slow Hedging trades capacity for latency; it only works when there is capacity to trade.

Verify: during a load test that saturates the upstream, hedging is disabled — either by policy or by the delay rising with p95.

5. Budget and observe it

Hedges are extra upstream load, so they belong under the same retry budget as retries:

    if not budget.allow_retry():
        continue                                       # no hedge: wait for the original

Three metrics make the behaviour legible: the hedge rate (hedges per request — it should be near your delay's tail fraction), the hedge win rate (how often the hedge answered first — if near zero, the delay is too high or slowness is not independent), and the amplification factor, which was 1.14x in the runs above.

Verify: the hedge rate matches the expected tail fraction and the win rate is materially above zero.

What the tail reduction costs upstream 3 bars comparing no hedging with the others. What the tail reduction costs upstream no hedging 1.00x hedge after 50 ms 1.14x hedge 50 ms, up to 2 1.14x Only the requests that exceed the delay are duplicated, which is 10% of traffic here. Cost tracks the fraction of slow requests, not the total request rate.

Verification

Hedging is correctly deployed when:

  • Only idempotent operations are hedged, or every request carries an idempotency key.
  • Losers are cancelled in a finally, and the cancellation reaches the upstream.
  • The delay tracks p95 of the recent latency distribution rather than a hard-coded constant.
  • p50 is unchanged and p99 improves in your own measurements.
  • Hedges draw on the retry budget and are counted in amplification metrics.
  • Hedging disables itself under overload, by breaker or by a rising delay.

Pitfalls & edge cases

  • Awaiting the loser. await asyncio.gather(*tasks) after returning defeats the purpose; cancel, do not collect.
  • Hedging a streaming response. Two half-consumed streams is not a result; hedge the connection or the first byte, not the whole stream.
  • Hedging writes. Even with an idempotency key, two concurrent writes with the same key can race in a server that checks-then-inserts.
  • A fixed delay that ages. An upstream that got slower turns a p95 delay into a p40 delay, doubling load silently.
  • Error handling across attempts. If the first attempt fails fast with a deterministic error, the hedge will too; return the error rather than waiting out the delay.
  • Client-side bottlenecks. A connection pool sized for one request per call will queue the hedges, so the measured benefit vanishes; raise the pool limit alongside.

Frequently Asked Questions

What is request hedging?

Sending a second, identical request when the first has not answered within a chosen delay, and using whichever responds first. Unlike a retry it does not wait for a failure — it treats slowness itself as the trigger, which is why it reduces tail latency rather than improving success rates.

How much does hedging reduce p99 latency?

It depends on how independent the slow cases are. In the measurements here — 10% of calls slow, hedge after 50 ms — p99 fell from 576.5 ms to 125.5 ms while p50 was unchanged, at the cost of 14% more upstream calls. If slowness is caused by overload, hedging makes things worse instead.

What hedge delay should I use?

Around p95 of the upstream's normal latency, computed from a live histogram rather than hard-coded. Below p50 you duplicate most of your traffic; above p99 you barely touch the tail. A delay derived from recent latencies also backs off automatically when the upstream slows down generally.

Is hedging safe for POST requests?

Only with an idempotency key the server honours. A hedge is a deliberate duplicate request, so any non-idempotent operation may take effect twice. For safe methods — GET, HEAD, and idempotent PUT or DELETE — no extra machinery is needed.

How do I cancel the losing hedged request in asyncio?

Keep every attempt in a set, return as soon as asyncio.wait reports FIRST_COMPLETED, and cancel the rest in a finally block. Make sure the cancellation reaches the underlying client, because a cancelled task whose HTTP request continues has not released the connection or reduced the load.