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

41–49 of 49 posts

Re: When Simple Wins: Power of 2 Load Balancing

#41

Post by justifier »

hvidgaard wrote: post #38
justifier wrote: post #33

Earlier quoted context omitted.

though a clever way to be able to ignore the real problem eventually time will force you to revisit from base principles user_id%numb_server may work early on when user activity and uptake are consistent, but what happens when user activity becomes more complex: increase in users, some users abandoning the platform, others using it more; and that complexity lacks homogeneous distribution through this only concerned p…

I can think of a few ways to rebalance things on the fly, but I would probably just hash some immutable values for the user, like Id and name, together with a nonce. If a server get's overloaded, slowly move people from it by changing their nonce.

if you are introducing a nonce why use a hash? with a performance reflective mutating nonce on the user id modulo works as is

if you are introducing monitoring on a per user precision why use modulo? with a per user scheduled monitoring moving users based on user ids works as is

maybe i was unclear in the above but i like the gp's simple solution.. especially because i personally have an affection for the modulo operator, but also because.. it only requires an operator that performs in a scale dependent finitely specific number of cycles and works as designed without any monitoring

the above was intended to bring attention to shortcomings and probable failures in an otherwise elegant attempt

the method is flawed but the direction is superb

Re: When Simple Wins: Power of 2 Load Balancing

#42

Post by user5994461 »

zubspace wrote: post #37

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

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.

Re: When Simple Wins: Power of 2 Load Balancing

#44

Post by hvidgaard »

justifier wrote: post #41
hvidgaard wrote: post #38

Earlier quoted context omitted.

I can think of a few ways to rebalance things on the fly, but I would probably just hash some immutable values for the user, like Id and name, together with a nonce. If a server get's overloaded, slowly move people from it by changing their nonce.

if you are introducing a nonce why use a hash? with a performance reflective mutating nonce on the user id modulo works as is if you are introducing monitoring on a per user precision why use modulo? with a per user scheduled monitoring moving users based on user ids works as is maybe i was unclear in the above but i like the gp's simple solution.. especially because i personally have an affection for the modulo oper…

You could use nonce to determine what server to use. But I didn't want to choose directly, just the ability to chance the output of the hash for whatever reason.

I did not want to use just any non random rebalancing mechanics to avoid advesaries attacking that implementation. With a hash the output is deterministic, but unpredictable.

Re: When Simple Wins: Power of 2 Load Balancing

#45

Post by pas »

user5994461 wrote: post #42
zubspace wrote: post #37

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

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.

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.

Re: When Simple Wins: Power of 2 Load Balancing

#46

Post by naiveattack »

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

"while each additional choice beyond two decreases the maximum load by only a constant factor"

Mathemagical!

Re: When Simple Wins: Power of 2 Load Balancing

#47

Post by candu »

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.

One problem with this is the "long tail" issue: in many applications, you have a highly active small minority of users, and any server assigned to enough of those users will be overloaded while other servers are underutilized. Since these are also (typically) your most excited / engaged users, this effectively penalizes user behaviors you'd rather encourage.

The other main problem is that it's not a consistent hash: if you grow the server pool, you typically need to reshard a lot of content.

(It's still useful in a pinch, but it helps to be aware of the tradeoffs.)

Re: When Simple Wins: Power of 2 Load Balancing

#48

Post by mrkurt »

zubspace wrote: post #37

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

Bounded load consistent hashing is interesting. It makes total sense that 2 random wouldn't work for vimeo, it actually doesn't work for us between visitors and our edge because we care a lot about cache data — we only use it between our load balancers and our customer's origin app instances.

For what we're doing, we actually need to consider more than just load. Since our LBs are distributed globally, we also want to make sure we're sending requests to backends that are geographically near them.

We can do this by tracking latency between the load balancer and origin servers, then using it to restrict the candidate pool we're going to choose two from at random.

Re: When Simple Wins: Power of 2 Load Balancing

#49

Post by justifier »

hvidgaard wrote: post #44
justifier wrote: post #41

Earlier quoted context omitted.

if you are introducing a nonce why use a hash? with a performance reflective mutating nonce on the user id modulo works as is if you are introducing monitoring on a per user precision why use modulo? with a per user scheduled monitoring moving users based on user ids works as is maybe i was unclear in the above but i like the gp's simple solution.. especially because i personally have an affection for the modulo oper…

You could use nonce to determine what server to use. But I didn't want to choose directly, just the ability to chance the output of the hash for whatever reason. I did not want to use just any non random rebalancing mechanics to avoid advesaries attacking that implementation. With a hash the output is deterministic, but unpredictable.

What are your adversarial concerns?
Post reply on HN