4 ms·
Queueing theory is an interesting discipline because the benefits of being a queue-theory expert are extremely subtle. There are some pressures that make it har
by roenxi 4y ago
Queueing theory is an interesting discipline because the benefits of being a queue-theory expert are extremely subtle. There are some pressures that make it hard to show off:
- There aren't really any flashy results (the whole thing could be sold as restatements of "if the average processing rate is similar to the arrival rate, any variance in arrivals will lead to long queues".
- As a corollary, most queues encountered in practice can also be dealt with using very simple techniques or making the queue negligible. Neither of which require the study of queue theory.
- The quick recommendations are really boring (if you want the queue to get shorter, you need to process faster or add more servers).
But studying queue theory handy nonetheless because it turns out that queues are, in practical systems, about as common as list data structures or associative maps in programming. They are everywhere. Every time a stream meets a buffer, in fact. Being able to see a situation and reducing a lot of the noise to (M/M/n, lambda = 0.2, mu = 0.4) can free up a lot of thinking horsepower for more interesting problems. Then there is no need to try to reason about queue lengths vs serving times vs variance vs how those change with the addition of servers. An expert understands that a lot of results flow from a few simple variables, and doesn't have to remember the details because they are just symptoms of a few key observations.
So, in a sense, the reward for knowing a lot of queue theory is not having to think very much about queues.
- pontifier 4y agoTheme parks have made queueing a multi-billion dollar business. I just spent a nightmarish time in Orlando. The theme parks there are insane, and I don't believe I'll ever go back. 2 of my friends and I literally stood in a two and a half hour queue for one ride and it cost us $150 each. The ride was terrible, and the queue length was constantly being hidden. The companies have no incentive to increase throughput because building extremely long lines is cheaper than building efficient rides.
- gnull 4y agoAnother fun fact: if instead of considering a distribution on the inputs, you consider worst case, then Queueing Theory becomes Online Algorithms. The techniques there seem very different from Queueing Theory, but I also heard some Computer Scientists calling Online Algorithms boring because the techniques used there are very similar and results aren't too suprizing (I can't say I share this sentiment).
- Der_Einzige 4y agoIf by "online algorithm" you mean incremental learning, the problem is that they still don't work well due to catastrophic forgetting...
- dunham 4y agoBack when I was in college, an online algorithm was one where you had to make scheduling decisions as the jobs came in. There would be an optimal schedule (say differing size jobs coming in with n cpus) if you knew the future, and you prove things like "this algorithm can hit that optimal time with 1.x as many CPUs" or "this algorithm is within 1.x of optimal". This also applies to stuff like swapping / expiring cache - if you knew all of the future disk / memory accesses you could hit optimal, otherwise you need some heuristics. It's been a couple of decades, but I think some the proofs involved playing the part of an omniscient adversary.
- gnull 4y agoIndeed. One impressive result I remember from that area (if I'm not mistaken) is that Least Recently Used cache policy with cache size S performs at least as well as an offline algorithm with cache size S/2. I don't remember the details now, but the proof wasn't too complicated, they gave it to us as an exercise.
- q-big 4y ago> If by "online algorithm" you mean incremental learning, the problem is that they still don't work well due to catastrophic forgetting... I rather think that with "online algorithm", gnull means exactly this classic computer science topic: > https://en.wikipedia.org/wiki/Online_algorithm https://en.wikipedia.org/wiki/Online_algorithm
- kqr 4y agoSomething not as obvious is the relationship between service time, utilisation, and response time. Even rough estimations of that can be very helpful, but most people I speak to don't even know there is a useful relationship -- some even think service time and response time are the same. Come to think of it, the obvious general principles of queueing theory have several consequences that aren't immediately intuitive to people: - A system where concurrency is limited (practically all systems) often bottlenecks on its slowest component, meaning almost any upgrade will do nothing to improve its performance. - The average time a task is stuck waiting is longer than the average waiting time, once there's significant variation (greater than Poisson) in arrivals. - Based on only local measurements in an auxiliary, asynchronous component you can determine global throughput for the whole system.
- roenxi 4y agoIf we're intellectually honest, how many hours of studying Markov chains does any one insight there really justify? And what are the odds that any one insight is useful even while dealing with an honest-to-goodness queue? We're not exactly talking e^{i\pi} levels of "wow!" which almost justify teaching complex numbers just to hit people with the one equation. The power is in the sheer number of semi-trivial observations that a queue theorist can start making after seeing only a small part of the system. And that is impressive - but mostly because you don't need to consider all those individual things as variables once the basic theory is understood. So the theorist can start ignoring all those variables really quickly and move on to dealing with the problem at hand.
- gillh 4y agoYou should really check out the recent Aperture[1] project on GitHub that applies all these ideas in practice to protect services from cascading failures. 1. Aperture automatically detects queue buildup based on metrics such as latency. 2. Adjusts the concurrency on a service. 3. Weighted Fair Scheduling of workloads (i.e. APIs) based on their labels. [1] https://github.com/fluxninja/aperture https://github.com/fluxninja/aperture
- kqr 4y ago
- User23 4y agoI’ve found Little’s law to be a pretty deep observation.
- kqr 4y agoIt can also be applied in creative ways! In a company's annual report they state revenue for the year as well as a snapshot of accounts receivable. Divide one by the other and you get a snapshot of how long time it takes the company to collect on its debts!
- redanddead 4y agoHow long do companies usually take to collect?
- deleted 4y ago[deleted]
- photochemsyn 4y agoI feel like this would go hand-in-hand with graph theory, as many problems are something like a graph with a queue at each node, with the goal being to manage traffic through the graph so that each queue is kept as short as possible.
- tomcam 4y agoThat’s low-key the best explanation of queuing theory I have ever encountered.
- flashgordon 4y ago+100. If people are interested in quick-win practical usage - consider efficacy in system design intervews. Eg What many people dont realise is that google system design interviews are subtly testing your ability to model queues :)