The tail at scale

What it is

In a system where one user request fans out to many backend servers and waits for all of them, the tail latency of individual servers becomes the typical latency of the whole request. If a request touches 100 servers and each has a 1 percent chance of taking longer than a second, the probability that none of them does is $0.99^{100} = 0.366$, so 63 percent of requests take over a second even though 99 percent of individual calls are fast.

That arithmetic is the whole idea, and it is worth writing on the board because it is genuinely counter-intuitive: a backend fleet with an excellent p99 produces a terrible user-facing p50.

Commonly confused with "the system is slow". It is not slow; it is variable, and fan-out converts variance into latency. Optimising the mean does nothing here. Reducing variance does everything.

The problem it solves

Latency variability at the individual-server level is unavoidable at scale, and listing the causes is a useful part of the answer because it shows why you cannot simply eliminate it:

• Shared resources: CPU contention with co-tenants, memory bandwidth, network links.
• Background activity: log compaction, garbage collection, cache warming, periodic reindexing.
• Queueing at any of several layers, each of which has its own $1/(1-\rho)$ behaviour.
• Maintenance: a kernel update, a certificate rotation, a leader election.
• Power and thermal management: a CPU dropping frequency.
• Bad luck: a request that happens to miss every cache.

You cannot remove these from a fleet of thousands of machines. The insight of the tail-at-scale work is that you do not have to: you can build a predictably responsive whole out of unpredictable parts, the same way TCP builds a reliable channel out of an unreliable one.

Mechanics

The amplification arithmetic

For a fan-out of $N$ and a per-server probability $p$ of exceeding some latency threshold, the probability the aggregate exceeds it is:

$$P(\text{slow}) = 1 - (1-p)^N$$

Two conclusions follow, and they are the design principles.

The tail you must control is at the percentile determined by your fan-out. With $N = 100$ and a target that 99 percent of user requests are fast, you need each server's p99.99, not its p99. Stating your fan-out and deriving the required per-server percentile is the single most useful thing to do in this conversation.

Reducing fan-out is a latency optimisation. Halving $N$ from 100 to 50 at $p = 1%$ takes the aggregate from 63 percent to 39 percent. Micro-partitioning that increases fan-out for load-balancing reasons is trading tail latency for distribution quality, and that trade should be conscious.

The mitigations, in the order to name them

1. Hedged requests. Send to one replica; if no response by the p95, send a duplicate to another and take whichever answers first.

// The p95 threshold is the design: hedge late enough that only the genuinely
// slow requests trigger it, so extra load stays around a few percent.
func hedged(ctx context.Context, replicas []Client, key string,
            after time.Duration) (Result, error) {
    ctx, cancel := context.WithCancel(ctx)
    defer cancel()                      // cancels the loser as soon as we return

    results := make(chan Result, len(replicas))
    launch := func(c Client) {
        if r, err := c.Get(ctx, key); err == nil {
            results <- r
        }
    }

    go launch(replicas[0])
    timer := time.NewTimer(after)
    defer timer.Stop()

    for i := 1; ; {
        select {
        case r := <-results:
            return r, nil               // first answer wins
        case <-timer.C:
            if i < len(replicas) {
                go launch(replicas[i]); i++
                timer.Reset(after)
            }
        case <-ctx.Done():
            return Result{}, ctx.Err()
        }
    }
}

Because only requests slower than the p95 hedge, extra load is bounded at roughly 5 percent, and Google reported this cutting p99 substantially at about that cost. It is the highest return-to-complexity item on the list.

2. Tied requests. Send to two replicas simultaneously, each request carrying the identity of its twin. Whichever server dequeues the work first sends a cancellation to the other. This removes the p95 wait that hedging pays, at the cost of a small window where both may start.

3. Micro-partitioning. Partition into far more shards than machines (say 20 per machine) so that rebalancing is fine-grained: a hot partition can be moved without relocating a whole machine's worth of load. This is how Bigtable and Slicer manage skew.

4. Selective replication. Detect hot items and add replicas for those items only, rather than replicating everything.

5. Latency-induced probation. Temporarily remove a slow replica from the serving pool while continuing to send it shadow traffic, so you can detect recovery and return it. This handles the case where one machine is degraded rather than the fleet being variable.

6. Per-request deadlines propagated through the whole call tree. A request with a 200 ms budget that has consumed 180 ms should not start a 100 ms downstream call. gRPC does this natively with deadlines; REST usually does not, which is a real point in gRPC's favour.

7. Good-enough responses. Return after 95 of 100 shards answer, marking the result partial. For search, dropping 5 percent of the corpus changes results imperceptibly; waiting for the last shard changes latency by an order of magnitude. This is the largest available win and it is a product decision, so agree it before the incident rather than during.

The critical operational caveat

Hedging under overload is an amplifier. If the system is slow because it is saturated, hedging adds load and accelerates collapse. Gate it:

// Hedge only while the hedge rate is low. If more than ~5% of requests are
// hedging, the system is not experiencing variance, it is experiencing
// overload, and hedging makes it worse.
if hedgeRate.Rate() < 0.05 && !circuitBreaker.Open() {
    return hedged(ctx, replicas, key, p95)
}
return replicas[0].Get(ctx, key)

Saying this unprompted is the difference between having read the paper and having run it in production.

A worked example

A search service. A query fans out to 60 index shards and merges the results. Per-shard p50 is 8 ms, p99 is 90 ms. Target: user-facing p99 under 200 ms.

What actually happens without mitigation. The aggregate takes the max of 60 shard latencies. The probability that at least one exceeds 90 ms is $1 - 0.99^{60} = 45$ percent, so 45 percent of queries include a 90 ms-plus shard. The user-facing p50 lands near the shards' p98 rather than near their p50, and the measured p50 is around 85 ms rather than the 8 ms the shard graph suggests. The team's dashboard says the index is fast; users say search is slow. Both are right.

Fan-out arithmetic for the target. To get a 99 percent chance that no shard exceeds the threshold with $N = 60$, each shard must satisfy $(1-p)^{60} \ge 0.99$, so $p \le 1.7 \times 10^{-4}$. We need the shards' p99.98, not their p99. No amount of median optimisation touches that number.

Mitigations, with their measured effect:

The hedge is the cheapest and the good-enough response is the largest. The fan-out reduction is the structurally interesting one, because it trades against the reason you sharded in the first place, and it is only available if per-shard latency does not grow faster than the shard count falls.

The thing to say out loud: "the biggest win here is a product decision, not an engineering one. Returning after 57 of 60 shards costs 0.3 percent of recall and halves the tail. I would want that agreed with product in advance, with the partial flag surfaced in telemetry, rather than discovered during an incident."

Production evidence

Dean and Barroso, "The Tail at Scale" (CACM, February 2013) is the primary source for all of the above: the amplification arithmetic, hedged and tied requests, micro-partitioning, selective replication and latency-induced probation, drawn from Google's production experience. They reported hedged requests reducing p99 substantially at roughly a few percent of additional load.

Bigtable and Slicer are the named systems behind micro-partitioning: many more tablets than machines, with an allocator moving them to balance load.

gRPC implements deadline propagation natively, so a deadline set at the edge flows through the entire call tree and downstream servers can abandon work whose answer is no longer wanted. This is one of the clearest practical advantages of gRPC over REST for internal service-to-service traffic.

Envoy and modern service meshes ship request hedging and outlier detection (automatically ejecting hosts whose latency or error rate diverges from their peers) as configuration, which is latency-induced probation productised.

The debate

The alternative to mitigation is reducing variance at the source: eliminate garbage collection pauses, pin CPUs, disable background compaction during peak, use dedicated hardware. This is real engineering and it works, and it is where a latency-critical system should start.

Its limit is that variance at the individual-server level is irreducible past a point. You do not control co-tenants on shared infrastructure, you cannot avoid all background work, and a fleet of thousands will always have some machines in a bad state. Past that point the only lever is architectural.

My position: reduce fan-out where you can, because it attacks the exponent rather than the base. Add hedged requests, gated on hedge rate so they cannot amplify an overload. Propagate deadlines through the call tree so a doomed request stops consuming capacity. And agree a good-enough-response policy with product in advance, because it is the largest single win and it is not an engineering decision to make unilaterally.

These techniques are the wrong focus when fan-out is small, where the amplification does not apply and the problem is ordinary latency; when the system is saturated, where hedging makes it worse and the answer is capacity or load shedding; and when the variance comes from one identifiable bad component, where fixing it beats routing around it.

Follow-up Q&A

"Why does a service with a good p99 have a bad user-facing p50?" Fan-out. If a request touches $N$ backends and waits for all of them, the aggregate takes the maximum, so the probability of hitting at least one slow backend is $1 - (1-p)^N$. At $N = 100$ and a 1 percent chance per backend, 63 percent of user requests include a slow backend. The user-facing median is determined by the backends' high percentiles, not their median, which is why optimising the mean does nothing.

"What percentile do you need to control?" The one your fan-out demands. Solve $(1-p)^N \ge$ your target, so for $N = 60$ and a 99 percent target you need each backend's p99.98. Stating that arithmetic converts a vague "improve the tail" into a specific number, and it also tells you when the target is unachievable and you need to reduce $N$ or accept partial results instead.

"How do hedged requests work and what is the risk?" Send to one replica, and if no response arrives by roughly the p95, send a duplicate to another and take whichever answers first, cancelling the loser. Because only the slowest 5 percent hedge, extra load is bounded at a few percent. The risk is that under overload hedging amplifies: if the system is slow because it is saturated, adding duplicate requests accelerates collapse. So gate it on the observed hedge rate and disable it when the circuit breaker is open.

"What is the difference between hedged and tied requests?" Hedging waits for the p95 before sending the second request, so it pays that wait on every slow request. Tied requests send both immediately, each carrying the identity of the other, and whichever server dequeues the work first cancels its twin. Tied removes the wait at the cost of a small window where both may begin work, so it is better when the wait matters more than the duplicated work, and worse when the work is expensive.

"When would you return a partial result?" When the marginal value of the last few shards is lower than the latency they cost, which for search and recommendations is almost always. Dropping 3 of 60 shards costs a fraction of a percent of recall and can halve the tail. Two conditions: the result must be marked partial so downstream systems and telemetry can distinguish it, and the policy must be agreed with product in advance, because silently returning incomplete results is a correctness decision an engineer should not make alone.

Common misconceptions

The most common is that the tail is a rare-event problem affecting a few unlucky users. Under fan-out it is the typical case: a 1 percent per-server tail becomes a 63 percent aggregate tail at $N = 100$.

The second is that hedging is free insurance. It is bounded extra load in normal operation and an amplifier under overload, which is why the gate matters more than the mechanism.

The third is that adding replicas fixes it. Replicas help hedging and selective replication have somewhere to go; they do not reduce the per-server variance that causes the problem, and they increase the fan-out if you query more of them.

Interview delivery note

Do the arithmetic out loud, because it is the whole idea: "If a request fans out to 100 servers and each has a 1 percent chance of exceeding a second, then 63 percent of requests exceed a second, because it's one minus 0.99 to the hundred. So the tail at the leaf becomes the median at the root, and the percentile I actually need to control is set by my fan-out: at 60 shards and a 99 percent target, I need each shard's p99.98."

Then the mitigations, ranked: "Hedged requests are the cheapest, send a duplicate at the p95 and take the first answer, which is a few percent extra load. Deadline propagation so a doomed request stops consuming capacity. And the biggest win is usually a good-enough response, returning after 57 of 60 shards, which costs a fraction of a percent of recall and halves the tail."

The depth signal is the caveat: "hedging under overload is an amplifier, so I'd gate it on the observed hedge rate and turn it off when the circuit breaker is open." That sentence is the difference between having read the paper and having operated it.

Further reading

• Dean and Barroso, "The Tail at Scale" (CACM 2013). Read it twice; it is short and it is the source for everything here.
• Google, Site Reliability Engineering, on load balancing and handling overload, for the interaction between hedging and saturation.
• Envoy documentation on retry policies, request hedging and outlier detection, for the productised form of probation.
• gRPC documentation on deadlines and cancellation propagation.