The method is called "Power of Two Random Choices" (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/).
When Simple Wins: Power of 2 Load Balancing
11–20 of 49 posts
Re: When Simple Wins: Power of 2 Load Balancing
#12Regarding 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)
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.
Re: When Simple Wins: Power of 2 Load Balancing
#13Regarding 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)
There is a proof shown in this handout: 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.
Re: When Simple Wins: Power of 2 Load Balancing
#14The 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.
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.
Consistent hashing is a bit cleaner way to do it, but pretty much the same result as modulo-ing the user id against number of servers. At least as I understand it, you consistently hash something (a user id, a request URL, etc) into N buckets, where N is the number of servers, so changing N re-shuffles all of the buckets anyway.
Short of something like cassandra's ring topology, how would you use consistent hashing add new servers and assign them requests?
Re: When Simple Wins: Power of 2 Load Balancing
#15Regarding 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)
[deleted]
Re: When Simple Wins: Power of 2 Load Balancing
#16Earlier quoted context omitted.
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.
Consistent hashing is a bit cleaner way to do it, but pretty much the same result as modulo-ing the user id against number of servers. At least as I understand it, you consistently hash something (a user id, a request URL, etc) into N buckets, where N is the number of servers, so changing N re-shuffles all of the buckets anyway. Short of something like cassandra's ring topology, how would you use consistent hashing a…
Proper consistent hashing will only move (on average) K/N assignments when going from N to N+1 servers, for K original assignments.
Re: When Simple Wins: Power of 2 Load Balancing
#17Earlier quoted context omitted.
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.
Consistent hashing is a bit cleaner way to do it, but pretty much the same result as modulo-ing the user id against number of servers. At least as I understand it, you consistently hash something (a user id, a request URL, etc) into N buckets, where N is the number of servers, so changing N re-shuffles all of the buckets anyway. Short of something like cassandra's ring topology, how would you use consistent hashing a…
You are missing a crucial piece here to have consistent hashing: you also need hash the names of the servers. With consistent hashing you hash both the names of the requests and of the servers, then you assign the request to the server with closest hash (under the modulus). With this scheme, you only need to remap 1/n of the keys (where n is the number of servers).
Re: When Simple Wins: Power of 2 Load Balancing
#18Regarding 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)
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 ;)
Re: When Simple Wins: Power of 2 Load Balancing
#19Regarding 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)
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…
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).
Re: When Simple Wins: Power of 2 Load Balancing
#20The 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.
User ID is not exactly random material. Might be better to do mod(md5(user_id), server_count) to scatter the bits using MD5.