The idea: slow is rare, until you ask many servers
Most replies from a server come back fast, but a few are slow: the server was in a garbage-collection pause, its disk was busy, or a queue was briefly full. These few slow replies are the tail of the latency distribution, measured as the 99th percentile (p99) or the maximum. A user waits for the slowest reply the page needs, so the tail, not the median, is what users feel.
Large services fan out: one search or one page touches tens or hundreds of servers and waits for all of them. Then rare becomes normal. This is the problem in Dean and Barroso's paper The Tail at Scale, and its best-known fix is the hedged request.
The page runs one small scenario. A front end makes 10 reads, one after another, to three replicas R1–R3 that hold the same data. Each read normally takes 5–7 ms. Read #4 hits a GC pause on R1 (48 ms) and read #9 a busy disk on R3 (52 ms). Pick a policy and press Next Request or Run 10 Requests. The timeline shows each copy of the current read as a bar; the results table keeps one row per policy.
Hedged requests
A hedged request sends the read to one replica and starts a timer, the hedge delay. If the reply is back before the timer fires, nothing else happens. If not, the client sends a copy of the same read to a second replica. Whichever reply comes first is used, and the client cancels the other copy so that replica stops wasting work.
Without hedging the 10 reads take 5, 6, 5, 48, 6, 5, 7, 5, 52 and 6 ms: the median is 6 ms but the maximum is 52 (Demo 1). With a 10 ms hedge only #4 and #9 are still waiting when the timer fires. Each gets a copy to the next replica, which answers 6 ms later, so both finish at 16 ms. The maximum drops from 52 to 16 ms, and the cost is 12 copies instead of 10 (Demo 2).
Choosing the hedge delay
The delay decides how much extra load hedging adds. The usual choice is about the 95th percentile of normal latency: only the slowest 5% of requests get a second copy, so the load grows by about 5% while the tail shrinks a lot. In Google's BigTable test from the paper, hedging after 10 ms cut the 99.9th percentile of reading 1,000 keys from 1,800 ms to 74 ms, with only 2% more requests.
| policy | on the page: p50 / max | copies for 10 reads |
|---|---|---|
| no hedging | 6 / 52 ms | 10 |
| hedge after 25 ms (late) | 6 / 31 ms | 12 |
| hedge after 10 ms (about p95) | 6 / 16 ms | 12 |
| hedge after 3 ms (too early) | 6 / 9 ms | 20 |
| 2 copies at once | 5 / 6 ms | 20 |
Sending two copies at once gives the best latency but doubles the work on every replica (Demo 3). A hedge delay below normal latency does the same: at 3 ms every read is still running, so every read is copied (Demo 4). In a busy system doubled work means longer queues, which makes every request slower. The delay is set in Options; Demo 5 fills the table with the three policies side by side.
Cancellation and tied requests
- Cancel the loser. Without the cancel the slow replica keeps working on a reply nobody reads.
- Tied requests go one step further: both copies are sent at once, each tagged with the other server's address, and the first server to start the work tells the other to drop its copy. This removes queueing delay at almost no extra work.
- Only for safe calls. Hedging runs the same call twice, so it fits reads and idempotent writes, not a payment.
- Where it is used: gRPC has a
hedgingPolicy(maxAttempts,hedgingDelay,nonFatalStatusCodes); Cassandra hasspeculative_retry(for example99p); Envoy can hedge on a per-try timeout.
See also Retry, Exponential Backoff and Jitter (a retry waits for a failure, a hedge only for slowness), Circuit Breaker and Bulkhead, Latency vs Throughput, Java Garbage Collectors for where pauses come from, and Quorum Reads and Writes, another way to read from several replicas.
What the page leaves out
Network time; queueing, so the extra load of early hedges does not slow other requests on the page; requests running at the same time; real latency distributions and measuring the p95 to set the delay; tied requests (only in the text); hedge budgets that cap copies as a share of traffic; and fan-out itself (only in the first figure).