Tail latency amplification: why p99 of one service becomes p50 of the aggregate

A search endpoint queries 60 shards in parallel and merges the results. Each shard responds within 5 milliseconds 99 percent of the time, which everybody agrees is a healthy service.

The search endpoint’s p50 is 47 milliseconds.

Nothing is broken. Every shard is meeting its latency target. The endpoint is slow because it waits for all 60, and with 60 independent draws from a distribution where one percent exceed 5 milliseconds, the chance that at least one of them does is about 45 percent. The endpoint experiences the shards’ tail as its own median.

The arithmetic is unforgiving

If a single call is slow with probability p, then all N calls being fast has probability (1 minus p) to the power N. The chance of at least one being slow is the complement.

def at_least_one_slow(p_slow, fanout):
    return 1 - (1 - p_slow) ** fanout

at_least_one_slow(0.01, 1)     # 0.01   one call, rarely slow
at_least_one_slow(0.01, 10)    # 0.096
at_least_one_slow(0.01, 60)    # 0.453
at_least_one_slow(0.01, 100)   # 0.634  the p99 event is now the common case

At 100 parallel calls, the thing that happens to one percent of backend requests happens to roughly two thirds of your requests. You have not made anything slower. You have simply asked enough times that the rare outcome becomes likely.

flowchart TB
    R["One aggregate request"] --> F{"Fan out to N backends"}
    F --> B1["backend 1: 2ms"]
    F --> B2["backend 2: 3ms"]
    F --> BD["... 57 more, all fast"]
    F --> BN["backend 60: 340ms<br/>(this one is in its p99)"]
    B1 --> W["Wait for ALL"]
    B2 --> W
    BD --> W
    BN --> W
    W --> OUT["Aggregate latency: 340ms.<br/>59 fast responses bought nothing."]

    style BN stroke:#ef4444,stroke-width:3px,color:#fff
    style OUT stroke:#ef4444,stroke-width:2px,color:#fff

The corollary that matters for planning: reducing fan-out helps as much as making the backend faster, and it is often easier. Going from 100 shards to 20 does more for the tail than shaving the backend’s p99 in half.

Correlation makes it worse, not better

The formula assumes independence, which flatters reality.

Backends sharing a rack share a network path. Backends running the same code garbage collect on similar schedules once traffic is similar. Backends behind the same load balancer see the same connection churn. A deploy rolls across all of them.

When slowness is correlated, several calls in a fan-out go slow together, which does not help the aggregate at all, because you were already waiting for the worst one. What correlation does change is that the slow events cluster in time, so the aggregate has periods that are uniformly bad rather than a steady sprinkle.

The one case where correlation helps is if you can exploit it: if slowness is caused by something local to a replica, then a second replica is likely to be fine, which is exactly what hedging depends on.

Averages cannot see any of this

Watching mean latency on a fan-out service is close to useless.

Sixty calls where 59 take 2 milliseconds and one takes 400 has a mean of about 8.6 milliseconds. The aggregate request took 400. The mean describes a number that no request experienced and hides the only one that mattered.

What is worth measuring is the max per request, or a high percentile of the per-request max. That is the number that determines what the user waits for.

// The aggregate's latency is the max, not the mean. Record it as such.
long start = System.nanoTime();
List<Result> results = shards.parallelStream()
        .map(shard -> shard.query(term))
        .toList();
metrics.timer("search.fanout.max").record(System.nanoTime() - start, NANOSECONDS);

There is a second measurement worth having: which backend was slowest, recorded per request. Over a day that distribution tells you whether one replica is disproportionately responsible, which is usually the case and is usually fixable.

Hedging is the cheap fix

The technique from Google’s The Tail at Scale paper by Dean and Barroso is to send a duplicate request to another replica after a short delay, take whichever answer arrives first, and cancel the other.

public Result hedged(Query q, Duration hedgeAfter) {
    CompletableFuture<Result> first = replicaA.queryAsync(q);
    CompletableFuture<Result> second = new CompletableFuture<>();

    // Only fires if the first has not answered by the hedge delay.
    scheduler.schedule(() -> {
        if (!first.isDone()) {
            replicaB.queryAsync(q).whenComplete((r, e) -> second.complete(r));
        }
    }, hedgeAfter.toMillis(), MILLISECONDS);

    return first.applyToEither(second, Function.identity()).join();
}

Setting the hedge delay to the p95 of normal response time means only the slowest 5 percent of requests ever trigger a duplicate, so the added load is around 5 percent while the tail improvement is large. That ratio is what makes the technique worth the complexity.

Two conditions have to hold. The request must be safe to duplicate, which means reads or writes carrying an idempotency key. And the system must have capacity for the extra requests, because hedging under saturation adds load exactly when the cause of slowness is load, which turns a tail problem into an amplification problem. Tying hedging to a budget, the same way retries should be, keeps that bounded.

The other levers

Returning partial results is often the honest answer for a fan-out. If 58 of 60 shards responded within the deadline, returning results from 58 is usually better than making the user wait for the other two. Search and recommendation surfaces tolerate this well. Anything with a correctness requirement does not.

Reducing fan-out is the structural fix and it is underused. Fewer, larger shards mean fewer draws from the tail distribution. The trade is per-shard work, and there is usually a sweet spot well below the shard count people arrive at by default.

Deadline propagation stops the aggregate waiting on work that is already useless. If the caller’s deadline is 100ms and 90 have elapsed, a shard should not start a query it cannot finish in 10.

And routing away from slow replicas, using something like least-outstanding-requests rather than round robin, keeps traffic off the replica that is currently having a bad time. That is a load balancer setting rather than application code, and it is one of the higher leverage changes available.

The framing that stuck with me is that in a fan-out system, your p99 is not your users’ rare bad day. It is what a large share of them get every time, and the component teams meeting their targets will all correctly tell you that nothing is wrong.