Tail Amplification
Description
Tail amplification is a statistical phenomenon observed in process or operation fanout in software and other systems. A single request that fans out to multiple requests to downstream services amplifies the probability of sampling a tail probability that is disproportionate to the sampling rate. This result implies that parallelism does not result in linear probability sampling, and as a result, parallelism with fanout results in worse performance, especially as parallelism increases, than batched processes, such as batch API calls.
This phenomenon is most often observed in latency metrics in distributed software systems, but it's important to remember that it's a purely statistical phenomenon. The same probabilistic amplification will be observed in error rates, for example.
The phenomenon is imperfect, since it assumes that sampling is completely random and independent. However, sampling is not completely random and is not independent.
In practice, tail sampling is usually likely to be higher during fanout in distributed software systems, since the probability of resource consumption is higher during highly parallel job execution as opposed to singular requests, all else being equal. Tail sampling can be better than the formula here suggests, as well. For example, if parallel operations are only happening during low-load times.
Because closer temporal proximity implies less independence, the phenomenon is, as would intuitively seem the case, more likely to be accurate the narrower the window for probability distribution calculation. E.g., the exact amplification will be more likely to be observed for a 1-minute window than for a 1-week window (since the fanout might, as suggested earlier, happen during a low-load time of the week).
Explanation
An upstream service making a single call to a downstream service samples 1 result (of any sort, be it latency or error rate), resulting in a linear translation of any tail result with probability $\phi$. However, if the upstream service makes 2 calls, then it samples 2 results from the distribution. However, the probability $P(\phi,\ 2)$ that the upstream service samples a $\phi$-tail result is greater than $\phi$ since there are 3 cases where at least one $\phi$-tail result is sampled out of a total of 4 cases, with $F$ representing a sample from the $\phi$-tail and $O$ representing a sample outside of the $\phi$-tail: $OF$, $FO$, $FF$ out of $OO$, $OF$, $FO$, $FF$. Each of these cases has a probability (a simple derivation based on the probability of selecting a tail result with probability $\phi$ or a non-tail result with probability $1 - \phi$):
| Sample | Probability Formula | Example: $\phi = \frac{1}{2}$ | Example: $\phi = \frac{1}{100}$ |
| $OO$ | $(1-\phi) \cdot (1-\phi) = (1-\phi)^2$ | $(1 - \frac{1}{2})^2 = \frac{1}{2}^2 = \frac{1}{4}$ | $(1 - \frac{1}{100})^2 = \frac{99}{100}^2 = \frac{9,801}{10,000}$ |
| $OF$ | $(1 - \phi) \cdot \phi = \phi - \phi^2$ | $\frac{1}{2} - \frac{1}{2}^2 = \frac{1}{2} - \frac{1}{4} = \frac{1}{4}$ | $\frac{1}{100} - \frac{1}{100}^2 = \frac{1}{100} - \frac{1}{10,000} = \frac{99}{10,000}$ |
| $FO$ | $\phi \cdot (1-\phi) = \phi - \phi^2$ | $\frac{1}{2} - \frac{1}{2}^2 = \frac{1}{2} - \frac{1}{4} = \frac{1}{4}$ | $\frac{1}{100} - \frac{1}{100}^2 = \frac{1}{100} - \frac{1}{10,000} = \frac{99}{10,000}$ |
| $FF$ | $\phi \cdot \phi = \phi^2$ | $\frac{1}{2}^2 = \frac{1}{4}$ | $\frac{1}{100}^2 = \frac{1}{10,000}$ |
So the total probability of sampling a $\phi$-tail result is:
$$ P(\phi,\ 2) = (\phi - \phi^2) + (\phi-\phi^2) + \phi^2 = 2 \cdot (\phi - \phi^2) + \phi^2 = 2 \phi - \phi^2 $$Note that there are 2 distinct ways to select just one $F$ ($OF$ & $FO$). I.e., there are 2 permutations with 1 $\phi$-tail sample. In general, if we sample $n$ times, there are $\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}$ permutations ("$n$ choose $k$" or a binomial coefficient $C(n,\ k)$) with exactly $k$ $F$-samples and $n-k$ $O$-samples, and since each result with exactly $k$ $F$-samples has a probability of $\phi^k \cdot (1 - \phi)^{n-k}$ (the probability of choosing $F$ exactly $k$ times multiplied by the probability of choosing $O$ exactly $n-k$ times), giving us a probability mass function:
$$ Pr(X=k) = \binom{n}{k} \cdot \phi^k \cdot (1 - \phi)^{n-k} $$(You may recognize this as the binomial distribution.)
We can derive a generalized formula for computing tail amplification by summing over all values for $1 \leq k \leq n$.
Formula
If the fanout factor is $n$ (1 request makes $n$ downstream requests), then the amplification of a tail probability $\phi$ to a new probability $P(\phi, n)$ can be calculated with:
$$ P(\phi,\ n) = \sum_{k=1}^{n} \binom{n}{k} \cdot \phi^k \cdot (1-\phi)^{n-k} $$(This is the Binomial Theorem, and stated another way, the fanout is a binomial experiment.)
Examples
10x Fanout $p99$ Latency Amplification
An upstream service fanning out by a factor of $n=10$ to a downstream service will sample the downstream service's latency $p99$ with this probability:
$$ P(0.01,\ 10) = \sum_{k=1}^{10} \binom{10}{k} \cdot 0.01^k \cdot (1-0.01)^{10-k} = \sum_{k=1}^{10} \binom{10}{k} \cdot 0.01^k \cdot 0.99^{10-k} \approx 0.0956 = 9.56\% $$This result implies that, all else being equal, the $p90$ latency of the upstream service will be determined by the $p99$ latency of the downstream service.
10x Fanout $p999$ Failure Amplification
An upstream service fanning out by a factor of $n = 10$ to a downstream service with a $0.1\%$ failure rate will fail its own requests (without partial retries or other mitigations) with this rate:
$$ P(0.001,\ 10) = \sum_{k=1}^{10} \binom{10}{k} \cdot 0.001^k \cdot (1-0.001)^{10-k} = \sum_{k=1}^{10} \binom{10}{k} \cdot 0.001^k \cdot 0.999^{10-k} \approx 0.009955 \approx 0.0100 = 1\% $$I.e., approximately $1\%$ of requests to the upstream service will fail if it fans out by a factor of 10 to a downstream service with a $0.1\%$ failure rate.
100x Fanout $p999$ Failure Amplification
An upstream service fanning out by a factor of $n = 100$ to a downstream service with a $0.1\%$ failure rate will fail its own requests (without partial retries or other mitigations) with this rate:
$$ P(0.001,\ 100) = \sum_{k=1}^{100} \binom{100}{k} \cdot 0.001^k \cdot (1-0.001)^{100-k} = \sum_{k=1}^{100} \binom{100}{k} \cdot 0.001^k \cdot 0.999^{100-k} \approx 0.0952 = 9.52\% $$I.e., approximately $9.52\%$ of requests to the upstream service will fail if it fans out by a factor of 100 to a downstream service with a $0.1\%$ failure rate.
100x Fanout $p9999$ Failure Amplification
An upstream service fanning out by a factor of $n = 100$ to a downstream service with a $0.01\%$ failure rate will fail its own requests (without partial retries or other mitigations) with this rate:
$$ P(0.0001,\ 100) = \sum_{k=1}^{100} \binom{100}{k} \cdot 0.0001^k \cdot (1-0.0001)^{100-k} = \sum_{k=1}^{100} \binom{100}{k} \cdot 0.0001^k \cdot 0.9999^{100-k} \approx 0.00995066 \approx 0.0100 = 1\% $$I.e., approximately $1\%$ of requests to the upstream service will fail if it fans out by a factor of 100 to a downstream service with a $0.01\%$ failure rate.
