What a Serving System Must Guarantee

The four quantities

DefinitionOffered load, throughput, concurrency, utilisation

For a system in steady state over a long interval:

• Offered load $\lambda$ — the rate at which requests arrive, in requests per second. It is a property of the world, not of your system.
• Service time $S$ — the time one request occupies a server, excluding any time spent waiting. It is a random variable; write $\E[S]$ for its mean.
• Throughput $X$ — the rate at which requests complete.
• Concurrency $L$ — the number of requests inside the system at a given instant, waiting or being served.
• Latency $W$ — the time from arrival to completion, including queueing: $W \ge S$ always.
• Capacity $\mu$ — the maximum completion rate. With $c$ identical servers each able to complete $1/\E[S]$ requests per second, $\mu = c/\E[S]$.
• Utilisation $\rho = \lambda/\mu$ — the fraction of capacity the offered load asks for.

Stability

PropositionStability requires utilisation below one

Let $A(t)$ be the number of arrivals and $D(t)$ the number of departures by time $t$, with $A(t)/t \to \lambda$ and departure capacity $D(t)/t \le \mu$. If $\lambda > \mu$ then the backlog $L(t) = A(t) - D(t)$ satisfies $L(t) \to \infty$. Consequently throughput $X = \lambda$ is achievable only when $\rho = \lambda/\mu \le 1$, and, as the next page shows, only $\rho < 1$ keeps latency finite.

ProofReveal

Which latency you mean

A latency distribution is summarised by its quantiles. Write $F$ for the CDF of $W$ and

$$q_p \ =\ \inf\{t : F(t) \ge p\}$$

for the $p$-quantile — "p99" is $q_{0.99}$, the value 99% of requests come in under.

PropositionThe mean constrains the tail only by a factor of 1/(1-p)

Let $W \ge 0$ have mean $m$. Then for every $p \in (0,1)$,

$$q_p(W) \ \le\ \frac{m}{1-p} ,$$

and the bound is attained: for every $\varepsilon > 0$ there is a distribution with mean $m$ whose $p$-quantile exceeds $m/(1-p) - \varepsilon$. In particular a mean of 200 ms permits a p99 of just under 20 s, and permits nothing worse.

ProofReveal

Composing stages

Real requests pass through several stages in sequence: a load balancer, a tokeniser, a retrieval call, the model itself. It is tempting to budget a latency target by adding up per-stage p99s.

PropositionPercentiles do not add

Let $W = W_1 + \cdots + W_k$ with the $W_i$ non-negative. Then

$$q_p(W) \ \le\ \sum_{i=1}^k q_{p_i}(W_i) \qquad \text{whenever} \quad \sum_{i=1}^k (1-p_i) \le 1-p .$$

Independence is not needed; the bound holds for arbitrarily dependent stages.

ProofReveal

What an SLO actually asserts

DefinitionService-level objective

A service-level objective is a triple: a metric, a quantile, and a window. "p99 latency under 500 ms over a rolling 28 days" asserts that, of the requests in any such window, at most 1% took longer than 500 ms.

Three consequences follow immediately from the definitions and are worth stating because they are routinely missed.

1. An SLO is a budget, not a bound. 1% of a billion requests is ten million slow requests. The SLO permits them.
2. The window matters as much as the quantile. A 28-day p99 permits a single catastrophic hour, because one hour is 0.15% of 28 days. A one-hour p99 does not.
3. Quantiles of quantiles are not quantiles. Averaging per-minute p99s over a day does not give the day's p99, and in general underestimates it, because the average of a set of quantiles is not the quantile of the pooled distribution.

Where this goes

The next pages turn these definitions into predictions. Little's Law and the Capacity of a Serving System pins down the relationship between concurrency, throughput and latency with no distributional assumptions at all. Queueing and the Utilisation Wall explains why latency explodes well before $\rho = 1$, and Tail Latency and Fan-Out Amplification explains why the explosion is felt first, and worst, by requests that touch many machines.