15 ms·
Queueing theory: The science of waiting in line
- Jtsummers 8y agoQueuing theory is something I'm familiar with from my educational background and general interest in math and systems. But I don't actually know of a good introduction to the topic, it's just a set of information I've accumulated and internalized over the years. Any suggestions from the HN crowd for something I can pass around to some of my team leads and managers that will help them to understand these topics?
- sacheendra 8y agoThe book Queuing Theory in Action: http://www.cs.cmu.edu/~harchol/PerformanceModeling/book.html http://www.cs.cmu.edu/~harchol/PerformanceModeling/book.html
- deleted 8y ago[deleted]
- r4um 8y ago+1 For the above mentioned book, especially if you are looking at computer systems/networks. For more pragmatic treatment found "Fundamentals of Queueing Theory"[1] really good. [1] http://mason.gmu.edu/~jshortle/fqt5th.html http://mason.gmu.edu/~jshortle/fqt5th.html
- weitzj 8y agoRelated: Stochastic Transport in Complex Systems Ant trails, traffic jams, ... https://www.elsevier.com/books/stochastic-transport-in-complex-systems/schadschneider/978-0-444-52853-7 https://www.elsevier.com/books/stochastic-transport-in-compl...
- kqr 8y agoThank you for asking! Queueing theory is a topic I was completely unaware of despite a few years of CS in university. It seems like such a fundamental and useful model for just about anything in software and computing.
- benj111 8y agoI was expecting them to explain why the queue I join is always the slowest.
- SketchySeaBeast 8y agoBecause you stop paying attention to the queues once you're done in them so you're the last person you ever observe being served?
- deleted 8y ago[deleted]
- 11thEarlOfMar 8y agoThey did. Because you're buying ice cream.
- macintux 8y agoA classic gif on that theme: https://giphy.com/gifs/queue-waiting-100mhETqKYJNf2 https://giphy.com/gifs/queue-waiting-100mhETqKYJNf2
- objektif 8y agoBeautiful! Actually very realistic except the end.
- Someone 8y agoIt isn’t, but it can easily appear to be the case because you do spend more time in slower queues (simple example: 2 queues with waiting times of one minute and five minutes give an expected waiting time of three minutes, of which you are expected to spend 2.5 (83% of waiting time) in the slower queue), and almost no time in queues that move so fast that you’re out of them before the waiting starts to annoy you.
- deleted 8y ago[deleted]
- 8y ago
- nullandvoid 8y agoVaguely on the topic of queing I noticed this year on black Friday several sites had queue systems ( e.g 'game' store was one I remember and even had a limited time you could spend on the site after the queue ). Part of me wonders whether this was really a server capacity issue or there was some sort of psychological gaming scheme for customers to feel like they need to make a commitment to purchase. Does anyone have some information on this sort of tactic if so?
- theNJR 8y agoIf this wasn't a gaming scheme, it soon will be. I bet it worked.
- scott_s 8y agoUnderstanding the basics of queueing theory means that you will be eternally frustrated in most US grocery store checkout lines. And you may be kicked out for screaming "Basically zero-cost queue synchronization and heavily variable server time means a global queue is better!"
- vardump 8y agoWhy just US? I think that's pretty universal, at least in most western countries.
- scott_s 8y agoI don't have much firsthand knowledge of grocery stores outside the US, so I didn't want to over-generalize.
- mikeryan 8y agoThis is getting better with self checkouts which tend to use a single Queue. The only grocery store I knew that used it is the Whole foods on Harrison in SF. Technically they have 2 global lines/queues for some reason. (Pro-Tip the inside line is shorter because of the single turn in the line)
- vardump 8y agoThose self checkouts are curious. Many people seem to take longer compared to traditional cashier line, but still prefer them. Maybe the same is true for me, although I feel I'm fast... Perhaps it's something similar like with car vs airplane safety perception. Cars feel safe. Even though planes are extremely safe in reality, you are in control of your own car. Like you're at control in a self-checkout line.
- badwolf 8y agoAfter working a checkout counter for a couple years as a teen, I cringe when I see how slow self-checkout makes you scan your items :(
- crdrost 8y agoThere is also a rough application of some queueing theory ideas (one might also say, the more general lessons one sees in the physics of transport phenomena, before one specializes in continuums etc) to business, called "theory of constraints." The basic idea is that there is probably right now only a handful of things that are slowing down your ability to make more money, and if you can figure out what they are and add extra capacity to those things, you can presumably get "more bang for your buck" than attempts to improve every part of the system individually. A lot of authors also discuss similar concepts under "systems thinking." More specifically, the theory of constraints is kind of half-applied to the "projects" contexts that we work in in software in the "critical chain" methodology. It basically says in our context that for each project you have, at any given point during a sprint, there should be one person who is "holding the baton" for that project, they need to be aware that any delays in their work are getting communicated to the project launch date, while others working in parallel are usually exempt. Essentially exactly one person on the project should be panicking, and everyone else should have spare capacity to handle the routine "hey Alice from HR wants us to change all of the articles in the table which Bob has authored so that they no longer say that they were authored by Bob since his last day is next Friday, can someone write SQL to do that?" -- even if Carol has the most domain knowledge about that, if she's holding some other baton, that comes first. In fact, if Carol can split her work -- one common one in our field would be between functionality and tests/documentation -- so that she can pass the baton a little sooner, often that is a net win, too: she finishes the core functionality up to testing-by-hand, she delivers it to Darryl who is the next to hold the baton, then she documents and adds unit tests in a separate PR before she loses her context about it. Similarly the management of these projects is different because you don't want to estimate "hey Carol we think this is a two-day PR and we will hassle you come day three," since if she judges it to be a half-day PR then it's in her best interests to spend a week on other urgent-seeming requests as those minimize who is hassling her. But instead you want to communicate "hey, this is going to take however long it takes, and I know I cannot make it happen faster by hassling you. I want you to know that even though we guessed that this was a within-one-day task we put an extra safety cushion in the project in case it goes longer, but you have the entire project's safety cushion if you ultimately need it: conversely, any time you save right now can be passed on to your other developers. What I need from you is a daily guess about when you realistically think you can pass that baton so that I can tell Darryl, 'hey, heads up, you're about to have to drop everything and pick up this baton.' You can change that estimate at any time, I just want to minimize that friction and encourage you to sprint as hard as you can on this since you're on the critical path, if anyone tries to tell you that they have something more important for you to be doing, you tell them to talk to me and I will do it personally." Also the queueing theory makes me a lot more patient with myself. Like I used to get really hard on myself about how "you spent all of this time on the job doing this other thing that didn't need to get done, you lazy procrastinator you!" ... with some queueing theory you start to ask, "what would happen if we defined load as the maximum usage of CPU, RAM, network -- what would happen if we ran a server at 100% load? Machine failure, yes... but also high latency, and things would just get dropped forever. So what would happen if I run myself at 100% load, is that really what's best for the company?" and in a couple of cases (like on these critical paths, with a crucial deadline) that is what's best for the company, but in most cases actually the company should want you to have some idle bandwidth so that you can promptly serve their ad-hoc needs.
- theoh 8y agoSome goodies via Jon Bentley: http://www.eecs.harvard.edu/~margo/cs261/background/p176-bentley.pdf http://www.eecs.harvard.edu/~margo/cs261/background/p176-ben... And a different presentation of some of the same material, on consequences of Little's Law, from his book Programming Pearls, quoted here: http://www.cs.fsu.edu/~baker/opsys/notes/queueing.html http://www.cs.fsu.edu/~baker/opsys/notes/queueing.html (I'll paste this here as it's already being shared online) "For instance, if you're in line waiting to get into a popular nightspot, you might figure out how long you'll have to wait by standing there for a while and trying to estimate the rate at which people are entering. With Little's Law, though, you could reason, `This place holds about 60 people, and the average Joe will be in there about 3 hours, so we're entering at the rate of about 20 people an hour. The line has 20 people in it, so that means we'll wait about an hour." Bentley also cites the following, attributing them to Peter Denning: "The average number of objects in a queue is the product of the entry rate and the average holding time." "I have 150 cases of wine in my basement and I consume (and purchase) 25 cases per year. How long do I hold each case? Little's Law tells me to divide 150 cases by 25 cases/year, which gives 6 years per case." "The response-time formula for a multi-user system can be proved using Little's Law and flow balance. 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."
- elviejo 8y agoIs there a nice and visual queueing theory simulator for python or other programming language?
- nileshtrivedi 8y agoI had written a quick visual demo using the Python mode of Processing language. Perhaps someone here can build upon it. https://gitlab.com/nileshtrivedi/queue_simulation https://gitlab.com/nileshtrivedi/queue_simulation
- ggm 8y agoTwo large Australian department stores implemented single global queueing for non-self-serve when they introduced self-serve. Its a mixed bag because they also reduced staff on the line to match maximal delay for minimum fuss: ie, they don't aim to serve this line any faster than the worst-case single line instance. It doesn't invalidate the single global line theory: it points out that the qui bono moment in a queue is not you the customer: its the profit centre. They do anything to maximise profit absent a strong signal they went too far. its morally akin to basic time-and-motion/taylorism.
- Tor3 8y agoThe signal I usually give is that when I arrive at a line of (understaffed) counters, with all of them having long queues, I turn around with my basket or cart, put everything back on the shelves, and leave. I do that if I it's clear that I have to wait more than a few minutes.
- mmikeff 8y agoThe signal is clearer if you abandon the trolley and walk out.
- velosol 8y agoSo should I leave space on the highway so my lowest speed through the occasional slowdown is higher than average or am I hurting the traffic flow? I recall reading about (highway) traffic being a queuing problem where the arrival rate exceeded the clearance rate due to a transient action (someone tapping their brakes because they were distracted or a bright glint from a glass truck going the other way). If you decrease the arrival rate slightly such that the clearance rate can remove the stopped/slowed cars then the entire traffic flow will return to the norm for the volume of traffic on the road. Sound? Valid?
- jedberg 8y agoIf the drivers are rational then going at the average speed works best. But in real life people would cut you off making you slam the breaks and making the problem worse.
- kokokokoko 8y agoBraking or a quick lane change causing traffic jams is a well known and refuted myth. Similar to the idea that driving slower on the highway is more dangerous. We have massive amounts of data on both of those. I wouldn't put too much value in that source.
- velosol 8y agoAnd that would be my fault - my parenthetical was just imagined reasons why there might be a saturation-related slow down. In trying to look for the source I did come across [1] from a few years ago and may have been remembered incorrectly. Edit: More details at [2], [3], and [4] some noting transient braking may be a factor. [1]: https://www.npr.org/2013/11/29/247825768/phantom-traffic-jams-what-causes-mysterious-highway-backups https://www.npr.org/2013/11/29/247825768/phantom-traffic-jam... [2]: https://www.vox.com/2014/11/24/7276027/traffic-jam https://www.vox.com/2014/11/24/7276027/traffic-jam [3]: http://math.mit.edu/projects/traffic/ http://math.mit.edu/projects/traffic/ [4]: https://www.sciencedaily.com/releases/2007/12/071219103102.htm https://www.sciencedaily.com/releases/2007/12/071219103102.h...
- sixstringtheory 8y agoInteresting Freakonomics episode [0] about this, where among other things they suggest that the most efficient queue puts newcomers at the front, essentially LIFO... thus transforming the queue to a stack! [0]: http://freakonomics.com/podcast/what-are-you-waiting-for/ http://freakonomics.com/podcast/what-are-you-waiting-for/
- jedberg 8y agoBut only if all the players are rational. :)
- jimpick 8y agoAnd then there’s how they wait in line in Cuba... https://www.washingtonpost.com/world/the_americas/in-an-online-world-cuba-remains-a-stand-in-line-society/2015/05/31/07459d7e-fd90-11e4-8c77-bf274685e1df_story.html?utm_term=.7047f0afbd48 https://www.washingtonpost.com/world/the_americas/in-an-onli...
- ojbyrne 8y agoIt’s interesting that all the grocery stores with automated checkouts I’ve been to have single lines for multiple automated checkouts, but multiple lines/single servers for human checkouts.
- foolfoolz 8y agothat happens a lot at grocery stores because of carts. it’s even more obvious at costco. stores where people are more likely to hold items in their hand or a small basket can do global queue like home goods or old navy. but once you have 10-40 carts lined up it’s a shit show. imagine costco on the weekend with everyone trying to push their cart through a maze of switchbacks. self checkout likely has less carts through it than staffed chashier lines. also their close grouping makes this a little less of an issue
- adanto6840 8y agoWe've gone to great lengths to get as close to accurate 'queueing theory' for our game, SimAirport. The systems allow for a global queue for many desks, or one queue per desk, or any hybrid of one queue per N desks, etc... It's tough because scaling time & 'movement distance' in a simulation game isn't easy -- but sounds like that's actually an issue in real-life, too. :)
- bdz 8y agoAre there any good reads about matchmaking in video games? Which is basically the same queueing theory
- vanderZwan 8y agoTangential: in the article submitted the other day[0] that interviewed Japanese demoscener 0x4015, he brought up a time-lapse video of half a million people queueing for an event in Tokyo: > I should also mention Comic Market (Comiket). It’s the world’s largest self-published manga exhibition & sale fair, and about half a million people (back then, quarter-million) visit there. This is a time-lapse video of the queue for the Comiket entrance. It gets demo-ish after 40 seconds and I find it interesting. It is oddly mesmerizing to watch, indeed[1]. [0] https://news.ycombinator.com/item?id=18965767 https://news.ycombinator.com/item?id=18965767 [1] https://www.youtube.com/watch?v=ermNqkUUiJw https://www.youtube.com/watch?v=ermNqkUUiJw
- amelius 8y ago> With only one teller, customers will have to wait nearly five hours on average before they are served. But if you add a second teller, the average waiting time is not just cut in half; it goes down to about 3 minutes. The waiting time is reduced by a factor of 93x. This is exactly why asynchronous programming (where every task competes for the same CPU) is such a bad idea.
- icebraining 8y agoI don't see what this has to do with asynchronous or synchronous programming. If you have more work to do than what the core can handle, you're going to wait a while no matter what style of programming you use.
- amelius 8y agoThe point is that the async style of programming will introduce unpredictable and potentially wildly varying service times. Contrast this to multithreaded programming, where the program is cut into thin time-slices which all have a similar, predictable duration.
- icebraining 8y agoAverage and variance are different things, though.
- kqr 8y agoI'm not sure I follow... If I understand the async style correctly, the idea is that a task will yield the CPU as soon as it is about to wait for I/O an insignificant time. This allows CPU bound tasks to race to idle, and prevents context switches unless they are nearly certain to be needed. I guess I understand your concern in the case of multiples tasks that are very CPU heavy, but that hardly seems like a universal issue. I also think it's a bit of a mathematical sleight of hand to use measures very sensitive to outliers with a distribution that generates large outliers in order to make a point. Perhaps the median or the 95th percentile is more useful. But less dramatic.
- smarri 8y agoI wonder if a noble goal for queuing systems would be to eradicate the need for the queue all together. E.g. more frequent public transport, designated security screening times at airports and gigs, supermarket checkout without tills or home delivery as an alternative. Theoretically it would be nice, but could it be ever be practical...
- Markoff 8y agobesides self service cashiers i saw here in Europe global queues implemented only in Kaufland hypermarket, they actually don't use one big global queue but have queues assigned to group maybe of 4 cashiers max., in the end anything it's better than waiting at one cashier queue
- kneebull 8y agoI thoroughly enjoyed my queueing theory classes in college. The word queueing has five vowels in a row. Try that the next time you play scrabble.
- kneebull 8y agoI thoroughly enjoyed my queueing theory classes in college. The word queueing has five vowels in a row. Try that the next time you play scrabble.