Power of Two Choices - Load Balancing Algorithm

I just saw a nice talk from a good friend of mine about load balancing techniques, you can take a look here: https://www.infoq.com/presentations/load-balancing. One of the interesting approaches mentioned in the talk is the "Power of Two Choices" algorithm, which has been explained in detailed here: http://www.eecs.harvard.edu/~michaelm/postscripts/tpds2001.pdf. It is amazing for its simplicity and effectiveness: a simple variation of random choice, but instead of selecting a bin (server) randomly, the idea becomes the following:

• Pick two bins (servers) randomly, call them "A" and "B"
• If "A" is under less load (define load as you wish), then select "A" as your target
• Otherwise, "B"

The simplicity is striking, to a point that it is even questionable whether or not it works. But comparing the approach with a simple random approach you can definitely see that the distribution of the servers load balanced becomes much more "balanced", with a much smaller standard deviation. The code down below implements both concepts - take a look at the distribution results:

Random

Bin[0]: 8.46075433231396%

Bin[1]: 11.7227319062181%

Bin[2]: 10.1936799184506%

Bin[3]: 10.1936799184506%

Bin[4]: 7.95107033639144%

Bin[5]: 11.2130479102956%

Bin[6]: 10.6014271151886%

Bin[7]: 10.2956167176351%

Bin[8]: 9.98980632008155%

Bin[9]: 9.37818552497452%

Power of Two Choices

Bin[0]: 10.0917431192661%

Bin[1]: 9.98980632008155%

Bin[2]: 9.98980632008155%

Bin[3]: 9.88786952089704%

Bin[4]: 9.98980632008155%

Bin[5]: 9.98980632008155%

Bin[6]: 10.0917431192661%

Bin[7]: 9.88786952089704%

Bin[8]: 10.0917431192661%

Bin[9]: 9.98980632008155%

Fascinating! C# code below, cheers my friends!!! Marcelo

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace PowerOf2LoadBalancer

{

    class Program

    {

        static void Main(string[] args)

        {

            int[] bins = new int[10];

            int nRequests = 981;

            LoadBalancerRandom(nRequests, bins);

            bins = new int[10];

            LoadBalancerPowerOf2(nRequests, bins);

        }

        static void LoadBalancerRandom(int nRequests, int[] bins)

        {

            Random rd = new Random();

            for (int i = 0; i < nRequests; i++)

                bins[rd.Next(0, bins.Length)]++;

            PrintBinsPercentage(bins);

        }

        static void LoadBalancerPowerOf2(int nRequests, int[] bins)

        {

            Random rd = new Random();

            for (int i = 0; i < nRequests; i++)

            {

                int a = rd.Next(0, bins.Length);

                int b = rd.Next(0, bins.Length);

                bins[bins[a] < bins[b] ? a : b]++;

            }

            PrintBinsPercentage(bins);

        }

        static void PrintBinsPercentage(int[] bins)

        {

            int total = 0;

            for (int i = 0; i < bins.Length; i++) total += bins[i];

            for (int i = 0; i < bins.Length; i++) Console.WriteLine("Bin[{0}]: {1}%", i, (bins[i] * 100.0) / total);

            Console.WriteLine();

        }

    }

}