Load Balancing Algorithms: Each One Fixes the Last One's Flaw

Spreading requests across a handful of servers sounds like the most trivial problem in distributed systems. You have three backends and a request; pick one, send it, done. A single call to rand.Intn(3) and you have a load balancer. Ship it.

It works right up until reality shows up. One backend runs on a bigger machine than the others. One request takes five seconds while the rest take five milliseconds. One client needs to land on the same server every time because that is where its session lives. One backend quietly dies and your perfectly random balancer keeps cheerfully sending it a third of all traffic. Each of these is a different way the naive answer breaks, and each classic load balancing algorithm is a response to one specific break.

So this is not a list of six algorithms. It is a chain. We start with the simplest thing that works, watch it fail, and reach for the next algorithm precisely because it fixes what the last one could not. Go for the code, but the progression is the point. Everything hangs off one interface:

// A Balancer picks the backend that should serve the next request.
type Balancer interface {
    Next(r *Request) *Backend
}

type Backend struct {
    URL         string
    Weight      int          // relative capacity, for weighted schemes
    ActiveConns int64        // in-flight requests, for least-connections
    Healthy     bool
}

Round robin: the honest starting point

The first real algorithm past "pick at random" is round robin: hand each request to the next backend in order, wrapping around at the end. Every server gets an equal turn, in a predictable rotation.

type RoundRobin struct {
    backends []*Backend
    counter  uint64
}

func (rr *RoundRobin) Next(_ *Request) *Backend {
    // atomic increment so concurrent callers each get a distinct slot
    n := atomic.AddUint64(&rr.counter, 1)
    return rr.backends[n%uint64(len(rr.backends))]
}

That atomic.AddUint64 matters: a load balancer is hammered by many goroutines at once, and a plain counter++ would race and hand two callers the same index. With the atomic, round robin is correct, lock-free, and about as cheap as dispatch gets.

Round robin makes one promise and keeps it: over time, every backend receives the same number of requests. The trouble is that equal is not the same as fair. Round robin assumes every server is identical and every request costs the same, and both assumptions are usually false. Send a 16-core box and a 2-core box the same request count and you have overloaded one while the other idles. That gap between equal and fair is the flaw the next algorithm exists to fix.

Weighted round robin: when servers are not equal

If one backend can handle three times the load of another, it should receive three times the traffic. Attach a weight to each server and distribute in proportion.

The obvious implementation is to expand the list, repeating each backend weight-many times, and round robin over that. It works, but it clusters: a server with weight 3 gets three requests in a burst, then nothing, which spikes load instead of smoothing it. The version real proxies use is smooth weighted round robin (this is Nginx's algorithm), which interleaves the picks so a weight-3 server is spread evenly through the rotation rather than bunched.

type SmoothWRR struct {
    backends []*Backend
    current  []int // running "credit" per backend
    mu       sync.Mutex
}

func (w *SmoothWRR) Next(_ *Request) *Backend {
    w.mu.Lock()
    defer w.mu.Unlock()

    total := 0
    best := -1
    for i, b := range w.backends {
        w.current[i] += b.Weight // each backend earns its weight in credit
        total += b.Weight
        if best == -1 || w.current[i] > w.current[best] {
            best = i // the most-owed backend wins this round
        }
    }
    w.current[best] -= total // and pays it back down
    return w.backends[best]
}

Each backend accrues credit equal to its weight every round; the one with the most credit is chosen and then charged the total weight back. Over a full cycle a weight-3 server wins three times as often, but the wins are spread out, not clumped. The spikes are gone.

Weighted round robin fixes static capacity differences. What it cannot see is dynamic load. Weights are configured ahead of time and never change, so if a "small" server happens to catch a burst of slow requests, weighted round robin keeps feeding it at its configured rate, blind to the fact that it is drowning right now. The weights describe capacity in theory, not load in the moment.

Least connections: react to real load

To respond to what is actually happening, stop counting turns and start counting work in flight. Least connections routes each request to the backend with the fewest active connections, so a server bogged down by slow requests naturally stops receiving new ones until it catches up.

func (lc *LeastConn) Next(_ *Request) *Backend {
    var best *Backend
    min := int64(math.MaxInt64)
    for _, b := range lc.backends {
        c := atomic.LoadInt64(&b.ActiveConns)
        if c < min {
            min, best = c, b
        }
    }
    return best // caller increments ActiveConns, decrements when the request finishes
}

This adapts to reality in a way round robin never can. Uneven request durations, a backend having a bad minute, a slow downstream: least connections routes around all of it automatically, because a struggling server accumulates connections and drops to the back of the queue. It is the first algorithm here that reacts to load instead of assuming it.

The cost is in that loop. To pick the minimum, least connections scans every backend on every request, which is fine for a handful of servers and painful for hundreds. Worse, under high concurrency the read-then-route is racy: many goroutines all observe the same least-loaded backend at the same instant and stampede it together, the very imbalance the algorithm was meant to prevent. Reading global state to make a local decision does not scale.

Power of two choices: the trick nobody teaches

Here is the algorithm that should be far more famous than it is. Instead of scanning all backends for the true minimum, pick two backends at random and route to the less loaded of the two. That is the whole idea.

func (p *P2C) Next(_ *Request) *Backend {
    a := p.backends[rand.Intn(len(p.backends))]
    b := p.backends[rand.Intn(len(p.backends))]
    // compare only these two, not the whole fleet
    if atomic.LoadInt64(&a.ActiveConns) <= atomic.LoadInt64(&b.ActiveConns) {
        return a
    }
    return b
}

It looks too simple to be good, and the result is genuinely surprising: sampling just two and taking the better one gives you load distribution nearly as even as scanning the entire fleet, at O(1) cost instead of O(N). The math behind it (the "power of two choices" result) shows that the maximum load across servers drops exponentially compared to pure random, while a single extra sample buys almost all of that benefit. And because two goroutines rarely sample the same pair, the herding problem that plagued least connections mostly evaporates.

This is not a toy. Power of two choices is what production systems actually reach for: it is the default in HAProxy's newer versions, in Twitter's Finagle, in Envoy's load balancing. It is the sweet spot of the whole progression, near-global quality at local cost, and most tutorials skip straight past it. If you remember one algorithm from this article, remember this one.

IP hash: when the client must stick

Everything so far assumes any backend can serve any request. Sometimes that is false: a client has a session, a cache, or an upload in progress tied to one specific server, and it must return to the same one. The classic answer is to hash the client's IP and use it to pick a backend deterministically.

func (h *IPHash) Next(r *Request) *Backend {
    sum := fnv.New32a()
    sum.Write([]byte(r.ClientIP))
    return h.backends[sum.Sum32()%uint32(len(h.backends))]
}

Same IP, same hash, same backend, every time. Sessions stay pinned. It is clean and it works, and it hides a trap that only springs when you change the pool. That % len(backends) is the whole problem: the moment you add or remove a single server, N changes, and almost every client suddenly hashes to a different backend. Every session breaks, every cache goes cold, all at once, for a one-server change. Naive hashing is stable only as long as the pool never changes, which is not a property real systems have.

Consistent hashing: stability under change

The fix is to hash servers and clients onto the same abstract ring, a space of, say, 0 to 2^32, and walk clockwise from the client's position to the first server on the ring. Add or remove a server and only the keys in that server's arc move; everyone else stays put.

type Ring struct {
    sorted []uint32          // hash positions, sorted
    owner  map[uint32]*Backend
}

func (r *Ring) Next(req *Request) *Backend {
    h := hash(req.ClientIP)
    // binary search for the first ring position >= h, wrapping around
    i := sort.Search(len(r.sorted), func(i int) bool { return r.sorted[i] >= h })
    if i == len(r.sorted) {
        i = 0 // past the end of the ring, wrap to the start
    }
    return r.owner[r.sorted[i]]
}

With naive hashing, removing one of N servers remaps roughly all keys. With consistent hashing, it remaps only about K/N of them, the ones that lived in the departed server's arc. In practice you also add virtual nodes, hashing each backend to many ring positions instead of one, so load spreads evenly and no single server owns a giant arc by accident. This is the same structure behind distributed caches and hash-based sharding: consistent hashing is less a load balancing trick than a general answer to "assign keys to nodes so that adding a node barely disturbs anything."

The failure no algorithm fixes: dead servers

Step back and notice what every algorithm above quietly assumes: that the backend it picks is alive. Round robin will dutifully route a third of your traffic to a server that died thirty seconds ago. Power of two choices will sample a corpse. Consistent hashing will pin a client to a backend that stopped answering. A flawless selection algorithm pointed at a dead server returns errors just as reliably as it would return successes.

So a real load balancer needs a layer none of these algorithms provide: knowing which backends are actually up. Two approaches, usually combined:

• Active health checks. Periodically probe each backend (a GET /healthz on a timer). Mark it unhealthy on failure, drop it from the pool, and keep probing so it can rejoin when it recovers.
• Passive health checks. Watch real traffic. If a backend starts returning errors or timing out, eject it without waiting for the next probe. This is the load balancer's version of a circuit breaker.

func (rr *RoundRobin) Next(_ *Request) *Backend {
    for i := 0; i < len(rr.backends); i++ {
        n := atomic.AddUint64(&rr.counter, 1)
        b := rr.backends[n%uint64(len(rr.backends))]
        if b.Healthy { // skip ejected backends, try the next slot
            return b
        }
    }
    return nil // whole pool is down; caller must shed or fail fast
}

This closes the loop with the rest of the resilience toolkit. Health-check ejection is the server-selection cousin of the circuit breaker a client uses to stop calling a dead dependency, and it sits alongside rate limiting that sheds load a service cannot serve. Load balancing is the third face of the same coin: rate limiting decides how much a server takes, retries decide when a client sends, and load balancing decides which server gets it. Get the selection perfect and skip the health checks, and you have built a very fair way to distribute failure.

The chain, at a glance

None of these is "the best." Each is the right answer to a specific pressure, and each was reached for because the previous one hit a wall.

Takeaways

• Start simpler than you think you need. For a small fleet of similar servers with similar requests, round robin or even plain random is genuinely fine. Reach for more only when a real flaw bites.
• Equal is not fair. Use weights when servers differ in capacity, and connection counts when requests differ in cost. Round robin conflates both and is blind to both.
• Power of two choices is the underrated sweet spot. Near-global load quality at O(1) cost, with none of least-connections' scanning or herding. It is what production proxies actually use, and it is one rand call away.
• Naive hashing breaks the instant the pool changes. If you need sticky routing, use consistent hashing with virtual nodes, or accept that adding one server will cold-cache all of them.
• The best selection algorithm still routes to dead servers. Health checks and ejection are not optional polish; they are the layer that makes every algorithm above actually work in production.

The lesson of the whole chain is that "load balancing" is not one problem with one answer. It is a sequence of increasingly specific pressures, capacity, live load, cost, stickiness, churn, failure, and each classic algorithm is the tool that answers exactly one of them. Knowing which pressure you actually have is most of knowing which algorithm to pick.