3 ms·

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

by 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.
- User23 3y ago
  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.
  - Joker_vD 3y ago
    > I would be very hesitant to introduce a sorting proxy > fair queuing is a good idea for the majority of production services Huh? As you've said, fair queuing requires one to quickly look at incoming messages, decide whether they are high/low-priority and route accordingly (to the processing server/to the queue). This is a sorting proxy, and so it seems that having it in some form is required to implement fair queuing. Right? > It’s absolutely great when a misbehaving client only DoSes themselves and doesn’t affect anyone else. Yes, of course. But that's precisely the problem with DoS/DDoS attacks: they're, inherently, the cases of a client/clients refusing to obey the back pressure demands from the upstream. Over network, a misbehaving client affects also affects their ISP at the very least, by the way.
LanceH 3y ago
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.
- xyzzy_plugh 3y ago
  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.
Sohcahtoa82 3y ago
> However, that may very well change with fair queueing. It doesn't matter what kind of queueing system you put in place. No matter how fancy it is, and even if the queue adds negligible overhead, if your average request arrival rate is higher than the average handling rate, your queue will grow unbounded. Then, for some requests, the system will appear to grind to a halt. There's no way around it. A priority queue just means that high-priority requests get processed faster. Low-priority requests might end up never getting handled. Here's a concrete example. I've got a web service that requires a login. I'm using bcrypt to hash passwords with a sufficiently large work factor that I can only hash 5 passwords per second and have a queue for the password hashing. If 6 people are trying to login every second, then after 1 minute, I will have received 360 login requests. 300 of them will have completed, but the queue has grown to 60. Anybody trying to log in at that point will have to wait a minimum of 12 seconds to get their login processed. But what if I also have users trying to sign up? I have to hash their password, so those get added to the queue as well. If I prioritize logins over signups, then under my scenario, a signup will never complete. There's really nothing that can be done. An unbounded queue means unbounded latency. Eventually, a login request would have to get rejected just because the queue is full. Of course, in the real world, this creates frustration for the user. They'll either try to login again, or give up.
- tanveergill 3y ago
  Aperture (https://github.com/fluxninja/aperture https://github.com/fluxninja/aperture) takes a slightly opinionated take on queue size. Instead of defining queue sizes, you put a timeout on each request which is the amount of time the request is willing to wait in the queue. Then we run a weighted fair queuing algorithm that ensures relative allocation across workloads, e.g. 90% capacity for critical requests. But the capacity is allowed to burst when there is low demand.
tanveergill 3y ago
I am in the same school of thought as you, fair queuing is the most optimal solution while capacity is constrained. This is the approach we took in Aperture, an open-source load management system. Read more about our Scheduler which implements a variant of WFQ (Weighted Fair Queuing) to ensure desired capacity allocation across workloads (group of requests at the same priority level) and SWFQ (Stochastic Weighted Fair Queuing) to ensure fairness across users within each workload: https://docs.fluxninja.com/concepts/scheduler https://docs.fluxninja.com/concepts/scheduler

by User23 3y ago

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.

User23 3y ago
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.
- Joker_vD 3y ago
  > I would be very hesitant to introduce a sorting proxy > fair queuing is a good idea for the majority of production services Huh? As you've said, fair queuing requires one to quickly look at incoming messages, decide whether they are high/low-priority and route accordingly (to the processing server/to the queue). This is a sorting proxy, and so it seems that having it in some form is required to implement fair queuing. Right? > It’s absolutely great when a misbehaving client only DoSes themselves and doesn’t affect anyone else. Yes, of course. But that's precisely the problem with DoS/DDoS attacks: they're, inherently, the cases of a client/clients refusing to obey the back pressure demands from the upstream. Over network, a misbehaving client affects also affects their ISP at the very least, by the way.

LanceH 3y ago

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.

xyzzy_plugh 3y ago
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.

Sohcahtoa82 3y ago

> However, that may very well change with fair queueing. It doesn't matter what kind of queueing system you put in place. No matter how fancy it is, and even if the queue adds negligible overhead, if your average request arrival rate is higher than the average handling rate, your queue will grow unbounded. Then, for some requests, the system will appear to grind to a halt. There's no way around it. A priority queue just means that high-priority requests get processed faster. Low-priority requests might end up never getting handled. Here's a concrete example. I've got a web service that requires a login. I'm using bcrypt to hash passwords with a sufficiently large work factor that I can only hash 5 passwords per second and have a queue for the password hashing. If 6 people are trying to login every second, then after 1 minute, I will have received 360 login requests. 300 of them will have completed, but the queue has grown to 60. Anybody trying to log in at that point will have to wait a minimum of 12 seconds to get their login processed. But what if I also have users trying to sign up? I have to hash their password, so those get added to the queue as well. If I prioritize logins over signups, then under my scenario, a signup will never complete. There's really nothing that can be done. An unbounded queue means unbounded latency. Eventually, a login request would have to get rejected just because the queue is full. Of course, in the real world, this creates frustration for the user. They'll either try to login again, or give up.

tanveergill 3y ago
Aperture (https://github.com/fluxninja/aperture https://github.com/fluxninja/aperture) takes a slightly opinionated take on queue size. Instead of defining queue sizes, you put a timeout on each request which is the amount of time the request is willing to wait in the queue. Then we run a weighted fair queuing algorithm that ensures relative allocation across workloads, e.g. 90% capacity for critical requests. But the capacity is allowed to burst when there is low demand.

tanveergill 3y ago

I am in the same school of thought as you, fair queuing is the most optimal solution while capacity is constrained. This is the approach we took in Aperture, an open-source load management system. Read more about our Scheduler which implements a variant of WFQ (Weighted Fair Queuing) to ensure desired capacity allocation across workloads (group of requests at the same priority level) and SWFQ (Stochastic Weighted Fair Queuing) to ensure fairness across users within each workload: https://docs.fluxninja.com/concepts/scheduler https://docs.fluxninja.com/concepts/scheduler