"The Power of Two Choices" Load-Balancing Algorithm

[analogrelay]

This falls somewhere between Random (#73) and Least-Requests (#74). It tends to be easier to implement across a cluster of proxies.

Given that load-balancers don't share state about the load to each backend (this would be very costly), a proxy instance is making it's decision based on the number of outstanding requests it has to the backends, and not the number of requests all instances have. This means that often multiple proxy instances can see the same nodes as under-utilized and send a storm of requests to it (if the incoming traffic is randomly balanced, as tends to be the case).

The "Power of Two Choices" model (discussed in some sources below) adds a degree of randomness by first selecting two random backends and then making a "least-outstanding-requests" decision between those two. This helps to prevent these storms of traffic. This doesn't generally perform better than Least Requests/Connections in a single-node proxy deployment, but it can be better than Random in situations where each node doesn't have perfect knowledge of the load

Sources

• NGINX and the “Power of Two Choices” Load-Balancing Algorithm
• Test Driving “Power of Two Random Choices” Load Balancing
• Michael Mitzenmacher. 2001. The Power of Two Choices in Randomized Load Balancing. IEEE Trans. Parallel Distrib. Syst. 12, 10 (October 2001), 1094–1104. DOI:https://doi.org/10.1109/71.963420