Load Balancing

Power of Two Choices Reduces Load Imbalance with Two Samples

Power of Two Choices Reduces Load Imbalance with Two Samples A load balancer that chooses one destination uniformly at random is cheap and decentralized, but random placement can produce uneven queues. At the other extreme, selecting the least loaded destination from the entire pool requires current load information for every candidate and can make the balancer itself expensive. The power-of-two-choices strategy sits between those designs. For each request, sample two eligible destinations, compare a load signal, and send the request to the better candidate. Two observations are enough to avoid many unlucky placements without requiring a global search.