9 ms·

we are so stuck with this push request load balancing its crazy, if we just switch to pull instead of push things get much smoother, and resources get better ut

we are so stuck with this push request load balancing its crazy, if we just switch to pull instead of push things get much smoother, and resources get better utilized you cant reliably guess if the instance where you will push your request actually has capacity to handle it, even using ML to guess it will still have thrashing properties but if you just let instances pull work, things work out for themselves sadly, the whole industry is stuck on http push i was playing with it few years ago making a simple queue and wrote my ideas here: https://punkjazz.org/jack/we-got-it-all-wrong.txt https://punkjazz.org/jack/we-got-it-all-wrong.txt and some basic benchmarks https://punkjazz.org/jack/we-got-it-all-wrong-2.txt https://punkjazz.org/jack/we-got-it-all-wrong-2.txt in the same time, there is so much tooling for http, and its so natural to use it, that it is actually hard to switch to another transport layer, so now the best we have is some naive bayesian classifiers in the LB and some exponential backoff here is the difference i had in timings using synchronous io queue vs http for 2 endpoints, one fast and one slow (endpoints had the same code, just transport was different) 2019/02/19 22:26:27 synchronous QUEUE ... 20000 messages, took: 29.95s, speed: 667.74 per second - 0+10=9711 48.55% ****************************** - 10+ 5= 276 49.94% - 15+ 8= 20 50.03% - 23+12= 16 50.11% - 35+18=3398 67.11% ********** - 53+27=6549 99.85% ******************** - 80+40= 30 100.00% - 120+60= 0 100.00% - 180+90= 0 100.00% - 270+ 0= 0 100.00% 2019/02/19 22:26:56 http ... 20000 messages, took: 29.55s, speed: 676.91 per second - 0+10=3274 16.37% ******************** - 10+ 5=1523 23.98% ********* - 15+ 8=4439 46.18% **************************** - 23+12=4756 69.96% ****************************** - 35+18=3318 86.55% ******************** - 53+27=2037 96.73% ************ - 80+40= 581 99.64% *** - 120+60= 70 99.99% - 180+90= 2 100.00% - 270+ 0= 0 100.00% you can see how the fast endpoint is always fast with the queue transport, but with classic push load balancing it spills latency a lot, because the instance is sometime busy servicing the slow request PS: this post is absolutely amazing! and the animations are brilliant! thanks a lot for making it

preseinger 3y ago
if your load balancer holds on to each received request until a downstream server happens to pull that request and process it, then it's not a load balancer, it's a queue different concept, different semantics, different results
Mavvie 3y ago
So what do you think the disadvantage is of a pull approach? Presumably it's not just better or else tools would use it?
- throwaway71271 3y ago
  i never ran this in prod, so not sure i think the retries are a bit strange, and debugging was weirder as well, but its probably just me not used to it even though i had multiple chances to use it in prod, i always go for http somehow, it just feels so familiar also because of the way the REPLY_TO address:port worked in my experiments, sometimes having half open tcp connections really messes up things
- jgtrosh 3y ago
  Not an expert in load balancing, but in similar problems (work sharing / work stealing, MPI get/put) it makes sense to pull only if you can pull fast enough to avoid incurring prohibitive latency at every request/message. Multithreading-based work stealing à la Cilk relies on extremely cheap thread mechanisms and implementation to minimize communication. In another similar situation, HPC switches are credit based so that until you hit congestion, you can “instantaneously” know if a remote is ready to receive. This isn't a formal explanation, of course. Edit: after some thought, that's not really the distinction that is made for load balancing. There's already knowledge of the remote state required for pushing to the last loaded queue. So the difference between pull and push is about having one queue vs several. In that sense it is like supermarkets that implement the more efficient one queue to every cashier Vs the more traditional one queue per cashier. In supermarkets there is a choice to make because there's other constraints, but just optimising for load balancing it's strictly better to have a single queue, if you only have one input.
  - rektide 3y ago
    Having enough workers to do the work shouldn't be any more constraining than it was before. The article does nicely mention that simple round Robin actually has lower latency, because some traffic gets lucky & goes to under-utilized machines. Unfairness helps some traffic go faster. The queue is probably going to eliminate this, but the unfairness advantage comes at the cost of a lot of other traffic getting put into long queues on workers, so it wasn't really a good thing anyways. The p90+ is usually awful.
gbuk2013 3y ago
Moving to async model adds new set of operational challenges as well as some interesting failure scenarios. (Edit) Also, in practice you would need at least one more system to enqueue request into the broker, as the latter would typically not be exposed to the outside world. Request/response on the other hand is much simpler to configure and operate.
- throwaway71271 3y ago
  this is not async, its sync queue the lb puts a request where it has some reply_to (ip:port) where it waits (blockingly) for response from whoever picked up the request, it just does now know who that is until a reply comes
  - gbuk2013 3y ago
    If you have a queue then you have async model. As an example of a failure scenario, how does your system distinguish between a request timeout, a response that didn’t get sent back because of network failure and the consumer crashing and losing the message?
    - throwaway71271 3y ago
      pretty much the same way a push load balancer does https://github.com/jackdoe/back-to-back/blob/master/broker/broker.go#L135 https://github.com/jackdoe/back-to-back/blob/master/broker/b... for { select { case reply := <-replyChannel: if reply.Uuid == r.message.Uuid { return reply } case <-timeout: return makeError(r.message, MessageType_ERROR_CONSUMER_TIMEOUT, "consumer timed out") } } not much different than what you do with normal http timeouts, you send a request, sometimes a response comes sometimes it doesnt, up to the load balancer to decide if it wants to retry or error out also, queue does not mean async model, it means a queue, there are many queues in http requests responses (e.g. the listen(2) backlog queue itself) and it does not make it async :)
      - gbuk2013 3y ago
paulddraper 3y ago
One of the nicest things about pull load balancing is that it completely replaces the need for a separate registration + health check system. Once you consider that, IDK if someone can really claim "more complicated."
- throwaway71271 3y ago
  oh yea, the amount of outages we had in my last company because of weighted roundrobbin registration/healthcheck/watermark/latch issues were way more than anyone would guess
- samwho 3y ago
  I honestly had never thought hard about reversing the relationship and having workers pull. This point about no longer requiring health checks is a real "woah" moment. Thanks for expanding my mind!
  - throwaway894345 3y ago
    Agreed on the “whoa moment”. Not needing health checks seems pretty compelling. I’m curious if there are any off-the-shelf pull-based load balancer that don’t require the full HTTP request copied onto the queue before handing off to a worker?
    - adql 3y ago
      You need health checks. If not for LB then for your own monitoring.
      - preseinger 3y ago
        you don't a server can return 200 OK to every health check query and 5xx to every production request, is that server up or down? hopefully clear it is down similarly, if it returns 5xx to every health check query but 200 to every prod request, is it up or down? hopefully clear it is up if you want to monitor the status of a server (or application) for internal purposes, that's fine, but that's (at best) supplementary signal for the decisions made by a load balancer, not something you can make load balancing decisions on in isolation
samwho 3y ago
Thank _you_ for striking up a spirited discussion! :)
artworx 3y ago
The AWS Lambda Runtime API is pull based: - GET events from ${AWS_LAMBDA_RUNTIME_API}/2018-06-01/runtime/invocation/next - process it (run your handler) - POST the response to /runtime/invocation/AwsRequestId/response https://docs.aws.amazon.com/lambda/latest/dg/runtimes-api.html https://docs.aws.amazon.com/lambda/latest/dg/runtimes-api.ht...
jayd16 3y ago
Honestly, I disagree. It's not like queue systems are rare. They're fairly common and they're often seen as an over complication! Once and only once queuing is hard. Async programming is hard. Streaming requests or responses is out the window! Now you're storing the full request and response blobs in your infrastructure instead of chunks at a time in the network layer. Is a whole Netflix movie queued? If we're talking about queued chunks then its just UDP you're describing. Connection oriented designs tend to more transparency end to end. The synchronous nature means a failed call can be bubbled back through the remote call chain. Failed async calls can be dropped, which leaves ambiguity. The callers need to resort to timeouts instead of closed connection signals. Not to mention the issue that this doesn't work for client calls. The response handling from the client is more complex. The async callback would need to be demuxed such that a response can be associated with a call. There's no open connection so you'd need to punch the firewall somehow...honestly its very messy.
- throwaway71271 3y ago
  'once and only once' anything is hard, including connection oriented designs, also sync calls can fail in quite similar ways as async calls as per FLP/CAP the truth is that sync calls (in normal aws + k8s example) have like 50 queues between the user's kernel and your program actually doing the work, just considering the listen(2) queues, and the network card queues, and the reality is that every one of them can just drop packets on the floor whenever it wants so in reality, network programming is hard, and even sync things are just a collection of many async pieces from the network card to the userspace
- paulddraper 3y ago
  https://news.ycombinator.com/item?id=35614032 https://news.ycombinator.com/item?id=35614032 tl;dr The difference is internal queue vs external queue. As another commenter points out, AWS Lambda operates this way.
mholt 3y ago
In Caddy we've implemented "dynamic upstream modules" which allow an arbitrary (compiled-in) plugin to give the reverse proxy a list of upstreams that can take the request. A pull-based mechanism could relatively easily be constructed with this feature: https://caddyserver.com/docs/json/apps/http/servers/routes/handle/reverse_proxy/dynamic_upstreams/ https://caddyserver.com/docs/json/apps/http/servers/routes/h... I could imagine a dynamic upstream module that receives UDP or TCP packets from backends with a number estimating how many connections it can handle at that time. The module then tells the reverse proxy which upstream has the highest number and the reverse proxy selects it.
deleted 3y ago
[deleted]
zokier 3y ago
That sort pull architecture is interesting thought. I do see it working best when a worker nodes ability to do work is very clear cut, i.e. the response time does not significantly vary with the number of concurrent requests it is handling. Here is an example where it would not work well: lets imagine workers are doing a CPU bound task and each worker has one cpu (for simplicity), but we have also identified that we can handle up to 10 requests concurrently on one worker, but they will be just slower (because they will get smaller slices of cpu). Ideally we'd wish the requests to be divided equally between the workers, but with naive pull model one worker could greedily grab requests up until its at capacity while the other workers stay idle, making the response times worse than they need to be.
- throwway120385 3y ago
  With a pull architecture you wouldn't identify a request queue depth up front. Rather, each incoming connection gets delayed until a worker attaches to EG the TCP stream. If you're serving a webpage the client wouldn't see anything other than a little load lag, especially if your load balancer took care of the TLS connection before pausing to wait for a worker. So if you can handle every incoming request with one worker that worker gets them all. Otherwise each worker pops off the stack as it becomes free. And if you can service more concurrent requests you just add more workers.
  - zokier 3y ago
    > So if you can handle every incoming request with one worker that worker gets them all. Otherwise each worker pops off the stack as it becomes free As I alluded, that works great if "can handle" and "being free" are clear-cut binary properties. But for complex applications when you are driving for high utilization while keeping latency down those questions become complicated; a worker might have some free capacity to handle requests but it doesn't mean that it would produce response as quickly as some other (more idle) worker. In other words, the problem is not just assigning requests to workers that can handle them but assigning requests to workers that can handle them with lowest latency.
  - preseinger 3y ago
mgoetzke 3y ago
Peter Hintjens wrote a lot of different protocols in https://zguide.zeromq.org/docs/chapter4/#Service-Oriented-Reliable-Queuing-Majordomo-Pattern https://zguide.zeromq.org/docs/chapter4/#Service-Oriented-Re... and they mostly are part of the spec https://rfc.zeromq.org/spec/18/ https://rfc.zeromq.org/spec/18/ now. Some of these protocols are a good improvement when looking for the ultimate in speed and I used them where applicable, but as a first order approximation a simple load balancer approach is quite good enough. Especially when you do not have dedicated people vested in that domain for maintenance.

preseinger 3y ago

if your load balancer holds on to each received request until a downstream server happens to pull that request and process it, then it's not a load balancer, it's a queue different concept, different semantics, different results

Mavvie 3y ago

So what do you think the disadvantage is of a pull approach? Presumably it's not just better or else tools would use it?

throwaway71271 3y ago
i never ran this in prod, so not sure i think the retries are a bit strange, and debugging was weirder as well, but its probably just me not used to it even though i had multiple chances to use it in prod, i always go for http somehow, it just feels so familiar also because of the way the REPLY_TO address:port worked in my experiments, sometimes having half open tcp connections really messes up things
jgtrosh 3y ago
Not an expert in load balancing, but in similar problems (work sharing / work stealing, MPI get/put) it makes sense to pull only if you can pull fast enough to avoid incurring prohibitive latency at every request/message. Multithreading-based work stealing à la Cilk relies on extremely cheap thread mechanisms and implementation to minimize communication. In another similar situation, HPC switches are credit based so that until you hit congestion, you can “instantaneously” know if a remote is ready to receive. This isn't a formal explanation, of course. Edit: after some thought, that's not really the distinction that is made for load balancing. There's already knowledge of the remote state required for pushing to the last loaded queue. So the difference between pull and push is about having one queue vs several. In that sense it is like supermarkets that implement the more efficient one queue to every cashier Vs the more traditional one queue per cashier. In supermarkets there is a choice to make because there's other constraints, but just optimising for load balancing it's strictly better to have a single queue, if you only have one input.
- rektide 3y ago
  Having enough workers to do the work shouldn't be any more constraining than it was before. The article does nicely mention that simple round Robin actually has lower latency, because some traffic gets lucky & goes to under-utilized machines. Unfairness helps some traffic go faster. The queue is probably going to eliminate this, but the unfairness advantage comes at the cost of a lot of other traffic getting put into long queues on workers, so it wasn't really a good thing anyways. The p90+ is usually awful.

gbuk2013 3y ago

Moving to async model adds new set of operational challenges as well as some interesting failure scenarios. (Edit) Also, in practice you would need at least one more system to enqueue request into the broker, as the latter would typically not be exposed to the outside world. Request/response on the other hand is much simpler to configure and operate.

throwaway71271 3y ago
this is not async, its sync queue the lb puts a request where it has some reply_to (ip:port) where it waits (blockingly) for response from whoever picked up the request, it just does now know who that is until a reply comes
- gbuk2013 3y ago
  If you have a queue then you have async model. As an example of a failure scenario, how does your system distinguish between a request timeout, a response that didn’t get sent back because of network failure and the consumer crashing and losing the message?
  - throwaway71271 3y ago
    pretty much the same way a push load balancer does https://github.com/jackdoe/back-to-back/blob/master/broker/broker.go#L135 https://github.com/jackdoe/back-to-back/blob/master/broker/b... for { select { case reply := <-replyChannel: if reply.Uuid == r.message.Uuid { return reply } case <-timeout: return makeError(r.message, MessageType_ERROR_CONSUMER_TIMEOUT, "consumer timed out") } } not much different than what you do with normal http timeouts, you send a request, sometimes a response comes sometimes it doesnt, up to the load balancer to decide if it wants to retry or error out also, queue does not mean async model, it means a queue, there are many queues in http requests responses (e.g. the listen(2) backlog queue itself) and it does not make it async :)
    - gbuk2013 3y ago

paulddraper 3y ago

One of the nicest things about pull load balancing is that it completely replaces the need for a separate registration + health check system. Once you consider that, IDK if someone can really claim "more complicated."

throwaway71271 3y ago
oh yea, the amount of outages we had in my last company because of weighted roundrobbin registration/healthcheck/watermark/latch issues were way more than anyone would guess
samwho 3y ago
I honestly had never thought hard about reversing the relationship and having workers pull. This point about no longer requiring health checks is a real "woah" moment. Thanks for expanding my mind!
- throwaway894345 3y ago
  Agreed on the “whoa moment”. Not needing health checks seems pretty compelling. I’m curious if there are any off-the-shelf pull-based load balancer that don’t require the full HTTP request copied onto the queue before handing off to a worker?
  - adql 3y ago
    You need health checks. If not for LB then for your own monitoring.
    - preseinger 3y ago
      you don't a server can return 200 OK to every health check query and 5xx to every production request, is that server up or down? hopefully clear it is down similarly, if it returns 5xx to every health check query but 200 to every prod request, is it up or down? hopefully clear it is up if you want to monitor the status of a server (or application) for internal purposes, that's fine, but that's (at best) supplementary signal for the decisions made by a load balancer, not something you can make load balancing decisions on in isolation

samwho 3y ago

Thank _you_ for striking up a spirited discussion! :)

artworx 3y ago

The AWS Lambda Runtime API is pull based: - GET events from ${AWS_LAMBDA_RUNTIME_API}/2018-06-01/runtime/invocation/next - process it (run your handler) - POST the response to /runtime/invocation/AwsRequestId/response https://docs.aws.amazon.com/lambda/latest/dg/runtimes-api.html https://docs.aws.amazon.com/lambda/latest/dg/runtimes-api.ht...

jayd16 3y ago

Honestly, I disagree. It's not like queue systems are rare. They're fairly common and they're often seen as an over complication! Once and only once queuing is hard. Async programming is hard. Streaming requests or responses is out the window! Now you're storing the full request and response blobs in your infrastructure instead of chunks at a time in the network layer. Is a whole Netflix movie queued? If we're talking about queued chunks then its just UDP you're describing. Connection oriented designs tend to more transparency end to end. The synchronous nature means a failed call can be bubbled back through the remote call chain. Failed async calls can be dropped, which leaves ambiguity. The callers need to resort to timeouts instead of closed connection signals. Not to mention the issue that this doesn't work for client calls. The response handling from the client is more complex. The async callback would need to be demuxed such that a response can be associated with a call. There's no open connection so you'd need to punch the firewall somehow...honestly its very messy.

throwaway71271 3y ago
'once and only once' anything is hard, including connection oriented designs, also sync calls can fail in quite similar ways as async calls as per FLP/CAP the truth is that sync calls (in normal aws + k8s example) have like 50 queues between the user's kernel and your program actually doing the work, just considering the listen(2) queues, and the network card queues, and the reality is that every one of them can just drop packets on the floor whenever it wants so in reality, network programming is hard, and even sync things are just a collection of many async pieces from the network card to the userspace
paulddraper 3y ago
https://news.ycombinator.com/item?id=35614032 https://news.ycombinator.com/item?id=35614032 tl;dr The difference is internal queue vs external queue. As another commenter points out, AWS Lambda operates this way.

mholt 3y ago

In Caddy we've implemented "dynamic upstream modules" which allow an arbitrary (compiled-in) plugin to give the reverse proxy a list of upstreams that can take the request. A pull-based mechanism could relatively easily be constructed with this feature: https://caddyserver.com/docs/json/apps/http/servers/routes/handle/reverse_proxy/dynamic_upstreams/ https://caddyserver.com/docs/json/apps/http/servers/routes/h... I could imagine a dynamic upstream module that receives UDP or TCP packets from backends with a number estimating how many connections it can handle at that time. The module then tells the reverse proxy which upstream has the highest number and the reverse proxy selects it.

deleted 3y ago

[deleted]

zokier 3y ago

That sort pull architecture is interesting thought. I do see it working best when a worker nodes ability to do work is very clear cut, i.e. the response time does not significantly vary with the number of concurrent requests it is handling. Here is an example where it would not work well: lets imagine workers are doing a CPU bound task and each worker has one cpu (for simplicity), but we have also identified that we can handle up to 10 requests concurrently on one worker, but they will be just slower (because they will get smaller slices of cpu). Ideally we'd wish the requests to be divided equally between the workers, but with naive pull model one worker could greedily grab requests up until its at capacity while the other workers stay idle, making the response times worse than they need to be.

throwway120385 3y ago
With a pull architecture you wouldn't identify a request queue depth up front. Rather, each incoming connection gets delayed until a worker attaches to EG the TCP stream. If you're serving a webpage the client wouldn't see anything other than a little load lag, especially if your load balancer took care of the TLS connection before pausing to wait for a worker. So if you can handle every incoming request with one worker that worker gets them all. Otherwise each worker pops off the stack as it becomes free. And if you can service more concurrent requests you just add more workers.
- zokier 3y ago
  > So if you can handle every incoming request with one worker that worker gets them all. Otherwise each worker pops off the stack as it becomes free As I alluded, that works great if "can handle" and "being free" are clear-cut binary properties. But for complex applications when you are driving for high utilization while keeping latency down those questions become complicated; a worker might have some free capacity to handle requests but it doesn't mean that it would produce response as quickly as some other (more idle) worker. In other words, the problem is not just assigning requests to workers that can handle them but assigning requests to workers that can handle them with lowest latency.
- preseinger 3y ago

mgoetzke 3y ago

Peter Hintjens wrote a lot of different protocols in https://zguide.zeromq.org/docs/chapter4/#Service-Oriented-Reliable-Queuing-Majordomo-Pattern https://zguide.zeromq.org/docs/chapter4/#Service-Oriented-Re... and they mostly are part of the spec https://rfc.zeromq.org/spec/18/ https://rfc.zeromq.org/spec/18/ now. Some of these protocols are a good improvement when looking for the ultimate in speed and I used them where applicable, but as a first order approximation a simple load balancer approach is quite good enough. Especially when you do not have dedicated people vested in that domain for maintenance.