◇ Math reference · Part 03
M/M/1 and M/M/c
Poisson arrivals, exponential service. The two simplest non-trivial queues — and the workhorses of the Kendall engine.
M/M/1
A single server with Poisson arrivals and exponential service times. The simplest non-trivial queue, and the model Kendall uses for cache nodes (which are typically single-process Redis / Memcached instances).
Key formulas
When to use it
Anywhere requests are queued at a single bottleneck — a single-threaded service, a single DB writer, a Redis primary. Even when the bottleneck has multiple threads, M/M/1 is a useful approximation if the threads share a single queue.
M/M/c (Erlang C)
c identical servers in front of a shared queue, Poisson arrivals, exponential service times. The canonical model for a load-balancer-fronted pool of stateless workers: Lambda concurrent executions, Cloud Run instances, web app replicas, etc.
The key result is Erlang's C formula for the probability that an arriving request has to wait at all (i.e., that all c servers are busy):
From there the mean wait time conditional on waiting is 1 / (cμ − λ), and total mean response time is W = P(wait) / (cμ − λ) + 1/μ.
Worked example
4 backend replicas, each capable of μ = 100 req/s, receiving λ = 300 req/s:
- Utilisation:
ρ = 300 / (4 · 100) = 0.75 P(wait > 0)≈ 0.51 — about half of all requests find every replica busy- Mean wait conditional on waiting:
1 / (400 − 300) s = 10 ms - Mean response time:
0.51 · 10 + 10 = 15.1 ms