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 random with two draws the default. NGINX has random 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).

Recall

These cards are also in your review deck, scheduled with spaced repetition.