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.
Connections
- Part of
- Load Balancer
- Contains
- Power of Two Choices
- Related
- Consistent Hashing
- In real systems
- Envoy
Recall
These cards are also in your review deck, scheduled with spaced repetition.