Load Balancing Strategies

A few months ago I came across this tweet that showed an interesting load balancing technique.

Load balancing by choosing a random node isn’t great because you can get unlucky with randomness and keep choosing the same node. However, load balancing by choosing two random nodes and picking the minimum does a pretty good job of balancing load.

This was surprising to me.

Below, I’ve created a demo of load balancing using 4 different strategies:

  1. Random
  2. Double Random
  3. Round Robin
  4. Always First

Each load balancer is given some load and slowly processes it. Although the amount of load each turn is random, each load balancer is given the same amount of load. When a load balancer runs out of capacity, it goes offline leaving the remaining nodes to shoulder the burden.

It surprised me to see that round robin and double random are both significantly better at balancing load than a purely random approach. Round robin has the disadvantage of having the load balancer keep track of some state. This means that multiple load balancers would have a more complicated set up if they were both distributing load to a shared node pool.