This is the easiest of the questions to answer, because it asks for the probability of needing the holding space provided that both sevrers are busy. That condition means we can derive the probability just from the transition rates, without knowing how often both servers are busy.

What we’re essentially asking here is “if we find ourselves in a situation where both servers are busy, what is the probability that another request arrives before one of the servers are finished with the requests they are processing?”

Intuition check 3: Recall that we get 75 requests/second into the system on average, and our servers can process them at an average rate of 110 requests/second. What do you think is the probability that another request comes in before one of the servers is finished? What does your gut say?

Let’s find out. The state in the Markov chain where both servers are busy and the holding space is free is \(s_2\). This can transition either up to \(s_3\) if another request arrives first, or back down to \(s_1\), if one of the servers finish processing a request first. The total rate of transitions out of \(s_2\) is then \(\lambda + 2\mu\). The probability that another request arrives first is, thanks to the exponential distribution,

\[P_{2,3} = \frac{\lambda}{\lambda + 2\mu}\]

In other words, if we’re talking about exponentially distributed times between events, the probability that a particular event happens first is just the rate of that event divided by the total rate of all events that can happen.

Given our specific system specifications, we have

\[P_{2,3} = \frac{75}{75 + 2 \cdot 110} \approx 25 \%\]

Thus, when the two servers are busy, it’s most likely one of them will be free before the next request arrives, but one in four times, the next request ends up in the holding space instead.

One of the things we wanted to know was how often the system is idle. Basically, how much of the hours of the day are we paying for expensive servers doing absolutely nothing? This is a measure of how much we have over-sized the system.

Intuition check 4: Recall that the request rate into the system is 75 requests/second, and our servers can process on average 110 requests/second. What percentage of the time do you think both our servers are completely idle? Do you have any intuitive sense for this?

For the actual answer, we can go back to the definition of \(\pi_0\) from the last question, because that is the probability that the Markov chain is in the “completely idle” state. We plug in \(\lambda = 75\) and \(\mu = 110\) and get \(R=0.68\), which then goes into

\[\pi_0 = \left(1 + 0.68 + \frac{0.68^2}{2} + \frac{0.68^3}{4}\right)^{-1} \approx 0.5\]

We find that roughly half the time, our system stands completely idle! Whether or not this is acceptable might depend on the performance metrics we’ll compute next: the request rejection rate and metrics like response time and throughput.

How does this vary with \(R\)? Well, quite simply:

In other words, the more requests your servers have to answer simultaneously, the less likely they are to be idle.7⁷ Someone who has dabbled in queueing theory might be confused that there is still some probability the servers are idle when R is greater than 2. This is because this is a rejecting system. Rejecting a bunch of requests during a burst tends to leave the system more breathing room afterward. It’s never stuck catching up on a long backlog of requests.

How often are requests rejected? This is asking “how often is the system in state \(s_3\) and what’s the rate of incoming additional requests then, that have to be rejected?”

Intuition check 5: Again, we have 75 requests/second incoming on average, and an average processing rate of 110 requests/second for each server. How often do you think requests would be rejected, if you went with your gut feeling?

We can work out the fraction of the time the server is in state \(s_3\), which is

\[\pi_3 = \frac{R^3}{4} \pi_0\]

Then we need to multiply this with \(\lambda\) to get the total rate of requests received in this state (all requests received in that state will be rejected). Let’s call the rate of rejected requests \(v_r\). In our system (see previous question about \(\pi_0\)), this will be

\[v_r = \pi_3 \lambda = \frac{0.68^3}{4} \cdot 0.5 \cdot 75 \approx 3\]

In other words, we will reject 3 requests per second, or 4 % of our workload. This might not be considered great, so we’ll get back to that!

Let’s look at throughput (denoted \(X\)). In a non-rejecting queue, this is easy:

\[X = \lambda\]

This is because every request is served eventually, and that some take longer and some go faster averages out over time. It’s a common mistake to think that the throughput will be equal to the maximum processing rate \(\mu\), but note that the maximum processing rate is never the rate we operate at in production – that would be insane!8⁸ It leads to an infinite queue, thus rendering the system practically unavailable, even if it’s processing things as fast as it can.

We know that our system rejects \(v_r\) requests of the \(\lambda\) received. So the throughput is, quite naturally,

\[X = \lambda - v_r\]

Or, for our current system specifications,

\[X = 75 - 3 = 72\]

Thus, the throughput is 72 requests per second.

Response time is in many cases one of the most important system performance metrics.

Intuition check: What do you think is the response time of our system where each server can handle 110 requests per second?

We can calculate the average response time through Little’s law, which says that average response time \(E(T)\) is given by the average number of requests in the system \(E(N)\), divided by the throughput (X).

Stated mathematically, then, Little’s law says that

\[E(T) = \frac{E(N)}{X}\]

This should be quite intuitive: if you arrive at a bank and there are 6 people ahead of you in line, and the counter seems to be able to handle 12 people per hour, then you know you’ll be there for half an hour.

We know the throughput. How do we figure out the average number of requests in the system? We know the probabilities of each state (\(\pi_0\), \(\pi_1\), etc.) and how many requests are in the system for each of those states (0, 1, etc.) We can compute that weighted average:

\[E(N) = 0\pi_0 + 1\pi_1 + 2\pi_2 + 3\pi_3 =\]

\[= 0\pi_0 + 1\pi_0 R + 2\pi_0 \frac{R^2}{2} + 3\pi_0 \frac{R^3}{4}\]

Using numbers from our system, we have:

\[ E(N) = 0.5 \left(0 + 0.68 + 2 \frac{0.68^2}{2} + 3 \frac{0.68^3}{4}\right) \approx 0.69\]

So we have on average 0.69 requests in the system. This makes the response time

\[ E(T) = \frac{0.69}{72} \approx 0.0096\]

That’s in seconds, so 9.6 milliseconds.9⁹ Note that if we used the arrival rate \(\lambda\) instead of the throughput \(X\) for this, it would look like the response time was faster. That confused me at first: why would we get a slower response time by rejecting requests? But that’s reading the causation the wrong way around: we are forced to drop requests because the response time is too slow not to! That’s about as fast as we can expect, given that the maximum theoretical response time our servers can offer is

\[ T_\mathrm{max} = \frac{1}{110} \approx 0.0091\]

This makes sense: our system stands idle most of the time, so whenever a request comes in, it’s likely it will get the full attention of one of the servers. Only rarely does it have to hang out in the holding space for a short while.

We know that our servers are idle a lot, so maybe we should work with slower servers. We think that 110 requests/second is too much, and the next step down is a server type that does 60 requests/second. If we evaluate the equations at that point instead, we get the following comparison

This doesn’t look very good, though. Two of the 60 requests/second servers are very cheap, but they also don’t perform very well.

What if we get three servers of the slower kind, instead of just two? Or maybe even four? Four servers that can do 60 requests/second ought to be a little bit better than two servers that do 110 requests/second – and it’s still cheaper.

Note that it takes three of the slower servers to match the rejection rate of two of the faster ones – but the response time is much worse! Getting four servers improves the rejection rate, but doesn’t do much for response time.

We like the idea of three slower servers, but our customer complains about the rejection rate.

One obvious thing to do to improve the rejection rate is to make the holding space bigger, so more requests can wait for a free server.

If we keep the three slower servers and adjust the size of the holding space, we have the following results:

Some, perhaps obvious, observations:

• Adding more queueing does not actually improve the performance of our system. What it does is turn immediate rejections into slower responses – as can be witnessed by the increasing response time as queueing spaces are added.
• A longer queue to work on means less idle time for the servers – but this isn’t necessarily a good thing: the servers might now be working on requests where the results are no longer relevant for the customer.

It turns out that response time is very important for our customer. They work in a high-speed industry, and a response that comes a few milliseconds late might as well never have arrived. In particular, they have now clarified that they need an average response time10¹⁰ If you’ve done high-speed stuff, you know that nobody in their right mind would measure response times by the average. Analysing the full distribution of performance from a queueing system will have to be a separate article, though, so just play along here, please. of less than 10 ms, and a request rejection rate of less than 1 request/second. We cannot provide that response time with 60 request/second servers, because the fastest response time they can provide is \(1/60 = 16.7\) ms.

There’s also no queue length that gives the two 110 request/second servers the correct combination of response time and rejection rate: if the queue is long enough to guarantee rejection rate less than 1 per second, the response time is just over 10 ms, and vice versa.

So we try instead one, fat, 195 requests/second server.

With this, the response time looks great, but everything else seems terrible. However, we try increasing the holding space to size four for the fat server:

We are there!

This beastly server stands idle a lot of the time, but that’s what it takes to have fast response times. This goes back to Little’s law, which makes it a very general rule: in order to guarantee fast response, you have to have few things going on.

There’s anothing thing worth noting: we saw before that queues don’t improve performance. However, if performance is good enough to begin with, we can afford longer queues to soak up variability in the work demanded of our servers. But only if we have good performance to begin with.

Yet one more observation: a queue on a performant system doesn’t have to be very long to soak up a lot of variability. It’s when you have a slow system that the queue needs to be really long to avoid rejecting things. But then again, you’re not serving them any faster, you’re just turning rejection into waiting.