Power of Two Choices

The "Power of Two Choices" is a principle often used in load balancing algorithms to achieve better distribution of tasks across a system. The basic idea is that instead of assigning a task to a random server, you select two servers at random and assign the task to the one that is currently less loaded. This seemingly small change can lead to a significant improvement in the load distribution.

To understand why, consider the following simplified scenario: you have a large number of balls and a large number of bins, and you want to distribute the balls among the bins. Each time you pick up a ball, you randomly select two bins and place the ball in the one that currently has fewer balls.

Let's denote:

• (n): the number of bins

• (m): the number of balls

• (X): the number of balls in the most loaded bin

Under the "Power of Two Choices" principle, it can be shown that (E[X]) (the expected maximum load or the expected number of balls in the most loaded bin) is approximately (log log n), which is significantly smaller than the expected maximum load in the case of simple random placement, which is approximately (log n / log log n).

This result has been formalized and proven in a paper by Azar, Broder, Karlin, and Upfal in 1999. The proof involves a bit of combinatorics and probability theory, specifically using Poisson approximation and Chernoff bounds.

The "Power of Two Choices" principle is widely used in distributed systems, hash table implementations, and other load balancing algorithms because it provides a simple yet effective way to distribute load more evenly across the system. This results in better utilization of resources, less congestion, and generally better performance.

Why not "Power of Three or More Choices"

The "Power of Two Choices" is somewhat of a sweet spot in terms of the trade-off between efficiency and overhead. While using the "Power of Three Choices" (or more) would indeed decrease the maximum load even further, the difference becomes less pronounced as you increase the number of choices.

So why not always use more choices? The issue is the increased overhead. Each additional choice requires more resources: more time to select and compare the servers, more network bandwidth to communicate with them, etc. This overhead can eventually outweigh the marginal benefits of the improved load balancing.

Moreover, with each additional choice, you get diminishing returns. The improvement from one choice to two is much greater than the improvement from two to three, which is in turn greater than the improvement from three to four, and so on.

So while you could use more than two choices in your load balancing algorithm, two is often a good balance between the gains in load balancing and the additional overhead. This is why the "Power of Two Choices" is a commonly used principle in practice.

However, depending on the specific circumstances and requirements of your system, it might be beneficial to use more than two choices. For example, if the cost of having an overloaded server is extremely high, it might be worth the extra overhead to use the "Power of Three Choices" or more. The right choice depends on the specifics of the situation.

Refer to https://www.nginx.com/blog/nginx-power-of-two-choices-load-balancing-algorithm/