It's not explicitly mentioned in the article, but the arrival rate and queue sizes are related via Little's Law [0] — the average number of people in a system is equal to the arrival rate multiplied by the mean wait time, regardless of the arrival distribution, service distribution, or service order (e.g. FIFO, LIFO, random).
I was fortunate enough to take some great queueing theory classes in college, and fondly remember flailing about in Simio [1] trying to get a bank teller simulation to work. Really useful stuff to learn, although it did make me incredibly susceptible to Factorio and similar games.
Agreed! The Principles of Product Development Flow by Donald G. Reinertsen[1] is one of my favorite product management books because it's very conceptual, but man the concepts hit home fast. This summary has a lot of great details [2] and the third chapter is entirely dedicated to the properties of queues.
After, Little's law, he introduces the First Queue Size Control Principle (Q13): Controlling queue size rather than capacity utilization offers a more effective way to manage cycle time and process efficiency. — No mister business stakeholder, adding items to the dev team's to-do list and making sure they are working 110% isn't going to get stuff delivered faster.
Diffusion Principle (Q15): Random processes can lead to queues spinning out of control; these high-queue states can last long and cause significant economic damage. — No mister business stakeholder, we can't fix this one little thing right now, it's bigger than you think and is going to make it harder to deliver the big important project.
Queueing theory is one of my favourite secret superweapons. You can use it to back-of-the-napkin solutions out of feasibility much quicker than it'd take to simulate.
Little's law comes up in the beautiful book 'Programming Pearls' by Jon Bentley in 'Back of the Envelope' calculations:
- `Little’s Law`: The average number of objects in a queue is the product of the entry rate and the average holding time
- Response-time formula for a multi-user system:
- Assume n users of average think time z are connected to an arbitrary system with response time r.
- Each user cycles between thinking and waiting-for-response, so the total number of jobs in the meta-system (consisting of users and the computer system) is fixed at n.
- If you cut the path from the system's output to the users, you see a meta-system with average load n, average response time z + r, and throughput x (measured in jobs per time unit).
- Little’s Law says n = x × (z + r), and solving for r gives r = n/x – z.
> In an ideal world, we wouldn’t need queues. Who likes waiting in lines after all? This would only be possible if the arrival rate of items in a queue was less than or equal to the departure rate and there were no variability in either. Not likely to happen in the real world.
It's not only possible if there's no variability. It's only possible if the arrival rate is always less than number of available processing slots, which can be engineered in a number of ways. (e.g. ensuring that the number of processing units is oversupplied, i.e. exceeds the maximum arrival rate + departure rate; or altering number of processing units dynamically so that utilisation never exceeds 80%.)
However, these approaches are generally not the lowest cost approaches, and so are only used when queueing is incredibly undesirable, e.g. when the cost of maintaining the queue exceeds the cost of holding the spare capacity.
One example for oversupply is airports - most airports have enough gates that incoming aircraft never have to queue, despite that meaning that many gates are empty for most of the day.
For dynamically adjusting capacity examples include listening thread pools for network applications which can spin up new waiting threads whenever the pool free count drops below a certain threshold (the threshold being decided based on the maximum arrival rate). Or a cloud service which spins up new servers whenever cpu utilisation exceeds 80%.
I disliked that they don't explain the logic in the ```arrivals()``` function, but it is because in a uniform distribution from 0 to 1 (which is what ```random()``` is), the probability that a value falls below 1/6 is exactly 1/6, i.e.:
P(random() < 1/6) ~= 1/6 .
Which is how they simulate a dice landing a "6". This explanation could be included in the text.
intereresting read. I might be wrong but I think the central limit theorem is what's contributing to the binomial distribution of arrivals approaching a normal distribution due to the summation of qi-1 + arrivals().
Over many iterations (minutes, hours), you accumulate the effects of these random additions. As a result, even though the distribution is binomial (or approximated Poisson), its behavior for large enough values and sums of multiple minutes becomes approximately gaussian due to CLT.
It's not explicitly mentioned in the article, but the arrival rate and queue sizes are related via Little's Law [0] — the average number of people in a system is equal to the arrival rate multiplied by the mean wait time, regardless of the arrival distribution, service distribution, or service order (e.g. FIFO, LIFO, random).
I was fortunate enough to take some great queueing theory classes in college, and fondly remember flailing about in Simio [1] trying to get a bank teller simulation to work. Really useful stuff to learn, although it did make me incredibly susceptible to Factorio and similar games.
[0] https://en.wikipedia.org/wiki/Little%27s_law
[1] https://www.youtube.com/watch?v=xCzAhKtucck
Agreed! The Principles of Product Development Flow by Donald G. Reinertsen[1] is one of my favorite product management books because it's very conceptual, but man the concepts hit home fast. This summary has a lot of great details [2] and the third chapter is entirely dedicated to the properties of queues.
After, Little's law, he introduces the First Queue Size Control Principle (Q13): Controlling queue size rather than capacity utilization offers a more effective way to manage cycle time and process efficiency. — No mister business stakeholder, adding items to the dev team's to-do list and making sure they are working 110% isn't going to get stuff delivered faster.
Diffusion Principle (Q15): Random processes can lead to queues spinning out of control; these high-queue states can last long and cause significant economic damage. — No mister business stakeholder, we can't fix this one little thing right now, it's bigger than you think and is going to make it harder to deliver the big important project.
[1] https://www.amazon.com/Principles-Product-Development-Flow-G...
[2] https://www.joecotellese.com/posts/principles-of-product-dev...
Queueing theory is one of my favourite secret superweapons. You can use it to back-of-the-napkin solutions out of feasibility much quicker than it'd take to simulate.
I warmly recommend Harchol-Balter: https://www.amazon.com/Performance-Modeling-Design-Computer-... It is an eminintly practical book which is written in terms of computers, goes beyond the basic M/M/1 but without being overbearing.
(The other secret superpower is statistical process control.)
You may have seen it already, but the queueing saga by Defunctland remains fascinating [0].
[0]: https://youtu.be/9yjZpBq1XBE
Little's law comes up in the beautiful book 'Programming Pearls' by Jon Bentley in 'Back of the Envelope' calculations:
- `Little’s Law`: The average number of objects in a queue is the product of the entry rate and the average holding time - Response-time formula for a multi-user system: - Assume n users of average think time z are connected to an arbitrary system with response time r. - Each user cycles between thinking and waiting-for-response, so the total number of jobs in the meta-system (consisting of users and the computer system) is fixed at n. - If you cut the path from the system's output to the users, you see a meta-system with average load n, average response time z + r, and throughput x (measured in jobs per time unit). - Little’s Law says n = x × (z + r), and solving for r gives r = n/x – z.
> In an ideal world, we wouldn’t need queues. Who likes waiting in lines after all? This would only be possible if the arrival rate of items in a queue was less than or equal to the departure rate and there were no variability in either. Not likely to happen in the real world.
It's not only possible if there's no variability. It's only possible if the arrival rate is always less than number of available processing slots, which can be engineered in a number of ways. (e.g. ensuring that the number of processing units is oversupplied, i.e. exceeds the maximum arrival rate + departure rate; or altering number of processing units dynamically so that utilisation never exceeds 80%.)
However, these approaches are generally not the lowest cost approaches, and so are only used when queueing is incredibly undesirable, e.g. when the cost of maintaining the queue exceeds the cost of holding the spare capacity.
One example for oversupply is airports - most airports have enough gates that incoming aircraft never have to queue, despite that meaning that many gates are empty for most of the day.
For dynamically adjusting capacity examples include listening thread pools for network applications which can spin up new waiting threads whenever the pool free count drops below a certain threshold (the threshold being decided based on the maximum arrival rate). Or a cloud service which spins up new servers whenever cpu utilisation exceeds 80%.
A simulation of queue behavior where you can intuitively get a feeling of what happens: https://queuewiz.queuemetrics.com/
This is great! Another simulator that is interesting to explore M/M/1 queues is provided by Wolfram: https://demonstrations.wolfram.com/SimulatingTheMM1Queue/.
Is that a simulation in closed form, ie only parameters change?
How does this compare to the widely used Completely Fair Queue scheduler that Linux uses for block devices?
Enjoyed the read - thanks for sharing! Found a small typo here:
> For the service rate (λ), we can keep things simple and assume that our server can service 10 items per minute with zero variation.
I think it's supposed to be mu and not lambda
Thank you for the sharp eye!
I disliked that they don't explain the logic in the ```arrivals()``` function, but it is because in a uniform distribution from 0 to 1 (which is what ```random()``` is), the probability that a value falls below 1/6 is exactly 1/6, i.e.:
P(random() < 1/6) ~= 1/6 .
Which is how they simulate a dice landing a "6". This explanation could be included in the text.
intereresting read. I might be wrong but I think the central limit theorem is what's contributing to the binomial distribution of arrivals approaching a normal distribution due to the summation of qi-1 + arrivals().
Over many iterations (minutes, hours), you accumulate the effects of these random additions. As a result, even though the distribution is binomial (or approximated Poisson), its behavior for large enough values and sums of multiple minutes becomes approximately gaussian due to CLT.
Does anyone have any good resources they'd recommend for learning queueing theory? I'd like to learn it
That was a nice read. Do you recommend any books for one who wants to get into queue theory?