8 ms·

It’s Time for Some Queueing Theory

282 points by sogen 7y ago

tomsthumb 7y ago
There’s a great Kubecon talk on Queueing Theory if you want a bit more: https://youtube.com/watch?v=yf6wSsOFqdI https://youtube.com/watch?v=yf6wSsOFqdI
lcuff 7y ago
Does it get more light-weight than this? Grrr. It's time for fluff.
- kyllo 7y ago
  I had never heard of queueing theory until I read about it in a supply chain management textbook, and would have appreciated being at least aware of its existence much earlier than that. This is light, but it's a great way to introduce the topic to people who have never been exposed to it. By the way, I also worked in a supply chain management department of about two thousand people for three years and I never heard anyone else mention queueing theory while I was there, so now I really wish at least this blog post were required reading for everyone in that department.
numlock86 7y ago
From the article: > We assume customer arrivals and customer service times are random (details later). Where are those details? I expected some math about the random distribution and how that adds up, but I can't even find the corresponding text passage to explain anything related to that.
- moandcompany 7y ago
  They probably intend to discuss the Poisson distribution which is commonly used to characterize random customer inter-arrival times, and similar or other distributions for how long it takes to process the customer's request. https://www.wikiwand.com/en/Poisson_distribution https://www.wikiwand.com/en/Poisson_distribution Queueing theory is a pretty common topic in Electrical Engineering and Computer Science curriculum related to scheduling or computer networks. Also part of Operations Research curriculum. Probably worth reading more about Leonard Kleinrock's work if you are interested in this topic and the context where it was applied: https://www.wikiwand.com/en/Leonard_Kleinrock https://www.wikiwand.com/en/Leonard_Kleinrock
  - Animats 7y ago
    Reading that, years ago, was what led me to figure out how to approach congestion control. Everybody was reading Kleinrock and assuming random arrival rates. Klienrock had done a study of Western Union Plan 55-A, which was Sendmail for telegrams, built with paper tape for buffering and telephone switches for routing. That led to the original analyses of how the Arpanet should work. The trouble with that approach is that it assumes packets just arrive randomly no matter what the network is doing. That was true for Plan 55-A; delays in the network had little influence on the submission rate for new telegrams. But it's not true once you put a protocol with backpressure, like TCP, on top of the raw packets. Now congestion becomes a feedback control system. I figured that out in the early 1980s and wrote RFC 970.[1] The idea of having one big line was introduced by banks some time in the 1970s. It helped some. But the big breakthrough came from Walter Wriston [2], CEO of what is now Citibank, who pushed his people to develop in-bank terminals and then ATMs, to get rid of the lines entirely. A classic piece of advice from retail consultants is "never place an obstacle in front of a customer who is ready to buy". Amazon's "one-click ordering" is the classic on-line example. Gap stores used to be noted for getting this. They had big, empty counters and more than enough people ready to check customers out. All that crap retailers put at checkouts? Few customers buy it, and it limits how much merchandise the customer can put on the counter. The big queuing theory insight for line management is that if you don't have some idle time, in an open loop situation the line length will go to infinity. In the real world, you start to lose customers. That's how closed loop feedback reacts to retailer incompetence. [1] https://tools.ietf.org/html/rfc970 https://tools.ietf.org/html/rfc970 [2] https://en.wikipedia.org/wiki/Walter_Wriston https://en.wikipedia.org/wiki/Walter_Wriston
    - iamnotacrook 7y ago
      "All that crap retailers put at checkouts? Few customers buy it, and it limits how much merchandise the customer can put on the counter." People select less stuff when they're shopping because they're concerned it won't fit on the counter, or they take a bunch of stuff there but end up not paying for it because it won't fit, or what?
      - 7y ago
- Pazzaz 7y ago
  That is actually a quote from the John Cook article[0] and so you can find the details of the random process there. [0]: https://www.johndcook.com/blog/2008/10/21/what-happens-when-you-add-a-new-teller/ https://www.johndcook.com/blog/2008/10/21/what-happens-when-...
- lapinot 7y ago
  Indeed some stuff is missing... Poisson distributions model independently random events that have a given average rate. Its variable counts the number of events occurring before t. Waiting time between events is an exponential distribution (derived by computing the probability that 0 event occur before t). Fun application: suppose you want to take a bus, on average they are independently 10mins apart (rate 1/10). On average when you arrive uniformly random, the next bus will arrive in 10mins (and likewise the last one was 10mins ago). This can be intuitively understood because you have more chances to arrive at a time when buses are further apart. The mean of the waiting time is 1/rate and not 1/(2*rate) like we could imagine.
- buckminster 7y ago
  Surprisingly, the distribution is not important. See Little's Law. https://en.m.wikipedia.org/wiki/Little%27s_law https://en.m.wikipedia.org/wiki/Little%27s_law
  - plorkyeran 7y ago
    Little's Law is not directly applicable here. LL tells us the average wait time given the arrival rate and average size of the queue. Only one of those three things are known, and the distribution is relevant for calculating a second (letting us use LL to find the third). There's a really obvious counterexample to "the distribution doesn't matter": with a uniform distribution, the average wait time will be zero.
winrid 7y ago
Thought I'd hear about some AMPQ... :)
- nurettin 7y ago
  What is there to hear about AMQP? Make exchanges, bind queues and send to routing keys. Add cluster and load balance for bonus points. Now fast-food queues, that is an interesting problem.
jph 7y ago
Great article! I'm adding it to the queueing theory intro repo: https://github.com/joelparkerhenderson/queueing_theory https://github.com/joelparkerhenderson/queueing_theory
jinpan 7y ago
Another fun surprising result from queuing theory is that if you have a buffer of pending RPC's that have some deadline, it is better to service them in a "unfair" LIFO order, as opposed to a fairer FIFO order. [0] goes into more gory details. In the bank example from the article, LIFO would dramatically shorten the median wait time (~5 minutes), at the cost of really upsetting customers [1]. In the case of a support queue, where the waiters are blind to each other, this cost could be reconsidered ... [0] https://arxiv.org/pdf/1008.4895.pdf https://arxiv.org/pdf/1008.4895.pdf [1] from the article, "We really, really hate it when someone shows up after us but gets served before us.
- pstuart 7y ago
  I thought the queuing algorithm for banks was to line up transactions so the largest go through first to increase the opportunity for overdraft fees.
  - ahmedalsudani 7y ago
    Debits first, credits last—just as the lord commanded.
    - gumby 7y ago
      By the way "debit" means "given" -- as in you "give" the money to the bank. "credit" means the money is being taken from them. Tells you a lot about their attitude to your money!
      - irishsultan 7y ago
        Debit comes from a latin verb that means to owe, and credit from a verb that means to trust. So a debit card is for the money that the bank owes you, and a credit card is for money that the bank trusts you will pay them back.
        dullgiulio 7y ago
hinkley 7y ago
My favorite bit from queuing theory is the observation that if you execute the shortest tasks first, the average wait time for any one task is minimized.
- amelius 7y ago
  Curious, does Linux take this into account when it schedules processes? (Of course, it can't know the execution time of a process beforehand, but it can deprioritize long-running processes, since the ETA for a long-running process is larger than for a short-running process).
  - Filligree 7y ago
    Of a sort. It down-prioritizes processes which were previously descheduled by timer, and up-prioritizes those which are waiting for I/O. This generally has the desired effect of prioritizing interactive work. If you mean prioritization based on total CPU time then no, I don't think it does that, but the above does approximate prioritization based on a (very small) sliding window of CPU use.
    - hinkley 7y ago
      I wonder if that policy is purely empirical or if the people who decided to favor I/O had a more sophisticated understanding of the system. Since a lot of algorithms have a log(n) component to them, either expressly or due to CPU physics, calling a function twice as often with half as much data may reduce call time a little bit, even a hair. I could see someone making a design decision based on a 2% disparity between two alternatives.
- lapinot 7y ago
  Are you sure? Aren't you talking about the average wait time for all tasks combined (sum of wait times) instead of the wait time for any one task. Obviously the optimal wait time any one task is 0, if you start right away. Intuitively i'd say if you sort the queue by size and always process the shortest task, you may indefinitely stall some long tasks.
z3t4 7y ago
You should not stare blindly on the average. It's in the 1% slowest requests the dragons are hidden.
- vitus 7y ago
  Not when you're looking at high utilization, as presented in the example in the article. For that particular case (a M/M/1 queue with arrival rate of 5.8 customers per hour and a service rate of 6 per hour), even your median response time is 3.5 hours. Unbounded FIFOs are _really_ bad once you get to high utilization.
oftenwrong 7y ago
Relevant to queueing theory: "Stop Rate Limiting! Capacity Management Done Right" by Jon Moore https://youtube.com/watch?v=m64SWl9bfvk https://youtube.com/watch?v=m64SWl9bfvk
davidw 7y ago
I'd definitely appreciate some 'next steps for the working programmer' that aren't a deep dive into math. What we need to be able to do is realize what sort of problem we're facing, how to describe it, and maybe what solutions might look like or where to learn more about them. At a certain company, we were dealing with a limited number of phone numbers that could be used in on-line ads to get people to call for more information. Reuse the numbers too quickly and you wouldn't be able to track what people were calling about. Having too many idle numbers cost money. Seemed like an interesting problem to me and it looked like "queuing theory" even if I didn't know the details. I suggested we could probably figure out a way to optimize our usage of the numbers. Blank looks and "let's just use 10 numbers per client and see how that goes". I'm definitely someone who's wary of coding up a big, complex solution as the first iteration, so I could live with "let's start with a number", but I think that needed to feed into a further iteration using the knowledge we gained and a bit more thinking about the problem.
- kragen 7y ago
  Maybe the next steps for the working programmer are, in fact, a deep dive into math.
  - davidw 7y ago
    Adam Smith's words about specialization apply to programming too. One of the best places I ever worked, I sat right next to a guy doing computer vision algorithms. He had a PhD, and was extremely smart and knowledgeable and fun to talk with. He also wasn't the most... practical programmer, and I was able to give him a variety of suggestions about how to improve his code, and of course I had ideas about data modelling and web programming that he didn't know much about. Neither one of us knew much about the details of the firmware, or the optics (mirrors and lenses and such) that another colleague was working on. I guess the point is that for some of us, the point is that we're probably not good candidates to become domain experts, but knowing enough to find help is probably a good move.
    - kragen 7y ago
wodenokoto 7y ago
Not really any theory, but some interesting anecdotes and research results. I’d wished the author at least explained the 5 hour average wait. I mean, if the queue started at 30 people, then I can see it, but not if we start at 0.
- isaacg 7y ago
  In that setting, the line queue is 30 people long, on average. Sometimes more, sometimes less. Because 5.8 people arrive an hour out of the maximum of 6 that can be served an hour, and 6/(6-5.8)=30, the average queue length is 30.
tombert 7y ago
About a year ago, I was waiting in line at Dollar Tree (guilty pleasure), and I had to wait almost a half-hour in line. Even though there were two cashiers, they were constantly communicating back and forth, introducing a constant blocking factor and effectively reducing it one queue, and I was trying to think about how to model this with pi-calculus while I was waiting. Obviously there's a math for basically anything, but reading this makes me glad I'm not the only one who has thought about this. This article has given me some reading fodder for this weekend...thanks!
takk309 7y ago
If any one is interested in a diving into queuing theory as it pertains to vehicular traffic, check out chapters 11 and 12 of Traffic Flow Fundamentals by Adolf May. [1] Chapter 11 discusses shockwaves and moving queues. Chapter 12 discusses both deterministic and stochastic queuing. [1] https://www.scribd.com/document/253416450/Traffic-Flow-Fundamentals https://www.scribd.com/document/253416450/Traffic-Flow-Funda...
pcvarmint 7y ago
Myron Hlynka https://web2.uwindsor.ca/math/hlynka/queue.html https://web2.uwindsor.ca/math/hlynka/queue.html
c3534l 7y ago
I'm always annoyed that whenever someone purports to have an article or book on queue theory, no one actually has any math. So I'm just left with a bunch of anectdotes and no understanding.

282 points by sogen 7y ago

There’s a great Kubecon talk on Queueing Theory if you want a bit more: https://youtube.com/watch?v=yf6wSsOFqdI https://youtube.com/watch?v=yf6wSsOFqdI

lcuff 7y ago

Does it get more light-weight than this? Grrr. It's time for fluff.

kyllo 7y ago
I had never heard of queueing theory until I read about it in a supply chain management textbook, and would have appreciated being at least aware of its existence much earlier than that. This is light, but it's a great way to introduce the topic to people who have never been exposed to it. By the way, I also worked in a supply chain management department of about two thousand people for three years and I never heard anyone else mention queueing theory while I was there, so now I really wish at least this blog post were required reading for everyone in that department.

numlock86 7y ago

From the article: > We assume customer arrivals and customer service times are random (details later). Where are those details? I expected some math about the random distribution and how that adds up, but I can't even find the corresponding text passage to explain anything related to that.

moandcompany 7y ago
They probably intend to discuss the Poisson distribution which is commonly used to characterize random customer inter-arrival times, and similar or other distributions for how long it takes to process the customer's request. https://www.wikiwand.com/en/Poisson_distribution https://www.wikiwand.com/en/Poisson_distribution Queueing theory is a pretty common topic in Electrical Engineering and Computer Science curriculum related to scheduling or computer networks. Also part of Operations Research curriculum. Probably worth reading more about Leonard Kleinrock's work if you are interested in this topic and the context where it was applied: https://www.wikiwand.com/en/Leonard_Kleinrock https://www.wikiwand.com/en/Leonard_Kleinrock
- Animats 7y ago
  Reading that, years ago, was what led me to figure out how to approach congestion control. Everybody was reading Kleinrock and assuming random arrival rates. Klienrock had done a study of Western Union Plan 55-A, which was Sendmail for telegrams, built with paper tape for buffering and telephone switches for routing. That led to the original analyses of how the Arpanet should work. The trouble with that approach is that it assumes packets just arrive randomly no matter what the network is doing. That was true for Plan 55-A; delays in the network had little influence on the submission rate for new telegrams. But it's not true once you put a protocol with backpressure, like TCP, on top of the raw packets. Now congestion becomes a feedback control system. I figured that out in the early 1980s and wrote RFC 970.[1] The idea of having one big line was introduced by banks some time in the 1970s. It helped some. But the big breakthrough came from Walter Wriston [2], CEO of what is now Citibank, who pushed his people to develop in-bank terminals and then ATMs, to get rid of the lines entirely. A classic piece of advice from retail consultants is "never place an obstacle in front of a customer who is ready to buy". Amazon's "one-click ordering" is the classic on-line example. Gap stores used to be noted for getting this. They had big, empty counters and more than enough people ready to check customers out. All that crap retailers put at checkouts? Few customers buy it, and it limits how much merchandise the customer can put on the counter. The big queuing theory insight for line management is that if you don't have some idle time, in an open loop situation the line length will go to infinity. In the real world, you start to lose customers. That's how closed loop feedback reacts to retailer incompetence. [1] https://tools.ietf.org/html/rfc970 https://tools.ietf.org/html/rfc970 [2] https://en.wikipedia.org/wiki/Walter_Wriston https://en.wikipedia.org/wiki/Walter_Wriston
  - iamnotacrook 7y ago
    "All that crap retailers put at checkouts? Few customers buy it, and it limits how much merchandise the customer can put on the counter." People select less stuff when they're shopping because they're concerned it won't fit on the counter, or they take a bunch of stuff there but end up not paying for it because it won't fit, or what?
    - 7y ago
Pazzaz 7y ago
That is actually a quote from the John Cook article[0] and so you can find the details of the random process there. [0]: https://www.johndcook.com/blog/2008/10/21/what-happens-when-you-add-a-new-teller/ https://www.johndcook.com/blog/2008/10/21/what-happens-when-...
lapinot 7y ago
Indeed some stuff is missing... Poisson distributions model independently random events that have a given average rate. Its variable counts the number of events occurring before t. Waiting time between events is an exponential distribution (derived by computing the probability that 0 event occur before t). Fun application: suppose you want to take a bus, on average they are independently 10mins apart (rate 1/10). On average when you arrive uniformly random, the next bus will arrive in 10mins (and likewise the last one was 10mins ago). This can be intuitively understood because you have more chances to arrive at a time when buses are further apart. The mean of the waiting time is 1/rate and not 1/(2*rate) like we could imagine.
buckminster 7y ago
Surprisingly, the distribution is not important. See Little's Law. https://en.m.wikipedia.org/wiki/Little%27s_law https://en.m.wikipedia.org/wiki/Little%27s_law
- plorkyeran 7y ago
  Little's Law is not directly applicable here. LL tells us the average wait time given the arrival rate and average size of the queue. Only one of those three things are known, and the distribution is relevant for calculating a second (letting us use LL to find the third). There's a really obvious counterexample to "the distribution doesn't matter": with a uniform distribution, the average wait time will be zero.

winrid 7y ago

Thought I'd hear about some AMPQ... :)

nurettin 7y ago
What is there to hear about AMQP? Make exchanges, bind queues and send to routing keys. Add cluster and load balance for bonus points. Now fast-food queues, that is an interesting problem.

jph 7y ago

Great article! I'm adding it to the queueing theory intro repo: https://github.com/joelparkerhenderson/queueing_theory https://github.com/joelparkerhenderson/queueing_theory

jinpan 7y ago

Another fun surprising result from queuing theory is that if you have a buffer of pending RPC's that have some deadline, it is better to service them in a "unfair" LIFO order, as opposed to a fairer FIFO order. [0] goes into more gory details. In the bank example from the article, LIFO would dramatically shorten the median wait time (~5 minutes), at the cost of really upsetting customers [1]. In the case of a support queue, where the waiters are blind to each other, this cost could be reconsidered ... [0] https://arxiv.org/pdf/1008.4895.pdf https://arxiv.org/pdf/1008.4895.pdf [1] from the article, "We really, really hate it when someone shows up after us but gets served before us.

pstuart 7y ago
I thought the queuing algorithm for banks was to line up transactions so the largest go through first to increase the opportunity for overdraft fees.
- ahmedalsudani 7y ago
  Debits first, credits last—just as the lord commanded.
  - gumby 7y ago
    By the way "debit" means "given" -- as in you "give" the money to the bank. "credit" means the money is being taken from them. Tells you a lot about their attitude to your money!
    - irishsultan 7y ago
      Debit comes from a latin verb that means to owe, and credit from a verb that means to trust. So a debit card is for the money that the bank owes you, and a credit card is for money that the bank trusts you will pay them back.
      - dullgiulio 7y ago

hinkley 7y ago

My favorite bit from queuing theory is the observation that if you execute the shortest tasks first, the average wait time for any one task is minimized.

amelius 7y ago
Curious, does Linux take this into account when it schedules processes? (Of course, it can't know the execution time of a process beforehand, but it can deprioritize long-running processes, since the ETA for a long-running process is larger than for a short-running process).
- Filligree 7y ago
  Of a sort. It down-prioritizes processes which were previously descheduled by timer, and up-prioritizes those which are waiting for I/O. This generally has the desired effect of prioritizing interactive work. If you mean prioritization based on total CPU time then no, I don't think it does that, but the above does approximate prioritization based on a (very small) sliding window of CPU use.
  - hinkley 7y ago
    I wonder if that policy is purely empirical or if the people who decided to favor I/O had a more sophisticated understanding of the system. Since a lot of algorithms have a log(n) component to them, either expressly or due to CPU physics, calling a function twice as often with half as much data may reduce call time a little bit, even a hair. I could see someone making a design decision based on a 2% disparity between two alternatives.
lapinot 7y ago
Are you sure? Aren't you talking about the average wait time for all tasks combined (sum of wait times) instead of the wait time for any one task. Obviously the optimal wait time any one task is 0, if you start right away. Intuitively i'd say if you sort the queue by size and always process the shortest task, you may indefinitely stall some long tasks.

z3t4 7y ago

You should not stare blindly on the average. It's in the 1% slowest requests the dragons are hidden.

vitus 7y ago
Not when you're looking at high utilization, as presented in the example in the article. For that particular case (a M/M/1 queue with arrival rate of 5.8 customers per hour and a service rate of 6 per hour), even your median response time is 3.5 hours. Unbounded FIFOs are _really_ bad once you get to high utilization.

oftenwrong 7y ago

Relevant to queueing theory: "Stop Rate Limiting! Capacity Management Done Right" by Jon Moore https://youtube.com/watch?v=m64SWl9bfvk https://youtube.com/watch?v=m64SWl9bfvk

davidw 7y ago

I'd definitely appreciate some 'next steps for the working programmer' that aren't a deep dive into math. What we need to be able to do is realize what sort of problem we're facing, how to describe it, and maybe what solutions might look like or where to learn more about them. At a certain company, we were dealing with a limited number of phone numbers that could be used in on-line ads to get people to call for more information. Reuse the numbers too quickly and you wouldn't be able to track what people were calling about. Having too many idle numbers cost money. Seemed like an interesting problem to me and it looked like "queuing theory" even if I didn't know the details. I suggested we could probably figure out a way to optimize our usage of the numbers. Blank looks and "let's just use 10 numbers per client and see how that goes". I'm definitely someone who's wary of coding up a big, complex solution as the first iteration, so I could live with "let's start with a number", but I think that needed to feed into a further iteration using the knowledge we gained and a bit more thinking about the problem.

kragen 7y ago
Maybe the next steps for the working programmer are, in fact, a deep dive into math.
- davidw 7y ago
  Adam Smith's words about specialization apply to programming too. One of the best places I ever worked, I sat right next to a guy doing computer vision algorithms. He had a PhD, and was extremely smart and knowledgeable and fun to talk with. He also wasn't the most... practical programmer, and I was able to give him a variety of suggestions about how to improve his code, and of course I had ideas about data modelling and web programming that he didn't know much about. Neither one of us knew much about the details of the firmware, or the optics (mirrors and lenses and such) that another colleague was working on. I guess the point is that for some of us, the point is that we're probably not good candidates to become domain experts, but knowing enough to find help is probably a good move.
  - kragen 7y ago

wodenokoto 7y ago

Not really any theory, but some interesting anecdotes and research results. I’d wished the author at least explained the 5 hour average wait. I mean, if the queue started at 30 people, then I can see it, but not if we start at 0.

isaacg 7y ago
In that setting, the line queue is 30 people long, on average. Sometimes more, sometimes less. Because 5.8 people arrive an hour out of the maximum of 6 that can be served an hour, and 6/(6-5.8)=30, the average queue length is 30.

tombert 7y ago

About a year ago, I was waiting in line at Dollar Tree (guilty pleasure), and I had to wait almost a half-hour in line. Even though there were two cashiers, they were constantly communicating back and forth, introducing a constant blocking factor and effectively reducing it one queue, and I was trying to think about how to model this with pi-calculus while I was waiting. Obviously there's a math for basically anything, but reading this makes me glad I'm not the only one who has thought about this. This article has given me some reading fodder for this weekend...thanks!

takk309 7y ago

If any one is interested in a diving into queuing theory as it pertains to vehicular traffic, check out chapters 11 and 12 of Traffic Flow Fundamentals by Adolf May. [1] Chapter 11 discusses shockwaves and moving queues. Chapter 12 discusses both deterministic and stochastic queuing. [1] https://www.scribd.com/document/253416450/Traffic-Flow-Fundamentals https://www.scribd.com/document/253416450/Traffic-Flow-Funda...

pcvarmint 7y ago

Myron Hlynka https://web2.uwindsor.ca/math/hlynka/queue.html https://web2.uwindsor.ca/math/hlynka/queue.html

c3534l 7y ago

I'm always annoyed that whenever someone purports to have an article or book on queue theory, no one actually has any math. So I'm just left with a bunch of anectdotes and no understanding.