5 ms·

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

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.
  - sethammons 3y ago
    > But if your queue is never emptying, you've hit an equilibrium where you're persistently overloaded and constantly load shedding I believe this is an incorrect assertion. You have hit equilibrium, yes. But you are not load shedding unless you are preventing new queue entrants. And if you are allowing new entrants and the latency is acceptable to customers, you are not overloaded. Like you said, you are at an equilibrium.
  - datadrivenangel 3y ago
    It sounds like the above poster is in a situation with multiple priority queues, where as long as latency and throughput for high priority items is good, having higher latency for lower priority items is fine, and could be a form of low-cost back pressure on new orders or signalling to improve the throughput a little bit.
  - sokoloff 3y ago
    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.
PaulHoule 3y ago
See https://en.wikipedia.org/wiki/Bufferbloat 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 < 1 s but it would start to grow to a length of 90 seconds, 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.
- pjdesno 3y ago
  See RFC 970, "On Packet Switches With Infinite Storage" by John Nagle: https://datatracker.ietf.org/doc/html/rfc970 https://datatracker.ietf.org/doc/html/rfc970 Back then (I was studying networking as an undergrad at the time, and interned with the Arpanet team) people really did think of network congestion as a buffer allocation problem, so the obvious solution was more buffering - i.e. adding queues. Nagel was one of the first people to point out the problem with this.
  - kccqzy 3y ago
    That's because it is obvious and intuitive even though it's wrong. In the first year of my undergrad in an assignment I added unlimited buffering to every single place that needed buffering. I remember a sense of superiority from all the extra code I wrote to do it. Of course buffering felt correct! That was long before I heard of the word backpressure.
eddd-ddde 3y ago
The simplest example, try to empty a bucket on a pipe, you'll have a real struggle, you are gonna be standing there for awhile. Now empty a bucket in a sink, yeah it will fill up and maybe you can do two buckets at once, but after dumping it in one second you can leave it unattended and know that all that water will drain correctly.
kqr 3y ago
It's important to note that for interactive applications, queues can have surprisingly little capacity and still provide all the demand levelling necessary. Technically this depends on the variance of the arrivals, but in my practical experience, even quite bursty arrivals are often well-behaved enough that a second or so of queue capacity is sufficient. Any time I've had queues need more than a second of capacity has been when the system is broken and user experience has already degraded to the point where it might be better for the median user to shed a small amount of load to get back to a sub-second queue. (In batch processing where you aim for maximum throughput, obviously you need a long queue to make sure you never run out of job.)
- vidarh 3y ago
  You don't need a long queue even there if the producer can keep a short queue filled. E.g. a producer that receives an error when the queue is full and backs off but never backs off enough for the queue to fully empty can very well do just as well as maximizing throughout.
wegfawefgawefg 3y ago
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.
tanveergill 3y ago
We have been building a platform called Aperture in the open-source trying to solve this very problem. Our approach is to let the developer decide how long they want to wait in the queue using a timeout parameter. If timeout is hit, they may re-try with exponential backoff or load shed. While in the queue, requests get prioritized based on a weighted fair queuing algorithm. If there is tiering in the app, there could be a policy that can allocate majority of the capacity to paid vs free customer tiers. But this allocation is not really static, if there is free capacity available in the system then the free customer tier can take all of it. This is just like how CPU time is allocated by Linux based on nice values, even low priority processes are allowed to take up all the CPU time when demand is low. Apart from relative allocation across user tiers, Aperture's request scheduler can also ensure fairness across individual users within each tier to make sure no single user is hogging up all of the server capacity. The demand and capacity is determined based on a request rate quota or the maximum number of in-flight requests. Would love the community here to check us out on GitHub and provide feedback: https://github.com/fluxninja/aperture https://github.com/fluxninja/aperture

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.
- sethammons 3y ago
  > But if your queue is never emptying, you've hit an equilibrium where you're persistently overloaded and constantly load shedding I believe this is an incorrect assertion. You have hit equilibrium, yes. But you are not load shedding unless you are preventing new queue entrants. And if you are allowing new entrants and the latency is acceptable to customers, you are not overloaded. Like you said, you are at an equilibrium.
- datadrivenangel 3y ago
  It sounds like the above poster is in a situation with multiple priority queues, where as long as latency and throughput for high priority items is good, having higher latency for lower priority items is fine, and could be a form of low-cost back pressure on new orders or signalling to improve the throughput a little bit.
- sokoloff 3y ago
  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.

PaulHoule 3y ago

See https://en.wikipedia.org/wiki/Bufferbloat 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 < 1 s but it would start to grow to a length of 90 seconds, 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.

pjdesno 3y ago
See RFC 970, "On Packet Switches With Infinite Storage" by John Nagle: https://datatracker.ietf.org/doc/html/rfc970 https://datatracker.ietf.org/doc/html/rfc970 Back then (I was studying networking as an undergrad at the time, and interned with the Arpanet team) people really did think of network congestion as a buffer allocation problem, so the obvious solution was more buffering - i.e. adding queues. Nagel was one of the first people to point out the problem with this.
- kccqzy 3y ago
  That's because it is obvious and intuitive even though it's wrong. In the first year of my undergrad in an assignment I added unlimited buffering to every single place that needed buffering. I remember a sense of superiority from all the extra code I wrote to do it. Of course buffering felt correct! That was long before I heard of the word backpressure.

eddd-ddde 3y ago

The simplest example, try to empty a bucket on a pipe, you'll have a real struggle, you are gonna be standing there for awhile. Now empty a bucket in a sink, yeah it will fill up and maybe you can do two buckets at once, but after dumping it in one second you can leave it unattended and know that all that water will drain correctly.

kqr 3y ago

It's important to note that for interactive applications, queues can have surprisingly little capacity and still provide all the demand levelling necessary. Technically this depends on the variance of the arrivals, but in my practical experience, even quite bursty arrivals are often well-behaved enough that a second or so of queue capacity is sufficient. Any time I've had queues need more than a second of capacity has been when the system is broken and user experience has already degraded to the point where it might be better for the median user to shed a small amount of load to get back to a sub-second queue. (In batch processing where you aim for maximum throughput, obviously you need a long queue to make sure you never run out of job.)

vidarh 3y ago
You don't need a long queue even there if the producer can keep a short queue filled. E.g. a producer that receives an error when the queue is full and backs off but never backs off enough for the queue to fully empty can very well do just as well as maximizing throughout.

wegfawefgawefg 3y ago

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.

tanveergill 3y ago

We have been building a platform called Aperture in the open-source trying to solve this very problem. Our approach is to let the developer decide how long they want to wait in the queue using a timeout parameter. If timeout is hit, they may re-try with exponential backoff or load shed. While in the queue, requests get prioritized based on a weighted fair queuing algorithm. If there is tiering in the app, there could be a policy that can allocate majority of the capacity to paid vs free customer tiers. But this allocation is not really static, if there is free capacity available in the system then the free customer tier can take all of it. This is just like how CPU time is allocated by Linux based on nice values, even low priority processes are allowed to take up all the CPU time when demand is low. Apart from relative allocation across user tiers, Aperture's request scheduler can also ensure fairness across individual users within each tier to make sure no single user is hogging up all of the server capacity. The demand and capacity is determined based on a request rate quota or the maximum number of in-flight requests. Would love the community here to check us out on GitHub and provide feedback: https://github.com/fluxninja/aperture https://github.com/fluxninja/aperture