Notesfoundations🌱 seedling
Power of Two Choices
Also: P2C · Two Random Choices · Best of Two · Balanced Allocations
Pick two backends at random and send the request to the less loaded one. That one extra sample shrinks the worst server's load exponentially compared with a single random pick, and it doesn't herd when load data is stale.
Why it exists
Finding the true least-loaded server needs fresh load data from every server: expensive at scale, and harmful when stale, because every balancer piles onto the same "idle" server. One random pick is cheap but leaves some servers badly overloaded.
How it works
- Put n requests on n servers one random pick at a time, and the busiest server gets about log n / log log n.
- Let each request compare two random servers and take the emptier, and the busiest gets about log log n / log 2 + O(1).
- A server only wins a request by beating a rival, so heavily loaded servers almost always lose. Load past the average has to win repeated contests, which gets exponentially unlikely.
- d choices give log log n / log d: going from 1 to 2 is the big jump (exponential); more choices only improve it by a constant factor.
- Each balancer samples a different pair, so stale or shared information doesn't make them all agree on one target.
Trade-offs
| Gains | Costs |
|---|---|
| near-optimal balance from two lookups | not perfectly even |
| robust to stale data and many independent balancers | still needs some load signal (in-flight count, reported utilization) |
In practice
- Envoy: its least-request balancer samples 2 hosts by default (configurable).
- HAProxy 3.3 made
balance randomwith two draws the default. NGINX hasrandom two least_conn. - Netflix Zuul: choice-of-2 scored on local in-flight requests plus server-reported utilization, which captures load from every other balancer.
Pitfalls
- Using only the balancer's local view: with many balancers, each one sees a small slice of each server's load. Server-reported utilization fixes that.
- It still trusts the load signal, so a server that fails instantly looks idle (see Health Check).
Connections
- Part of
- Load Balancing Algorithms
- In real systems
- Envoy
- Mentioned
- Health Check
Recall
These cards are also in your review deck, scheduled with spaced repetition.