10 ms·

When Simple Wins: Power of 2 Load Balancing

140 points by mattdennewitz 9y ago

euph0ria 9y ago
Regarding the math section, could someone please describe it like you were talking to a 5 year old? 1) Θ( log n = log / log n ) 2) Θ(log log n)
- rawnlq 9y ago
  1) Throw n balls into n bins, the bin for each ball chosen randomly 2) Throw n balls into n bins, two bin for each ball chosen randomly, always picking the bin with fewer balls in it In both cases you will have n balls distributed over n bins in the end. But the number of balls in the largest bin will be different for the two processes above. In the first case the largest bin has more balls: O(log n / log log n) == O(log n). And the second case has just O(log log n) balls. So just adding an extra choice of bins made the expected largest bin exponentially smaller. More rough intuition: if x of your bins are occupied, in the first case your next ball has x/n probability of queueing instead of finding an empty bin but in the second it's only (x/n)^2 chance to need to queue.
  - matahwoosh 9y ago
    Generally, yes, but I think `O(log n / log log n) == O(log n)` is wrong. log(n) / log(log(n)) = logx(n) (where x = log(n), wasn't sure how to describe logarithm base in a better way). So you get O(logx(n)). In general the logarithm base doesn't matter for Big-O when it's a constant, but I'm not sure you can apply the same thing to a base of log(n).
  - adrianratnapala 9y ago
    So that means the expectation value of the maximum scales as O(log n / log log n)?
- alxv 9y ago
  There is a proof shown in this handout: https://people.eecs.berkeley.edu/~sinclair/cs271/n15.pdf https://people.eecs.berkeley.edu/~sinclair/cs271/n15.pdf It's hard to understand why this technique works so well without digging deep in the math. Roughly speaking, if you throw n balls in n bins at random, the maximum of number balls in any bins will grow surprisingly quickly (because of the birthday paradox). However, if we allow ourselves to choose between two random bins instead of one, and put the ball in the one with the fewest balls in it, the maximum number of balls in any bins grow much more slowly (i.e., O(ln ln n)). Hence, having that one extra random choice allows us to get surprisingly close to the optimal approach of comparing all bins (which would give us O(1)), without doing all that work.
  - MichaelGG 9y ago
    Thanks for the explanation! Much clearer and I get the concept. In the case of load balancing, we'd need a ton of servers (1000s?) for this to pay off vs just comparing all, right? Cache updating aside, most of the overhead would be in reading the load numbers in. Comparing a thousand numbers has to be quick in comparison, no?
    - mrkurt 9y ago
      The problem with load balancing is herd behavior. Stats for load are usually at least a little stale, because it's a distributed system where you can't afford to wait for consistency. When there are traffic spikes a whole herd of new connections will go to the least loaded server for a window of time where the cached "load" number is out of date. Picking two at random helps keep from a bunch of connections racing to one server, even when you're only running 3-4 of them.
  - nickpsecurity 9y ago
    That's a really intuitive explanation. Appreciate that.
  - euph0ria 9y ago
    Thank you sir!
- deleted 9y ago
  [deleted]
- matahwoosh 9y ago
  small correction, it's Θ( log n / log log n ). I noticed though, when I copied the formula from the original paper, this what I got, too ;)
throwaway13337 9y ago
The simplest load balancing I've done is modulo the user ID by the number of servers then point at that server. This solves caching too since you are only ever receiving and caching user data on a single server. No cache communication required. You can enforce it on the server side for security as well. Doesn't require a load balance server - just an extra line of code. Keep it simple.
- kornish 9y ago
  This is how many horizontally scalable OLTP databases operate too (e.g. DynamoDB, Citus): picking a partition key, then deterministically routing work associated with that partition key to the proper, well, partition.
- kinkrtyavimoodh 9y ago
  But where is the modulo being calculated?
  - toomuchtodo 9y ago
    [removed, brain failure]
    - lordvarys 9y ago
      In the original comment, user mentions that the modulo logic would not require a loadbalancer server. So, I would assume what the user meant is that you do not require a high throughput loadbalancer. But you still need some entity to do the modulo work as well as health-checking servers to calculate modulo for active servers only.
- alxv 9y ago
  What happens when the number of servers changes? The cache hit rate would likely drop to zero until it warms up again, which is a good way to accidentally overload your systems. Load balancing based on consistent hashing is the better way to implement this.
gopalv 9y ago
"Power of 2 Random Choices" ... has nothing to do with the "Power of 2" directly. I like 2Choice because it is not dependent on hash function design & is temporal, but I have a positive aversion to the 2^n hash distributions when it comes to data, specifically for distributed systems which need to flex up/down [1]. [1] - http://notmysock.org/blog/hacks/1440 http://notmysock.org/blog/hacks/1440
deleted 9y ago
[deleted]
alxv 9y ago
The method is called "Power of Two Random Choices" (http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...). And the two-choices paradigm is widely applicable beyond load balancing. In particular, it applies to hash table design (e.g. cuckoo hashing) and cache eviction schemes (https://danluu.com/2choices-eviction/ https://danluu.com/2choices-eviction/).
- mrkurt 9y ago
  You're right, I updated the title. Got a little too clever with the whole "power" thing.
- adrianN 9y ago
  It also works for solving SAT. Try two literals and recurse on the one that can be made to satisfy more clauses.
- naiveattack 9y ago
  "while each additional choice beyond two decreases the maximum load by only a constant factor" Mathemagical!
adrianratnapala 9y ago
Can someone expand on the maths that the OP elided? What is the thing that comes out to O(log n / log log n)?
zubspace 9y ago
I'm not an expert in this field, but an engineer of vimeo went into detail, why this approach did not work for them. [1] Problem with consistent hashing: However, consistent hashing comes with its own problem: uneven distribution of requests. Because of its mathematical properties, consistent hashing only balances loads about as well as choosing a random server for each request, when the distribution of requests is equal. But if some content is much more popular than others (as usual for the internet), it can be worse than that. Problem with Power of 2 Load Balancing: Why wasn’t there a way to say “use consistent hashing, but please don’t overload any servers”? As early as August 2015, I had tried to come up with an algorithm based on the power of two random choices that would do just that, but a bit of simulation said that it didn’t work. Too many requests were sent to non-ideal servers to be worthwhile. Instead, he used something called Consistent Hashing with Bounded Loads. [1] https://medium.com/vimeo-engineering-blog/improving-load-balancing-with-a-new-consistent-hashing-algorithm-9f1bd75709ed https://medium.com/vimeo-engineering-blog/improving-load-bal...
- maffydub 9y ago
  It looks as though the approach proposed in the article is random, rather than attempting to use consistent hashing (as Vimeo investigated) - that may be why the results the Vimeo engineers found are worse than those the artcile suggests?
- user5994461 9y ago
  They are different algorithm for different purpose. Consistent hashing is used to always attach a request to the same host. It's the opposite of load balancing. Load balancing algorithms (least connection, business, etc...) are used to distribute requests across servers as well as possible to maximize performances.
  - pas 9y ago
    Usually both properties are desirable .. up to a point. You want to minimize load on all servers, but you also want to pack things up efficiently (so minimize operational costs), but of course you want the benefits of caching, so you want requests from a sessions to land on the same node/server/box. Basically a multi-dimensional optimization problem. Completely solvable with constraints. Let the business people decide what's more important, latency or throughput or low cost of operations.
prashantswain 9y ago
If you seek legitimate hacking service ,contact hdmoore.hacks@gmail.com ...dude's a cyber guru, involved with cloning phones, hacked into my ex's gmail and facbook, what let me knowing she was infidel and also gave my nephew some really outstanding school scores which he upgraded himself, cool way to have financial freedom as well. Get your bank blank atm cards which could debit money from any a.t.m machine. Make $20,000 and more in a couple days. Bank transfers and wire transfers as well as Paypal jobs, hes that good, had to make him my personal hacker. You could mail him as well if you got issues, he's as discreet and professional too. He's kinda picky though so make mention of the reference
scame 9y ago
I've seen a paper doing the same thing directly at the network layer using IPv6 extension headers: http://www.thomasclausen.net/wp-content/uploads/2017/06/2017-ICDCS-SRLB-The-Power-of-Choices-in-Load-Balancing-with-Segment-Routing.pdf http://www.thomasclausen.net/wp-content/uploads/2017/06/2017...

140 points by mattdennewitz 9y ago

Regarding the math section, could someone please describe it like you were talking to a 5 year old? 1) Θ( log n = log / log n ) 2) Θ(log log n)

rawnlq 9y ago
1) Throw n balls into n bins, the bin for each ball chosen randomly 2) Throw n balls into n bins, two bin for each ball chosen randomly, always picking the bin with fewer balls in it In both cases you will have n balls distributed over n bins in the end. But the number of balls in the largest bin will be different for the two processes above. In the first case the largest bin has more balls: O(log n / log log n) == O(log n). And the second case has just O(log log n) balls. So just adding an extra choice of bins made the expected largest bin exponentially smaller. More rough intuition: if x of your bins are occupied, in the first case your next ball has x/n probability of queueing instead of finding an empty bin but in the second it's only (x/n)^2 chance to need to queue.
- matahwoosh 9y ago
  Generally, yes, but I think `O(log n / log log n) == O(log n)` is wrong. log(n) / log(log(n)) = logx(n) (where x = log(n), wasn't sure how to describe logarithm base in a better way). So you get O(logx(n)). In general the logarithm base doesn't matter for Big-O when it's a constant, but I'm not sure you can apply the same thing to a base of log(n).
- adrianratnapala 9y ago
  So that means the expectation value of the maximum scales as O(log n / log log n)?
alxv 9y ago
There is a proof shown in this handout: https://people.eecs.berkeley.edu/~sinclair/cs271/n15.pdf https://people.eecs.berkeley.edu/~sinclair/cs271/n15.pdf It's hard to understand why this technique works so well without digging deep in the math. Roughly speaking, if you throw n balls in n bins at random, the maximum of number balls in any bins will grow surprisingly quickly (because of the birthday paradox). However, if we allow ourselves to choose between two random bins instead of one, and put the ball in the one with the fewest balls in it, the maximum number of balls in any bins grow much more slowly (i.e., O(ln ln n)). Hence, having that one extra random choice allows us to get surprisingly close to the optimal approach of comparing all bins (which would give us O(1)), without doing all that work.
- MichaelGG 9y ago
  Thanks for the explanation! Much clearer and I get the concept. In the case of load balancing, we'd need a ton of servers (1000s?) for this to pay off vs just comparing all, right? Cache updating aside, most of the overhead would be in reading the load numbers in. Comparing a thousand numbers has to be quick in comparison, no?
  - mrkurt 9y ago
    The problem with load balancing is herd behavior. Stats for load are usually at least a little stale, because it's a distributed system where you can't afford to wait for consistency. When there are traffic spikes a whole herd of new connections will go to the least loaded server for a window of time where the cached "load" number is out of date. Picking two at random helps keep from a bunch of connections racing to one server, even when you're only running 3-4 of them.
- nickpsecurity 9y ago
  That's a really intuitive explanation. Appreciate that.
- euph0ria 9y ago
  Thank you sir!
deleted 9y ago
[deleted]
matahwoosh 9y ago
small correction, it's Θ( log n / log log n ). I noticed though, when I copied the formula from the original paper, this what I got, too ;)

throwaway13337 9y ago

The simplest load balancing I've done is modulo the user ID by the number of servers then point at that server. This solves caching too since you are only ever receiving and caching user data on a single server. No cache communication required. You can enforce it on the server side for security as well. Doesn't require a load balance server - just an extra line of code. Keep it simple.

kornish 9y ago
This is how many horizontally scalable OLTP databases operate too (e.g. DynamoDB, Citus): picking a partition key, then deterministically routing work associated with that partition key to the proper, well, partition.
kinkrtyavimoodh 9y ago
But where is the modulo being calculated?
- toomuchtodo 9y ago
  [removed, brain failure]
  - lordvarys 9y ago
    In the original comment, user mentions that the modulo logic would not require a loadbalancer server. So, I would assume what the user meant is that you do not require a high throughput loadbalancer. But you still need some entity to do the modulo work as well as health-checking servers to calculate modulo for active servers only.
alxv 9y ago
What happens when the number of servers changes? The cache hit rate would likely drop to zero until it warms up again, which is a good way to accidentally overload your systems. Load balancing based on consistent hashing is the better way to implement this.

gopalv 9y ago

"Power of 2 Random Choices" ... has nothing to do with the "Power of 2" directly. I like 2Choice because it is not dependent on hash function design & is temporal, but I have a positive aversion to the 2^n hash distributions when it comes to data, specifically for distributed systems which need to flex up/down [1]. [1] - http://notmysock.org/blog/hacks/1440 http://notmysock.org/blog/hacks/1440

deleted 9y ago

[deleted]

alxv 9y ago

The method is called "Power of Two Random Choices" (http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...). And the two-choices paradigm is widely applicable beyond load balancing. In particular, it applies to hash table design (e.g. cuckoo hashing) and cache eviction schemes (https://danluu.com/2choices-eviction/ https://danluu.com/2choices-eviction/).

mrkurt 9y ago
You're right, I updated the title. Got a little too clever with the whole "power" thing.
adrianN 9y ago
It also works for solving SAT. Try two literals and recurse on the one that can be made to satisfy more clauses.
naiveattack 9y ago
"while each additional choice beyond two decreases the maximum load by only a constant factor" Mathemagical!

adrianratnapala 9y ago

Can someone expand on the maths that the OP elided? What is the thing that comes out to O(log n / log log n)?

zubspace 9y ago

I'm not an expert in this field, but an engineer of vimeo went into detail, why this approach did not work for them. [1] Problem with consistent hashing: However, consistent hashing comes with its own problem: uneven distribution of requests. Because of its mathematical properties, consistent hashing only balances loads about as well as choosing a random server for each request, when the distribution of requests is equal. But if some content is much more popular than others (as usual for the internet), it can be worse than that. Problem with Power of 2 Load Balancing: Why wasn’t there a way to say “use consistent hashing, but please don’t overload any servers”? As early as August 2015, I had tried to come up with an algorithm based on the power of two random choices that would do just that, but a bit of simulation said that it didn’t work. Too many requests were sent to non-ideal servers to be worthwhile. Instead, he used something called Consistent Hashing with Bounded Loads. [1] https://medium.com/vimeo-engineering-blog/improving-load-balancing-with-a-new-consistent-hashing-algorithm-9f1bd75709ed https://medium.com/vimeo-engineering-blog/improving-load-bal...

maffydub 9y ago
It looks as though the approach proposed in the article is random, rather than attempting to use consistent hashing (as Vimeo investigated) - that may be why the results the Vimeo engineers found are worse than those the artcile suggests?
user5994461 9y ago
They are different algorithm for different purpose. Consistent hashing is used to always attach a request to the same host. It's the opposite of load balancing. Load balancing algorithms (least connection, business, etc...) are used to distribute requests across servers as well as possible to maximize performances.
- pas 9y ago
  Usually both properties are desirable .. up to a point. You want to minimize load on all servers, but you also want to pack things up efficiently (so minimize operational costs), but of course you want the benefits of caching, so you want requests from a sessions to land on the same node/server/box. Basically a multi-dimensional optimization problem. Completely solvable with constraints. Let the business people decide what's more important, latency or throughput or low cost of operations.

prashantswain 9y ago

If you seek legitimate hacking service ,contact hdmoore.hacks@gmail.com ...dude's a cyber guru, involved with cloning phones, hacked into my ex's gmail and facbook, what let me knowing she was infidel and also gave my nephew some really outstanding school scores which he upgraded himself, cool way to have financial freedom as well. Get your bank blank atm cards which could debit money from any a.t.m machine. Make $20,000 and more in a couple days. Bank transfers and wire transfers as well as Paypal jobs, hes that good, had to make him my personal hacker. You could mail him as well if you got issues, he's as discreet and professional too. He's kinda picky though so make mention of the reference

scame 9y ago

I've seen a paper doing the same thing directly at the network layer using IPv6 extension headers: http://www.thomasclausen.net/wp-content/uploads/2017/06/2017-ICDCS-SRLB-The-Power-of-Choices-in-Load-Balancing-with-Segment-Routing.pdf http://www.thomasclausen.net/wp-content/uploads/2017/06/2017...