[HN Gopher] Dice and Queues
___________________________________________________________________
Dice and Queues
Author : jcartw
Score : 58 points
Date : 2025-04-10 02:38 UTC (20 hours ago)
(HTM) web link (justincartwright.com)
(TXT) w3m dump (justincartwright.com)
| jcalx wrote:
| 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
| dleeftink wrote:
| You may have seen it already, but the queueing saga by
| Defunctland remains fascinating [0].
|
| [0]: https://youtu.be/9yjZpBq1XBE
| kqr wrote:
| 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.)
| code_biologist wrote:
| 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...
| degamad wrote:
| > 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%.
| Datagenerator wrote:
| How does this compare to the widely used Completely Fair Queue
| scheduler that Linux uses for block devices?
| alex5207 wrote:
| Enjoyed the read - thanks for sharing! Found a small typo here:
|
| > For the service rate (l), 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
| jcartw wrote:
| Thank you for the sharp eye!
| halayli wrote:
| 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.
| kimi wrote:
| A simulation of queue behavior where you can intuitively get a
| feeling of what happens: https://queuewiz.queuemetrics.com/
| kamma4434 wrote:
| Is that a simulation in closed form, ie only parameters change?
| jcartw wrote:
| This is great! Another simulator that is interesting to explore
| M/M/1 queues is provided by Wolfram:
| https://demonstrations.wolfram.com/SimulatingTheMM1Queue/.
| zekrioca wrote:
| 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.
| incognito124 wrote:
| Does anyone have any good resources they'd recommend for learning
| queueing theory? I'd like to learn it
| carlosneves wrote:
| That was a nice read. Do you recommend any books for one who
| wants to get into queue theory?
___________________________________________________________________
(page generated 2025-04-10 23:01 UTC)