Hedged requests and fan-out width vs extra load

The decision

A fan-out request asks many servers for a part of the answer and waits for all of them. A search over 100 shards is an example. The slowest part sets the speed of the whole request. The tail latency is the slow end of the response times, for example the slowest 1 percent. A hedged request sends a second copy of a slow call to another server and uses the first answer. Hedging cuts the tail, but it adds load, and extra load can make the tail worse. The other tools are to make the fan-out narrower, or to return a partial answer when a few parts are late.

Choose hedging when

• The slowness comes from random causes. Examples are a busy disk, a garbage collection pause or one queue. The whole system is not busy.
• Calls are safe to repeat, because they only read data or are idempotent.
• You have spare capacity. Assumption: servers run below about 70 percent busy.
• Another copy of the data exists on a second server that can answer.
• The user cares about the slowest 1 percent, because the fan-out is wide.

Choose a narrower fan-out when

• Most of the work is wasted. A query that touches 100 shards but needs 3 of them can be routed better, by an index or a cache.
• Servers are already above 80 percent busy (Assumption). Extra copies would make queues longer.
• The calls change data and cannot be repeated.
• You can reduce the width by changing the data layout, for example keeping one customer's data on one shard.

Choose partial results when

• A late part matters less than a fast answer, as with a search where the missing shard holds a small share of the results.
• You can tell the user clearly that the result is partial.

The numbers that change the answer

Why the tail matters (calculation). Assumption: each server is slow, over 1 second, for 1 percent of calls, and the calls are independent. A request that waits for N servers is slow if any one is slow: 1 - 0.99 to the power of N.

• N = 1: 1 percent.
• N = 10: 1 - 0.99^10 = 9.6 percent.
• N = 100: 1 - 0.99^100 = 63.4 percent.
• N = 1,000: 99.996 percent.

The paper "The Tail at Scale" by Dean and Barroso (2013) uses this same example. It reports a case with 100 servers, where each has a 1 in 100 chance of a one-second reply. Then 63 percent of user requests take more than one second (cited fact; see Sources).

What hedging gives (our calculation). Send the second copy only when the first call is later than the 95th percentile (p95). That is the time that 95 percent of calls beat. Only 5 percent of calls pass that point, so the extra requests are at most 5 percent. The paper gives the same figure, about 5 percent. Now assume both copies are slow independently, each with chance 0.01. A call is then slow with chance 0.01 x 0.01 = 0.0001. At N = 100: 1 - (1 - 0.0001)^100 = 1.0 percent, compared with 63.4 percent.

A cited benchmark. The paper reads 1,000 keys from a table spread over 100 servers. Hedging after a 10 ms delay cut the 99.9th percentile from 1,800 ms to 74 ms, with 2 percent more requests. This is a measurement by the paper authors on their own system. Your numbers will differ.

What hedging costs near full load (assumption plus a simple model). Assume waiting time is proportional to 1 / (1 - busy share). At 85 percent busy the factor is 1 / 0.15 = 6.7. Add 5 percent more requests: busy share 0.85 x 1.05 = 0.8925, and the factor is 1 / 0.1075 = 9.3. Queues grow by about 40 percent, because 9.3 / 6.7 = 1.39. Real systems differ, but the direction is the same.

The storm (calculation). Assume the hedge fires at a fixed 100 ms, the old p95. During a slowdown, 30 percent of calls pass 100 ms. Load is then 0.85 x 1.3 = 1.105, which is above 100 percent. The queue grows without limit, and more calls pass 100 ms. Hedging turns a small problem into an outage. A budget fixes this: allow hedges for at most 5 percent of requests, counted with a token bucket.

Narrowing (calculation). Assumption: an index lets a query touch 10 shards instead of 100. The slow chance falls from 63.4 percent to 9.6 percent, and the load on the cluster falls by 90 percent. Cost: building and keeping the index, and some queries cannot use it.

What breaks with each choice

Hedging.

• A hedge storm in a slowdown, as above. Fallback: a budget of 5 percent, hedge only after p95, and turn it off when the error rate rises.
• Slowness is shared, for example one bad rack or one slow database that both copies call. Both copies are slow. Fallback: send the second copy to a different rack or zone.
• Duplicate writes. Fallback: hedge only reads and idempotent calls, and cancel the loser.
• Wasted work if you do not cancel. Fallback: cancel the slower copy as soon as the other one answers, and mark hedges as lower priority (the paper suggests both).

Narrow fan-out.

• The index goes stale or hot shards appear. Fallback: refresh it often, and watch skew.

Partial results.

• Users see wrong totals without knowing. Fallback: mark the answer as partial, and do not use it for money.
• A failure looks like a quiet loss. Fallback: count the partial responses and alarm on them.

What it costs

• Hedging (Assumption): 3 to 5 engineer-days for a client library with a budget and cancel, plus a load test. Extra load of 2 to 5 percent means 2 to 5 percent more servers if you were full.
• Narrowing: weeks to months, because data layout and routing change.
• Partial results: days, plus a product decision on what users see.
• Changing your mind: hedging is a setting you can turn off in minutes, which makes it the cheapest first step. A data layout change is slow to undo.

How each level answers

SDE-1: In a fan-out, the slowest server decides the speed. A hedged request sends a second copy and uses the first answer.

SDE-2: For a search over 100 shards I hedge reads after the p95 time. I only repeat safe calls, and I cancel the slower copy.

Senior: With 1 percent slow calls and 100 shards, 63 percent of requests are slow. Hedging after p95 adds at most 5 percent load and cuts that to about 1 percent if the copies fail independently. At 85 percent busy that load adds about 40 percent to queue delay in my model. So I cap hedges at 5 percent of requests and turn them off when errors rise. My fallback is partial results, marked as such.

Staff: I ask what slow requests cost in money and what extra load costs in servers. I set a latency target with product. One team owns the shared client library and the hedge budget. We measure p99 of the full request, extra load and hedge win rate. I start with hedging because it is reversible. I reduce the fan-out through data layout when the extra load passes about 5 percent of capacity, or the tail target is still missed. I revisit it when traffic or shard count doubles.

Say it in the interview

With 100 shards and 1 percent slow calls, 63 percent of requests wait for a slow one. So I would hedge reads after the p95 time, with a budget of 5 percent extra requests. The risk is that near full load the extra requests make queues longer. So I would cap them, cancel the loser, and turn hedging off when errors rise. If that is not enough, I would narrow the fan-out with an index.

Common mistakes

• Hedging every request at once. That doubles the load. Wait until p95.
• Hedging writes. A repeated write can happen twice. Hedge only safe calls.
• Using a fixed delay. When the system slows, many calls pass it and the load climbs. Use a budget.
• Ignoring shared causes. If the cause is a slow dependency, a second copy is also slow.

Sources

• J. Dean and L. A. Barroso, "The Tail at Scale", Communications of the ACM 56(2), 2013. Full text, read from the site of one of the authors (63 percent of requests slow with 100 servers; about 5 percent extra load when hedging after the 95th percentile; the BigTable benchmark of 1,000 keys on 100 servers with a 10 ms hedge, 1,800 ms to 74 ms, 2 percent more requests; cancel the other copy; lower priority for hedges): https://www.barroso.org/publications/TheTailAtScale.pdf (opens in a new tab) (checked 26 Oct 2026). Publication page: https://research.google/pubs/the-tail-at-scale/ (opens in a new tab) (abstract only).
• The 1 percent slow rate, the 85 percent load, the waiting-time model, the 30 percent slowdown and the effort figures are assumptions made for teaching. The tail, hedge and storm figures are our own calculations from them.