Load balancing algorithms: round robin to consistent hashing

Three identical instances sit behind the load balancer, average CPU is at 40 percent, and p99 latency has doubled since Tuesday. Nothing is down. One instance is slow: a noisy neighbor on its host, a garbage collector working a bigger heap, a deploy that landed on a smaller VM class than the other two. The balancer does not know any of that. It was told to spread requests evenly, and evenly is what it does, which is how a healthy fleet ends up with a third of its users waiting on its worst machine.

A load balancing algorithm is a bet about what the backends and the requests look like. Each algorithm makes a different bet, and each is exactly right for the fleet it assumes and quietly wrong for the one it gets.

Round robin bets that every server and every request is the same. The day that bet loses, the average looks fine and the p99 tells the truth.

Round robin bets everything is equal

Round robin hands request one to server A, request two to server B, request three to server C, and starts over. It needs no state beyond a counter, it is fair over time, and it is the default in most balancers for good reason. Its bet is that the servers have equal capacity and the requests have equal cost, so equal counts mean equal load.

Weighted round robin repairs the first half of the bet. If server C has half the cores, give it weight 1 against 2 for the others and it receives a quarter of the traffic instead of a third. The weights are static, though. They describe the machine you provisioned, not the one that is currently swapping.

Least connections bets requests are uneven

The second half of the bet fails on its own. Requests are not equal: one returns a cached row in 5 milliseconds, the next runs a report for 2 seconds. Least connections sends each new request to the server with the fewest requests in flight. A server that is slow, for whatever reason, holds its requests longer, its count stays high, and it stops being chosen until it catches up. The algorithm never learns why C is slow. It only notices that C is not finishing.

A worked example makes the difference concrete. Three servers, 60 requests per second, each request taking 100 milliseconds on A and B and 500 milliseconds on C. Under round robin each server gets 20 requests per second. Little's law (requests in flight equal arrival rate times time in the system) says A and B each hold 2 requests at a time and C holds 10. If C can run 8 concurrently, the other 2 queue, the queue grows, its response time climbs past 500 milliseconds, and the higher time raises the in-flight count further. The balancer keeps sending C one request in three the whole way down.

Under least connections the in-flight counts equalize instead. If every server holds L requests, A and B each complete L / 0.1 per second and C completes L / 0.5, so A and B each take five times C's share. Out of 60 requests per second, C gets 60 x (2 / 22), just under 6, and its in-flight count settles near 3. Same fleet, same slow machine, and C is no longer the p99.

Least connections has a cost: the balancer must track live counts per backend, and with several balancer instances those counts are local views that disagree. Power-of-two-choices is the cheap approximation. Pick two backends at random and send the request to the one with fewer connections. Michael Mitzenmacher's analysis of the technique showed that the second random choice removes most of the imbalance of purely random assignment, and it needs no coordination between balancers, which is why several modern proxies default to it.

Consistent hashing bets affinity is worth it

Sometimes which backend answers matters. A cache node holds the keys it has seen, a websocket server holds the connections it accepted, a worker holds a warm model in memory. You want the same key to land on the same node every time, and the obvious way is hash(key) % nodeCount. It works until the node count changes.

Modulo hashing moves almost every key when a node is added or removed, because hash % 4 and hash % 3 agree only when the hash happens to satisfy both, roughly one time in four. Consistent hashing places every node at many points on a ring and assigns each key to the first node clockwise from the key's own hash. Removing a node moves only the keys that node owned, about 1/N of them, to its clockwise neighbors. Everyone else's cache stays warm.

using System.IO.Hashing;
using System.Text;

public sealed class HashRing
{
    private readonly uint[] _points;
    private readonly string[] _owners;

    public HashRing(IEnumerable<string> nodes, int virtualNodes = 100)
    {
        var ring = new SortedDictionary<uint, string>();
        foreach (var node in nodes)
        {
            for (var i = 0; i < virtualNodes; i++)
            {
                ring[Hash($"{node}#{i}")] = node;
            }
        }

        _points = [.. ring.Keys];
        _owners = [.. ring.Values];
    }

    public string NodeFor(string key)
    {
        var index = Array.BinarySearch(_points, Hash(key));
        if (index < 0)
        {
            index = ~index; // first point clockwise from the key
        }

        return _owners[index == _points.Length ? 0 : index]; // wrap past the last point
    }

    internal static uint Hash(string value) =>
        XxHash32.HashToUInt32(Encoding.UTF8.GetBytes(value)); // stable across processes
}

The hash must be stable across processes and runtime versions, which rules out string.GetHashCode(); XxHash32 from the System.IO.Hashing package qualifies. Virtual nodes matter because a single point per node makes the arcs wildly uneven. Counting what moves when one of four nodes leaves:

var nodes = new[] { "api-1", "api-2", "api-3", "api-4" };
var keys = Enumerable.Range(0, 1_000).Select(i => $"session:{i}").ToArray();

var before = new HashRing(nodes);
var after = new HashRing(nodes[..3]); // api-4 removed

var ringMoved = keys.Count(key => before.NodeFor(key) != after.NodeFor(key));
var moduloMoved = keys.Count(key => HashRing.Hash(key) % 4 != HashRing.Hash(key) % 3);

An example run of that code:

modulo:  737 of 1,000 keys changed owner
ring:    238 of 1,000 keys changed owner   (every one of them was api-4's)

with virtualNodes = 1,   api-4 owned 412 keys before removal
with virtualNodes = 100, api-4 owned 238

Modulo moved three quarters of the keys; the ring moved exactly the removed node's share, and 100 virtual nodes brought that share close to the ideal quarter. Rendezvous hashing reaches the same property differently, scoring every node for each key and picking the highest, which is simpler when the node count is small. Both share a cost: affinity concentrates load. One hot key is one hot node, and the algorithm will not spread it, because not spreading it was the point. The caching strategies guide covers what a hot key does to the node that owns it.

Health checks decide who is in the rotation

The best algorithm is useless if an unhealthy node stays in the pool. Three mechanisms keep the rotation honest, and all three are separate from the algorithm.

Active health checks poll each backend, usually a readiness endpoint that verifies the process can reach its own dependencies, and remove a backend after a few consecutive failures. Outlier ejection is the passive version: the balancer watches real responses, and a backend returning a burst of 5xx or timing out is ejected for a while, then allowed back with a probe. Envoy's outlier detection is the reference implementation, and it is a circuit breaker living on the balancer's side of the call. Connection draining handles the planned case: on a deploy, stop routing new requests to the instance, let in-flight ones finish, then terminate. Skip it and every deploy is a small outage no algorithm can prevent.

Layer 4, layer 7, and the sticky-session smell

A layer 4 balancer forwards TCP connections. It is fast and cannot see HTTP, so it balances connections rather than requests, which is fine for short-lived connections and unhelpful for a client that opens one HTTP/2 connection and sends ten thousand requests down it. A layer 7 balancer terminates the connection, reads the request, and can route by path, header, or cookie, at the cost of more work per request. Most fleets run both, one at the edge and one in front of the services, with service discovery telling the inner one where the instances are.

Sticky sessions are the layer 7 feature that should make you suspicious. If a user must return to the same instance because that instance holds their session, the instance is not stateless, the balancer cannot move the user when the instance is slow, and losing the instance logs them out. The fix is rarely a better cookie. It is moving the state into a shared store so any instance can serve any request, which returns you to the world where round robin was a reasonable bet.

Practicing the bet

Knowing the algorithms is the easy half. The judgment is seeing that a fleet with one slow instance is a least-connections problem, that a warm-cache tier is a hashing problem, and that a sticky session is a state problem wearing a routing costume.

Katabench's System Design Studio starts there. The Scale the Web Tier fundamentals challenge asks for a web tier that survives losing an instance, and its deterministic rules check the required path through a load balancer, the redundancy behind it, and the bypasses you forgot to forbid. The capacity simulation then reports p99 latency, throughput, and the component that saturates first under a versioned traffic scenario, which is where an uneven fleet shows up as a number rather than a feeling. It is a reproducible model for learning, not a load test. The tracks overview explains how the studio sits beside the code tracks, and the nine fundamentals put this block in context.