Send the request; if it has not answered by the p95 delay, send a second copy and take whichever returns first. Under independence the request is slow only if both copies are, so the tail past the delay is squared — and the second copy goes out only for the five percent of requests that were still running, so it costs about five percent more load. On the lab’s service that takes a 120 ms p99 to 45 ms.
Core ideas
The hard idea is that the same independence that made a fan-out worse makes a duplicate better, and that the cost of the duplicate is decided entirely by when you send it.
Issue the call. If no answer has arrived by d milliseconds, issue a second copy and use whichever finishes first. The request finishes at min(X, d + Y) with Y an independent copy of the same service, so a request is slow only when both copies are slow at once.
P(hedged > t) = P(X > t) · P(X > t − d). Just past d that is roughly the tail squared: on the lab’s service, a 1/20 tail at 30 ms becomes 1/400. Squaring a small probability is a large change, and it is the same multiplication rule that made a fan-out of sixty-nine calls miss its p99 half the time.
The second copy is sent only for requests still running at d, so the extra load is P(X > d) and nothing else. Hedge at the p95 and that is 5%. Hedge nearer the median and the figure climbs fast: at the lab’s 12 ms median the backup goes out for 35% of requests, seven times the traffic for a worse result.
The material
What squaring a tail buys, what sending it costs, and the assumption that decides whether either number is real.
The lab’s preset is a hundred measured calls, given as run lengths: forty at 10 ms, twenty-five at 12 ms, fifteen at 15 ms, ten at 20 ms, five at 30 ms, three at 50 ms, one at 120 ms and one at 300 ms. Its median is 12 ms, its p95 is 30 ms and its p99 is 120 ms — a tail ten times the median, which is an ordinary shape for a service that is not in trouble.
A hedged request with delay d issues a second, independent copy of the call if the first has not answered within d, and completes when either copy answers. Its completion time is min(X, d + Y), where X and Y are independent draws from the service’s latency distribution. The extra load it creates is P(X > d): the fraction of requests that live long enough to trigger the copy.
The tail of the hedged request factorises. It exceeds t only if the first copy is still running at t and the second copy, which started at d, is still running at t. Those are independent, so their probabilities multiply:
Two things happened and only one of them was asked for. The p99 fell from 120 ms to 45 ms, a reduction of 62%, for five percent more traffic. The median did not move at all — it is still 12 ms — because ninety-five percent of requests never reach the delay and never trigger anything. A hedge is a tail instrument. It does not make a service faster; it makes a service less occasionally awful.
The list is the whole design decision. Hedging at the median buys 15 ms more of tail reduction than hedging at the p95 and costs seven times the extra traffic to get it. Hedging at the p99 costs almost nothing and achieves almost nothing, because by 120 ms the only requests left running are the ones whose second copy will not finish in time either. Somewhere around the p95 is where the curve bends, which is why that is the usual recommendation.
A service handling 40 000 requests a second at a 5% hedge rate sends an extra 2000 calls a second. That is real capacity, it must be provisioned, and it arrives precisely when the service is already having difficulty — the requests that trigger hedges are the slow ones, and slowness is correlated in time. A hedge that is not capacity-planned adds load to a system at the exact moment load is what is wrong with it.
That last observation is also the limit of the technique, and it is worth stating as sharply as possible. Every number on this page assumes the second copy is independent of the first. If the call is slow because the request is expensive — a large query, a cold cache entry, a user with a great deal of data — then the second copy is expensive in exactly the same way and P(both slow) is not p² but something close to p. The hedge then costs its extra load and buys nothing.
Independence is plausible when the slowness belongs to the server: a garbage-collection pause, a scheduling delay, a disk that is briefly busy. It is implausible when the slowness belongs to the request, and it is worse than implausible when the second copy is routed to the same replica, which makes the two copies the same draw. Hedging to a different replica is not a refinement of the technique; it is a condition for the arithmetic being about anything.
Interactive
The tail squared past the hedge delay, bought with the tail in extra load
Method
The delay is the only parameter, and it sets both numbers at once.
If an expensive request is slow on every replica, a second copy is a second expensive request. Hedging is for variance that the request does not carry with it, and this question is prior to all the arithmetic.
You need the distribution, not a mean: the median, the p95 and the p99 of measured calls. The delay will be chosen against these and the extra load read off the same list.
The extra load is P(X > d), straight off the distribution. The hedged percentile comes from P(X > t)·P(X > t − d). Quote them together: a hedge is a trade and a number that reports only the improvement is half an answer.
The hedge rate is extra steady-state load and it clusters in time with the trouble that caused it. Route the second copy to a different replica, or the two draws are the same draw and p² is a fiction.
One hundred measured calls, one delay, and the two numbers that decide whether to do it.
The final line is the comparison worth keeping. Moving the delay from the p95 to the median improves the hedged p99 from 45 ms to 30 ms — a further 15 ms — and takes the extra load from 5% to 35%. Seven times the traffic to remove a further fifteen milliseconds is the sort of trade that looks reasonable when only one of its two numbers is on the slide.
Notice also how the hedged p99 is found. It is not a formula: the function P(X > t)·P(X > t − d) can only change at the sample’s own values and at those values shifted by d, so the answer is a search over that grid for the first time the product falls to 1/100. Here it lands exactly on 1/100 at 45 ms, which is 30 ms of delay plus the 15 ms atom.
For a faded rehearsal, keep the same service and set the delay to 20 ms. The supplied first move is the cost: P(X > 20) = (5 + 3 + 1 + 1)/100 = 10.0%. Work out the hedged p99 by walking the grid upward from 20 ms, then say whether doubling the extra load from the p95 choice was worth the improvement it bought. Check both figures in the lab before opening the quiz.
You should be able to read a service’s percentiles from a sample, choose a hedge delay, compute the extra load and the hedged percentile it produces, and state the condition under which the second of those figures is meaningless.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.