Tail Latency and Fan-Out Amplification

The maximum is the parent

PropositionThe distribution of the slowest of n calls

Let a parent request issue $n$ sub-requests with latencies $X_1,\dots,X_n$, independent and identically distributed with CDF $F$, and let the parent complete when the last child does. Then the parent latency $M_n = \max_i X_i$ has

$$\Pr[M_n \le t] \;=\; F(t)^n , \qquad \Pr[M_n > t] \;=\; 1 - \bigl(1-\bar F(t)\bigr)^n \;\le\; n\,\bar F(t) ,$$

where $\bar F = 1-F$ is the tail function.

ProofReveal

CorollaryFan-out shifts which quantile you must control

To achieve $\Pr[M_n \le t] \ge p$ it is necessary and sufficient that each child satisfies $F(t) \ge p^{1/n}$ — that is, $t$ must be the child's $p^{1/n}$ quantile. For $p = 0.99$:

$$\begin{array}{r|cccc} n & 1 & 10 & 100 & 1000\\ \hline p^{1/n} & 0.99 & 0.99899 & 0.999899 & 0.9999899 \end{array}$$

So a hundred-way fan-out turns a p99 target on the parent into a p99.99 target on each child.

ProofReveal

What hedging buys

The standard countermeasure is to send a second copy of a sub-request if the first has not returned by some deadline $d$, and take whichever answers first.

PropositionA hedged request truncates the tail at the hedge delay

Let $X$ be the latency of one attempt, with tail $\bar F$. Issue a second, independent attempt at time $d$ if the first is still outstanding, and let $Y$ be the time until the first response. Then for $t > d$,

$$\Pr[Y > t] \;=\; \bar F(t)\cdot \bar F(t-d) ,$$

and for $t \le d$, $\Pr[Y>t] = \bar F(t)$.

ProofReveal

Take $d$ to be the p95 of $X$. Then for $t$ beyond $d$ the tail is the product of two small numbers rather than one. If $\bar F$ decays exponentially with scale $\tau$, so $\bar F(t) = e^{-t/\tau}$, the hedged tail is $e^{-(2t-d)/\tau}$ — the decay rate has doubled.

PropositionThe extra load a hedge creates

If the hedge fires at delay $d = q_p(X)$, the expected number of attempts per logical request is

$$\E[\#\text{attempts}] \;=\; 1 + \Pr[X > d] \;=\; 1 + (1-p) ,$$

so hedging at the p95 costs at most 5% additional load, and at the p99 at most 1%.

ProofReveal

Reading the numbers

Two consequences are worth carrying around.

1. Measure the quantile your architecture actually consumes. If a request fans out $n$ ways, instrument the child at $1 - (1-p)/n$, not at $p$. For $n = 100$ and a p99 parent target that is p99.99 — which needs on the order of $10^5$ samples to estimate at all, a measurement problem in its own right.
2. Reducing fan-out is a latency optimisation. Halving the number of shards a query touches moves the consumed quantile from $p^{1/n}$ to $p^{2/n}$, which is a strictly easier target. This is a real argument for larger shards, and it trades against the memory and pooling arguments elsewhere in this field.