What request hedging is and why fan-out tails dominate p99 latency

A hedged request, also called a backup request, is a second copy of a call sent to another replica while the original is still in flight. The client uses whichever good response arrives first and discards or cancels the other. A retry is different: it fires only after the first attempt has failed or timed out. Retries recover from errors. Hedging reduces latency variance, the case where a request succeeds but happens to land on a replica that is briefly slow.

Retry Hedged request
Trigger Failure or timeout Original still pending after a delay
Original call Abandoned Still racing
Targets Errors Tail latency
Typical cost Extra calls on failure Extra calls on slow responses

Hedging matters most in fan-out. When one user request depends on many backend calls, it completes only when the slowest call returns. Here is an illustrative estimate, assuming independent backends that are each slow 1 time in 100. A 100-way fan-out then hits at least one slow call in 1 − 0.99¹⁰⁰ ≈ 63% of requests. The 99th-percentile behaviour of each backend becomes the median behaviour of the whole request, so p99 latency at the edge is shaped almost entirely by rare per-replica stalls.

The teams that gain the most run read-heavy, fan-out services where those stalls are transient and local to one replica. Common causes are garbage-collection pauses, noisy neighbours on shared hosts, and cache misses on a single node. A second copy sent to a different replica is unlikely to hit the same stall.

How delay-based hedging works and how to choose the hedge delay

The client sends the primary request and starts a timer. If a response arrives before the timer fires, nothing else happens. If the timer fires first, the client sends a backup to a different replica, accepts whichever response comes back first and is valid, and cancels the other. The timer value is the hedge delay, and it is usually set near a high percentile of observed latency, such as p95.

That choice bounds the extra load. A backup is sent only when the primary has not answered by the threshold, so the added traffic is roughly the fraction of requests slower than that point. Requests that would have been fast never trigger a hedge.

Illustrative estimate: assume a service with a measured p95 of 40 ms and a hedge delay fixed at 40 ms. In steady state about 5% of requests exceed it, so the hedge adds about 5% more requests. Now assume a deploy or a traffic shift moves the whole distribution so that 40 ms sits at the old p75. About 25% of requests now trigger backups. The extra load has grown fivefold, and it arrives exactly when the service is already slower.

Adaptive delays address this by recomputing the threshold from a rolling latency histogram, so the delay tracks the current p95. The cost is complexity: you need window sizing, a minimum sample count, and floors and ceilings. Adaptive delays can also oscillate. Hedges add load, the added load raises latency, and the higher latency moves the threshold, which changes how many hedges fire.

+--------------+                                  +-----------+
|    Client    |--- t=0: primary request -------->| Replica A |
| start timer  |                                  +-----------+
| d ~ p95      |<-- reply before d: no hedge --------+     |
| (e.g. 40 ms) |                                           |
+--------------+                                           |
       |                                                   |
       | timer fires at t=d, no reply yet (~5%)            |
       v                                                   |
+--------------+                        +-----------+      |
| send backup  |--- t=d: backup ------->| Replica B |      |
| to another   |                        +-----------+      |
| replica      |                              |            |
+--------------+                              |            |
                                              v            v
                                      +---------------------------+
                                      | first valid reply wins;   |
                                      | cancel the loser (A or B) |
                                      +---------------------------+

Extra load ~= share of requests slower than d (illustrative estimate):
  d = 40 ms = p95, steady state ............ ~5% extra requests
  latency shifts, 40 ms now at old p75 ..... ~25% extra requests (5x)

Delay-based hedging: the client sends a backup to a different replica only if the primary has not replied within the hedge delay d, takes the first valid reply and cancels the other, so extra load tracks the share of requests slower than d (illustrative estimate).

Implementing hedging safely: budgets, caps, cancellation and idempotency

That feedback loop is why the hedging wrapper needs hard limits that don't depend on the delay estimate.

The wrapper sends the primary attempt and starts a timer set to the hedge delay. If the primary returns first, the timer is cleared and nothing else happens. If the timer fires, the wrapper asks a token bucket for permission before it sends a backup. The bucket refills at a fixed fraction of primary traffic, for example one token per twenty primaries. That bounds extra load at roughly hedge_rate ≤ budget_fraction × primary_rate, no matter how badly the delay is tuned. A per-request attempt cap, usually two in total, stops a single slow call from multiplying. The backup goes to a different replica than the primary, because the same replica would likely repeat the slowness. The first success wins. The wrapper then cancels the other attempt through the shared context or deadline, so the cancellation reaches the remote call.

Cancellation only saves anything if servers act on it. A server that ignores a cancelled deadline keeps doing the work: it burns CPU, finishes disk and network I/O, and issues its own downstream calls, which can fan out further. The client sees the capped load, but the cluster carries much more.

The correctness rule matters more than the load limits. Hedge only idempotent reads, or writes deduplicated by an idempotency key that the server enforces. Exclude every other mutation by default. Breaking this rule causes double charges, duplicate messages, and conflicting updates where the losing write lands last.

// Go-style hedging wrapper: hedge after delay, budgeted, max 2 attempts.
func Hedged(ctx context.Context, req Request, delay time.Duration) (Response, error) {
    // Correctness gate: plain mutations are never hedged.
    if !req.Idempotent && req.IdempotencyKey == "" {
        return pickReplica("").Call(ctx, req)
    }
    ctx, cancel := context.WithCancel(ctx)
    defer cancel() // on return, cancellation propagates to the losing call

    results := make(chan result, 2) // buffered: the loser never blocks
    budget.RecordPrimary()          // refills about 1 token per 20 primaries
    primary := pickReplica("")
    go func() { r, err := primary.Call(ctx, req); results <- result{r, err} }()

    attempts, received := 1, 0
    timer := time.NewTimer(delay)
    defer timer.Stop()
    var lastErr error
    for received < attempts {
        select {
        case <-timer.C:
            // Hedge only if under the per-request cap and the budget allows it.
            if attempts < 2 && budget.TryTake() {
                backup := pickReplica(primary.ID) // exclude the slow replica
                attempts++
                go func() { r, err := backup.Call(ctx, req); results <- result{r, err} }()
            }
        case res := <-results:
            received++
            if res.err == nil {
                return res.resp, nil // first success wins; defer cancels the other
            }
            lastErr = res.err
        case <-ctx.Done():
            return Response{}, ctx.Err() // caller deadline expired
        }
    }
    return Response{}, lastErr
}

A Go-style hedging wrapper that skips non-idempotent requests, hedges once after a delay if the token bucket allows, picks a different replica, and cancels the losing attempt via context.

Routing the backup and getting cooperation from the server side

A hedge that lands on the same replica as the original usually fails, because whatever stalled the first request (a GC pause, a hot disk, a saturated thread pool) is still there. Send the backup to a different replica, and preferably a different zone, so the two attempts fail independently. With client-side load balancing, exclude the replica that holds the original from the hedge's pick. Feed hedge outcomes into outlier ejection carefully: a cancelled original is not an error. Duplicates also inflate request counts and shift latency histograms, so least-request and EWMA-style balancers can misjudge load unless hedges are tagged and accounted for separately.

Purely client-side hedging accepts duplicate work as a cost. Server cooperation reduces that cost. With tied requests, each copy carries the identity of its sibling replica. The first replica to dequeue the request tells the other to drop its copy, so in the common case only one replica does real work. With queue-aware rejection, a replica whose queue is already deep refuses the hedge immediately. The client then hears "no" quickly instead of adding to the backlog.

Approach Duplicate work Server changes Main risk
Client-only hedge Up to the full second attempt None Extra load during slowdowns
Tied requests Mostly queue time only Cross-replica cancel signal Cancel message lost or late
Queue-aware rejection Near zero when busy Queue-depth check Reject threshold tuned too high

Hedge at one layer only. If the client, the mesh sidecar and the gateway each hedge or retry independently, their multipliers compound, and one slow call can turn into many attempts. Treat retries and hedges as draws from a single attempt budget, owned by one layer and passed downstream in request metadata.

When to avoid hedging: overload, correlated slowness and side effects

Hedging assumes the slow attempt is unlucky and the backup will not be. Every failure mode below comes from that assumption being wrong.

Overload and metastable failure

Under saturation, latency rises because queues are full, so more requests cross the hedge delay and more backups get sent. That extra load lengthens the queues further. The loop can keep a system degraded after the original trigger is gone, which is the definition of a metastable failure. Disabling must therefore be automatic and load-aware. Stop hedging when the backend's error rate, queue depth or recent hedge ratio exceeds a threshold. An operator flag is too slow.

Correlated slowness

A slow shared database, a hot key or a degraded cross-zone link makes both copies slow. The backup waits behind the same lock or traverses the same congested path, so it adds load and does not improve p99 latency.

Side effects you don't see

  • Cache pollution: backups landing on cold replicas fill their caches with entries that would otherwise not be there, and can evict entries that are still useful.
  • Rate limits and quotas: downstream and third-party APIs count every attempt. Hedges spend quota and can trigger throttling or extra billing.
  • Coverage gaps: restricting hedging to idempotent reads leaves writes and multi-step calls unprotected. These are often the slowest paths.

Candidate checklist

  • Idempotent, or protected by dedup keys
  • Variance comes from independent replicas, not shared state
  • Spare capacity exists at expected hedge rates
  • No per-call quota or billing downstream
  • Cancellation propagates to the server

Alternatives and complements to hedged requests

Hedging is one tool among several, and most of the others are cheaper or address the cause instead of the symptom. The useful question is what kind of slowness you have: random per-request variance on healthy replicas, a persistently bad replica, or a system that is simply out of capacity.

Technique Latency problem it addresses Load cost
Timeouts plus retries Hung or failed requests Extra request only after timeout; retry storms if unbounded
Tighter deadlines Work continuing after the caller gave up Reduces load
Load shedding, admission control Queueing under overload Reduces load; some requests rejected
Outlier ejection One persistently slow or failing replica Shifts load to remaining replicas
Caching Repeated expensive reads Reduces load; adds staleness risk
Reducing fan-out width Tail amplification across many backends Reduces load
Partial or degraded responses One slow shard blocking the whole reply Neutral; lowers result quality
GC tuning, noisy-neighbor isolation Root sources of per-request variance Engineering time; possibly reserved capacity

Retries wait for a full timeout, so they protect against failures but do little for p99. Hedging fires much earlier, which is why it works on tails, and also why it costs more. Outlier ejection is a better fit when one replica is consistently slow, because hedging would keep paying for duplicates sent to that node. If p99 rises with load, the cause is queueing. Hedging adds traffic to the queue and makes the problem worse, so shedding and capacity work are the right fixes. Use hedging for the variance that is left after these measures, when that variance is random across independent replicas.

Observability, rollout, and impact on cost and engineering time

Metrics to emit

For every hedged method, record five things:

  • Hedges sent. How often a backup request fires.
  • Hedge win rate. How often the backup finishes first.
  • Wasted work. Losing attempts that completed or were cancelled late.
  • Budget exhaustion events. Times a hedge was suppressed because the budget was spent.
  • Latency per attempt and client-observed latency, recorded separately.

A win rate near zero means either the delay is too short or the slowness is correlated across replicas. Frequent budget exhaustion means the cap, not the delay, is shaping your tail.

Read the client and server views together. Client p99 can fall while server request rate, CPU and queue depth rise. Put both on the same dashboard so a "win" that is really added load shows up.

Rollout

Gate hedging behind a per-method flag. One example: hedging.GetProfile.enabled=true, delay_ms=40, max_extra_fraction=0.05. To validate, compare before and after histograms of the full distribution, not just p99, over comparable traffic windows. Turning off the flag reverts the change.

Cost

The engineering cost has four parts:

  • implementation
  • an idempotency audit per method
  • cancellation plumbing through every hop
  • ongoing tuning

The infrastructure cost comes from duplicate work.

Illustrative estimate (assumed numbers, not a benchmark): extra server work ≈ hedge rate × (1 − fraction of backup work saved by cancellation). With a 5% hedge rate and cancellation saving 40% of each backup's work: 0.05 × 0.6 = 3% extra load.

Hedging can still save engineering time. Chasing every source of per-node variance (GC pauses, noisy neighbours, cold caches) is open-ended work. Hedging gives a bounded, reversible p99 improvement instead, as long as budgets and dashboards are in place before it ships.

from prometheus_client import Counter, Histogram

# Per-method flag config. Unlisted methods are never hedged; setting enabled=False reverts.
HEDGING = {
    "GetProfile": {"enabled": True, "delay_ms": 40, "max_extra_fraction": 0.05},
    "UpdateProfile": {"enabled": False},  # not idempotent: never hedge
}

LABELS = ["method"]
HEDGES_SENT = Counter("hedge_sent_total", "Backup requests fired", LABELS)
HEDGE_WINS = Counter("hedge_wins_total", "Backup finished before primary", LABELS)
WASTED = Counter("hedge_wasted_total", "Losing attempts that completed or were cancelled late", LABELS)
BUDGET_EXHAUSTED = Counter("hedge_budget_exhausted_total", "Hedges suppressed by the budget", LABELS)

BUCKETS = (0.005, 0.01, 0.02, 0.04, 0.08, 0.16, 0.32, 0.64, 1.28)
# Each individual attempt, labelled primary or backup: shows what servers actually serve.
ATTEMPT_LATENCY = Histogram("rpc_attempt_seconds", "Per-attempt latency", LABELS + ["attempt"], buckets=BUCKETS)
# What the caller waited for: this is where hedging should improve p99.
CLIENT_LATENCY = Histogram("rpc_client_seconds", "Client-observed latency", LABELS, buckets=BUCKETS)


def hedge_config(method):
    cfg = HEDGING.get(method, {})
    return cfg if cfg.get("enabled") else None


def record_call(method, attempts, winner, total_seconds, hedged, suppressed, loser_wasted):
    # attempts: list of ("primary"|"backup", seconds) for attempts that finished
    for kind, seconds in attempts:
        ATTEMPT_LATENCY.labels(method=method, attempt=kind).observe(seconds)
    CLIENT_LATENCY.labels(method=method).observe(total_seconds)
    if hedged:
        HEDGES_SENT.labels(method=method).inc()
        if winner == "backup":
            HEDGE_WINS.labels(method=method).inc()
        if loser_wasted:
            WASTED.labels(method=method).inc()
    if suppressed:
        BUDGET_EXHAUSTED.labels(method=method).inc()

A per-method hedging flag table and Prometheus client instrumentation that records hedges sent, wins, wasted work, budget exhaustion, and per-attempt latency kept separate from client-observed latency, so client and server views can be read side by side.

How OneEnv can help

Disclosure: OneEnv is the product behind this blog.

OneEnv (oneenv.io) is a workspace-based governance platform for the things services share — environment variables, database structure, API routes and validation rules. A change to a shared value is staged on a branch, reviewed once, and then every affected service explicitly approves or rejects it before it goes live, so you can see who a change touches before it ships instead of finding out in production.

Applied to request hedging tail latency, this is where it helps:

Saves time

  • Every service that inherits a shared value is listed in one place, so nobody searches repos and chats to find out who is affected.
  • One review per branch replaces coordinating each team separately; each service still keeps its own approve/reject.
  • Reviewers see the exact diff and the list of affected services up front, so approval is a decision rather than an investigation.

Saves cost

  • Fewer production incidents and rollbacks caused by a shared value, route or column changing under a consumer unannounced.
  • Less duplicated configuration to maintain: one shared definition inherited by many services.
  • Per-service approve/reject means a bad shared value can be refused where it would break something, before it is live.
  • OneEnv has a free plan (1 workspace, unlimited services and members, full governance), so trying it costs nothing.

These are qualitative benefits, not measured results — how much you save depends on how many services share the value.

Want to try it? Start at oneenv.io.