Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Queues don't fix overload (2014)

ferd.ca

Post reply on HN
Print view View original

61–70 of 156 posts

Re: Queues don't fix overload (2014)

#61

Post by xyzzy_plugh »

LanceH wrote: post #39
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.

It's turtles all the way down. At some point, it's _not really_ a queue.

For example imagine a computer program to fetch the contents of a list of URLs. Perhaps it makes some number of parallel requests.

If the URLs are hard coded, e.g.:

  fetch("https://news.ycombinator.com/")
  fetch("https://bbc.co.uk/")
  fetch("https://archive.org/")
  ...
When the maximum concurrency is reached (which could simply be 1) and all requests are blocking, then back-pressure is applied. The callers wait before submitting more work.

In this example the queue is the code, and the program counter acts represents the head of the queue. I wouldn't regularly refer to that as a queue.

Perhaps instead it reads a list of entries from a file. The queue's state can be represented by file offset. And so on.

Computers are by definition carry out sequences of operations. A sequence can be viewed as a queue. Everything is a queue.

So yes, ignore requests and make the caller implement their own queue _is a completely correct take_ in a sense, but I don't find it productive.

Re: Queues don't fix overload (2014)

#62

Post by lucidguppy »

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.

Re: Queues don't fix overload (2014)

#63

Post by tonyarkles »

PaulHoule wrote: post #31
domano wrote: post #12

Earlier quoted context omitted.

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 "e…

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.

Re: Queues don't fix overload (2014)

#64

Post by smaudet »

0xbadcafebee wrote: post #45
manuelabeledo wrote: post #34

Earlier quoted context omitted.

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

There's no product in the world that would hit a limit if autoscaled globally on AWS. Sure, you could write an app whose literal sole purpose is "take up all memory, CPU and bandwidth, recursively, infinitely", but nobody is making that product. Real products built today have a finite amount of demand, and global cloud capacity is larger than that. You can't say what architecture is or isn't profitable in general, bu…

> There's no product in the world that would hit a limit if autoscaled globally on AWS > but nobody is making that product

Nobody is making that product because nobody has money for it...(or the demand to supply that money).

You can auto-scale without AWS, actually, its called measuring server load and auto-ordering new machines when your load increases (and keeping machines turned off on standby for spikes).

Or you can go hybrid, and load-shed to a cloud...which would be the smart thing to do.

Re: Queues don't fix overload (2014)

#65

Post by supertrope »

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

Re: Queues don't fix overload (2014)

#66

Post by smaudet »

marcosdumay wrote: post #35
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…

Queues provide you breathing room to increase your throughput. They don't fix the clog, but they keep the kitchen sink from over-flowing while you call the plumber/install a new industrial line.

Re: Queues don't fix overload (2014)

#67

Post by wegfawefgawefg »

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…

buffers buffer. difficult to debate.

edit: theyre being called queues and a lot of effort is being put here into just describing the merits and demerits of them which i assumed would be self evident to anyone who can conceptualize a buffer in any context, not just software. savings buffer, heat buffer, coal buffer, resource buffer, inductors, capacitance.

they have fill and drain times, soften spikes, but require additional energy.

A math model of throughpts and voltages would be more useful than all the metaphors of pipes and buckets in this thread.

Re: Queues don't fix overload (2014)

#68

Post by User23 »

Joker_vD wrote: post #32
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 incomin…

Sure, and at some level everything is processing. Even putting an object at the end of a FIFO queue has overhead.

I would be very hesitant to introduce a sorting proxy unless the need for it had been thoroughly demonstrated though. If your prioritization isn’t lightweight enough to do in the server it’s probably too heavy. Also you might accomplish it at the network level. Regardless your point stands that the work has to be done somewhere, but that doesn’t change the fact that fair queuing is a good idea for the majority of production services. It’s absolutely great when a misbehaving client only DoSes themselves and doesn’t affect anyone else.

Re: Queues don't fix overload (2014)

#69

Post by vault_ »

0xbadcafebee wrote: post #45
manuelabeledo wrote: post #34

Earlier quoted context omitted.

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

There's no product in the world that would hit a limit if autoscaled globally on AWS. Sure, you could write an app whose literal sole purpose is "take up all memory, CPU and bandwidth, recursively, infinitely", but nobody is making that product. Real products built today have a finite amount of demand, and global cloud capacity is larger than that. You can't say what architecture is or isn't profitable in general, bu…

> Real products built today have a finite amount of demand, and global cloud capacity is larger than that.

This isn't really true, and it's especially not true when specialized hardware comes into play. If you have a "web-scale" GPU workload, it's not unlikely that you'll hit resource availability constraints from time to time. The question isn't whether cloud capacity is larger than your demand for a particular resource, it's whether cloud capacity is larger than the aggregate peak demand for that resource. Cloud providers aren't magic. They engage in capacity planning, sometimes underestimate, and are sometimes unable to actually procure as much hardware as they want to.

Re: Queues don't fix overload (2014)

#70

Post by sokoloff »

mhandley wrote: post #36
sokoloff wrote: post #33

Earlier quoted context omitted.

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…

As long as we are consistently emptying the queue of all orders due to be produced on the next shift, I think we are correctly sized while losing nothing (no load-shedding or turning orders away), even though we carry an overall non-zero backlog essentially permanently.

Having 48 hours of weekend where order volume is way down, but processing volume is constant is a key part of maintaining this equilibrium.

Post reply on HN