Notesfoundations🌱 seedling

Load Balancing Algorithms

Also: Round Robin · Least Connections · Least Outstanding Requests · Weighted Round Robin

The rule a load balancer uses to pick a backend: rotation, load-aware choice, randomness or hashing. Each one trades how even the load is against how much state and how fresh a load signal it needs.

Why it exists

Requests differ in cost and servers differ in capacity, so "give everyone the same number of requests" is rarely the same as "give everyone the same amount of work".

How it works

  • Round robin: 1, 2, 3, 1, 2, 3. Stateless and fair only if requests and servers are uniform. A fixed rotation can even line up with a periodic pattern of expensive requests.
  • Weighted round robin: bigger servers get more turns. It handles mixed hardware, not mixed requests.
  • Least connections / least outstanding requests: pick the backend with the fewest in flight. It reacts to slow requests and slow servers.
  • Random: no state and no coordination, and no rotation to resonate with. Fair in expectation but noisier than round robin.
  • Power of Two Choices: sample two at random, take the less loaded. Near-optimal and robust to stale data.
  • Hashing: a key (client IP, user, URL) maps to a backend, giving affinity for caches and sessions. Consistent Hashing limits reshuffling when the pool changes.
  • Feedback weights: a controller adjusts weights from reported utilization until every server runs near the fleet average.

Trade-offs

Algorithm Gains Costs
round robin trivial, predictable blind to request cost
least outstanding live load signal per-backend state; rewards fast failures
exact least-loaded best on paper needs fresh global info; herds when stale
hashing affinity, cache hits uneven with hot keys

In practice

  • AWS ALB: round robin by default, with least outstanding requests and weighted random (with automatic target weights) as options.
  • Dropbox: per-node PID controllers set weights for client-side weighted round robin, bringing max/average CPU close to 1.

Pitfalls

  • Herding: many balancers acting on the same stale "least loaded" report all hit the same server.
  • Black holes: load-aware algorithms send the most traffic to a server that fails instantly, unless outlier detection ejects it.

Recall

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