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

31–40 of 49 posts

Re: When Simple Wins: Power of 2 Load Balancing

#31

Post by cbhl »

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.

Facebook chat used to use this scheme, but eventually had to move away from it because it made it difficult to add and remove servers to the fleet in response to load.

Re: When Simple Wins: Power of 2 Load Balancing

#32

Post by boyter »

mnutt wrote: post #14
alxv wrote: post #7

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

Or how memcached does it https://www.adayinthelifeof.nl/2011/02/06/memcache-internals...

Re: When Simple Wins: Power of 2 Load Balancing

#33

Post by justifier »

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.

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 property: 'user id';

what if over time you gain more users but the majority of people who drop the platform have a user_id%numb_servers==2|11|13|17

in this case you would have some servers working hard while others sitting dormant

what is the real distribution of the relation between activity and user_id over time? asymptotic(o)? similar to the prime numbers(i)? a gaussian distribution(ii)? a benford distribution(iii)?

whichever future dada will show to be the best fit, most distributions show a strong trend toward eventual favoring of values

which i think implies, to ensure an even distribution of work across servers, the problem requires something with greater dimensionality than modulo on an immutable value that is defined serially

(o) https://en.wikipedia.org/wiki/Asymptotic_analysis

(i) https://en.wikipedia.org/wiki/Prime_number_theorem

(ii) https://en.wikipedia.org/wiki/Probability_density_function

(iii) https://en.wikipedia.org/wiki/Benford's_law

Re: When Simple Wins: Power of 2 Load Balancing

#34

Post by euph0ria »

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…

Thank you sir!

Re: When Simple Wins: Power of 2 Load Balancing

#35

Post by adrianN »

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

It also works for solving SAT. Try two literals and recurse on the one that can be made to satisfy more clauses.

Re: When Simple Wins: Power of 2 Load Balancing

#36

Post by adrianN »

alxv wrote: post #7
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.

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.

When the number of server changes you slowly ramp up from mod n to mod (n+1). Flip a biased coin for each user to decide whether to use n or n+1, slowly crank up the bias to the n+1 side.

Re: When Simple Wins: Power of 2 Load Balancing

#37

Post by zubspace »

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

Re: When Simple Wins: Power of 2 Load Balancing

#38

Post by hvidgaard »

justifier wrote: post #33
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.

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.

Re: When Simple Wins: Power of 2 Load Balancing

#39

Post by prashantswain »

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

Re: When Simple Wins: Power of 2 Load Balancing

#40

Post by maffydub »

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…

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?
Post reply on HN