Fan-Out and the Amplification of Tail Latency

A single request to a single backend has a latency distribution, and its ninety-ninth percentile is the number that operations teams track. A request that fans out to twenty backends and waits for all of them has a different distribution, and its ninety-ninth percentile is not the ninety-ninth percentile of the components. It is much worse, and the gap grows with the fan-out width. This is the single most reliable way to turn a well-behaved service into a badly-behaved one without changing any of its parts.

The mechanism is order statistics, and it needs no assumption about the shape of the component distribution beyond independence. If one call exceeds a threshold with probability p, then n independent calls all stay below that threshold with probability (1 − p)^n, so the probability that at least one exceeds it is 1 − (1 − p)^n. At p = 0.01 and n = 20, that is roughly 0.18: a tail event that happens to one call in a hundred happens to one fan-out request in about five.

The arithmetic of waiting for the slowest

The amplification is easy to underestimate because the percentile of interest moves with the width. Suppose each backend’s response time has a ninety-ninth percentile of 100 milliseconds and a median of 10 milliseconds. A single call meets a 100 millisecond budget 99 percent of the time. A fan-out to twenty such backends meets the same budget only if all twenty finish within it, which happens with probability 0.99^20 ≈ 0.82. The service’s own ninety-ninth percentile is therefore not 100 milliseconds at all; the service’s 99th percentile is the latency at which 99 percent of fan-out requests complete, and that is the 99.95th percentile of the component distribution.

def fanout_exceeds(n, p_single_exceeds):
    """Probability that at least one of n independent calls misses the budget."""
    return 1.0 - (1.0 - p_single_exceeds) ** n

fanout_exceeds(20, 0.01)   # 0.182: one request in five misses

The same function run backwards answers the other question: given a target miss rate for the fan-out, each component must miss with probability below 1 − 0.99^(1/20), about 0.05 percent. The budget the service needs is therefore the component’s 99.95th percentile, which is why fan-out services end up specifying component percentiles far beyond the ones their own objectives mention.

The same arithmetic explains why mean latency is a poor guide. The mean of the maximum of n independent draws grows with n but slowly for light-tailed distributions and quickly for heavy-tailed ones. A service with a fan-out of a hundred can have a mean latency only modestly above a single call’s mean while its tail is an order of magnitude worse. The mean is dominated by the many requests where no component is slow; the tail is dominated by the few where one is.

Serial fan-out compounds instead of amplifying

Fan-out is not always parallel. A handler that issues calls one after another has service time equal to the sum of the component latencies, and its tail is the sum of the component tails rather than their maximum. The distinction matters for the shape of the distribution: a sum of many independent latencies concentrates around its mean, so a serial fan-out’s relative tail is often better than a parallel fan-out’s, even though its absolute latency is larger. Serial fan-out costs latency in the median and buys predictability in the tail; parallel fan-out does the reverse.

Most designs want parallel fan-out and therefore inherit the maximum rather than the sum, which is why the amplification described above is the normal case rather than a corner case. The exception is a handler whose downstream calls depend on each other’s results, where parallelism is impossible and the sum is unavoidable. Such a handler is a chain of serialization points, and each link contributes its own tail; the chain’s tail is dominated by its slowest link’s tail, not by the product of the links’ failure probabilities.

Where the independence assumption breaks

The amplification formula assumes independent component latencies. Real backends violate that assumption in ways that usually make things worse. A shared resource — a database, a lock service, a network link — makes many components slow at the same moment, so the probability that all are fast is lower than the product of the marginals. Correlated slowness means the fan-out does not average away; it concentrates.

Two common sources of correlation are worth naming. The first is a shared dependency: twenty shards of a storage system that all commit through one log, or twenty services that all call one metadata service. The second is a shared bottleneck on the caller’s side: the connection pool, the network interface, or the CPU. When the caller’s own resources are the constraint, adding fan-out width makes the caller’s queue longer and every component call slower, which is a positive feedback loop rather than a statistical effect.

A useful diagnostic is to compare the fan-out latency distribution against a synthetic one built by sampling the components’ individual distributions independently. If the real distribution has a heavier tail than the synthetic, the components are correlated, and the fix is at the shared dependency rather than at the fan-out. Instrumentation that records per-component timing within a request makes this comparison possible; the tracing model in distributed tracing systems exists precisely to attribute a fan-out request’s latency to its components.

Capping the width, and what it costs

The direct control on amplification is the width: fewer components means less amplification. Several designs reduce width without reducing the work.

One is to partition the fan-out so that each request contacts a subset. Instead of querying all shards, query the shards that hold the data the request needs; instead of asking every replica, choose one. The gain is real when the data is already partitioned by the request key, and the cost is that a request spanning keys must still contact every relevant shard.

Another is to return as soon as enough responses arrive rather than waiting for all. For a query that needs the top ten results from twenty shards, the answer is complete only when all shards respond, but an approximate answer may be acceptable after a subset. The trade is accuracy for tail latency, and it has to be made explicitly per query type rather than globally.

A third is to bound the wait with a deadline and treat a missing response as absent. This converts a slow component into a missing component, which changes the result’s completeness rather than its correctness of timing. The failure mode is that the deadline becomes the latency, and the fraction of requests that hit it becomes the error rate. Setting the deadline to the desired tail means the error rate equals the amplification probability, which is exactly the quantity the design was trying to avoid; the deadline is a bound, not a fix.

Redundancy as a substitute for width reduction

If the amplification comes from the maximum of many draws, one response to the problem is to issue more draws and take the first to finish. Sending the same request to two replicas and using whichever answers first halves the effective latency distribution’s tail — the minimum of two draws is below the median of one draw more often than not — at the cost of doubling the load on the backend. That cost is the reason the technique is applied to a small fraction of requests rather than all of them, a design treated in hedged requests and tail tolerance.

The load increase is not merely a doubling of requests; it is a doubling of the concurrency demanded of the backend, which the pool sizing arithmetic in Little’s law and the size of a request pool converts into additional workers. A service that hedges every request must size its backends for twice the concurrency, and the benefit only appears if the backend has spare capacity to absorb it. When the backend is already near saturation, hedging raises queue depth, raises latency, and makes the tail worse — the classic case of a mitigation applied at the wrong time.

Recording the fan-out honestly

The measurement problem mirrors the design problem. A fan-out request’s latency must be attributed to the request as a whole, not to an average of its components, because the whole is what the caller experiences. Per-component histograms are useful for finding the slow component, but a service-level objective has to be computed from the fan-out request’s own distribution.

Two mistakes recur. The first is to compute the service’s percentile from per-component percentiles by taking the maximum, which is neither the component’s percentile nor the service’s; the service’s ninety-ninth percentile is a property of the fan-out distribution and has to be measured as such. The second is to measure only completed requests, excluding the ones that hit the deadline and returned partial results. Those are the slowest requests, and excluding them removes exactly the tail the measurement exists to find, as described in coordinated omission in latency measurement.

A fan-out architecture is therefore not merely a performance choice; it is a choice about which distribution the service’s objectives describe. The component distributions can stay unchanged while the service’s tail moves by an order of magnitude, and no amount of component-level tuning recovers the difference. Width is the parameter that governs the relationship, and it deserves to be treated as a capacity decision rather than an implementation detail.