Load balancing

The problem it solves

You have more traffic than one machine can serve, so you buy several machines. Immediately you have a new problem the machines cannot solve for you: when a request arrives, which one gets it? The question sounds administrative. It is not. The answer determines your tail latency, and the tail is what users experience as “the site is slow” — because a page that makes twenty backend calls is only as fast as its slowest one.

The naive mental model is that traffic divides. Six servers, six thousand requests a second, a thousand each, everybody at the same load. That model is wrong in a specific and consequential way: it assumes every request costs the same. Real requests do not. A product page for an ordinary item and a product page for the item on the front of the site are the same endpoint with wildly different work behind them. Once service times vary, an even split of requests is not an even split of work, and the difference shows up as one machine with a queue while its neighbour sits idle.

The mechanism

Every strategy above answers the same question with a different amount of information.

Round robin uses none. It hands out requests in rotation, which guarantees an even count and says nothing about load. Random uses none either, and is slightly worse: rotation at least avoids the clumping that independent coin flips produce.

Least connections uses all of it. It scans every server, finds the one holding the fewest in-flight requests, and sends there. That is the best decision available — and it costs a global scan on every request, plus a piece of shared state every balancer instance must agree on. At scale, that state is the bottleneck.

Random of two choices is the interesting one. Pick two servers at random. Send to the lighter. That is the whole algorithm. It uses two lookups instead of n, needs no shared state, and its tail lands far closer to least-connections than to random. The result is famous in queueing theory: the maximum load under one random choice grows like log n / log log n, while under two choices it grows like log log n / log 2 — an exponential improvement bought with one extra sample.

Consistent hashing answers a different question entirely. It does not ask which server is free; it asks which server owns this key, so the same key lands on the same server every time. That is what you want when the server holds a cache. It is also what makes it uniquely vulnerable to the failure below.

What the simulation shows

Run the defaults and the strategies look similar, because the default service-time spread is modest. Now widen the spread and watch the percentiles separate. Round robin’s p99 climbs steeply; two-choices barely moves. The panel that explains it is work-in-progress per node: under round robin you can watch a server that drew three expensive requests in a row sit with a queue while its neighbour is empty — and the next request in rotation goes to it anyway, because rotation does not look.

Then turn on a hot key under consistent hashing. Half the traffic now belongs to a single key. The utilisation panel shows one node pinned at the top of the range and the others loafing, and — this is the part worth internalising — adding servers does not help. The hot key hashes to one place. It will hash to one place with twelve servers too. You have not built a capacity problem you can buy your way out of; you have built a single-key problem that requires a different design.

The numbers worth carrying

Two random samples instead of one is the cheapest improvement in this whole section: identical infrastructure, one extra lookup per request, and a tail that lands far closer to the omniscient strategy than to the blind one. If you take one operational habit from this page, it is that your balancer’s algorithm setting is probably round-robin and probably should not be.

The second number belongs to the utilisation curve: a request arriving at a pool of six servers has six chances to find a free one, which is why pooled capacity behaves so much better than the same capacity divided into private slices. Load balancing is the mechanism by which the pool exists at all. Sixteen servers at 95% utilisation are a far more comfortable place than one server at 95%, and the difference is entirely about the balancer’s ability to find the free one.

Where it breaks down

Least connections is the best algorithm on this page and not the one to reach for first, because “connections in flight” is a proxy for “work in flight” and the proxy fails whenever connections are long-lived. On a service using WebSockets or HTTP/2 multiplexing, connection count is nearly constant and tells you nothing.

Two-choices degrades when the two samples are not independent — which happens when several balancer instances share a random seed, or when a “random” choice is really consistent-hash-with-jitter. It degrades further when the load signal is stale: if what you compare is a health-check reading from three seconds ago, you are not choosing the lighter server, you are choosing the server that was lighter, and every balancer makes the same wrong choice at the same moment. That failure has a name — herding — and it produces a sawtooth in the utilisation panel that is unmistakable once you have seen it.

Consistent hashing breaks on skew, as above, and it also breaks on heterogeneous capacity: a ring does not know one of your nodes is a newer instance type with twice the cores. Weighted virtual nodes fix that, and are covered on the consistent hashing page.

What people get wrong

“Least connections is strictly better, so use it.” It is strictly better per decision, and it requires shared, current state. In a real deployment with several balancer processes, each has its own partial view, and a partial least-connections is often worse than two-choices, because every balancer independently concludes the same server is emptiest and they all send there at once.

“We use round robin because it is fair.” It is fair in requests and unfair in work, and the servers experience work. Fairness in the count is not a property anyone benefits from.

“Health checks handle the slow server.” Health checks handle the dead server. The slow server passes its health check — it responds, just late — and round robin keeps feeding it. The load-aware strategies handle this automatically, which is a second reason to use them.

“Add more servers.” For a hot key, no. Watch the utilisation panel with the hot key on and the server count at twelve.

In production

Every real load balancer implements most of these. Nginx has least_conn and hash; Envoy has LEAST_REQUEST — which in its default configuration is literally random-of-two-choices rather than a full scan, for exactly the reason described above — plus RING_HASH and MAGLEV for the consistent-hash family. HAProxy has leastconn. AWS Application Load Balancer defaults to round robin and offers least outstanding requests; the second is usually the right setting and is not the default.

The other production concern is what the balancer does when a server is saturated rather than dead. The answer should involve a bounded queue and a fast rejection rather than an unbounded wait — the subject of backpressure — and it should not involve the client retrying immediately, which is the subject of retry storms.

The follow-up questions

“You said round robin. What happens when one server is slow but healthy?” — It keeps receiving its full share. Name the fix: a load-aware strategy, or an active health check with latency thresholds rather than liveness alone.

“Why is two-choices nearly as good as scanning everything?” — Because a random choice is only bad when it lands on a loaded server, and the probability that both samples are loaded is the square of the probability that one is. Squaring a small number makes it very small.

“Your cache hit ratio depends on the same key reaching the same server. How does that interact with balancing?” — This is the question that forces consistent hashing into the answer, and then forces you to say what you will do about a hot key: a compound key, a dedicated shard for the hot tenant, or a local cache in front of the ring.

“One tenant is 40% of your traffic. What changes?” — Everything on this page. Say so before you are asked.