A surprisingly strong trick
The power of two choices is a load balancing technique: instead of picking one server at random, sample two at random and send the request to the less loaded of the pair.
Why it works so well
- Pure random placement leaves the busiest server with a queue that grows with the logarithm of the server count.
- Checking just two and choosing the shorter queue shrinks the worst case to roughly the log of the log, a dramatic improvement.
The leap from one choice to two is huge; going from two to three choices adds far less, so two is the sweet spot.
Where it shows up
- Load balancers distributing requests across backends.
- Hash based systems placing keys across shards.
It avoids the cost of querying every server for its load, which would be accurate but far too expensive at scale, while capturing most of the benefit.
Key idea
Sampling two servers and choosing the lighter one cuts worst case queue length dramatically for almost no extra cost.