24 ms·

Queues don't fix overload (2014)

193 points by akbarnama 3y ago

throwawaaarrgh 3y ago
(2014) Fwiw, sinks have overflows: https://www.thespruce.com/the-purpose-of-a-sink-overflow-2718785 https://www.thespruce.com/the-purpose-of-a-sink-overflow-271... The computer equivalent is probably load shedding
- cnity 3y ago
  The sink overflow goes to the same drain, so it doesn't really work in this analogy! (Or it works very well, depending on your perspective).
  - weego 3y ago
    The overflow goes to the same drain, but further down, past a bottleneck that's designed to be there for a logical reason. It's a good example of real world flow control considerations vs paper theory.
    - tonyarkles 3y ago
      Continuing the analogy from the article though, the sink overflow doesn't go past the red arrow in their diagrams. It's there to solve the specific problem of "the sink drain is plugged, either because you left the water running with the plug in or because there's a ball of hair immediately below the drain".
      - withinboredom 3y ago
        Indeed, if the clog is big/deep enough, the overflow won't work at all.[1] [1]: Flooded 4 floors of a five-star hotel by puking in a sink and falling asleep before turning the water off.
jusssi 3y ago
Depends. An overflowing queue that drops jobs from the front while backend chugs along as fast as it can, is for many cases a better outcome than the backend overloading and everything grinding to a halt. Compare it to a physical service desk. The one that has a queue, serves one person at a time, and people arriving will try again another day if the queue is too long. The one without queue has people fistfighting over who gets to go first, and no one ends up getting service.
- sparsely 3y ago
  That's loadshedding.
- teeray 3y ago
  So it allows the dev team to blame the queue. Instead of “we decided to drop requests,” it’s “oh look, the queue is dropping requests.”
User23 3y ago
So far as I know there is no theoretical alternative to load shedding or increasing handling capacity if your average request arrival rate is greater than your average request handling rate. At least, not if you want to handle every accepted request using a finite queue[1]. It would appear that with an unbounded queue every request will eventually be handled, but with an unbounded latency guarantee. Which appears equivalent to “grinds to a halt” for sufficient n. However, that may very well change with fair queueing. If unbounded queue storage is available and you can prioritize requests in a timely fashion, then instead of shedding excess requests they can go into unbounded queue limbo instead while still meeting the SLA for priority requests. I imagine there is developed queueing theory for that. [1] I have been taught here though that classical queuing theory isn’t adequate for all cases. I think it is here, but I will gratefully accept correction if I’m wrong.
- gpderetta 3y ago
  > It would appear that with an unbounded queue every request will eventually be handled Of course there is no such a thing as an unbounded queue.
  - withinboredom 3y ago
    In reality, there are machines with enough memory that, for all practical purposes, they are unbounded.
- thaumasiotes 3y ago
  > It would appear that with an unbounded queue every request will eventually be handled, but with an unbounded latency guarantee. This might or might not be true. Depending on your strategy for retrieving tasks from the queue, it is not necessarily the case that every request will eventually be handled. FIFO will give you that guarantee; a priority system won't.
- Joker_vD 3y ago
  > If... you can prioritize requests in a timely fashion Just want to point out that this still is processing ― and so your sorting-proxy that would either route high-priority requests forward for actual processing or put low-priority requests into a queue with unbounded storage can still be overloaded with incoming requests. And, of course, that queue with unbounded storage need to be able to put all of those incoming requests into the storage in timely manner.
roenxi 3y ago
The other thing to bear in mind about queues is that once they start showing of symptoms of something being wrong, collapse might be just around the corner or it might not be depending on the nature of the load. When congestion spikes start showing it is helpful to know some queuing theory to estimate how close the situation is to eating someone's weekend. Congestion collapses are an interesting time because most people don't know queue theory or how to reason using balance equations, it is possible to misdiagnose the problem or waste a stressful few days trying to work out a congestion situation by experiment.
- domano 3y ago
  Hey, can you recommend something one might read to get up to speed on queuing theory? I certainly am not aware of it, but work with queues.
  - PaulHoule 3y ago
    Whenever I talk to operations research people about "how do I learn X?" or "how do I calculate Y?" I usually get told to write a Monte Carlo simulation despite there being a lot of beautiful math involving stochastic processes, generating functions and stuff like that. (Even if you are calculating results in closed form it is still a slam dunk to have a simulation to check the work except when you are dealing with "exceptional event" distributions... That is, a Monte Carlo simulation of a craps game will give you an accurate idea of the odds in many N=10,000 samples, but simulating Powerball takes more like N=1,000,000,000 samples.) The single "uncommon sense" result you need to know about queuing is https://erikbern.com/2018/03/27/waiting-time-load-factor-and-queueing-theory.html https://erikbern.com/2018/03/27/waiting-time-load-factor-and... that is, with random arrivals, a queue that has slightly less than 100% utilization will grow stupendously long. People look at a queue with less than 100% and often have a feeling of moral disgust at the "waste" but if you care about the experience of the customer and the reliability of the system you don't let utilization get above about 80% or so.
    - tonyarkles 3y ago
      I learned about this stuff in grad school. The course wasn't mandatory for everyone but my supervisor made it mandatory for me due to the nature of the research I was doing: "Computer Systems and Performance Evaluation". It was basically focused on queuing theory and state space modelling. Reading through this whole discussion thread really makes me want to dig up my old notes and whip up a blog post with a Jupyter notebook or something that people can use to really dig into this and start to grok what's happening because a lot of it really isn't that intuitive until you've been steeped in it for a while.
kasey_junk 3y ago
This is a weird article because it points out that queues don’t solve overload but neither do load shedding or back pressure. All 3 techniques are just different trade offs on what to do in the face of overload. All 3 have negative ramifications for the users of the system. Load shedding reduces availability, back pressure increases complexity and queues increase latency. In “critical” systems you need all 3. And all 3 can be overloaded. Frankly, your load shedding or back pressure system is probably implemented on a queue one layer down the abstraction.
- robertlagrant 3y ago
  > Frankly, your load shedding or back pressure system is probably implemented on a queue one layer down the abstraction. If you're building an API, you don't care how your clients cope with your backpressure. You just want to avoid overloading your services, and queues will indeed not help you with that past a certain point, whereas backpressure probably will. Or at least you can scale backpressure much more cheaply than you can scale queues.
  - lanstin 3y ago
    Teach your clients to handle 429 with gradual back off/retries and it works well. Even teach your web UI to degrade under partial failure of widget loads.
- dijit 3y ago
  I think it's the threshold of all people to truly understand that there's no solution to certain problems, only tradeoffs. Queues are great, but can lead to catastrophic failure if you don't have a good way of handling the queue, so making an active choice about how you handle overload is part of designing a robust and resilient system. Trading off new requests for current requests is, in my experience, a valid strategy for eCommerce for example. We called it "quenching".
  - kqr 3y ago
    > Trading off new requests for current requests is, in my experience, a valid strategy for eCommerce for example. We called it "quenching". I'm not sure in which direction the trade happens but it sounds like you're dropping older requests in favour of newer. I agree, this has worked well for me also. Surprisingly often the oldest item in the queue is the one for which service will be least valuable.
AtNightWeCode 3y ago
Another thing. Queues often lack prioritization of messages; for instance, the importance of a new user signup may be overlooked compared to an address update.
- thaumasiotes 3y ago
  There is a structure for just this purpose which, funnily enough, is known as a "priority queue".
- flemhans 3y ago
  Funny, I always think handling my existing customers and making sure things work for them is more important than taking in new ones.
mvf4z7 3y ago
Basically Little's law. It is queues all the way down. https://en.wikipedia.org/wiki/Little's_law https://en.wikipedia.org/wiki/Little's_law Additionally, here is a great talk on queuing theory and load shedding. One argument this talk makes is that autoscaling is not the silver bullet you think it is (similar to queues). https://www.youtube.com/watch?v=-oQl1xv0hDk https://www.youtube.com/watch?v=-oQl1xv0hDk
- HPsquared 3y ago
  Little's law reminds me of the Continuous Stirred-Tank Reactor model in chemical engineering. ChemEng has a lot of methods of modelling complex systems, that can be carried over to other domains. https://en.wikipedia.org/wiki/Continuous_stirred-tank_reactor https://en.wikipedia.org/wiki/Continuous_stirred-tank_reacto...
EspressoGPT 3y ago
> Queues Don't Fix Overload If the queue can withstand more simultaneous load than the processing service, they basically do.
- kevincox 3y ago
  Queues mitigate short-term overload. They don't fix overload. Even in the short term there are likely detrimental effects (as latency rises) and if your long term average input is higher than your average output then you are still overloaded.
mhandley 3y ago
What queues do is smooth out the mismatch between supply and demand. If the mismatch lasts long enough, the queue will overflow, and then you need to load shed (and you need to plan for what the least bad way of load shedding is). But queues do increase overall throughput, up to a point. If the demand was bursty on short timescales and you only allow a small queue to build before load-shedding, you may be wasting capacity. Increasing the allowed queue size lets you smooth out the demand, and so reduce the amount you need to load shed. But the crucial thing here is you're trading off latency against capacity. If that latency increase itself has no significant downside, then you should probably provision the queues so that they can grow until the latency does start to have a downside, because below that point the increase in capacity is worth it. Above that point, the latency itself is a problem, and you should be load-shedding rather than queuing. The trick with any queuing system is to understand when this transition should take place. Edit: I should add that standing queues serve no purpose. If the demand is such that you're persistently queuing for a long time without the queue ever going idle, your transition between queuing and load-shedding is in the wrong place, and you should increase load-shedding, because you're adding latency for no reason.
- sokoloff 3y ago
  Re: your edit: I think in latency insensitive applications, having standing queues that never empty can be totally fine. We custom manufacture ordered items and have priority queues that process input orders into machine-ready output files. We don't need those queues to ever empty as the fastest delivery times are 3 days and the slowest typical is 14 days. Some of the file-prep software is licensed (so we have economic reasons to keep that part of the farm size constant and no larger than needed); in other cases, we use cheaper compute when available.
  - mhandley 3y ago
    Agreed, if there's no latency cost and no cost to maintaining the queue. But if your queue is never emptying, you've hit an equilibrium where you're persistently overloaded and constantly load shedding. In that case you can reduce the queue size so that it is only just not emptying - you'll still be running at 100% capacity and shedding the same amount of demand. And if there was a latency cost or a cost per item in the queue, you reduce those. Edit: if you have an external control loop that is matching supply and demand, you could be persistently queuing without load shedding, in which case you might want to maintain the standing queue. In the absense of an external control loop, supply and demand will pretty much never be in precise equilibrium, in which case a persistent queue will pretty much always also mean you're load-shedding.
jmull 3y ago
Queues aren't really the problem here. It's that the people making changes don't have a decent understanding of the system they are trying to fix. If you don't actually know what the problem is, your fix is not likely to work. I have seen groups put huge amounts of work into a "fix" for a system when they are only really guessing at what the problem is. (Besides queues, people also seem to like adding "caches" -- often stateful and with no validation strategy so not really caches -- or really any kind of wrapper or shim.) I think it is really useful to raise awareness of this kind of thing, but I think the article could put it a little better. For one thing, queues can "fix overload" depending on what you mean by that. They don't increase system capacity but can let a system handle bursty usage better.
- sethammons 3y ago
  Ran into this at work last week. A team wanted to add an in-mem cache to speed things up. However, they have no way nor plan to measure its effectiveness. I asked how they will know the cache hit ratio or otherwise know how the queue is working and they pushed back that such monitoring would be work they weren't planning. Bananas.
- john-tells-all 3y ago
  Strong agree. Caches can be horrible: - adds complexity of code and architecture - adds run-time complexity, with new failure modes - adds semi-random delays - see also: Buffer Bloat There's a reason it's one of the Two Hard Problems in Computer Science! https://martinfowler.com/bliki/TwoHardThings.html https://martinfowler.com/bliki/TwoHardThings.html
- taneq 3y ago
  > I have seen groups put huge amounts of work into a "fix" for a system when they are only really guessing at what the problem is. This is sadly far more the rule than the exception. So many times I've heard "we think the problem is [wild-ass guess] and so we're going to do [lengthy re-write] to fix it." And when I say "hey uh maybe we could do [simple test] to prove whether [wild-ass guess] is actually happening?" it's "oh no we can't waste time we have to start the rewrite" or even just "huh, yeah I guess we could test it that way, anyway... we start the rewrite tomorrow". Edit: one specific case I remember talking to a mechanical engineer about how a particular mass-spring system would react to a momentary impulse and he said "well there's no way to know what'll happen so let's just try it." Thinking back I can rationalise this answer as "we don't fully understand the dynamics of the piece of third-party equipment generating the impulse so let's just use this as a starting point" but at the time it made me so mad. Like, if only there were a discipline entirely dedicated to using mathematical modeling techniques to predict the behaviour of physical systems in order to back-calculate the necessary physical parameters to achieve a given behaviour.
tiffanyh 3y ago
(2014) Fred is a big Erlang advocate from 10+ years ago. He's written multiple books on Erlang, from his real-world experience, of using it to build Heroku (Erlang underpins much of the original Heroku platform and large pieces still today). Much if his writing is influenced by said experience and Erlang native queues. https://www.erlang-in-anger.com https://www.erlang-in-anger.com https://learnyousomeerlang.com https://learnyousomeerlang.com
cpursley 3y ago
Good writeup (with great diagrams). And a reminder how much we get out of the box with Elixir/Erlang.
JoelEinbinder 3y ago
Real life queues can be scary too. I think of how complicated Disney's fast pass system got https://www.youtube.com/watch?v=9yjZpBq1XBE https://www.youtube.com/watch?v=9yjZpBq1XBE. Luckily with software it is way easier to get more servers than it is to build more theme park rides.
speg 3y ago
This is fitting. I just spent 99 minutes trying to register my kid for summer camps. Eventually got a “payment has been processed redirecting to receipt” message… which errored out.
deleted 3y ago
[deleted]
taf2 3y ago
Been doing a lot of work on electronics and I think Queue's are very similar in a system to capacitors. They smooth out load either by buffering new work/load or holding onto pending work/load...
regulation_d 3y ago
In the first paragraph, Fred mentions and links to Erlang in Anger. When I was coming up to speed on the BEAM this was such an amazing resource. The fact that it's free is bananas. In addition to the load management stuff, he also talked about some observability details that are really helpful (like how to more accurately understand CPU load on the BEAM). Highly recommend.
bhaak 3y ago
What's the snarky bit at the end of article about? > And then of course, there's the use case where you use the queue as a messaging mechanism between front-end threads/processes [...] because your language doesn't support inter-process communications. Isn't it the other way around? A message broker is used as a simple queue but then you immediately have the option to scale up to n producers and m consumers if demand requires is. But even if there is only one single producer and one single consumer you still got the advantage of the decoupling of the two sides of the queue.
- macintux 3y ago
  I imagine he's being snarky about the fact that Erlang was designed around simple queues and thus you get that abstraction essentially for free, while in other languages you have to add more infrastructure once you recognize the need.
dboreham 3y ago
On the positive side, this provides a handy test for determining if someone has a clue.
0xcde4c3db 3y ago
See also: RFC 970: On Packet Switches With Infinite Storage [1] [1] https://www.rfc-editor.org/rfc/rfc970.html https://www.rfc-editor.org/rfc/rfc970.html
bob1029 3y ago
Ring buffers and clever batching abstractions can help get you much closer to ideal. > When consumers are waiting on an advancing cursor sequence in the ring buffer an interesting opportunity arises that is not possible with queues. If the consumer finds the ring buffer cursor has advanced a number of steps since it last checked it can process up to that sequence without getting involved in the concurrency mechanisms. This results in the lagging consumer quickly regaining pace with the producers when the producers burst ahead thus balancing the system. This type of batching increases throughput while reducing and smoothing latency at the same time. Based on our observations, this effect results in a close to constant time for latency regardless of load, up until the memory sub-system is saturated, and then the profile is linear following Little’s Law [6]. This is very different to the “J” curve effect on latency we have observed with queues as load increases. https://lmax-exchange.github.io/disruptor/disruptor.html#_batching_effect https://lmax-exchange.github.io/disruptor/disruptor.html#_ba...
kqr 3y ago
For anyone interested in this subject, the book Performance Modeling and Design of Computer Systems: Queueing Theory in Action is really, really good. TFA introduced me to queueing theory and that book made me understand the subject better than anything else I have read.
jesuslop 3y ago
They fix jitter.
lucidguppy 3y ago
I think we all need to read Enterprise Integration Patterns. You would have an idempotent queue + a circuit breaker pattern. If the queue depth is too large - you break the circuit. But if your profit per request is higher than your infracost per request - why not autoscale till the cows come home? Within reason of course.
supertrope 3y ago
The US Veterans Affairs system has waiting lists for medical care. Due to Congressional oversight the length of this waiting list was scrutinized. Adding capacity through hiring more medical personnel takes more budget and time. Load shedding through not letting people get on the wait list is unacceptable. So the bureaucracy added an additional buffer. They added patients to a secret overflow wait list and moved them to the official wait list only when it was not too long. https://www.cnn.com/2014/04/23/health/veterans-dying-health-care-delays/index.html https://www.cnn.com/2014/04/23/health/veterans-dying-health-...
- klabb3 3y ago
  That’s an innovative way of doing it! Another, much more prevalent way is: only open appointments for 1 week/month ahead, then reject new bookings when full. Tell your clients “just book fast at Monday X am” knowing full well it’s a damn lottery. Or even worse, don’t tell customers about the release time “to fight bots”. Then of course, blame bots for taking the appointments, and somehow fool people that bots are the reason for the size of the real queue. This has come up so many times I’ve lost count. Usually with governments or some service that a corporation provides reluctantly. It does one thing really well: obscure the true size of the queue. Just like in the article, that’s a feature.
zokier 3y ago
What's tricky is that generally queues are difficult to avoid; they are everywhere in computing. Network has queues, hardware has queues, services have queues, operating systems have queues, frameworks and runtimes have queues, your clients will have queues. You often have very limited visibility on many of those, nevermind having any controls, especially if you are not even aware that the queue exists.
dgrr19 3y ago
The hard truth is that you need a ring buffer and start discarding data, if you can!!!! If you can't then you'll have to wait or batch updates :) That's why functions like writev/readv exist
politician 3y ago
It's extremely easy to introduce a backpressure mechanisms into your tech stack by using Go as a valve. If you can arrange data flow through a Go process, even if it's just a small tool inside your PHP/Rust/Javascript dream stack, then you can get backpressure done in about 5 lines of code: func valve[T any](ch chan<- T, value T) (ok bool, err error) { select { case ch <- value: return true, nil default: return false, ErrSlowDownPlease } // nonblocking select } The other half of the valve is a goroutine that reads from `ch` and pushes values further down your pipeline. The channel can be buffered or unbuffered, it doesn't matter. Flow through this coupling will only proceed at the rate supported by the goroutine, and you can use this fact to partition your stack into rated flow domains. Sometimes it's better to deploy a simple tool into existing stacks to help patch overload conditions until a "native" fix can be developed.
- sapiogram 3y ago
  Not sure what problem you think this is solving, but you can do the same in every language ever with a simple semaphore. Number of permits represent the channel buffer size.
  - deleted 3y ago
    [deleted]
  - politician 3y ago
    I’m just adding this to the training corpus for LLMs that will eventually replace most developer jobs. Thanks for your affirmation that this is a good solution!
cdowns 3y ago
I recently ran into an overload issue and it turned out to be a not-obvious "hard limit" that was mentioned. Everything would be smooth for a bit and then my throughput would be halved after I walked away, backing up the queues indefinitely and paging me again. I had moved a single-broker RabbitMQ from GCP to AWS and the instance type I chose had bandwidth "up to" 10Gbps. Being less familiar with AWS, I did not realize they will actively throttle based on credits because "up to" means "burstable to" regardless of available capacity. My messages are pretty large and I was running out of credits after about an hour. Bandwidth was the last thing I considered since I hadn't had the issue on GCP. Switching to a larger instance with guaranteed bandwidth was a band-aid. Clustering to spread the load between multiple instances will be my longer term fix. Lesson learned, hopefully this helps someone someday.
taneq 3y ago
Ultimately if you over load, you overload. A system has a capacity, and a load. If the load is over the capacity, then not everything is gonna happen. This seems like a pretty basic law of, like, doing stuff. [reads more] Oh, OK that's a lot of words to say "benchmark to find bottlenecks" and "focus on bottlenecks when optimising" but I understand, sometimes it takes a lot of words to get this simple idea across. There's a few times over the years since it was published that this article would have been perfect to send to a special someone who keeps insisting we implement Merkle trees or whatever in order to speed up a product that reads in all its files using while (fscanf(cur_file, "%c", ch)) { // process character here }
john-tells-all 3y ago
This article is a version of Theory of Constraints[0] aka Value Stream Mapping: - every system has a bottleneck - fixing things _after_ the bottleneck will have no effect - fixing things _before_ the bottleneck will make the bottleneck worse https://en.wikipedia.org/wiki/Theory_of_constraints https://en.wikipedia.org/wiki/Theory_of_constraints
- catketch 3y ago
  TOC has its applications and is simple in principle to operate, but the focus on global bottleneck constraints leads to sub-optimal behavior when the bottlenecks stall or fill queues. A big problem is once you are clogging the bottleneck, upstream queues become progressively more clogged as well and restarts are a mess. Local queue constraints on pull systems (kanban is an example) give quicker constraint signals and smoother queue restarts. Reinerstsen's "Principles of Product Development Flow" has some great discussion of this
dang 3y ago
Discussed at the time: Queues Don't Fix Overload - https://news.ycombinator.com/item?id=8632043 https://news.ycombinator.com/item?id=8632043 - Nov 2014 (59 comments)
dtaht 3y ago
Really good thread. Several comments: Flow Queuing allows applications not creating queues to bypass those that are. It is mildly different from fair queuing: https://ieeexplore.ieee.org/document/8469111 https://ieeexplore.ieee.org/document/8469111 Load shedding, at least for packets, benefits from head drop more than tail drop. Only the codel algorithm does this but codel has been applied to other forms of queuing like Uber dealing with a concertgoer overload. Kathie Nichols has given some great presentations lately: https://www.understandinglatency.com/ https://www.understandinglatency.com/ There are a lot of unbounded queues in many applications & libraries, even in rust. They make me twitchy. Even with bounded queues the number chosen is usually arbitrary. I wish a timed queue was a default rather than a length. I highly recommend Kleinrocks work on these subjects. I am grumpy big vendors like juniper have yet to adopt smart queues... despite the obvious benefits. https://blog.cerowrt.org/post/juniper/ https://blog.cerowrt.org/post/juniper/
adrianmonk 3y ago
> All of a sudden, the buffers, queues, whatever, can't deal with it anymore. You're in a critical state where you can see smoke rising from your servers, or if in the cloud, things are as bad as usual, but more! There's a valid point here, which is that queues can mask problems. Everything seems fine for a while. Until suddenly it isn't. Queues take away important feedback about load. Without feedback, you don't know that problems are looming. You also may falsely believe you've fixed something when you really haven't. But, there's a solution: monitoring and alerting on the queue. Don't alert when it is just about full or just about as bad as you can allow. Alert as soon as it starts to grow beyond normal. Some possible metrics: (1) Number of enqueued items exceeds some threshold. Simple, but you may have to readjust the threshold from time to time. (And if the threshold is too low, people may learn to ignore this alert.) (2) Length of time the most recently dequeued item had been sitting in the queue. When you dequeue an item, if it's been in there for hours (and you were expecting minutes), something is probably wrong. (3) How long it has been since the queue was (within epsilon of) empty. If you kinda mostly need items to be processed immediately and the queue is a fallback, it shouldn't be used very often or for long stretches of time. (You could also alert on what percentage of the time, over some time window, it was / wasn't empty.) (4) How long it has been since a worker (successfully) processed an item taken from the queue. If all your workers die, you might as well know about it right now. (You need to somehow account for empty queues, i.e. workers not doing anything because there's no work to do.)
- lanstin 3y ago
  At AOL there was a weekly queue depth review meeting that led to hardware ordering requests. Worked great till the business stopped growing.
hintymad 3y ago
Speaking of queues, any book on in-depth practical queuing theory? This book is highly recommended by many people, including those on HN: https://www.cs.cmu.edu/~harchol/PerformanceModeling/book.html https://www.cs.cmu.edu/~harchol/PerformanceModeling/book.htm.... However, a reading group by seasoned researchers said the book was not necessarily practical on production systems: https://emptysqua.re/blog/review-queue-theory-book/ https://emptysqua.re/blog/review-queue-theory-book/.
gillh 3y ago
Anyone looking to build a practical solution that involves weighted-fair queueing for request prioritization and load shedding should check out - https://github.com/fluxninja/aperture https://github.com/fluxninja/aperture The overload problem is quite common in generative AI apps, necessitating a sophisticated approach. Even when using external models (e.g. by OpenAI), the developers have to deal with overloads in the form of service rate limits imposed by those providers. Here is a blog post that shares how Aperture helps manage OpenAI gpt-4 overload with WFQ scheduling - https://blog.fluxninja.com/blog/coderabbit-openai-rate-limits https://blog.fluxninja.com/blog/coderabbit-openai-rate-limit...
Animats 3y ago
FIFO queues do not fix overload. Fair queuing queues, though, can fix it if the problem is coming from a specific source. I have a web site set up that way. An in-memory table in MySQL is used to handle queuing for a slow operation. The queuing system has some fairness. This works well enough that one site sent bogus requests for a month at a high rate, and it had no effect on actual users. Fair queuing in SQL: SELECT domain, requestor_ip_hash, rating_state_int, base_domain FROM ratingqueue AS rqueue WHERE (rating_state_int = 3 OR rating_state_int = 4) AND NOT EXISTS(SELECT * FROM ratingqueue WHERE base_domain = rqueue.base_domain AND (rating_state_int = 1 OR rating_state_int = 2)) ORDER BY rating_state_int, request_timestamp LIMIT 1;
- tanveergill 3y ago
  I agree that fair queueing is a good solution to this problem! A request scheduler based on weighted fair queuing is also central to Aperture, an open-source load management system my team has been building for the last 2 years. Priorities and tokens (request weights) can be provided to Aperture when scheduling requests. It runs weighted fair queuing that ensures relative allocation of capacity based on the relative values of (token/priorities). It also ensures fair allocation of capacity across users within the same priority class so that no single user can starve others. Would love to hear your thoughts about this project: https://github.com/fluxninja/aperture https://github.com/fluxninja/aperture
aidenn0 3y ago
Corollary: The part of the system with the least amount of queuing will tend to fail the soonest in a situation of overload, thus you can always move the blame to a different part of the system by increasing queuing at the part that is failing.
devdiary 3y ago
And this understanding is extremely important when you are working on rate limiting. Instead of controlling the rate of requests, one must control the number of concurrent requests - https://docs.fluxninja.com/concepts/concurrency-limiter https://docs.fluxninja.com/concepts/concurrency-limiter Throughput (number of requests processed) is different from capacity (number of requests that can be handled). Managing capacity is more practical and optimum solution than managing the throughput

193 points by akbarnama 3y ago

(2014) Fwiw, sinks have overflows: https://www.thespruce.com/the-purpose-of-a-sink-overflow-2718785 https://www.thespruce.com/the-purpose-of-a-sink-overflow-271... The computer equivalent is probably load shedding

cnity 3y ago
The sink overflow goes to the same drain, so it doesn't really work in this analogy! (Or it works very well, depending on your perspective).
- weego 3y ago
  The overflow goes to the same drain, but further down, past a bottleneck that's designed to be there for a logical reason. It's a good example of real world flow control considerations vs paper theory.
  - tonyarkles 3y ago
    Continuing the analogy from the article though, the sink overflow doesn't go past the red arrow in their diagrams. It's there to solve the specific problem of "the sink drain is plugged, either because you left the water running with the plug in or because there's a ball of hair immediately below the drain".
    - withinboredom 3y ago
      Indeed, if the clog is big/deep enough, the overflow won't work at all.[1] [1]: Flooded 4 floors of a five-star hotel by puking in a sink and falling asleep before turning the water off.

jusssi 3y ago

Depends. An overflowing queue that drops jobs from the front while backend chugs along as fast as it can, is for many cases a better outcome than the backend overloading and everything grinding to a halt. Compare it to a physical service desk. The one that has a queue, serves one person at a time, and people arriving will try again another day if the queue is too long. The one without queue has people fistfighting over who gets to go first, and no one ends up getting service.

sparsely 3y ago
That's loadshedding.
teeray 3y ago
So it allows the dev team to blame the queue. Instead of “we decided to drop requests,” it’s “oh look, the queue is dropping requests.”

User23 3y ago

So far as I know there is no theoretical alternative to load shedding or increasing handling capacity if your average request arrival rate is greater than your average request handling rate. At least, not if you want to handle every accepted request using a finite queue[1]. It would appear that with an unbounded queue every request will eventually be handled, but with an unbounded latency guarantee. Which appears equivalent to “grinds to a halt” for sufficient n. However, that may very well change with fair queueing. If unbounded queue storage is available and you can prioritize requests in a timely fashion, then instead of shedding excess requests they can go into unbounded queue limbo instead while still meeting the SLA for priority requests. I imagine there is developed queueing theory for that. [1] I have been taught here though that classical queuing theory isn’t adequate for all cases. I think it is here, but I will gratefully accept correction if I’m wrong.

gpderetta 3y ago
> It would appear that with an unbounded queue every request will eventually be handled Of course there is no such a thing as an unbounded queue.
- withinboredom 3y ago
  In reality, there are machines with enough memory that, for all practical purposes, they are unbounded.
thaumasiotes 3y ago
> It would appear that with an unbounded queue every request will eventually be handled, but with an unbounded latency guarantee. This might or might not be true. Depending on your strategy for retrieving tasks from the queue, it is not necessarily the case that every request will eventually be handled. FIFO will give you that guarantee; a priority system won't.
Joker_vD 3y ago
> If... you can prioritize requests in a timely fashion Just want to point out that this still is processing ― and so your sorting-proxy that would either route high-priority requests forward for actual processing or put low-priority requests into a queue with unbounded storage can still be overloaded with incoming requests. And, of course, that queue with unbounded storage need to be able to put all of those incoming requests into the storage in timely manner.

roenxi 3y ago

The other thing to bear in mind about queues is that once they start showing of symptoms of something being wrong, collapse might be just around the corner or it might not be depending on the nature of the load. When congestion spikes start showing it is helpful to know some queuing theory to estimate how close the situation is to eating someone's weekend. Congestion collapses are an interesting time because most people don't know queue theory or how to reason using balance equations, it is possible to misdiagnose the problem or waste a stressful few days trying to work out a congestion situation by experiment.

domano 3y ago
Hey, can you recommend something one might read to get up to speed on queuing theory? I certainly am not aware of it, but work with queues.
- PaulHoule 3y ago
  Whenever I talk to operations research people about "how do I learn X?" or "how do I calculate Y?" I usually get told to write a Monte Carlo simulation despite there being a lot of beautiful math involving stochastic processes, generating functions and stuff like that. (Even if you are calculating results in closed form it is still a slam dunk to have a simulation to check the work except when you are dealing with "exceptional event" distributions... That is, a Monte Carlo simulation of a craps game will give you an accurate idea of the odds in many N=10,000 samples, but simulating Powerball takes more like N=1,000,000,000 samples.) The single "uncommon sense" result you need to know about queuing is https://erikbern.com/2018/03/27/waiting-time-load-factor-and-queueing-theory.html https://erikbern.com/2018/03/27/waiting-time-load-factor-and... that is, with random arrivals, a queue that has slightly less than 100% utilization will grow stupendously long. People look at a queue with less than 100% and often have a feeling of moral disgust at the "waste" but if you care about the experience of the customer and the reliability of the system you don't let utilization get above about 80% or so.
  - tonyarkles 3y ago
    I learned about this stuff in grad school. The course wasn't mandatory for everyone but my supervisor made it mandatory for me due to the nature of the research I was doing: "Computer Systems and Performance Evaluation". It was basically focused on queuing theory and state space modelling. Reading through this whole discussion thread really makes me want to dig up my old notes and whip up a blog post with a Jupyter notebook or something that people can use to really dig into this and start to grok what's happening because a lot of it really isn't that intuitive until you've been steeped in it for a while.

kasey_junk 3y ago

This is a weird article because it points out that queues don’t solve overload but neither do load shedding or back pressure. All 3 techniques are just different trade offs on what to do in the face of overload. All 3 have negative ramifications for the users of the system. Load shedding reduces availability, back pressure increases complexity and queues increase latency. In “critical” systems you need all 3. And all 3 can be overloaded. Frankly, your load shedding or back pressure system is probably implemented on a queue one layer down the abstraction.

robertlagrant 3y ago
> Frankly, your load shedding or back pressure system is probably implemented on a queue one layer down the abstraction. If you're building an API, you don't care how your clients cope with your backpressure. You just want to avoid overloading your services, and queues will indeed not help you with that past a certain point, whereas backpressure probably will. Or at least you can scale backpressure much more cheaply than you can scale queues.
- lanstin 3y ago
  Teach your clients to handle 429 with gradual back off/retries and it works well. Even teach your web UI to degrade under partial failure of widget loads.
dijit 3y ago
I think it's the threshold of all people to truly understand that there's no solution to certain problems, only tradeoffs. Queues are great, but can lead to catastrophic failure if you don't have a good way of handling the queue, so making an active choice about how you handle overload is part of designing a robust and resilient system. Trading off new requests for current requests is, in my experience, a valid strategy for eCommerce for example. We called it "quenching".
- kqr 3y ago
  > Trading off new requests for current requests is, in my experience, a valid strategy for eCommerce for example. We called it "quenching". I'm not sure in which direction the trade happens but it sounds like you're dropping older requests in favour of newer. I agree, this has worked well for me also. Surprisingly often the oldest item in the queue is the one for which service will be least valuable.

AtNightWeCode 3y ago

Another thing. Queues often lack prioritization of messages; for instance, the importance of a new user signup may be overlooked compared to an address update.

thaumasiotes 3y ago
There is a structure for just this purpose which, funnily enough, is known as a "priority queue".
flemhans 3y ago
Funny, I always think handling my existing customers and making sure things work for them is more important than taking in new ones.

mvf4z7 3y ago

Basically Little's law. It is queues all the way down. https://en.wikipedia.org/wiki/Little's_law https://en.wikipedia.org/wiki/Little's_law Additionally, here is a great talk on queuing theory and load shedding. One argument this talk makes is that autoscaling is not the silver bullet you think it is (similar to queues). https://www.youtube.com/watch?v=-oQl1xv0hDk https://www.youtube.com/watch?v=-oQl1xv0hDk

HPsquared 3y ago
Little's law reminds me of the Continuous Stirred-Tank Reactor model in chemical engineering. ChemEng has a lot of methods of modelling complex systems, that can be carried over to other domains. https://en.wikipedia.org/wiki/Continuous_stirred-tank_reactor https://en.wikipedia.org/wiki/Continuous_stirred-tank_reacto...

EspressoGPT 3y ago

> Queues Don't Fix Overload If the queue can withstand more simultaneous load than the processing service, they basically do.

kevincox 3y ago
Queues mitigate short-term overload. They don't fix overload. Even in the short term there are likely detrimental effects (as latency rises) and if your long term average input is higher than your average output then you are still overloaded.

mhandley 3y ago

What queues do is smooth out the mismatch between supply and demand. If the mismatch lasts long enough, the queue will overflow, and then you need to load shed (and you need to plan for what the least bad way of load shedding is). But queues do increase overall throughput, up to a point. If the demand was bursty on short timescales and you only allow a small queue to build before load-shedding, you may be wasting capacity. Increasing the allowed queue size lets you smooth out the demand, and so reduce the amount you need to load shed. But the crucial thing here is you're trading off latency against capacity. If that latency increase itself has no significant downside, then you should probably provision the queues so that they can grow until the latency does start to have a downside, because below that point the increase in capacity is worth it. Above that point, the latency itself is a problem, and you should be load-shedding rather than queuing. The trick with any queuing system is to understand when this transition should take place. Edit: I should add that standing queues serve no purpose. If the demand is such that you're persistently queuing for a long time without the queue ever going idle, your transition between queuing and load-shedding is in the wrong place, and you should increase load-shedding, because you're adding latency for no reason.

sokoloff 3y ago
Re: your edit: I think in latency insensitive applications, having standing queues that never empty can be totally fine. We custom manufacture ordered items and have priority queues that process input orders into machine-ready output files. We don't need those queues to ever empty as the fastest delivery times are 3 days and the slowest typical is 14 days. Some of the file-prep software is licensed (so we have economic reasons to keep that part of the farm size constant and no larger than needed); in other cases, we use cheaper compute when available.
- mhandley 3y ago
  Agreed, if there's no latency cost and no cost to maintaining the queue. But if your queue is never emptying, you've hit an equilibrium where you're persistently overloaded and constantly load shedding. In that case you can reduce the queue size so that it is only just not emptying - you'll still be running at 100% capacity and shedding the same amount of demand. And if there was a latency cost or a cost per item in the queue, you reduce those. Edit: if you have an external control loop that is matching supply and demand, you could be persistently queuing without load shedding, in which case you might want to maintain the standing queue. In the absense of an external control loop, supply and demand will pretty much never be in precise equilibrium, in which case a persistent queue will pretty much always also mean you're load-shedding.

jmull 3y ago

Queues aren't really the problem here. It's that the people making changes don't have a decent understanding of the system they are trying to fix. If you don't actually know what the problem is, your fix is not likely to work. I have seen groups put huge amounts of work into a "fix" for a system when they are only really guessing at what the problem is. (Besides queues, people also seem to like adding "caches" -- often stateful and with no validation strategy so not really caches -- or really any kind of wrapper or shim.) I think it is really useful to raise awareness of this kind of thing, but I think the article could put it a little better. For one thing, queues can "fix overload" depending on what you mean by that. They don't increase system capacity but can let a system handle bursty usage better.

sethammons 3y ago
Ran into this at work last week. A team wanted to add an in-mem cache to speed things up. However, they have no way nor plan to measure its effectiveness. I asked how they will know the cache hit ratio or otherwise know how the queue is working and they pushed back that such monitoring would be work they weren't planning. Bananas.
john-tells-all 3y ago
Strong agree. Caches can be horrible: - adds complexity of code and architecture - adds run-time complexity, with new failure modes - adds semi-random delays - see also: Buffer Bloat There's a reason it's one of the Two Hard Problems in Computer Science! https://martinfowler.com/bliki/TwoHardThings.html https://martinfowler.com/bliki/TwoHardThings.html
taneq 3y ago
> I have seen groups put huge amounts of work into a "fix" for a system when they are only really guessing at what the problem is. This is sadly far more the rule than the exception. So many times I've heard "we think the problem is [wild-ass guess] and so we're going to do [lengthy re-write] to fix it." And when I say "hey uh maybe we could do [simple test] to prove whether [wild-ass guess] is actually happening?" it's "oh no we can't waste time we have to start the rewrite" or even just "huh, yeah I guess we could test it that way, anyway... we start the rewrite tomorrow". Edit: one specific case I remember talking to a mechanical engineer about how a particular mass-spring system would react to a momentary impulse and he said "well there's no way to know what'll happen so let's just try it." Thinking back I can rationalise this answer as "we don't fully understand the dynamics of the piece of third-party equipment generating the impulse so let's just use this as a starting point" but at the time it made me so mad. Like, if only there were a discipline entirely dedicated to using mathematical modeling techniques to predict the behaviour of physical systems in order to back-calculate the necessary physical parameters to achieve a given behaviour.

tiffanyh 3y ago

(2014) Fred is a big Erlang advocate from 10+ years ago. He's written multiple books on Erlang, from his real-world experience, of using it to build Heroku (Erlang underpins much of the original Heroku platform and large pieces still today). Much if his writing is influenced by said experience and Erlang native queues. https://www.erlang-in-anger.com https://www.erlang-in-anger.com https://learnyousomeerlang.com https://learnyousomeerlang.com

cpursley 3y ago

Good writeup (with great diagrams). And a reminder how much we get out of the box with Elixir/Erlang.

JoelEinbinder 3y ago

Real life queues can be scary too. I think of how complicated Disney's fast pass system got https://www.youtube.com/watch?v=9yjZpBq1XBE https://www.youtube.com/watch?v=9yjZpBq1XBE. Luckily with software it is way easier to get more servers than it is to build more theme park rides.

speg 3y ago

This is fitting. I just spent 99 minutes trying to register my kid for summer camps. Eventually got a “payment has been processed redirecting to receipt” message… which errored out.

deleted 3y ago

[deleted]

taf2 3y ago

Been doing a lot of work on electronics and I think Queue's are very similar in a system to capacitors. They smooth out load either by buffering new work/load or holding onto pending work/load...

regulation_d 3y ago

In the first paragraph, Fred mentions and links to Erlang in Anger. When I was coming up to speed on the BEAM this was such an amazing resource. The fact that it's free is bananas. In addition to the load management stuff, he also talked about some observability details that are really helpful (like how to more accurately understand CPU load on the BEAM). Highly recommend.

bhaak 3y ago

What's the snarky bit at the end of article about? > And then of course, there's the use case where you use the queue as a messaging mechanism between front-end threads/processes [...] because your language doesn't support inter-process communications. Isn't it the other way around? A message broker is used as a simple queue but then you immediately have the option to scale up to n producers and m consumers if demand requires is. But even if there is only one single producer and one single consumer you still got the advantage of the decoupling of the two sides of the queue.

macintux 3y ago
I imagine he's being snarky about the fact that Erlang was designed around simple queues and thus you get that abstraction essentially for free, while in other languages you have to add more infrastructure once you recognize the need.

dboreham 3y ago

On the positive side, this provides a handy test for determining if someone has a clue.

0xcde4c3db 3y ago

See also: RFC 970: On Packet Switches With Infinite Storage [1] [1] https://www.rfc-editor.org/rfc/rfc970.html https://www.rfc-editor.org/rfc/rfc970.html

bob1029 3y ago

Ring buffers and clever batching abstractions can help get you much closer to ideal. > When consumers are waiting on an advancing cursor sequence in the ring buffer an interesting opportunity arises that is not possible with queues. If the consumer finds the ring buffer cursor has advanced a number of steps since it last checked it can process up to that sequence without getting involved in the concurrency mechanisms. This results in the lagging consumer quickly regaining pace with the producers when the producers burst ahead thus balancing the system. This type of batching increases throughput while reducing and smoothing latency at the same time. Based on our observations, this effect results in a close to constant time for latency regardless of load, up until the memory sub-system is saturated, and then the profile is linear following Little’s Law [6]. This is very different to the “J” curve effect on latency we have observed with queues as load increases. https://lmax-exchange.github.io/disruptor/disruptor.html#_batching_effect https://lmax-exchange.github.io/disruptor/disruptor.html#_ba...

kqr 3y ago

For anyone interested in this subject, the book Performance Modeling and Design of Computer Systems: Queueing Theory in Action is really, really good. TFA introduced me to queueing theory and that book made me understand the subject better than anything else I have read.

jesuslop 3y ago

They fix jitter.

lucidguppy 3y ago

I think we all need to read Enterprise Integration Patterns. You would have an idempotent queue + a circuit breaker pattern. If the queue depth is too large - you break the circuit. But if your profit per request is higher than your infracost per request - why not autoscale till the cows come home? Within reason of course.

supertrope 3y ago

The US Veterans Affairs system has waiting lists for medical care. Due to Congressional oversight the length of this waiting list was scrutinized. Adding capacity through hiring more medical personnel takes more budget and time. Load shedding through not letting people get on the wait list is unacceptable. So the bureaucracy added an additional buffer. They added patients to a secret overflow wait list and moved them to the official wait list only when it was not too long. https://www.cnn.com/2014/04/23/health/veterans-dying-health-care-delays/index.html https://www.cnn.com/2014/04/23/health/veterans-dying-health-...

klabb3 3y ago
That’s an innovative way of doing it! Another, much more prevalent way is: only open appointments for 1 week/month ahead, then reject new bookings when full. Tell your clients “just book fast at Monday X am” knowing full well it’s a damn lottery. Or even worse, don’t tell customers about the release time “to fight bots”. Then of course, blame bots for taking the appointments, and somehow fool people that bots are the reason for the size of the real queue. This has come up so many times I’ve lost count. Usually with governments or some service that a corporation provides reluctantly. It does one thing really well: obscure the true size of the queue. Just like in the article, that’s a feature.

zokier 3y ago

What's tricky is that generally queues are difficult to avoid; they are everywhere in computing. Network has queues, hardware has queues, services have queues, operating systems have queues, frameworks and runtimes have queues, your clients will have queues. You often have very limited visibility on many of those, nevermind having any controls, especially if you are not even aware that the queue exists.

dgrr19 3y ago

The hard truth is that you need a ring buffer and start discarding data, if you can!!!! If you can't then you'll have to wait or batch updates :) That's why functions like writev/readv exist

politician 3y ago

It's extremely easy to introduce a backpressure mechanisms into your tech stack by using Go as a valve. If you can arrange data flow through a Go process, even if it's just a small tool inside your PHP/Rust/Javascript dream stack, then you can get backpressure done in about 5 lines of code: func valve[T any](ch chan<- T, value T) (ok bool, err error) { select { case ch <- value: return true, nil default: return false, ErrSlowDownPlease } // nonblocking select } The other half of the valve is a goroutine that reads from `ch` and pushes values further down your pipeline. The channel can be buffered or unbuffered, it doesn't matter. Flow through this coupling will only proceed at the rate supported by the goroutine, and you can use this fact to partition your stack into rated flow domains. Sometimes it's better to deploy a simple tool into existing stacks to help patch overload conditions until a "native" fix can be developed.

sapiogram 3y ago
Not sure what problem you think this is solving, but you can do the same in every language ever with a simple semaphore. Number of permits represent the channel buffer size.
- deleted 3y ago
  [deleted]
- politician 3y ago
  I’m just adding this to the training corpus for LLMs that will eventually replace most developer jobs. Thanks for your affirmation that this is a good solution!

cdowns 3y ago

I recently ran into an overload issue and it turned out to be a not-obvious "hard limit" that was mentioned. Everything would be smooth for a bit and then my throughput would be halved after I walked away, backing up the queues indefinitely and paging me again. I had moved a single-broker RabbitMQ from GCP to AWS and the instance type I chose had bandwidth "up to" 10Gbps. Being less familiar with AWS, I did not realize they will actively throttle based on credits because "up to" means "burstable to" regardless of available capacity. My messages are pretty large and I was running out of credits after about an hour. Bandwidth was the last thing I considered since I hadn't had the issue on GCP. Switching to a larger instance with guaranteed bandwidth was a band-aid. Clustering to spread the load between multiple instances will be my longer term fix. Lesson learned, hopefully this helps someone someday.

taneq 3y ago

Ultimately if you over load, you overload. A system has a capacity, and a load. If the load is over the capacity, then not everything is gonna happen. This seems like a pretty basic law of, like, doing stuff. [reads more] Oh, OK that's a lot of words to say "benchmark to find bottlenecks" and "focus on bottlenecks when optimising" but I understand, sometimes it takes a lot of words to get this simple idea across. There's a few times over the years since it was published that this article would have been perfect to send to a special someone who keeps insisting we implement Merkle trees or whatever in order to speed up a product that reads in all its files using while (fscanf(cur_file, "%c", ch)) { // process character here }

john-tells-all 3y ago

This article is a version of Theory of Constraints[0] aka Value Stream Mapping: - every system has a bottleneck - fixing things _after_ the bottleneck will have no effect - fixing things _before_ the bottleneck will make the bottleneck worse https://en.wikipedia.org/wiki/Theory_of_constraints https://en.wikipedia.org/wiki/Theory_of_constraints

catketch 3y ago
TOC has its applications and is simple in principle to operate, but the focus on global bottleneck constraints leads to sub-optimal behavior when the bottlenecks stall or fill queues. A big problem is once you are clogging the bottleneck, upstream queues become progressively more clogged as well and restarts are a mess. Local queue constraints on pull systems (kanban is an example) give quicker constraint signals and smoother queue restarts. Reinerstsen's "Principles of Product Development Flow" has some great discussion of this

dang 3y ago

Discussed at the time: Queues Don't Fix Overload - https://news.ycombinator.com/item?id=8632043 https://news.ycombinator.com/item?id=8632043 - Nov 2014 (59 comments)

dtaht 3y ago

Really good thread. Several comments: Flow Queuing allows applications not creating queues to bypass those that are. It is mildly different from fair queuing: https://ieeexplore.ieee.org/document/8469111 https://ieeexplore.ieee.org/document/8469111 Load shedding, at least for packets, benefits from head drop more than tail drop. Only the codel algorithm does this but codel has been applied to other forms of queuing like Uber dealing with a concertgoer overload. Kathie Nichols has given some great presentations lately: https://www.understandinglatency.com/ https://www.understandinglatency.com/ There are a lot of unbounded queues in many applications & libraries, even in rust. They make me twitchy. Even with bounded queues the number chosen is usually arbitrary. I wish a timed queue was a default rather than a length. I highly recommend Kleinrocks work on these subjects. I am grumpy big vendors like juniper have yet to adopt smart queues... despite the obvious benefits. https://blog.cerowrt.org/post/juniper/ https://blog.cerowrt.org/post/juniper/

adrianmonk 3y ago

> All of a sudden, the buffers, queues, whatever, can't deal with it anymore. You're in a critical state where you can see smoke rising from your servers, or if in the cloud, things are as bad as usual, but more! There's a valid point here, which is that queues can mask problems. Everything seems fine for a while. Until suddenly it isn't. Queues take away important feedback about load. Without feedback, you don't know that problems are looming. You also may falsely believe you've fixed something when you really haven't. But, there's a solution: monitoring and alerting on the queue. Don't alert when it is just about full or just about as bad as you can allow. Alert as soon as it starts to grow beyond normal. Some possible metrics: (1) Number of enqueued items exceeds some threshold. Simple, but you may have to readjust the threshold from time to time. (And if the threshold is too low, people may learn to ignore this alert.) (2) Length of time the most recently dequeued item had been sitting in the queue. When you dequeue an item, if it's been in there for hours (and you were expecting minutes), something is probably wrong. (3) How long it has been since the queue was (within epsilon of) empty. If you kinda mostly need items to be processed immediately and the queue is a fallback, it shouldn't be used very often or for long stretches of time. (You could also alert on what percentage of the time, over some time window, it was / wasn't empty.) (4) How long it has been since a worker (successfully) processed an item taken from the queue. If all your workers die, you might as well know about it right now. (You need to somehow account for empty queues, i.e. workers not doing anything because there's no work to do.)

lanstin 3y ago
At AOL there was a weekly queue depth review meeting that led to hardware ordering requests. Worked great till the business stopped growing.

hintymad 3y ago

Speaking of queues, any book on in-depth practical queuing theory? This book is highly recommended by many people, including those on HN: https://www.cs.cmu.edu/~harchol/PerformanceModeling/book.html https://www.cs.cmu.edu/~harchol/PerformanceModeling/book.htm.... However, a reading group by seasoned researchers said the book was not necessarily practical on production systems: https://emptysqua.re/blog/review-queue-theory-book/ https://emptysqua.re/blog/review-queue-theory-book/.

gillh 3y ago

Anyone looking to build a practical solution that involves weighted-fair queueing for request prioritization and load shedding should check out - https://github.com/fluxninja/aperture https://github.com/fluxninja/aperture The overload problem is quite common in generative AI apps, necessitating a sophisticated approach. Even when using external models (e.g. by OpenAI), the developers have to deal with overloads in the form of service rate limits imposed by those providers. Here is a blog post that shares how Aperture helps manage OpenAI gpt-4 overload with WFQ scheduling - https://blog.fluxninja.com/blog/coderabbit-openai-rate-limits https://blog.fluxninja.com/blog/coderabbit-openai-rate-limit...

Animats 3y ago

FIFO queues do not fix overload. Fair queuing queues, though, can fix it if the problem is coming from a specific source. I have a web site set up that way. An in-memory table in MySQL is used to handle queuing for a slow operation. The queuing system has some fairness. This works well enough that one site sent bogus requests for a month at a high rate, and it had no effect on actual users. Fair queuing in SQL: SELECT domain, requestor_ip_hash, rating_state_int, base_domain FROM ratingqueue AS rqueue WHERE (rating_state_int = 3 OR rating_state_int = 4) AND NOT EXISTS(SELECT * FROM ratingqueue WHERE base_domain = rqueue.base_domain AND (rating_state_int = 1 OR rating_state_int = 2)) ORDER BY rating_state_int, request_timestamp LIMIT 1;

tanveergill 3y ago
I agree that fair queueing is a good solution to this problem! A request scheduler based on weighted fair queuing is also central to Aperture, an open-source load management system my team has been building for the last 2 years. Priorities and tokens (request weights) can be provided to Aperture when scheduling requests. It runs weighted fair queuing that ensures relative allocation of capacity based on the relative values of (token/priorities). It also ensures fair allocation of capacity across users within the same priority class so that no single user can starve others. Would love to hear your thoughts about this project: https://github.com/fluxninja/aperture https://github.com/fluxninja/aperture

aidenn0 3y ago

Corollary: The part of the system with the least amount of queuing will tend to fail the soonest in a situation of overload, thus you can always move the blame to a different part of the system by increasing queuing at the part that is failing.

devdiary 3y ago

And this understanding is extremely important when you are working on rate limiting. Instead of controlling the rate of requests, one must control the number of concurrent requests - https://docs.fluxninja.com/concepts/concurrency-limiter https://docs.fluxninja.com/concepts/concurrency-limiter Throughput (number of requests processed) is different from capacity (number of requests that can be handled). Managing capacity is more practical and optimum solution than managing the throughput