Little's Law, M/M/1 and M/M/c queues

How can we predict performance when load testing a server or set of servers?

Well, it’s a queue: you send work at a rate (something per something) \(\lambda\), it takes \(W\) on average time to do the work, and at any given time you have \(L\) work items getting worked on. That’s Little’s Law: \(L = W \cdot \lambda\), where \(L\) is requests in the system, \(W\) is average base latency in seconds, and \(\lambda\) is the arrival rate of requests/transactions per second.

When doing a load test, you can just run your TPS generator until by some measure you consider the system overloaded: “there’s the max!” But you can also make predictions of what this max, in some sense, should be. You can run a request per second (assuming it runs in under a second) to get the average base latency of your system, \(W\), and if you think about it, you realize that it must equal \(\frac{1}{\mu}\), where \(\mu\) is the maximum TPS the system can take.

So let’s run an example and say that idle state average latency \(W\) is 0.05s (50 milliseconds). From that you predict your system’s \(\mu\) (max TPS) is 20. (Of course that seems insanely low but don’t worry we’ll get to that in a moment.) First observe that it’s a big assumption to believe your system behaves the same idle as it does busy. As your system receives more load, \(\lambda\), you need to absorb that the utilization you read is an average and from the perspective of a given request, it is not guaranteed access to idle resources at any given instant inside that second (measurement window). That is, even well below average 100% utilization, your request can queue. You need a term to model that.

To model this factor of utilization, which will cause a waiting time (\(W_q\) or \(P_{\text{wait}}\)), we can use the M/M/1 queue, which tells us that \(W\) under load will become \(\frac{1}{\mu-\lambda}\). That really makes a lot of sense: if other requests are coming to the server in the same second, there’s a chance you will compete. To continue the above example, this means at 15 TPS (75% utilization), your \(W\) becomes \(\frac{1}{5}\) or 0.2s (200 milliseconds). That is 4 times slower than your idle latency.

There’s actually a dimensionless multiplier you can use directly to calculate “how many times base latency will \(W\) be under arrival load \(\lambda\)?” \(\frac{1}{1-\frac{\lambda}{\mu}}\), where \(\frac{\lambda}{\mu}\) is directly the utilization term, \(\rho\).

Now, you should be asking somewhere in reading the foregoing, “hey, wait a second, what kind of system are we modeling, is it true to my system?”

M/M/1 is a really nice, tractable, understandable model. So obviously it’s also wrong. :) How wrong? We’ll show a table, but let’s actually talk about what it represents first so we have an intuition for why it’s wrong and how to get an exact, correct prediction.

M/M/1 stands for M=Markovian, M=memoryless, 1=worker. Really this models the simplest case: you have one worker handling things serially from one queue. That’s why you can just think of \(\frac{1}{\mu}\) as average latency – imagine a worker standing over a conveyer belt. The \(\frac{1}{1-\frac{\lambda}{\mu}}\) term is just saying, “how long will the average task take when the conveyer belt is adding tasks \(\lambda\)?”

But hey, it’s 2025, and your server has multiple CPUs, and each CPU is probably capable of doing some work for you in parallel. Many server files I see basically do # cpus - 1 to give a server thread sitting on the port and then the rest of the cores are workers handling requests… A scenario properly modeled by M/M/c, where c is the number of cores or servers.

M/M/c uses the Erlang C formula to get the \(W_q\) which is conceptually not too crazy (“what’s the probability all servers are busy over the probability of all server states?”) but it’s a lot of terms to work with in practice.

Zoomed out, we’re still dealing with:

But if we zoom in to \(W_q\), we see:

The blue term is just “what’s the probability that all cores/servers/workers are busy?” And the purple term is just “what’s the probability overall of all other states where only k servers are busy?” As a ratio, you’re asking “what’s the probability all workers are busy out of all their potential busyness states?” That’s the probability you’ll wait.

While \((2)\) isn’t really that bad, it’s a bit much for quick napkin math. We can use an approximation of the queue time for G/G/c by Allen-Cunneen where the exponent is \(\alpha(c) = \sqrt{2(c+1)-1}\). What’s nice about this term is that you can pretty much just memorize common values of \(c\), eg. 16 gives you \(\sqrt{34}-1 \approx 6\). And then \(W_q\) is just \(\frac{\rho^{\alpha(c)}}{c(1-\rho)} \cdot\frac{1}{\mu}\) (service time or \(S\)). This works about like the first pass we did above, where you know your idle time \(W\) is 0.05, and you can multiply it by \(\frac{1}{1-\frac{\lambda}{\mu}}\) with straightforward modifiers from \(c\), \(\rho\), and the approximated power factor. (Recall \(\rho\) is equal to \(\frac{\lambda}{\mu}\).)

Tabling this out, we can see assuming no parallelism massively underestimates our system¹ but that our approximation of Erlang C is pretty decent!

If we do our example with 50ms average base latency, you can see we need to go above 70% before (to my taste anyway) we see significant latency increase:

So if you want a very simple prediction table, you can take common values for cores, which are just bases of two, peg the desired utilization at 70% (you don’t want to waste hardware), and voila you can see your expected latency as a function of \(c\):

You can see that you need to run with some “real” slack in your system to keep overhead low, ie. you want to run at least 8-16 cores to stay close to your base latency. But if you need to spend less money, you can just accept higher latency. That’s often a great option because humans don’t tend to notice 50ms versus 100ms for something like a web server, and (eg.) a 4xl instance (16 vCPUs²) costs 8 times what an l (2 vCPUs) instance costs.

There’s one final observation we can make that handily bookends things. If we peg utilization to 70%, and can assume we have 8+ cores so overhead is negligible, then we can get max TPS just by doing \(\frac{c\rho}{S}\), where \(S\) was just the idle latency we measured by sending a few requests. If you have more hosts, trust your load balancer and just use it to multiply your cores further. This makes your max TPS math simple enough to do in your head!