7 ms·

I feel like something missing from people's perspective when thinking of load balancing is to consider pull models. All push load balancing algorithms try to so

I feel like something missing from people's perspective when thinking of load balancing is to consider pull models. All push load balancing algorithms try to somehow predict how busy downstreams are. Some even go as far as having downstreams send back some utilization metrics. But if you use a pull-based approach, this is all sort of moot. Downstreams will pull work when they're ready for it.

wmf 4y ago
For most protocols like HTTP there's no software to do this and it's not worth developing something nonstandard.
- blipvert 4y ago
  Should be something that could quite easily be added to a uWSGI subscription router - subscribing node periodically says “I have N slots available” and the router keeps track of how many requests are in flight.
orthecreedence 4y ago
The pull model works beautifully for background work queues. For load balancing it seems it would take a bit of re-plumbing on the expectations of request/response. How would you envision this working with something like HTTP? It seems it would reverse the direction, which would be interesting.
- AYBABTME 4y ago
  Very similar to background queues but the load balancer holds the request and dispatches it to a waiting worker, or waits until someone comes to serve it. While the worker handles the request, the load balancer proxies. The request serving is the same, the way the work is dispatched is just inverted.
  - bityard 4y ago
    Seems like this wouldn't work as well in situations where you care a lot about latency or resource utilization. If the workers are polling the LB every n ms, then that's an average of n / 2 ms added to _every_ request. Plus additional CPU cycles and network traffic on both ends due to the polling mechanism.
    - danielheath 3y ago
      If you care about that, having requests queue on a worker that’s already busy (while another worker is idle) is currently the most widely used alternative.
    - martin_ 4y ago
      couldn’t the workers longpoll vs interval based?
    - mst 3y ago
      High volume low latency message queueing is already a problem people have had and implemented solutions for that (for their use case) cost little enough in terms of latency that the advantages were well worth it. Also there's no reason to poll the LB/queue/etc., you just tell it "I'm ready" and it sends you something to handle when it's got something. Pull/push here is about who decides when a server is ready to receive another request. So ... I'm not an expert on actually implementing it, but I've seen systems in practice that -were- in such situations and it worked out extremely well.
eximius 4y ago
This is a fascinating blind spot I didn't know I had! Difficult to do much with as so many request/response load balancing software is inherently push based, but it's a great eye opener.
- adql 3y ago
  It's not difficult. loadbalancer knows how many requests are in-flight to server. The OP is plainly wrong. That's why leastconn works in the first place. And leastconn is almost always one you want. It's almost magical. GC stall on one server ? That means it isn't processing, which means every new request will go to other servers. One server processing 2x as fast as the other ? Well, it keeps its connection count low, so it gets more of them
  - CrimsonRain 3y ago
    What if a server has most of its request processing io blocked? It can process more requests because it has empty CPU RAM but load balancer will think the server is fully booked.
bombela 4y ago
The pull model, is similar to having some metrics to choose which backend to push to. I believe push/pull are the two faces of the same coin. You might physically initiate a connection one way or the other. You might in abstract push or pull information. Ultimately you are trying build an oracle that predicts the future.
p4l4g4 4y ago
I like the idea. I guess you could do something with pubsub to simulate this model. A regular http stack (load balancer and reverse proxies in front of some http framework) would probably need major modifications to work. It would be great if such a mechanism was part of the http standard, so you could easily connect compliant tools.
- capableweb 4y ago
  > It would be great if such a mechanism was part of the http standard, so you could easily connect compliant tools. Not sure HTTP is the best approach to the suggested method. Since you control both ends, there are surely better protocols to use, like QUIC or something similar (or just straight up UDP).
- hinkley 4y ago
  You can get a lot of traction with long polling. I use that in a couple of places where we talk to Consul to avoid a lot of polling nonsense. If I could figure out one last spot (where it's buried behind a service call due to separation of concerns), I could remove a lot of the remaining jitter from a rendezvous algorithm (tell me when all servers have made a change)
jedberg 4y ago
Leastconn is basically a pull model. The server sends the TCP close to the load balancer, which is its way of saying "I'm done with that request and I'm ready for the next one". It's essentially pulling the next connection from the LB.
- AYBABTME 4y ago
  Yes but only if connections aren't reused.
  - hinkley 4y ago
    I keep having to turn off keepalive between the service and the reverse proxies and I bet this is part of why. I think Node 12 introduced LIFO queuing for connection pools because they found the cost of silent disconnects from the server to be too high. They got much better histograms by using the most recently freed connection instead of round robin of available sockets.
    - mst 3y ago
      I don't remember the URL (sorry) but I saw something recently talking about Facebook's queueing approach for requests being FIFO under normal load and LIFO when overloaded, so that under an overload state you serve the number of requests you -can- serve reasonably quickly rather than -everything- timing out. For node's situation that sounds probably workable but I think a lot of the time I'd prefer to send periodic keepalives to the idle pool connections. However, you can't exactly bake -that- into the runtime so I can see their argument and perhaps the best thing would be "both, plus periodically do a clean shutdown on excess pool members until you need them again."
      - hinkley 3y ago
        SYN Flooding is solved by holding a lottery and dropping a certain fraction of all traffic, rather than looking for patterns that could be gamed.
- 4y ago
mlhpdx 3y ago
Indeed, and not only with HTTP. Stateless UDP protocols are the poster child for bad load balancing as a result of technology “tricking down” from HTTP. Push makes even more sense for those protocols.
majormajor 3y ago
This seems like it would be more resource demanding on the load balancer to manage that queue? If that's a single queue it's global state... if you partition it, well, that's just push-based load balancing moved inside your "outer" load balancer? The latency of round-tripping "finished a request, give me another" is probably also best-case ever so slightly worse than "finished one of my requests, loading the next from the buffer" (the HTTP load balanced apps I've worked on have had request queues on the workers too (framework-level, usually)). Moreso if you had multiple load balancers involved...
adql 3y ago
> All push load balancing algorithms try to somehow predict how busy downstreams are. They KNOW how busy they are. They are the ones tracking and forwarding connections to them. That's why leastconn works in the first palce But, for example HAProxy have option to directly back-feed weights via healthchecks from app, so there is an option for app to signal back-pressure in RR balancing
- philsnow 3y ago
  > They KNOW how busy they are. They are the ones tracking and forwarding connections to them. Well, they do when they're the only ones sending work to the workers. The article uses a literal black box for the load balancer, but there are workloads that are too heavy for a single machine, so in those cases (and others, like HA) you have to have a pool of load balancers. You can try to make those load balancers know everything about what's happening in the whole system but it can be hard and expensive. Or, you can have them operate on less-than-perfect knowledge. This is what the round-robin strategy does, and just like round-robin, has its tradeoffs (much simpler, worse 95%ile latency). All of this is assuming the load balancers and workers servicing connections are the only things running on those machines. In real world usage there can often be other loads on the same hardware, belonging to tenants your team doesn't even have a relationship with, which can complicate things quite a bit.
- SteveNuts 3y ago
  That’s interesting I haven’t heard of this in HAproxy. I’ve seen that it has a static weight for how many requests to send to a backend in the config file, what’s this functionality called for dynamic weights? And how do you expose that?

wmf 4y ago

For most protocols like HTTP there's no software to do this and it's not worth developing something nonstandard.

blipvert 4y ago
Should be something that could quite easily be added to a uWSGI subscription router - subscribing node periodically says “I have N slots available” and the router keeps track of how many requests are in flight.

orthecreedence 4y ago

The pull model works beautifully for background work queues. For load balancing it seems it would take a bit of re-plumbing on the expectations of request/response. How would you envision this working with something like HTTP? It seems it would reverse the direction, which would be interesting.

AYBABTME 4y ago
Very similar to background queues but the load balancer holds the request and dispatches it to a waiting worker, or waits until someone comes to serve it. While the worker handles the request, the load balancer proxies. The request serving is the same, the way the work is dispatched is just inverted.
- bityard 4y ago
  Seems like this wouldn't work as well in situations where you care a lot about latency or resource utilization. If the workers are polling the LB every n ms, then that's an average of n / 2 ms added to _every_ request. Plus additional CPU cycles and network traffic on both ends due to the polling mechanism.
  - danielheath 3y ago
    If you care about that, having requests queue on a worker that’s already busy (while another worker is idle) is currently the most widely used alternative.
  - martin_ 4y ago
    couldn’t the workers longpoll vs interval based?
  - mst 3y ago
    High volume low latency message queueing is already a problem people have had and implemented solutions for that (for their use case) cost little enough in terms of latency that the advantages were well worth it. Also there's no reason to poll the LB/queue/etc., you just tell it "I'm ready" and it sends you something to handle when it's got something. Pull/push here is about who decides when a server is ready to receive another request. So ... I'm not an expert on actually implementing it, but I've seen systems in practice that -were- in such situations and it worked out extremely well.

eximius 4y ago

This is a fascinating blind spot I didn't know I had! Difficult to do much with as so many request/response load balancing software is inherently push based, but it's a great eye opener.

adql 3y ago
It's not difficult. loadbalancer knows how many requests are in-flight to server. The OP is plainly wrong. That's why leastconn works in the first place. And leastconn is almost always one you want. It's almost magical. GC stall on one server ? That means it isn't processing, which means every new request will go to other servers. One server processing 2x as fast as the other ? Well, it keeps its connection count low, so it gets more of them
- CrimsonRain 3y ago
  What if a server has most of its request processing io blocked? It can process more requests because it has empty CPU RAM but load balancer will think the server is fully booked.

bombela 4y ago

The pull model, is similar to having some metrics to choose which backend to push to. I believe push/pull are the two faces of the same coin. You might physically initiate a connection one way or the other. You might in abstract push or pull information. Ultimately you are trying build an oracle that predicts the future.

p4l4g4 4y ago

I like the idea. I guess you could do something with pubsub to simulate this model. A regular http stack (load balancer and reverse proxies in front of some http framework) would probably need major modifications to work. It would be great if such a mechanism was part of the http standard, so you could easily connect compliant tools.

capableweb 4y ago
> It would be great if such a mechanism was part of the http standard, so you could easily connect compliant tools. Not sure HTTP is the best approach to the suggested method. Since you control both ends, there are surely better protocols to use, like QUIC or something similar (or just straight up UDP).
hinkley 4y ago
You can get a lot of traction with long polling. I use that in a couple of places where we talk to Consul to avoid a lot of polling nonsense. If I could figure out one last spot (where it's buried behind a service call due to separation of concerns), I could remove a lot of the remaining jitter from a rendezvous algorithm (tell me when all servers have made a change)

jedberg 4y ago

Leastconn is basically a pull model. The server sends the TCP close to the load balancer, which is its way of saying "I'm done with that request and I'm ready for the next one". It's essentially pulling the next connection from the LB.

AYBABTME 4y ago
Yes but only if connections aren't reused.
- hinkley 4y ago
  I keep having to turn off keepalive between the service and the reverse proxies and I bet this is part of why. I think Node 12 introduced LIFO queuing for connection pools because they found the cost of silent disconnects from the server to be too high. They got much better histograms by using the most recently freed connection instead of round robin of available sockets.
  - mst 3y ago
    I don't remember the URL (sorry) but I saw something recently talking about Facebook's queueing approach for requests being FIFO under normal load and LIFO when overloaded, so that under an overload state you serve the number of requests you -can- serve reasonably quickly rather than -everything- timing out. For node's situation that sounds probably workable but I think a lot of the time I'd prefer to send periodic keepalives to the idle pool connections. However, you can't exactly bake -that- into the runtime so I can see their argument and perhaps the best thing would be "both, plus periodically do a clean shutdown on excess pool members until you need them again."
    - hinkley 3y ago
      SYN Flooding is solved by holding a lottery and dropping a certain fraction of all traffic, rather than looking for patterns that could be gamed.
4y ago

mlhpdx 3y ago

Indeed, and not only with HTTP. Stateless UDP protocols are the poster child for bad load balancing as a result of technology “tricking down” from HTTP. Push makes even more sense for those protocols.

majormajor 3y ago

This seems like it would be more resource demanding on the load balancer to manage that queue? If that's a single queue it's global state... if you partition it, well, that's just push-based load balancing moved inside your "outer" load balancer? The latency of round-tripping "finished a request, give me another" is probably also best-case ever so slightly worse than "finished one of my requests, loading the next from the buffer" (the HTTP load balanced apps I've worked on have had request queues on the workers too (framework-level, usually)). Moreso if you had multiple load balancers involved...

adql 3y ago

> All push load balancing algorithms try to somehow predict how busy downstreams are. They KNOW how busy they are. They are the ones tracking and forwarding connections to them. That's why leastconn works in the first palce But, for example HAProxy have option to directly back-feed weights via healthchecks from app, so there is an option for app to signal back-pressure in RR balancing

philsnow 3y ago
> They KNOW how busy they are. They are the ones tracking and forwarding connections to them. Well, they do when they're the only ones sending work to the workers. The article uses a literal black box for the load balancer, but there are workloads that are too heavy for a single machine, so in those cases (and others, like HA) you have to have a pool of load balancers. You can try to make those load balancers know everything about what's happening in the whole system but it can be hard and expensive. Or, you can have them operate on less-than-perfect knowledge. This is what the round-robin strategy does, and just like round-robin, has its tradeoffs (much simpler, worse 95%ile latency). All of this is assuming the load balancers and workers servicing connections are the only things running on those machines. In real world usage there can often be other loads on the same hardware, belonging to tenants your team doesn't even have a relationship with, which can complicate things quite a bit.
SteveNuts 3y ago
That’s interesting I haven’t heard of this in HAproxy. I’ve seen that it has a static weight for how many requests to send to a backend in the config file, what’s this functionality called for dynamic weights? And how do you expose that?