6 ms·

Show HN: Queueing theory intro for software developers

126 points by jph 8y ago

jph 8y ago
Request for comments about queueing theory. This is a one-page GitHub README that introduces queueing theory and does it in context of software development, such as product management, message queues, and devops. I'm the author and glad to answer questions here or in the repo. Examples from the page that are the most relevant to Hacker News readers are relevant for devops continuous delivery: * Dτ = Delivery lead time. Some product teams know this as "from concept to customer" or "from spec complete to code complete". * Dμ = Delivery service rate. Some devops teams know this as "continuous deployment frequency" or "shipping X times per day". * Dε = Delivery error ratio. Some quality assurance teams call this "change fail rate" or "percentage of deployment rollbacks". * Rτ = Restore lead time. Some site reliability engineers call this "time to restore service" or "mean time to restore (MTTR)".
- shay_ker 8y ago
  I think queuing theory can be applied to A LOT of different concepts in software development. For instance, some people at Netflix use it to do predictive load balancing: https://youtu.be/6NdxUY1La2I https://youtu.be/6NdxUY1La2I I, personally, have been very interested (something about instantaneous velocity?). Though I was always pretty bad at math, so it takes me a while to get a handle on things.
spapas82 8y ago
I remember queueing theory from the "Automatic telephony" class we had at the university. It was used to solve the problem of how many operators you needed on your call center to have a waiting time of s seconds considering an average call time of s1 seconds and a poisson distribution of incoming calls with a rate r1. Of course queueing theory had various other applications (like the buffers of routers) but the call center one is the most interesting for me.
- zvrba 8y ago
  > a poisson distribution of incoming calls with a rate r1 This is what always confuses me about queueing theory. The analysis is valid assuming a particular distribution, but the justification given for using that distribution was very weak, if at all given. So how is the choice of a distribution justified?
  - spapas82 8y ago
    I think that a poisson distribution is the easiest for the problem to be solved. It may not be the most accurate incoming distribution for all cases but it should be good enough for most cases.
  - beagle3 8y ago
    Poisson is the limit distribution you converge to when n people each flip a coin with probability p to do something, when you drive n to infinity but keep np constant. It is well justified and models the world reasonably well. The parameter changes - e.g. when there’s a service outage, the proportion of people likely to call and report it, does change; but the number of calls per unit time within e.g. the first hour, indeed is Poisson with a higher-than-usual parameter.
- SuddsMcDuff 8y ago
  See also: https://en.wikipedia.org/wiki/Erlang_(unit) https://en.wikipedia.org/wiki/Erlang_(unit)
kreck 8y ago
Nice write up on a completely underrated but important and universal topic. I had to deal with queuing theory a lot in university in a course on stochastic modeling. IMHO you should add an introduction to Markov chains/processes and the concept of stationary distribution.
Sahhaese 8y ago
I did an undergrad course on queueing theory and I'm surprised there's no mention of little's law here. Is there some reason it doesn't "apply" here?
- jph 8y ago
  Good idea! I'll add it.
motohagiography 8y ago
Recommend this video instead. Comes with a python library (Ciw). https://www.youtube.com/watch?v=0_sIus0mPSM https://www.youtube.com/watch?v=0_sIus0mPSM I played with some python queuing to model an analysis pipeline of microservices, as when one of the analytic steps took too long, it jammed up the queue. A visual queue modeller for microservice orchestrations was a project I abandoned. Would be a fun utility, but requires people building services have heard of queues to begin with.
prickledpear 8y ago
This is a good introduction to the terminology and symbology used to describe queues, and the KPIs that it highlights are useful. I'm left wishing that the writeup included some more applications of queuing theory. Are there any unexpected or counterintuitive results that all the terminology makes it easier to understand or express? Otherwise, I'm not too motivated to learn all these Greek letters :)

126 points by jph 8y ago

jph 8y ago

Request for comments about queueing theory. This is a one-page GitHub README that introduces queueing theory and does it in context of software development, such as product management, message queues, and devops. I'm the author and glad to answer questions here or in the repo. Examples from the page that are the most relevant to Hacker News readers are relevant for devops continuous delivery: * Dτ = Delivery lead time. Some product teams know this as "from concept to customer" or "from spec complete to code complete". * Dμ = Delivery service rate. Some devops teams know this as "continuous deployment frequency" or "shipping X times per day". * Dε = Delivery error ratio. Some quality assurance teams call this "change fail rate" or "percentage of deployment rollbacks". * Rτ = Restore lead time. Some site reliability engineers call this "time to restore service" or "mean time to restore (MTTR)".

shay_ker 8y ago
I think queuing theory can be applied to A LOT of different concepts in software development. For instance, some people at Netflix use it to do predictive load balancing: https://youtu.be/6NdxUY1La2I https://youtu.be/6NdxUY1La2I I, personally, have been very interested (something about instantaneous velocity?). Though I was always pretty bad at math, so it takes me a while to get a handle on things.

spapas82 8y ago

I remember queueing theory from the "Automatic telephony" class we had at the university. It was used to solve the problem of how many operators you needed on your call center to have a waiting time of s seconds considering an average call time of s1 seconds and a poisson distribution of incoming calls with a rate r1. Of course queueing theory had various other applications (like the buffers of routers) but the call center one is the most interesting for me.

zvrba 8y ago
> a poisson distribution of incoming calls with a rate r1 This is what always confuses me about queueing theory. The analysis is valid assuming a particular distribution, but the justification given for using that distribution was very weak, if at all given. So how is the choice of a distribution justified?
- spapas82 8y ago
  I think that a poisson distribution is the easiest for the problem to be solved. It may not be the most accurate incoming distribution for all cases but it should be good enough for most cases.
- beagle3 8y ago
  Poisson is the limit distribution you converge to when n people each flip a coin with probability p to do something, when you drive n to infinity but keep np constant. It is well justified and models the world reasonably well. The parameter changes - e.g. when there’s a service outage, the proportion of people likely to call and report it, does change; but the number of calls per unit time within e.g. the first hour, indeed is Poisson with a higher-than-usual parameter.
SuddsMcDuff 8y ago
See also: https://en.wikipedia.org/wiki/Erlang_(unit) https://en.wikipedia.org/wiki/Erlang_(unit)

kreck 8y ago

Nice write up on a completely underrated but important and universal topic. I had to deal with queuing theory a lot in university in a course on stochastic modeling. IMHO you should add an introduction to Markov chains/processes and the concept of stationary distribution.

Sahhaese 8y ago

I did an undergrad course on queueing theory and I'm surprised there's no mention of little's law here. Is there some reason it doesn't "apply" here?

jph 8y ago
Good idea! I'll add it.

motohagiography 8y ago

Recommend this video instead. Comes with a python library (Ciw). https://www.youtube.com/watch?v=0_sIus0mPSM https://www.youtube.com/watch?v=0_sIus0mPSM I played with some python queuing to model an analysis pipeline of microservices, as when one of the analytic steps took too long, it jammed up the queue. A visual queue modeller for microservice orchestrations was a project I abandoned. Would be a fun utility, but requires people building services have heard of queues to begin with.

prickledpear 8y ago

This is a good introduction to the terminology and symbology used to describe queues, and the KPIs that it highlights are useful. I'm left wishing that the writeup included some more applications of queuing theory. Are there any unexpected or counterintuitive results that all the terminology makes it easier to understand or express? Otherwise, I'm not too motivated to learn all these Greek letters :)