9 ms·

Load Balancing: The Intuition Behind the Power of Two Random Choices

116 points by fagnerbrack 3y ago

codetrotter 3y ago
This is excellent! A prime example of what real engineering work can look like in the field of “software engineering”. I wish we saw more posts sharing this kind of knowledge.
digaozao 3y ago
I liked the approach. I did not know it. But what are the advantages against taking the least occupied server/bin always? I have seen good improvements with nginx load balancing when changing its configuration to least_conn, that chooses the server with least connections.
- dtjohnnymonkey 3y ago
  It’s more costly to determine the server with absolute least connections since you have to keep track of the ordering of the servers by how many connections they have.
- magicalhippo 3y ago
  Not my field but I'm guessing when you have thousands of servers it can be quite the overhead to keeping track of the load of each one for each request. The proposed algorithm only needs to consider two, and from what I can gather should work in parallel with multiple load balancers without coordination.
- andromeduck 3y ago
  O(log n) vs O(1)
  - ryanschaefer 3y ago
    Is there a way to keep a list with changing values sorted in real time in order to use a log n search algorithm?
    - andromeduck 3y ago
      It's log n either way.
    - throw_pm23 3y ago
      Yes, a binary search tree that is dynamically balanced, for example red-black or avl.
- Terretta 3y ago
  > what are the advantages against taking the least occupied server/bin always The other answers are saying for algo reasons. Sure, but, pick two is even more better for uptime reasons. In serving at scale, quite often the "least occupied" server of all of them is one with an error causing it to have least load/connections/whatever. By starting with a random two, you pick among probably healthy servers, and then the least load. > good improvements with nginx load balancing when changing its configuration to least_conn, that chooses the server with least connections. nginx doesn't know why your app is failing to keep connections open long enough to serve them, least_conn between two random results in far fewer 100% "outages" when a single box or subset of boxes among 10s or 1000s is bad.
  - semi 3y ago
    Wouldn't that be better solved with health checking and removing the poor performing server from the pool?
- ryanschaefer 3y ago
  In large enough systems, it becomes prohibitively expensive to keep consensus of the state of all members. Sure with 10 or so hosts it’s trivial to select the least busy one but at the scale of 1000s of hosts you begin to run into a ton overhead just to decide where to forward a request. As many others have said, O(N) for each request vs O(1) while avoiding hot spots.
- mjb 3y ago
  See my reply here: https://news.ycombinator.com/item?id=37175685 https://news.ycombinator.com/item?id=37175685 Short version: it's robust to staleness and concurrency, which is important in distributed settings ("find the best" is hard to do when "best" is a moving target).
magicalhippo 3y ago
Maybe I misunderstood something, I admit I glossed over parts of the article, but the explanations seemed a bit over-complicated. In the balls and bucket scenario, ideally you'd want to scan all the buckets and put the ball in the least filled one. By picking two random buckets and putting the ball in the least filled of the two, you approximate the ideal algorithm. The chance of picking two relatively filled buckets is inversely proportional to how "bad" it is. If there are just two buckets which have more balls than the others then it's relatively bad to pick those two, but chances are low. And vice versa. Still, hadn't thought about this before, interesting trick indeed!
- potamic 3y ago
  They talked about doing this for AWS lambda at "gigantic scale". I assume at some point scanning all the buckets becomes infeasible.
- movpasd 3y ago
  I think it comes down to complexity. Scanning is O(N) where N is the number of buckets, two random choices is O(1) (if bucket lookup is O(1), e.g. a hash map).
  - magicalhippo 3y ago
    Yes exactly. You approximate the full algorithm while not paying the overhead.
- xvector 3y ago
  Do you have to pick two random buckets or just one random bucket and one adjacent bucket? Feels like picking an adjacent bucket would work just as well and increase locality.
  - magicalhippo 3y ago
    I was thinking about that, but I haven't had time to really dig into it. My gut feeling is that it won't be sufficient, but it might be a bad hunch.
andromeduck 3y ago
Easier to think of it as a form of cuckoo hashing. https://en.m.wikipedia.org/wiki/Cuckoo_hashing https://en.m.wikipedia.org/wiki/Cuckoo_hashing
trabant00 3y ago
I do not understand why they chose random assignment as a base line instead of round robin which is really the simplest common load balancing algorithm.
- phrotoma 3y ago
  I suspect it’s because random assignment is simpler to implement than incremental round robin when the targets are moving rapidly (eg. pods coming and going in K8s). If you are iterating over N replicas in true round-robin fashion and the nth+1 replica comes online, you need to manage inserting it into your rotation to maintain true incremental round robin. To do it probabilistically you just update your weights. This is how kube-proxy sets up iptables based load balancing.
- mabbo 3y ago
  Round robin is hard when you're doing things concurrently and distributed, because state is hard. A server is taking requests 30 at a time in separate threads. To add a sequential step for picking which target is next, you need to add a synchronous piece of code that all of the threads depend on- a bottleneck. That's doable, but it adds complexity. And then you have (let's say) 30 servers making calls. Do they each use round robin load balancing separately, or do they try to coordinate? That's difficult. "Pick two randomly" requires no state. Every thread and server can run the same algorithm without regard for each other.
  - haimez 3y ago
    > "Pick two randomly" requires no state. Every thread and server can run the same algorithm without regard for each other. That’s not quite true. Picking between two “buckets” still requires knowing how many “balls” are in each which is state. That state can be local to each server or global, that state can be accessed concurrently or synchronously, but you still have the same problem to solve.
    - kuchenbecker 3y ago
      In addition, there is a physical machine somewhere that has all the actual data and it's costly to move. The machine you're connecting to can get taken down by a noisy neighbor and rebalancing data is expensive.
sh1mmer 3y ago
I think this was a nice article and helped walk through some of the maybe unintuitive maths but I feel like they missed the meat a bit. With random placement, as was said in the article, each flip is independent. With PoTRC it’s using knowledge of current queue depth. The author didn’t explain the challenges around tracking queue depth, or why PoTRC is better than say keeping an ordered list of queues depth and picking the smallest one. I’m assuming the trade off is about cost of managing the sorted list of queues depths vs just O(1) look ups of the random nodes’ depths. It just would’ve been nice to cover that in the article.
- kuchenbecker 3y ago
  The beauty is it doesn't need to be particularly for the technique to work.
cdstamper 3y ago
What's wrong with consistent hashing (hash requests and servers into a single coordinate space eg an array, randomly distributed, scan forward from the request until you find a server)? https://en.wikipedia.org/wiki/Consistent_hashing https://en.wikipedia.org/wiki/Consistent_hashing
- dastbe 3y ago
  consistent hashing requires a bunch of additional memory to solve load variance. there's a nice equation to calculate this somewhere that I'd have to search for, but roughly you need 100 virtual slots in your coordinate space per every destination server to reduce standard deviation to about 10%, and 1000 virtual slots to reduce it to less than 5%. There's some alternative hashing solutions (rendezvous hash, jump hash, maglev) that improve load distribution without the memory overhead, but still have similar challenges with node addition/removal overhead. Also, integrating state into any of these solutions is incredibly difficult and really antithetical to their point (being deterministic). This is fine when you're assigning uniform workloads and preferred when these assignments need to be long-lived, but for request load balancing you're dealing with uneven workloads and short-lived assignments. This is where power of two load balancing shines, as it allows you to perform stateful load balancing (using queued requests, cpu utilizations, host perf) efficiently with low memory overhead and minimal effort to add/remove nodes. And if you lose a node with state its no big deal because the lifetime of a request is so short.
mnutt 3y ago
It reminds me of the method redis used for evicting keys: it would randomly choose N keys and evict the oldest of the set. It approximated evicting the oldest key in the database (more or less, depending on your value of N) but was cheaper than keeping track of the oldest keys. And it needed to be cheap because when the database filled up it happened a whole lot.

116 points by fagnerbrack 3y ago

This is excellent! A prime example of what real engineering work can look like in the field of “software engineering”. I wish we saw more posts sharing this kind of knowledge.

digaozao 3y ago

I liked the approach. I did not know it. But what are the advantages against taking the least occupied server/bin always? I have seen good improvements with nginx load balancing when changing its configuration to least_conn, that chooses the server with least connections.

dtjohnnymonkey 3y ago
It’s more costly to determine the server with absolute least connections since you have to keep track of the ordering of the servers by how many connections they have.
magicalhippo 3y ago
Not my field but I'm guessing when you have thousands of servers it can be quite the overhead to keeping track of the load of each one for each request. The proposed algorithm only needs to consider two, and from what I can gather should work in parallel with multiple load balancers without coordination.
andromeduck 3y ago
O(log n) vs O(1)
- ryanschaefer 3y ago
  Is there a way to keep a list with changing values sorted in real time in order to use a log n search algorithm?
  - andromeduck 3y ago
    It's log n either way.
  - throw_pm23 3y ago
    Yes, a binary search tree that is dynamically balanced, for example red-black or avl.
Terretta 3y ago
> what are the advantages against taking the least occupied server/bin always The other answers are saying for algo reasons. Sure, but, pick two is even more better for uptime reasons. In serving at scale, quite often the "least occupied" server of all of them is one with an error causing it to have least load/connections/whatever. By starting with a random two, you pick among probably healthy servers, and then the least load. > good improvements with nginx load balancing when changing its configuration to least_conn, that chooses the server with least connections. nginx doesn't know why your app is failing to keep connections open long enough to serve them, least_conn between two random results in far fewer 100% "outages" when a single box or subset of boxes among 10s or 1000s is bad.
- semi 3y ago
  Wouldn't that be better solved with health checking and removing the poor performing server from the pool?
ryanschaefer 3y ago
In large enough systems, it becomes prohibitively expensive to keep consensus of the state of all members. Sure with 10 or so hosts it’s trivial to select the least busy one but at the scale of 1000s of hosts you begin to run into a ton overhead just to decide where to forward a request. As many others have said, O(N) for each request vs O(1) while avoiding hot spots.
mjb 3y ago
See my reply here: https://news.ycombinator.com/item?id=37175685 https://news.ycombinator.com/item?id=37175685 Short version: it's robust to staleness and concurrency, which is important in distributed settings ("find the best" is hard to do when "best" is a moving target).

magicalhippo 3y ago

Maybe I misunderstood something, I admit I glossed over parts of the article, but the explanations seemed a bit over-complicated. In the balls and bucket scenario, ideally you'd want to scan all the buckets and put the ball in the least filled one. By picking two random buckets and putting the ball in the least filled of the two, you approximate the ideal algorithm. The chance of picking two relatively filled buckets is inversely proportional to how "bad" it is. If there are just two buckets which have more balls than the others then it's relatively bad to pick those two, but chances are low. And vice versa. Still, hadn't thought about this before, interesting trick indeed!

potamic 3y ago
They talked about doing this for AWS lambda at "gigantic scale". I assume at some point scanning all the buckets becomes infeasible.
movpasd 3y ago
I think it comes down to complexity. Scanning is O(N) where N is the number of buckets, two random choices is O(1) (if bucket lookup is O(1), e.g. a hash map).
- magicalhippo 3y ago
  Yes exactly. You approximate the full algorithm while not paying the overhead.
xvector 3y ago
Do you have to pick two random buckets or just one random bucket and one adjacent bucket? Feels like picking an adjacent bucket would work just as well and increase locality.
- magicalhippo 3y ago
  I was thinking about that, but I haven't had time to really dig into it. My gut feeling is that it won't be sufficient, but it might be a bad hunch.

andromeduck 3y ago

Easier to think of it as a form of cuckoo hashing. https://en.m.wikipedia.org/wiki/Cuckoo_hashing https://en.m.wikipedia.org/wiki/Cuckoo_hashing

trabant00 3y ago

I do not understand why they chose random assignment as a base line instead of round robin which is really the simplest common load balancing algorithm.

phrotoma 3y ago
I suspect it’s because random assignment is simpler to implement than incremental round robin when the targets are moving rapidly (eg. pods coming and going in K8s). If you are iterating over N replicas in true round-robin fashion and the nth+1 replica comes online, you need to manage inserting it into your rotation to maintain true incremental round robin. To do it probabilistically you just update your weights. This is how kube-proxy sets up iptables based load balancing.
mabbo 3y ago
Round robin is hard when you're doing things concurrently and distributed, because state is hard. A server is taking requests 30 at a time in separate threads. To add a sequential step for picking which target is next, you need to add a synchronous piece of code that all of the threads depend on- a bottleneck. That's doable, but it adds complexity. And then you have (let's say) 30 servers making calls. Do they each use round robin load balancing separately, or do they try to coordinate? That's difficult. "Pick two randomly" requires no state. Every thread and server can run the same algorithm without regard for each other.
- haimez 3y ago
  > "Pick two randomly" requires no state. Every thread and server can run the same algorithm without regard for each other. That’s not quite true. Picking between two “buckets” still requires knowing how many “balls” are in each which is state. That state can be local to each server or global, that state can be accessed concurrently or synchronously, but you still have the same problem to solve.
  - kuchenbecker 3y ago
    In addition, there is a physical machine somewhere that has all the actual data and it's costly to move. The machine you're connecting to can get taken down by a noisy neighbor and rebalancing data is expensive.

sh1mmer 3y ago

I think this was a nice article and helped walk through some of the maybe unintuitive maths but I feel like they missed the meat a bit. With random placement, as was said in the article, each flip is independent. With PoTRC it’s using knowledge of current queue depth. The author didn’t explain the challenges around tracking queue depth, or why PoTRC is better than say keeping an ordered list of queues depth and picking the smallest one. I’m assuming the trade off is about cost of managing the sorted list of queues depths vs just O(1) look ups of the random nodes’ depths. It just would’ve been nice to cover that in the article.

kuchenbecker 3y ago
The beauty is it doesn't need to be particularly for the technique to work.

cdstamper 3y ago

What's wrong with consistent hashing (hash requests and servers into a single coordinate space eg an array, randomly distributed, scan forward from the request until you find a server)? https://en.wikipedia.org/wiki/Consistent_hashing https://en.wikipedia.org/wiki/Consistent_hashing

dastbe 3y ago
consistent hashing requires a bunch of additional memory to solve load variance. there's a nice equation to calculate this somewhere that I'd have to search for, but roughly you need 100 virtual slots in your coordinate space per every destination server to reduce standard deviation to about 10%, and 1000 virtual slots to reduce it to less than 5%. There's some alternative hashing solutions (rendezvous hash, jump hash, maglev) that improve load distribution without the memory overhead, but still have similar challenges with node addition/removal overhead. Also, integrating state into any of these solutions is incredibly difficult and really antithetical to their point (being deterministic). This is fine when you're assigning uniform workloads and preferred when these assignments need to be long-lived, but for request load balancing you're dealing with uneven workloads and short-lived assignments. This is where power of two load balancing shines, as it allows you to perform stateful load balancing (using queued requests, cpu utilizations, host perf) efficiently with low memory overhead and minimal effort to add/remove nodes. And if you lose a node with state its no big deal because the lifetime of a request is so short.

mnutt 3y ago

It reminds me of the method redis used for evicting keys: it would randomly choose N keys and evict the oldest of the set. It approximated evicting the oldest key in the database (more or less, depending on your value of N) but was cheaper than keeping track of the oldest keys. And it needed to be cheap because when the database filled up it happened a whole lot.