Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Hedging

When does sending a duplicate request cut the tail, and when is it pure waste?

Hedging: buying the tail with duplicate work

Scatter-gather showed that fan-out are worse than any single node's tail. is one thing you can do about it, and the arithmetic makes it a very good deal.

The mechanism. Send the request. If no answer has arrived by the 95th of normal latency, send a second copy to another . Take whichever answer returns first.

  • The extra load is only 5% of requests (the ones that crossed the p95 line).
  • If the two attempts are independent, completion time becomes the minimum of two draws. The chance that both are slow is p². A tail with a 1-in-20 chance (0.05) of being slow becomes 0.05² = 0.0025, which is 1-in-400.
RelationshipHedged requests →
chance one attempt is slow
independent attempts raced
p = 5% (hedge at p95)p = 1%
Data table
Chance a request is slow, by attempts raced
Attempts kseriesSlow requests
1p = 5% (hedge at p95)5%
1.04p = 5% (hedge at p95)4.47%
1.07p = 5% (hedge at p95)3.99%
1.11p = 5% (hedge at p95)3.57%
1.15p = 5% (hedge at p95)3.19%
1.19p = 5% (hedge at p95)2.85%
1.23p = 5% (hedge at p95)2.55%
1.26p = 5% (hedge at p95)2.28%
1.3p = 5% (hedge at p95)2.04%
1.34p = 5% (hedge at p95)1.82%
1.38p = 5% (hedge at p95)1.63%
1.41p = 5% (hedge at p95)1.45%
1.45p = 5% (hedge at p95)1.3%
1.49p = 5% (hedge at p95)1.16%
1.52p = 5% (hedge at p95)1.04%
1.56p = 5% (hedge at p95)0.927%
1.6p = 5% (hedge at p95)0.829%
1.64p = 5% (hedge at p95)0.741%
1.68p = 5% (hedge at p95)0.662%
1.71p = 5% (hedge at p95)0.592%
1.75p = 5% (hedge at p95)0.529%
1.79p = 5% (hedge at p95)0.473%
1.82p = 5% (hedge at p95)0.422%
1.86p = 5% (hedge at p95)0.377%
1.9p = 5% (hedge at p95)0.337%
1.94p = 5% (hedge at p95)0.301%
1.98p = 5% (hedge at p95)0.269%
2.01p = 5% (hedge at p95)0.241%
2.05p = 5% (hedge at p95)0.215%
2.09p = 5% (hedge at p95)0.192%
2.13p = 5% (hedge at p95)0.172%
2.16p = 5% (hedge at p95)0.154%
2.2p = 5% (hedge at p95)0.137%
2.24p = 5% (hedge at p95)0.123%
2.27p = 5% (hedge at p95)0.11%
2.31p = 5% (hedge at p95)0.098%
2.35p = 5% (hedge at p95)0.088%
2.39p = 5% (hedge at p95)0.078%
2.42p = 5% (hedge at p95)0.07%
2.46p = 5% (hedge at p95)0.063%
2.5p = 5% (hedge at p95)0.056%
2.54p = 5% (hedge at p95)0.05%
2.58p = 5% (hedge at p95)0.045%
2.61p = 5% (hedge at p95)0.04%
2.65p = 5% (hedge at p95)0.036%
2.69p = 5% (hedge at p95)0.032%
2.73p = 5% (hedge at p95)0.029%
2.76p = 5% (hedge at p95)0.026%
2.8p = 5% (hedge at p95)0.023%
2.84p = 5% (hedge at p95)0.02%
2.88p = 5% (hedge at p95)0.018%
2.91p = 5% (hedge at p95)0.016%
2.95p = 5% (hedge at p95)0.015%
2.99p = 5% (hedge at p95)0.013%
3.02p = 5% (hedge at p95)0.012%
3.06p = 5% (hedge at p95)0.01%
3.1p = 5% (hedge at p95)0.009%
3.14p = 5% (hedge at p95)0.008%
3.17p = 5% (hedge at p95)0.007%
3.21p = 5% (hedge at p95)0.007%
3.25p = 5% (hedge at p95)0.006%
3.29p = 5% (hedge at p95)0.005%
3.33p = 5% (hedge at p95)0.005%
3.36p = 5% (hedge at p95)0.004%
3.4p = 5% (hedge at p95)0.004%
3.44p = 5% (hedge at p95)0.003%
3.48p = 5% (hedge at p95)0.003%
3.51p = 5% (hedge at p95)0.003%
3.55p = 5% (hedge at p95)0.002%
3.59p = 5% (hedge at p95)0.002%
3.63p = 5% (hedge at p95)0.002%
3.66p = 5% (hedge at p95)0.002%
3.7p = 5% (hedge at p95)0.002%
3.74p = 5% (hedge at p95)0.001%
3.77p = 5% (hedge at p95)0.001%
3.81p = 5% (hedge at p95)0.001%
3.85p = 5% (hedge at p95)0.001%
3.89p = 5% (hedge at p95)0.001%
3.92p = 5% (hedge at p95)0.001%
3.96p = 5% (hedge at p95)0.001%
4p = 5% (hedge at p95)0.001%
1p = 1%1%
1.04p = 1%0.841%
1.07p = 1%0.708%
1.11p = 1%0.596%
1.15p = 1%0.501%
1.19p = 1%0.422%
1.23p = 1%0.355%
1.26p = 1%0.299%
1.3p = 1%0.251%
1.34p = 1%0.211%
1.38p = 1%0.178%
1.41p = 1%0.15%
1.45p = 1%0.126%
1.49p = 1%0.106%
1.52p = 1%0.089%
1.56p = 1%0.075%
1.6p = 1%0.063%
1.64p = 1%0.053%
1.68p = 1%0.045%
1.71p = 1%0.038%
1.75p = 1%0.032%
1.79p = 1%0.027%
1.82p = 1%0.022%
1.86p = 1%0.019%
1.9p = 1%0.016%
1.94p = 1%0.013%
1.98p = 1%0.011%
2.01p = 1%0.009%
2.05p = 1%0.008%
2.09p = 1%0.007%
2.13p = 1%0.006%
2.16p = 1%0.005%
2.2p = 1%0.004%
2.24p = 1%0.003%
2.27p = 1%0.003%
2.31p = 1%0.002%
2.35p = 1%0.002%
2.39p = 1%0.002%
2.42p = 1%0.001%
2.46p = 1%0.001%
2.5p = 1%0.001%
2.54p = 1%0.001%
2.58p = 1%0.001%
2.61p = 1%0.001%
2.65p = 1%0.001%
2.69p = 1%0%
2.73p = 1%0%
2.76p = 1%0%
2.8p = 1%0%
2.84p = 1%0%
2.88p = 1%0%
2.91p = 1%0%
2.95p = 1%0%
2.99p = 1%0%
3.02p = 1%0%
3.06p = 1%0%
3.1p = 1%0%
3.14p = 1%0%
3.17p = 1%0%
3.21p = 1%0%
3.25p = 1%0%
3.29p = 1%0%
3.33p = 1%0%
3.36p = 1%0%
3.4p = 1%0%
3.44p = 1%0%
3.48p = 1%0%
3.51p = 1%0%
3.55p = 1%0%
3.59p = 1%0%
3.63p = 1%0%
3.66p = 1%0%
3.7p = 1%0%
3.74p = 1%0%
3.77p = 1%0%
3.81p = 1%0%
3.85p = 1%0%
3.89p = 1%0%
3.92p = 1%0%
3.96p = 1%0%
4p = 1%0%
Stated in 2 places →Principle: Independence is assumed →
  • Published production numbers show the shape of this gain: an order-of-magnitude reduction in 99.9th-percentile latency for a couple of percent of extra requests.

This is a spectacular trade because the hedged fraction is small, and it is small because tails are, by definition, rare.

The boundary condition is where hedging is usually misused:

  • Attempt-local slowness: a GC pause, a scheduling hiccup, a disk that is briefly hot. A second attempt elsewhere is independent, so the arithmetic holds.
  • Request-local slowness: a very large key, a cold shard, a pathological predicate, a poison payload. The hedge is perfectly correlated with the original. You have doubled the load on the heaviest part of your workload and changed the latency by nothing. This is the "independence is assumed but rarely true" idea with the sign that hurts.

The diagnostic is simple: if your is above the configured percentile, the slowness is in the requests, not the servers. (If you hedge at p95, about 5% of requests should be hedged. If 20% are, hedging is not helping.)

Two further requirements

  • Cancellation is not an optimization. Without it, the duplicate work continues after the winner returns, and the extra load lands on a system that has just shown it is slow. (the request is sent to two servers at once, and each server's queue tells the other when it starts) shrink the duplicate window further, at the cost of a message between servers.
  • Hedging must be budgeted, for the same reason retries must (retry and hedge budgets). If the whole system becomes uniformly slow, every request crosses the hedge threshold, and the mechanism turns into a 2× load multiplier at the worst possible moment. The defence is a cap expressed as a fraction (for example "hedge at most 5% of requests"), not a rule applied per request.

In short: hedging trades a small fraction of duplicate work for the minimum of k latency draws, and it is worthless exactly when the slowness belongs to the request and not to the attempt.