It’s Time for Some Queueing Theory
kottke.org
kottke.org
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
[1] from the article, "We really, really hate it when someone shows up after us but gets served before us.
Tells you a lot about their attitude to your money!
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.
Like you say, people can just re-enter the queue, or (in meatspace) form a meta-queue that vies for entering the moment it has an open slot, reproducing FIFO all over again.
Furthermore, you get a lot of pro-cooperation effects (necessary for queues to work at all) by giving people "skin in the game" in the form of valuing their place in line. Once people lose nothing by inventing a new name and re-entering the line, that's all gone, and they no longer have an incentive not to be disruptive, which throws off disproportionate negative utility onto the rest of the system.
One day, I promise, I will unpack this result.
[1] My comment from 2015 expressing similar reservations: https://news.ycombinator.com/item?id=10182781
Ultimately, the utility of "lower 50%ile" vs "lower 99.9%ile" is a subjective choice.
The value in LIFO is the observation that real people would rather their 10-minute request fail and require a retry due to LIFO (since they are already disatisfied with the original service*) than their 1second request take 1 minute due to FIFO.
Alternative scenario: Someone figures out the best way of dealing with LIFO is spamming requests until one gets through and you end up with several multitudes of queuing work.
You're basically trading some higher latency for lower median latencies.
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.
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.
Math isn't a domain. It's the technique of abstraction we apply to any domain to make it tractable for computers, and it's the technique of reasoning we apply to any domain to figure out where our thinking has gone wrong. At least, any objective domain — except in rare cases, math isn't that useful for figuring out why your wife feels you don't love her anymore. But for you to program something on a computer, someone needs to mathematize it first. This can be done well or badly.
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.
[1] https://www.scribd.com/document/253416450/Traffic-Flow-Funda...
> 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.
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:
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.
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?
And the bigger the line, the more likely customers drop out (at least, I do, especially if the purchase is small/insignificant)
Yes. This is an issue for stores that don't use shopping carts.
Wouldn't that be the exponential distribution? The poisson distribution would tell you how many customers would arrive in any given time interval.
Service processes are often characterized using exponential distributions
Some wikipedia rabbit holes to dive down:
https://en.wikipedia.org/wiki/Queueing_theory
[0]: https://www.johndcook.com/blog/2008/10/21/what-happens-when-...
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.
There's a really obvious counterexample to "the distribution doesn't matter": with a uniform distribution, the average wait time will be zero.
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!
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.
"Stop Rate Limiting! Capacity Management Done Right" by Jon Moore
(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).
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.
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.
If long tasks are stalling indefinitely under this policy, then under FCFS the queue length with grow without bound, and that's not really much better.
Now that I'm rereading, I'm not even sure what 'average wait time for one task' was supposed to mean. Averages are aggregate data about multiple samples.
I learned queuing theory in a class about multimedia, and I came away with a good theoretical understanding but my practical understanding was rubbish. When synchronizing two streams of tasks, the queue is not finite, but the pattern is fixed. For A/V it might be 22 frames per second, best effort, and exactly one second of audio per second.
But any queue with even a vague notion of deadlines will only let so many tasks 'cut in line'. At some point the undesirable task gets scheduled, even in the face of a constant stream of other work. Or it gets dropped. From what I understand, in a realtime system a low priority, long task might just be aborted. Because it's never a good time to run it.
Harchol-Balter calls this the All-Can-Win Theorem, because it counterintuitively shows that jobs with more time to go being interrupted by jobs with less time to go will be better off.
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.
Now fast-food queues, that is an interesting problem.