News for hackers. Stuff that matters.
Re:A deep dive on load balancing algorithms by jedberg on Wednesday November 17, 2021 @04:40PM (#29259193)
I'm disappointed that this doesn't include HRW (Highest Random Weight or Rendezvous Caching). It has the advantages of consistent hashing without the disadvantage, and doesn't require a central coordinator like consistent hashing does.
Re:A deep dive on load balancing algorithms by skyde on Wednesday November 17, 2021 @06:49PM (#29260436)
does it handle overloaded service similar to "Bounded Consistent Hashing"?
Re:A deep dive on load balancing algorithms by jedberg on Wednesday November 17, 2021 @07:45PM (#29260836)
Yeah, it would. If the server returns a 503 to the caller when it's overloaded, the caller would move on to the next host, and if the server were taken out of service, then the call would move on to the next host.

The main difference is that only the calls for that host would move, and they would be distributed across multiple other hosts, instead of shifting the keyspace around, depending on what you are using for your HRW calculation to pick the server list.

Re:A deep dive on load balancing algorithms by recursive on Wednesday November 17, 2021 @05:47PM (#29259844)
I'm not familiar with any of these, but this point stuck out to me.

Two random choice says "Max load of any server is O(log log number_of_servers)."

If work accomplished is proportional to load, then the total work done by the entire system is O(number_of_servers * log log number_of_servers). It seems very suspicious, magical even, that the total work is more than linear with the number of servers. Free energy discovered?

Re:A deep dive on load balancing algorithms by scottlamb on Wednesday November 17, 2021 @06:25PM (#29260221)
> If work accomplished is proportional to load, then the total work done by the entire system is O(number_of_servers * log log number_of_servers). It seems very suspicious, magical even, that the total work is more than linear with the number of servers. Free energy discovered?

No free energy for at least a couple reasons:

* This is O(...) meaning (roughly) "bounded above by", not Theta(...) meaning "bounded above and below by".

* This is max load, not average load. Even if it were theta, it wouldn't follow from the max load on a server being Theta(log log number_of_servers) that the total load is Theta(number_of_servers * log log number_of_servers).

Re:A deep dive on load balancing algorithms by rp1 on Thursday November 18, 2021 @07:26AM (#29264639)
I imagine the reason is that the max load on a single server is O(log log number of servers), but it’s not possible for all the servers to be at max load.

For instance, imagine load balancing via random assignment. The theoretical max load of a server is receiving every request, but if one server receives more requests, then the other servers receive less.