Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

When Simple Wins: Power of 2 Load Balancing

fly.io

Post reply on HN
Print view View original

21–30 of 49 posts

Re: When Simple Wins: Power of 2 Load Balancing

#21

Post by alexgartrell »

alxv wrote: post #17
mnutt wrote: post #14

Earlier quoted context omitted.

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).

You're kind of right. You can also use something like jump consistent hash [0] which only requires you to have a consistent ordering of the hosts where you're sending the information. We (Facebook) use something similar for our caches. It requires a linear array of hosts but you've already got that if you're load balancing.

[0] https://arxiv.org/abs/1406.2294

Re: When Simple Wins: Power of 2 Load Balancing

#22

Post by mnutt »

alxv wrote: post #17
mnutt wrote: post #14

Earlier quoted context omitted.

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).

That makes a lot of sense, thanks.

Better consistent hashing means that existing servers don't have their caches invalidated, but the new servers that were just added start with empty caches anyway so are fielding all uncached requests. Hopefully the bottleneck is actually with some shared layer behind it (a database or something) otherwise I guess you'd need to come up with a more complex way to slowly distribute more traffic to the new nodes.

Re: When Simple Wins: Power of 2 Load Balancing

#23

Post by MichaelGG »

alxv wrote: post #13
euph0ria wrote: post #2

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)

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 i…

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?

Re: When Simple Wins: Power of 2 Load Balancing

#24

Post by adrianmonk »

throwaway13337 wrote: post #3

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.

Arguably, that's sharding, not load balancing. If you want to get picky with terminology at least.

Anyway, I do have a point beyond being pedantic: this offers two advantages that a fixed sharding scheme doesn't. #1: it doesn't need to identify a piece of data on the request to shard off of. #2: it actively (though imperfectly) attempts to achieve similar utilization on every server.

Re: When Simple Wins: Power of 2 Load Balancing

#25

Post by mrkurt »

MichaelGG wrote: post #23
alxv wrote: post #13

Earlier quoted context omitted.

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 i…

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?

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.

Re: When Simple Wins: Power of 2 Load Balancing

#26

Post by mrkurt »

alxv wrote: post #11

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/ ).

You're right, I updated the title. Got a little too clever with the whole "power" thing.

Re: When Simple Wins: Power of 2 Load Balancing

#27

Post by mrkurt »

throwaway13337 wrote: post #3

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.

That's very simple consistent hashing. Consistent hashing is great when you want to trade even load for localized data.

In fact, we use consistent hashing when we accept requests, and two random choices when we deliver them to the apps. This works much better for _most_ of the apps we see. We're typically worried about cache data for a particular app. The app instances themselves, though, tend to be mostly stateless and disposable.

Re: When Simple Wins: Power of 2 Load Balancing

#28

Post by nickpsecurity »

alxv wrote: post #13
euph0ria wrote: post #2

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)

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 i…

That's a really intuitive explanation. Appreciate that.

Re: When Simple Wins: Power of 2 Load Balancing

#30

Post by adrianratnapala »

rawnlq wrote: post #12
euph0ria wrote: post #2

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)

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…

So that means the expectation value of the maximum scales as O(log n / log log n)?
Post reply on HN