Queues don't fix overload (2014) • Hacker News Board

Re: Queues don't fix overload (2014)

#31

Post by PaulHoule » Thu, Jan 18, 2024, 2:48 PM UTC

domano wrote: post #12

roenxi wrote: post #7

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 peo…

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.

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...

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.

Re: Queues don't fix overload (2014)

#32

Post by Joker_vD » Thu, Jan 18, 2024, 2:48 PM UTC

User23 wrote: post #6

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 equ…

> 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.

Re: Queues don't fix overload (2014)

#33

Post by sokoloff » Thu, Jan 18, 2024, 2:50 PM UTC

mhandley wrote: post #18

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 cap…

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.

Re: Queues don't fix overload (2014)

#34

Post by manuelabeledo » Thu, Jan 18, 2024, 2:53 PM UTC

0xbadcafebee wrote: post #22

kasey_junk wrote: post #8

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…

The only real solution to overload (that is, the eventuality of the system not having enough capacity), in modern systems, is autoscaling. Nobody seems to talk about this, I guess because it's taken for granted? But you can literally just keep adding capacity now. We didn't really have that before the cloud; you had the servers you bought, and maybe you'd rush to repurpose some servers to add capacity. Now an algorit…

> Nobody seems to talk about this, I guess because it's taken for granted?

No, because it has a theoretical limit, same as queues, back pressure, etc.

One cannot simply scale up indefinitely because it is not profitable.

Re: Queues don't fix overload (2014)

#35

Post by marcosdumay » Thu, Jan 18, 2024, 2:53 PM UTC

kasey_junk wrote: post #8

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…

No, load shedding and back pressure present you trade-offs to deal with an overloaded system.

Queues don't. Queues just present you problems. If you take an overloaded system and add a queue, every single feature either gets worse or doesn't get any better.

And people like to deny this, and pretend that queues will help. They absolutely help with a lot of things but they do nothing but harm in front of an overloaded system.

Re: Queues don't fix overload (2014)

#36

Post by mhandley » Thu, Jan 18, 2024, 2:56 PM UTC

sokoloff wrote: post #33

mhandley wrote: post #18

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 cap…

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 econom…

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.

Re: Queues don't fix overload (2014)

#37

Post by regulation_d » Thu, Jan 18, 2024, 2:56 PM UTC

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.

Re: Queues don't fix overload (2014)

#38

Post by ahoka » Thu, Jan 18, 2024, 2:59 PM UTC

0xbadcafebee wrote: post #22

kasey_junk wrote: post #8

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…

The only real solution to overload (that is, the eventuality of the system not having enough capacity), in modern systems, is autoscaling. Nobody seems to talk about this, I guess because it's taken for granted? But you can literally just keep adding capacity now. We didn't really have that before the cloud; you had the servers you bought, and maybe you'd rush to repurpose some servers to add capacity. Now an algorit…

Increasing capacity would be very stupid if doing so does not also increase revenue.

Re: Queues don't fix overload (2014)

#39

Post by LanceH » Thu, Jan 18, 2024, 3:00 PM UTC

User23 wrote: post #6

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 equ…

Their alternative:

"To make stuff usable, a proper idempotent API with end-to-end principles in mind will make it so these instances of back-pressure and load shedding should rarely be a problem for your callers, because they can safely retry requests and know if they worked."

Is to ignore requests and make the caller implement their own queue, apparently.

Re: Queues don't fix overload (2014)

#40

Post by PaulHoule » Thu, Jan 18, 2024, 3:02 PM UTC

mhandley wrote: post #18

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 cap…

See https://en.wikipedia.org/wiki/Bufferbloat

I lived in Germany in 1999 and then the internet connection from Germany to the US would get overloaded during the day. At maybe 9am the latency would be then it would start dropping packets.

I don't know if it was the intention but it was about as good as a ban on VoIP at preventing people from making international VoIP calls.

Today there is more consciousness about the problem but people frequently create an overly long or nominally unbounded queue: in that case you start with one problem, insufficient throughput, can add the problem of unacceptable latency by adding a small queue. Limit the length of the queue and you put a cap on latency.

Backpressure is hard to implement for social and political reasons as much as technical, people don't really like the idea that the system can refuse service and of course it often has to be pushed further back than people would expect.

I'd point to the example of a medical specialist office where once you are being seen as a patient you might have a series of appointments. The initial appointment controls admission to the system as a whole so you might wait a few months to get the first appointment, enough that you might "balk" and look for another doctor who can see you sooner. Once you are being treated you often have no problem rescheduling an appointment or scheduling follow-up appointments in a timely manner.