When Simple Wins: Power of 2 Load Balancing

The method is called &quot;Power of Two <i>Random Choices</i>&quot; (<a href="http:&#x2F;&#x2F;www.eecs.harvard.edu&#x2F;~michaelm&#x2F;postscripts&#x2F;handbook2001.pdf" rel="nofollow">http:&#x2F;&#x2F;www.eecs.harvard.edu&#x2F;~michaelm&#x2F;postscripts&#x2F;handbook20...</a>). 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 (<a href="https:&#x2F;&#x2F;danluu.com&#x2F;2choices-eviction&#x2F;" rel="nofollow">https:&#x2F;&#x2F;danluu.com&#x2F;2choices-eviction&#x2F;</a>).

I&#x27;m not an expert in this field, but an engineer of vimeo went into detail, why this approach did not work for them. [1]<p>Problem with consistent hashing:<p><pre><code> 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. </code></pre> Problem with Power of 2 Load Balancing:<p><pre><code> 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. </code></pre> Instead, he used something called <i>Consistent Hashing with Bounded Loads</i>.<p>[1] <a href="https:&#x2F;&#x2F;medium.com&#x2F;vimeo-engineering-blog&#x2F;improving-load-balancing-with-a-new-consistent-hashing-algorithm-9f1bd75709ed" rel="nofollow">https:&#x2F;&#x2F;medium.com&#x2F;vimeo-engineering-blog&#x2F;improving-load-bal...</a>

The simplest load balancing I&#x27;ve done is modulo the user ID by the number of servers then point at that server.<p>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.<p>Doesn&#x27;t require a load balance server - just an extra line of code.<p>Keep it simple.

Regarding the math section, could someone please describe it like you were talking to a 5 year old?<p>1) Θ( log n = log &#x2F; log n )<p>2) Θ(log log n)

&quot;Power of 2 Random Choices&quot; ... has nothing to do with the &quot;Power of 2&quot; directly.<p>I like 2Choice because it is not dependent on hash function design &amp; is temporal, but I have a positive aversion to the 2^n hash distributions when it comes to data, specifically for distributed systems which need to flex up&#x2F;down [1].<p>[1] - <a href="http:&#x2F;&#x2F;notmysock.org&#x2F;blog&#x2F;hacks&#x2F;1440" rel="nofollow">http:&#x2F;&#x2F;notmysock.org&#x2F;blog&#x2F;hacks&#x2F;1440</a>

I&#x27;ve seen a paper doing the same thing directly at the network layer using IPv6 extension headers: <a href="http:&#x2F;&#x2F;www.thomasclausen.net&#x2F;wp-content&#x2F;uploads&#x2F;2017&#x2F;06&#x2F;2017-ICDCS-SRLB-The-Power-of-Choices-in-Load-Balancing-with-Segment-Routing.pdf" rel="nofollow">http:&#x2F;&#x2F;www.thomasclausen.net&#x2F;wp-content&#x2F;uploads&#x2F;2017&#x2F;06&#x2F;2017...</a>

Can someone expand on the maths that the OP elided? What is the thing that comes out to O(log n &#x2F; log log n)?