Under the Hood: Load Balancing Algorithms & Health Checks
A load balancer sits between clients and backend server pools, ensuring that no individual node becomes a bottleneck while masking node failures dynamically. How traffic is balanced depends on the mathematical algorithm employed.
Core Load Balancing Algorithms
Under the Hood: Algorithm Deep Dive
1. Round Robin & Weighted Round Robin
Requests are distributed in a circular sequence: node 0, 1, 2, …, N-1. While simple (O(1) selection via atomic pointer increment), it fails when request processing times vary widely: long-running batch requests can stack up on a single node while fast queries leave other nodes idle. Weighted Round Robin assigns higher quotas to machines with higher core/memory specs.
2. Least Connections
Maintains an atomic counter of active in-flight requests per server. New requests are dispatched to the server with the lowest current load. Well suited to variable request durations and long-lived connections such as WebSockets or streaming sessions.
3. The Power of Two Random Choices (P2C) with EWMA
The power-of-two-choices result comes from Azar, Broder, Karlin and Upfal (1994) and Mitzenmacher (1996); Twitter's Finagle popularised combining it with a peak EWMA latency estimate, and Envoy's least-request balancer uses P2C by default. Always picking the globally least-loaded node needs fresh shared state and causes herding when many balancers act on the same stale view. Instead, the load balancer picks two random nodes and routes to whichever has the lower Exponentially Weighted Moving Average (EWMA) latency. Mathematically, P2C cuts the expected maximum load from about log n / log log n (random choice) to about log log n, with O(1) computation: it greatly reduces hot spots, though it is not optimal.
Worked example: why random is not good enough, and two choices is
Suppose 1,000 servers each receive requests at random. If you throw n requests at n servers uniformly at random, the busiest server's load grows like log n / log log n. That is only a leading-order estimate (it evaluates to about 3.6 for n = 1,000); in simulation the busiest of 1,000 servers typically gets 5 or 6 requests while the average is 1. If instead each request samples two random servers and picks the less loaded, the maximum grows only as log log n / log 2 plus a constant, typically 3 for n = 1,000. This is the "power of two choices" result from Azar, Broder, Karlin and Upfal (1994) and Mitzenmacher's thesis (1996). Sampling more than two gives only small further gains.
It matters in practice because a central "least loaded" choice needs fresh global state. Many independent load balancer instances each picking the globally least-loaded server all pick the same one (herding). Two random choices use only local, slightly stale information yet avoid herding.
Algorithm comparison
| Algorithm | State needed | Handles uneven request cost | Good for |
|---|---|---|---|
| Round robin | A counter | Poorly | Uniform, short requests on identical servers |
| Weighted round robin | Counter and weights | Poorly | Mixed instance sizes |
| Least connections or outstanding requests | Active count per backend | Well | Variable request duration, long-lived connections |
| Power of two choices on load | Local counts or latency estimates | Well | Many distributed balancers, large pools |
| Peak EWMA latency with P2C | Latency average per backend | Well, and reacts to slow nodes | Client-side balancing (Finagle, Linkerd) |
| Hash (source IP, key, consistent hash) | Hash ring | No | Stickiness and cache locality |
Health checking details
- Active checks: the balancer calls
/healthzevery few seconds; typical settings mark a node down after 2 to 3 failures and up after 2 successes. - Passive checks (outlier detection): eject a backend that returns several consecutive 5xx responses to real traffic, as Envoy does.
- Panic threshold: if too many nodes look unhealthy (for example over 50%), send traffic to all of them rather than overload the few remaining; Envoy implements this.
- Connection draining: when removing a node, stop new requests but let in-flight ones finish.
How real systems do it
Google's Maglev is a software L4 balancer that runs on commodity servers and uses consistent hashing so that connections survive balancer failover. Twitter's Finagle and Linkerd popularised P2C with a peak EWMA latency estimate for client-side balancing. NGINX and HAProxy support round robin, least connections and hashing; Envoy's least-request policy uses power of two choices by default.