Load Balancing
One address, many servers. How a balancer decides where each request goes, why the obvious choices backfire, and why two random guesses beat one perfect one.
The whole idea
Why balance load
One server has a ceiling. Past some request rate its CPU saturates, its queues grow, and latency climbs until requests time out. It’s also a single machine, so when it dies, the service dies with it.
The fix for both is more servers. But “more servers” raises a new question that has to be answered for every single request: which one? Clients shouldn’t have to know. They want one stable name, and they want it to work whether there are two servers behind it or two thousand, whether one of them crashed a minute ago, and whether a deploy is halfway through.
A load balancer is the thing that answers “which one?”. It sits between clients and a pool of interchangeable backends and makes three promises:
- Spread the work so no backend is overloaded while others idle.
- Route around trouble so a dead or sick backend stops getting traffic.
- Hide change so backends can be added, drained and replaced without clients noticing.
That last one is what made the rolling upgrade possible: if you can take any server out of rotation, you can patch any server.
How a load balancer works
Every balancer, from a hardware appliance to a sidecar proxy to a library inside your client, runs the same loop.
The request path
- Clients send to a virtual IP (VIP) or a DNS name that resolves to the balancer, never to a backend directly.
- The balancer holds a pool: the backends it may use, usually fed by service discovery.
- A health signal filters the pool down to backends that should get traffic right now.
- An algorithm picks one of those for this request (or this connection), and the balancer forwards it.
Replies normally flow back through the balancer. Some layer-4 designs use direct server return: the backend answers the client directly, so the balancer only carries the inbound half of the traffic. Google’s Maglev works this way, because responses are typically larger than requests.
Where the balancer lives varies more than what it does. It can be a dedicated tier (AWS ELB, HAProxy, NGINX), a
proxy next to every service instance (Envoy as a sidecar), or code inside the client (gRPC’s round_robin
policy, Finagle). Client-side balancing removes a network hop and a shared bottleneck, but every client now needs
the pool, the health data and the logic.
Choosing a server
The algorithm is where intuition goes wrong most often. Start with the simplest one.
Round robin hands requests out in rotation: 1, 2, 3, 1, 2, 3. It’s stateless, cheap and perfectly fair if every request costs the same and every server is the same size. Real traffic breaks both assumptions.
Round robin counts requests, not work
The fixes form a family:
- Weighted round robin gives bigger machines more turns. It handles mixed hardware but still assumes equal requests.
- Least connections / least outstanding requests sends each request to the backend with the fewest in flight. That’s a live measure of how busy a server actually is, so slow requests and slow servers both push traffic away. AWS’s Application Load Balancer offers it as an alternative to its round-robin default.
- Random needs no state and no coordination, and has no rotation to resonate with. It’s fair in expectation but noisier than round robin: some servers get more than their share by chance. Envoy’s docs note it does better than round robin when no health checks are configured.
- Hashing sends the same key (client IP, user ID, URL) to the same backend. You give up some evenness to get affinity: warm caches, sticky sessions, connection state. Consistent hashing keeps most keys in place when the pool changes. It gets its own lesson in Sharding.
“Pick the least loaded” sounds like it can’t be beaten. It has two problems. Finding the true minimum means knowing every backend’s load, which at scale is expensive. And the moment the load information is even slightly old, the obvious strategy turns destructive.
Herding on stale information
This is the herd effect. Many independent balancers, or one balancer acting on a delayed load report, all see the same “idle” server and all pile onto it. By the time the next report arrives, it’s swamped and another server looks idle. Michael Mitzenmacher’s 2000 paper How Useful Is Old Information? modelled exactly this: with stale data, always picking the apparently least-loaded server performs badly, while picking the lesser of two random servers stays good across a wide range of conditions.
The power of two choices
Here’s the trick in full: pick two backends at random, compare their load, send to the less loaded one. That’s it.
It sounds like it should be only slightly better than one random pick. It is dramatically better. Put n requests on n servers by choosing one at random, and the busiest server ends up with about log n / log log n of them. Let each request look at two random servers and take the emptier, and the busiest server ends up with about log log n / log 2, plus a constant. Two choices give an exponential improvement over one; a third choice only shrinks that by a constant factor (log 2 / log 3, about 0.63).The bound comes from Azar, Broder, Karlin and Upfal’s “balanced allocations” result (1994). Mitzenmacher’s thesis and his 2001 paper extended it to servers with queues, where requests arrive and leave over time.
One random pick vs the best of two
one request servers sampled for the latest requestboth panels use the same random draws
Why does one extra glance help so much? A server only gets a request under two choices if it beat a rival, so heavily loaded servers almost always lose. Overload has to grow by winning coin flips against emptier servers, and that gets exponentially unlikely with each extra unit of load.
It also fixes the herd. Each balancer samples a different random pair, so even with stale data they don’t all agree on one target. And it’s cheap: two lookups instead of n. That combination is why it’s built into most modern balancers, and now HAProxy’s default:
NGINX has it as random two least_conn. Netflix’s Zuul edge proxy moved from round robin to choice-of-2 in 2018,
scoring each candidate on its own in-flight count plus a utilization figure the server reports in a response
header. That second signal is how it sees load from every other balancer, not just its own.
Health checks
The algorithm only works if the pool holds servers that can actually do the work. Health checks maintain that.
Active checks are probes: every few seconds the balancer requests something like GET /health and counts
consecutive passes and failures. AWS ALB’s defaults are a probe every 30 s, out of service after 2
failures, back in after 5 passes. Do the arithmetic: a dead server can keep receiving traffic for about a
minute before it’s removed. Faster probing finds failures sooner, but costs load and makes flapping more likely.
Requiring several passes before re-admitting a server is deliberate hysteresis.
Active checks have a blind spot: they test the health endpoint, not the real work.
The fast-failing black hole
AWS’s Builders’ Library describes exactly this incident: a bug made some servers return blank error pages very quickly, the servers didn’t know they were unhealthy, so nothing took them out of service, and because the balancer favoured fast servers, the broken ones attracted more traffic, a “black hole” in the fleet. The defence is passive health checking, also called outlier detection: watch real responses and eject backends that misbehave. Envoy’s defaults eject a host after 5 consecutive 5xx responses, for 30 s the first time and longer each repeat, and never eject more than 10% of the pool.
That last cap matters, because the opposite failure is worse. If a health check tests a shared dependency, one dependency hiccup fails every server’s check at once.
When the check is deeper than the server
So balancers fail open: when too much of the pool looks unhealthy at once, they assume the health signal is wrong rather than the servers.
- AWS ALB routes to all targets if all are unhealthy.
- Envoy has a panic threshold: below 50% healthy hosts, it ignores health and balances across the whole pool.
The other half of the fix is to keep load-balancer checks shallow and local. Is the process up, can it serve, is its disk writable? Leave “can we reach the database?” to monitoring that alerts a human.
L4 vs L7
Balancers come in two broad kinds, named after the network layer they understand.
An L4 (transport-layer) balancer sees TCP and UDP flows. It picks a backend when a connection starts, usually
by hashing the source and destination addresses and ports, and then forwards every packet of that connection to
the same place. It never parses HTTP or decrypts TLS, so it’s very fast and protocol-agnostic. AWS’s Network Load
Balancer hashes the protocol, addresses, ports and TCP sequence number, and pins each connection to one target for
its life. Kubernetes Services, through kube-proxy, also balance per connection.
An L7 (application-layer) balancer is a proxy. It terminates the client’s connection, reads each HTTP or gRPC request, and opens its own connection to the backend. Because it sees requests, it can route by path or header, retry, rewrite, rate-limit, and balance each request separately.
The difference bites hardest with long-lived, multiplexed connections.
One connection, one pod
This is the classic gRPC-on-Kubernetes surprise: several pods, one doing all the work. The fixes are an L7 proxy (a service mesh, or an ingress such as Envoy), or client-side balancing that opens a connection to every pod and spreads requests itself.
| L4 (connections) | L7 (requests) | |
|---|---|---|
| Sees | addresses, ports, packets | methods, paths, headers, bodies |
| Unit of balancing | a connection or flow | each request |
| TLS | passes through | terminates (and re-encrypts) |
| Cost per byte | very low; can run in the kernel or on a NIC | higher: parsing, buffering, two connections |
| Can do | spread flows, preserve client IP | path routing, retries, per-request metrics |
| Weak spot | long-lived multiplexed connections | CPU cost, and a larger blast radius when it’s wrong |
Big systems layer them: an L4 tier spreads raw connections across a fleet of L7 proxies, which do the clever per-request work.
Service discovery
A balancer is only as good as its pool. In a static world you type backend IPs into a config file. In a world of autoscaling groups and pods that live for minutes, the pool changes constantly, and something has to keep it current. That’s service discovery: a registry of which instances of each service exist right now, and where.
- Registration. Instances register themselves (or a platform such as Kubernetes registers them) and are removed when they stop heartbeating or are drained.
- Lookup. Callers or balancers query the registry. That’s either server-side discovery, where a balancer looks up the pool on your behalf, or client-side, where your client fetches the list and balances itself.
- Mechanisms. DNS is the universal fallback, but clients cache records and ignore short TTLs, so it changes slowly. Dedicated registries (Consul, etcd, ZooKeeper, the Kubernetes EndpointSlice API) push changes. Envoy receives its pool over the xDS APIs, so a control plane can update thousands of proxies at once.
Discovery becomes the dependency everything depends on. In October 2021, Roblox was down for 73 hours. The root of it was its Consul cluster, which handled service discovery, health checks, session locking and a key-value store for nearly every service. When Consul degraded under contention, services couldn’t find each other, and the tools engineers would normally use to diagnose and recover depended on Consul too.
The balancer can fail too
Spreading traffic over three servers so that any one can die is pointless if every request passes through one balancer.
Removing the last single point of failure
A single point of failure (SPOF) is any component whose failure alone takes the system down. Balancers are a classic one, because they sit in front of everything. There are two standard ways out:
- Active-passive pairs. Two balancers share a floating IP. The standby watches the active one’s heartbeats,
using a protocol such as VRRP (often via
keepalived), and claims the address when they stop. It’s simple, but half the capacity sits idle, and a heartbeat link failure can leave both thinking they’re active. - Active-active with ECMP. Every balancer announces the same VIP to the routers. The routers spread flows across them with equal-cost multi-path routing, and a dead balancer’s route is withdrawn. The catch is that the router’s hashing reshuffles when the set changes, so each balancer must pick the same backend for a given connection. That needs consistent hashing plus connection tracking.
At planet scale, the second pattern wins. Google’s Maglev has served Google’s traffic since 2008, on ordinary Linux servers with no special hardware. Routers spread packets across Maglev machines with ECMP. Each machine uses consistent hashing over a lookup table (a prime size, more than 100 times the number of backends) so that all of them agree on where each connection goes. Backends answer clients directly. A single machine can saturate a 10 Gbps link with small packets.
Trade-offs
| Choice | Gains | Costs |
|---|---|---|
| Round robin | stateless, simple, predictable | blind to uneven requests and uneven servers |
| Least outstanding requests | reacts to real load, slow requests and slow servers | needs per-backend state; rewards fast failures |
| Power of two choices | near-optimal balance, cheap, robust to stale data and many balancers | not perfectly even; needs some load signal |
| Hashing (consistent, Maglev) | affinity, cache locality, survives balancer failover | uneven with hot keys; reshuffles some keys on change |
| Active health checks | catch dead and unreachable backends | detection lag; deep checks cause correlated ejection |
| Passive outlier detection | catches real errors on real traffic | needs traffic to learn; must be capped |
| L7 proxy | per-request balancing, routing, retries, visibility | CPU, latency, TLS handling, more to break |
| Client-side balancing | no extra hop, no shared bottleneck | logic and discovery in every client, in every language |
In the real world
- Google Maglev (NSDI 2016). Software L4 balancing on commodity servers since 2008. It uses ECMP across balancers, consistent hashing and connection tracking so a balancer change breaks few connections, and direct server return. Envoy ships a Maglev balancer with a default table size of 65,537.
- GitHub GLB Director (2018). An open-source L4 balancer whose directors keep no per-connection state. Each flow maps to a primary and a secondary proxy through a table of about 65,000 rows built with rendezvous hashing. A proxy that doesn’t recognise a packet forwards it to the secondary (“second chance”), so draining a server doesn’t break its connections.
- Cloudflare Unimog (2020). No dedicated balancer tier at all: an XDP program makes every edge server a balancer, at under 1% of CPU. A control plane reads each server’s CPU and moves hash buckets toward the underloaded ones. That matters because a data centre mixes several hardware generations, and requests vary in cost.
- Netflix Zuul (2018). Choice-of-2, scored on in-flight requests, client-observed errors and server-reported utilization. Servers it hasn’t heard from yet are “on probation”, limited to one request in flight, and new servers ramp up over their first 90 seconds. Synthetic tests showed orders-of-magnitude fewer load-shedding errors than round robin.
- Dropbox Robinhood (2024). A PID controller per backend nudges its weight until its utilization matches the fleet average, and clients do weighted round robin with the result. Max-to-average CPU fell from 1.26 to 1.01 on a large Envoy cluster and from 1.4 to 1.05 on a database frontend. Dropbox cut fleet size by 25% for some of its largest services.
- AWS Elastic Load Balancing. NLB at L4 and ALB at L7. ALB offers round robin (the default), least outstanding requests, and weighted random with automatic target weights, which shifts traffic away from targets whose error rates stand out from their peers’. It also has slow start for cold targets, a 300-second default deregistration delay for draining, and fail-open when every target is unhealthy.
Pitfalls
- “Least connections is always best.” It rewards whatever finishes fastest, including servers failing instantly. Pair it with outlier detection.
- Deep health checks on the balancer. One shared dependency blip, and the whole pool is ejected at once. Keep those checks local and keep fail-open on.
- L4 balancing gRPC or HTTP/2. Long-lived multiplexed connections pin traffic to whichever backend they happened to land on. Balance per request.
- Forgetting warm-up. A new server with an empty cache, a cold JIT and empty connection pools looks idle, so least-loaded algorithms flood it. Use slow start or probation.
- Draining by killing. Removing a server without a deregistration delay cuts in-flight requests. Stop sending new work first, then wait.
- Sticky sessions as architecture. Affinity makes load uneven and failover lossy. Keep state out of the server where you can.
- A redundant fleet behind one balancer, or one discovery cluster. Redundancy has to reach every layer.
Recall
Go deeper
- Mitzenmacher, The Power of Two Choices in Randomized Load Balancing (IEEE TPDS, 2001): the queueing version of the result, and why two choices is the rule of thumb.
- Mitzenmacher, How Useful Is Old Information? (IEEE TPDS, 2000): herd behaviour with stale load data, and why random-of-two survives it.
- Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer (NSDI 2016): ECMP, consistent hashing and connection tracking at Google scale.
- David Yanacek, Implementing health checks (Amazon Builders’ Library): liveness, local and dependency checks, black holes, and failing open.
- Envoy docs, Load balancing: P2C, ring hash, Maglev, panic thresholds and zone-aware routing; outlier detection has its own page.
- Mike Smith, Rethinking Netflix’s Edge Load Balancing (2018): choice-of-2 with server-reported utilization, in production.
- David Wragg, Unimog: Cloudflare’s edge load balancer (2020): every server a balancer, and keeping connections alive through change.
- Roblox, Return to Service, 10/28–10/31 2021: what happens when service discovery is the single point of failure.
Keep going
The atomic notes for this lesson live in the knowledge graph:
Next on the map: Caching (serving repeat work without redoing it) and Timeouts, Retries & Overload (what to do when the servers behind the balancer can’t keep up).