Capacity and queueing planner

Little’s law — any two of L (items in the system), λ (throughput) and W (time in the system) give the third: L = λW. Pick what to solve, or open a worked example (connection pools, backlog drain, threads).

One server — arrival rate λ, mean service time E[S] and the variabilities Cs² (service) and Ca² (arrivals). Shows M/M/1 (exact), M/D/1 and M/G/1 (exact means from the Pollaczek–Khinchine formula Wq = ρ(1 + Cs²)/(2(1 − ρ))·E[S]) and Kingman’s G/G/1 approximation Wq ≈ ρ/(1 − ρ)·(Ca² + Cs²)/2·E[S], a chart of mean response time against utilisation, and M/M/1 percentiles (t_p = −ln(1 − p)/(μ − λ)).

M/M/c · Erlang C — c servers sharing one queue. Offered load A = λE[S] in Erlangs, utilisation, Erlang C (the probability of waiting), Erlang B (what would be blocked with no queue), mean wait and response, queue length, the service level P(wait ≤ t), exact percentiles of the waiting time, the response time and the number in the system, the response-time tail on a log scale, and a table of more or fewer servers. Erlang B is computed by its recursion B(n) = A·B(n−1)/(n + A·B(n−1)), then C = c·B/(c − A(1 − B)), so thousands of servers are fine.

Knee — response time (mean or p99, as a multiple of the service time) against utilisation for 1 to 64 servers, and where each curve doubles. One queue in front of many servers runs much hotter for the same latency: the case for pooling. The mean can include service variability (Allen–Cunneen); the p99 is exact M/M/c.

Tail at scale — the chance that a request fanning out to n servers meets at least one slow one, 1 − (1 − p)^n; the leaf percentile a user-facing p99 actually depends on, 0.99^(1/n); the largest fan-out that keeps slow requests under 1%; and Dean and Barroso’s measured table.

Hedged & tied — a replica’s latency as a lognormal mixture with a slow mode. A hedged request sends a second copy after the delay d (a percentile of one replica’s latency): P(R > t) = S(t)·S(t − d) past d, at the cost of S(d) extra requests (5% when d is the p95). Charts show the tail with and without hedging and the p99 against the extra load for every choice of d. Tied requests enqueue on two M/M/1 servers that cancel each other when one starts; a seeded Monte Carlo gives the percentiles and how often both servers do the work.

Simulator — a FCFS queue with c servers, customer by customer, in a Web Worker: service times exponential, constant, Erlang-k, lognormal or hyperexponential (H₂) with a chosen Cs², arrivals Poisson, evenly spaced or bursty H₂. It reports means with 95% confidence intervals (30 batch means after a 10% warm-up), P(wait), utilisation and percentiles next to the formula — exact M/M/c, exact Pollaczek–Khinchine for one server with Poisson arrivals, otherwise the Allen–Cunneen approximation — and plots the simulated response-time tail over the exact one.

Capacity planner — peak arrival rate, mean service time, a target (mean, p50 … p99.9 of the response time) and a utilisation cap. Gives the fewest servers that meet both under M/M/c, the utilisation, the share of requests that queue, the most load those servers take and the growth headroom, a table around the answer and a chart of servers against load. Check in the simulator runs the answer through the simulator.

The exact results assume Poisson arrivals, a single FCFS queue, identical servers and, for M/M/c and the planner, exponential service times. Real services have bursts, timeouts, retries and several queues; use the simulator and your own measurements before trusting a server count.

M/G/1 and M/D/1 give exact means only; their percentiles have no simple closed form. Kingman and Allen–Cunneen are approximations (typically within 10–20%, worse at light load).

The hedging model ignores the load the hedges add and assumes replicas are independent. The tied-request model assumes independent M/M/1 queues and instant cancellation of copies not yet started.

Simulated percentiles are estimates; the extreme ones need many customers.

J. D. C. Little, “A Proof for the Queuing Formula: L = λW”, Operations Research 9(3), 1961.

A. K. Erlang, “Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges” (1917) — the B and C formulas.

L. Kleinrock, Queueing Systems, Volume 1: Theory (Wiley, 1975): M/M/1, M/M/c, M/G/1 and the Pollaczek–Khinchine mean-value formula, waiting-time distributions.

M. Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action (Cambridge University Press, 2013): M/M/k, the square-root staffing intuition, the inspection paradox and why variability matters.

J. F. C. Kingman, “The single server queue in heavy traffic”, Proc. Cambridge Philosophical Society 57(4), 1961. Allen–Cunneen: A. O. Allen, Probability, Statistics, and Queueing Theory (Academic Press, 1990).

J. Dean and L. A. Barroso, “The Tail at Scale”, Communications of the ACM 56(2), 2013 — fan-out, Table 1, hedged and tied requests.

Erlang B table values used in the tests: 10 circuits at 1% blocking carry 4.461 Erlangs; 5 circuits carry 1.361 Erlangs.