Load Balancing Algorithms

In the last lesson we gave the load balancer a job — be the single front door, spread requests across the pool — and then quietly skated past the interesting part: how does it decide which server gets the next request?

We even planted a myth to come back to. "A load balancer is just round-robin." Round-robin is one algorithm, the simplest one, and for a surprising number of systems it is exactly the right choice. But it rests on an assumption that the real world loves to break, and when it breaks it breaks badly — one server melting down while the box right next to it sits half asleep.

So this lesson is about the choosing. There are only a handful of algorithms that matter, and once you see what each one is for — what problem forced it into existence — you will never again pick one by cargo-culting a config file. The whole family boils down to a single question: what do you do when the requests, or the servers, aren't all the same?

Start with the one everyone starts with. Round-robin keeps a pointer and walks it around the pool: request 1 to server A, request 2 to server B, request 3 to server C, request 4 back to A, and around it goes.

That's the entire algorithm. It holds no state beyond a single counter, the decision is O(1), and it needs to know nothing about what any server is doing. It is the default in nginx and HAProxy for good reason: when your servers are identical and your requests are interchangeable, round-robin gives every box an exactly equal share, and nothing fancier can beat "perfectly even" — it can only tie it while spending more.

Hold onto that sentence, because it hides the entire rest of the lesson inside two words: identical and interchangeable. Round-robin distributes requests by count. It is betting that one request equals one unit of work, and that every server can do that work equally fast. When that bet is true, round-robin is not just fine — it is optimal, and reaching for anything cleverer is a mistake. When that bet is false, round-robin is the algorithm most likely to hurt you, precisely because it looks so fair.

Here is the crack. To a load balancer, these two requests look identical — each is "one request":

• GET /health — a server answers in under a millisecond and forgets it happened.
• POST /reports/export — the server churns for eight seconds building a 200 MB spreadsheet, pinning a CPU the whole time.

Round-robin hands them out one-two-three-four without ever asking how heavy they are. So picture a stream that's mostly light with the occasional monster. Round-robin faithfully drops a monster on server B, then keeps piling the next light requests onto B by strict rotation — while A and C, who happened to draw only feathers, sit there with spare capacity. B's queue backs up, its latency spikes, maybe it starts dropping requests. Your dashboard shows one server at 140% and three servers at 40%, and the load balancer did exactly what you told it to: it split the requests evenly by count.

This is the core insight of the whole lesson, so let it land: equal counts are not equal load the moment your requests stop being uniform. Everything else we cover is an answer to that one sentence. And it has a twin — the servers themselves are often not equal — which is where we go next.

The first way the world gets uneven is the servers. You rarely run a fleet of perfect clones. You've got three old 4-vCPU boxes and one shiny 16-vCPU box you added last quarter; or you're mid-deploy and half the fleet is the new, faster build. Plain round-robin sends the tiny box and the huge box the same number of requests, which either wastes the big one or crushes the small one.

Weighted round-robin fixes exactly this. You give each server a weight roughly proportional to its capacity — the 16-vCPU box gets weight 4, the 4-vCPU boxes get weight 1 — and the higher-weighted servers simply show up more often in the rotation. Over a full cycle the big box handles four requests for every one the small boxes handle. It's the same dumb-simple round-robin, now with a capacity dial. Envoy's round-robin is weighted by default for this reason; you set the weights and forget it.

Weighted round-robin fixes the server axis of unevenness. It does not fix the request axis — it still can't tell a health check from a 10-second export. For that, you need an algorithm that stops guessing and starts looking.

Round-robin and its weighted cousin are open-loop: they decide by a fixed formula and never check the result. The fix is to close the loop — route based on a live signal of how busy each server actually is. The cheapest such signal you already have for free is the number of requests currently in flight to each server.

That's least-connections: for each new request, send it to the server with the fewest open connections right now. Watch what this buys you. When server B draws that 8-second export, its in-flight count stays elevated for the whole 8 seconds — so least-connections automatically stops sending it new work until it drains, and the light requests flow to A and C instead. Nobody configured "B is busy." The open-connection count noticed for you. A slow or overloaded box quietly recedes from the rotation and rejoins when it recovers.

This is why least-connections (AWS calls it least outstanding requests, Envoy calls it least request) is the right default the moment your request durations vary — mixed short and long calls, uploads, streaming, anything where "one request" is a lie. A weighted version blends in capacity: a rough form is effective load = active_requests / weight, so a big box tolerates proportionally more in-flight before it stops drawing new requests.

It sounds strictly better than round-robin, and on a single load balancer it usually is. But it has a subtle failure mode at scale, and dodging that failure is what produced the algorithm most modern systems now reach for — which is the best place to actually watch all of this happen.

This is the one you have to feel, because the whole lesson lives in a gap between two words — count and work — and words slide right off. So below is a live pool of four servers under a real request stream, and you drive it.

Start with the request mix set to all equal and the algorithm on round-robin: the load bars stay level, exactly as promised — with uniform requests, round-robin is already optimal. Now drag the mix toward heavy-tailed so some requests are monsters. Watch one server redline while the others idle. That red bar is "equal count, unequal work." Leave the mix heavy and flip to least-connections or power-of-two — the fleet levels out in real time as the balancer steers work away from the busy box.

Then poke the other two ideas: give the servers different weights and compare round-robin to weighted; or pick hash, watch the same clients stick to the same servers, and hit add a server to feel the rehash storm — most flows jump boxes at once, caches go cold — the exact pain the next section's consistent hashing exists to prevent.

So far every algorithm has tried to spread requests as evenly as possible. Sometimes you want the opposite: you want the same client to land on the same server every time. Two reasons come up constantly:

• Cache locality. If user 42's data is already warm in server C's memory, sending user 42 back to C is a free cache hit; scattering them across the fleet means every box holds a cold, half-useful copy of everyone.
• Cheap affinity. Before you've built a shared session store, pinning a user to one box is a poor-man's way to keep their in-progress state reachable.

The tool is hashing: compute server = hash(client_ip) % N (nginx ip_hash, HAProxy source). The same IP always hashes to the same server — no lookup table, no coordination, just arithmetic. Clean.

Except for the % N. That N is the number of servers, and the whole scheme is chained to it. Add or remove a single box and almost every key remaps — user 42 that always hit C now hits A, and so does nearly everyone else. Every cache goes cold at once; every pinned session scatters. A routine deploy or one dead server triggers a fleet-wide stampede of cold misses. Hashing gave you affinity and then wired that affinity to the one thing that changes most often: how many servers you have.

Consistent hashing keeps the affinity and cuts the wire to N. Instead of mod N, imagine a circle. Hash each server to a point on the circle, then hash each key to a point too, and a key belongs to the first server clockwise from it. That's the whole trick.

Now add a server: it drops onto one arc of the circle and steals only the keys in that arc from its clockwise neighbor. Every other key stays exactly where it was. Remove a server and only its arc spills to the next one. The blast radius of a membership change shrinks from "almost everything" to roughly K/N keys — with K keys and N servers, a change touches about one server's share, not the whole ring. A deploy stops being a cache apocalypse.

Two refinements you should know the names of, because they show up in every real implementation:

• Virtual nodes. A handful of servers hashed to a handful of points lands lumpy — one server owns a huge arc and gets hammered. So each physical server is hashed to many points (dozens to hundreds), scattering its ownership into small slivers all around the ring. The distribution smooths out and removing a node spreads its load across many neighbors instead of dumping it on one.
• Bounded loads. Even with virtual nodes a popular key can make one server hot. Bounded-load consistent hashing caps each server at (1 + ε) times the average and lets overflow walk clockwise to the next server — affinity when there's room, spillover when there isn't.

This is production-grade, not theory: Envoy ships Ring Hash and Maglev (two consistent-hashing schemes; Maglev builds its lookup table far faster but reshuffles a bit more on change), and it's the backbone of how caches, CDNs, and sharded stores decide who owns what.

Back to that subtle failure mode of least-connections. On a single load balancer, "always pick the least-loaded server" is great. But big systems run many load balancer instances, each with its own slightly-stale view of the fleet. If all of them independently decide "server C has the fewest connections," they all stampede C at the same instant — and now C is the overloaded one. This is the herd: the globally-optimal greedy choice, made by many actors at once, is self-defeating. Maintaining one true, shared, always-fresh "least-loaded" ranking across a busy fleet is also just expensive.

The fix is almost silly, and it's one of the prettier results in systems: power of two choices. For each request, pick two servers at random, and send the request to the less-loaded of those two. That's it. No global ranking, no coordination, two cheap peeks.

And it works astonishingly well. Purely random placement leaves a worst-case pile-up that grows like log N / log log N; checking two random options instead of one collapses that to about log log N — an exponential improvement in the worst imbalance, for the price of one extra look (Mitzenmacher, 1996). Because each balancer randomizes its two picks, they don't all rush the same box, so the herd never forms. nginx calls it random two and describes it as "the poor man's least connections"; Envoy Gateway's default is Least Request, which uses power-of-two under the hood. The rule of thumb: on one load balancer, true least-connections is slightly better; the moment you have several balancers or can't afford a shared global view, power of two is the one you want.

Strip away the names and every algorithm is an answer to "which kind of uneven am I dealing with?" Here's the whole decision in one table:

Your situation	Reach for
Requests uniform and servers identical	Round-robin — nothing beats free-and-even
Servers are different sizes	Weighted round-robin — weights ∝ capacity
Request cost or duration varies a lot	Least-connections — route by the live busy signal
Many load balancers / no cheap global view	Power of two choices — near-optimal, no herd
Same client must hit the same box (cache/affinity)	Consistent hashing — with virtual nodes

If you remember one default, make it least-connections or power-of-two — they degrade gracefully when your assumptions are wrong, which they will be. Reach down to round-robin only when you've actually confirmed your requests are uniform, and reach sideways to hashing only when you specifically need affinity. Notice the table never says "pick the fanciest option" — it says match the tool to the unevenness you have.

Every step up from plain round-robin buys balance with something — and knowing the price is what keeps you from over-engineering:

• Least-connections buys adaptivity with state. The balancer now has to track in-flight counts per server. On one box that's cheap; run several balancers off one shared count and you get the herd — which is the entire reason power of two exists (it trades a little optimality for no shared state).
• Hashing buys affinity by coupling to N. Plain % N is a deploy-time cache bomb. Consistent hashing buys the affinity back — at the cost of a ring, virtual nodes, and more moving parts to reason about.
• Weighted buys capacity-awareness with a knob you must keep correct. Upgrade half the fleet and forget to update the weights, and you're now quietly mis-routing — a stale weight is worse than no weight.

But the trade-off underneath all of them is the one nobody mentions: you cannot choose well without measuring. This whole lesson assumed you know whether your requests are uniform or heavy-tailed — and most teams don't, until they graph it. If your p50 and p99 request durations are a hair apart, your requests are basically uniform and round-robin is genuinely fine; if p99 is 50× your p50, you have a heavy tail and least-connections or power-of-two will pay for themselves immediately. Look at the distribution first. The algorithm is the easy part; knowing which world you're in is the real work.

A few beliefs that sound right and quietly cost people:

• "Round-robin is fair." It's fair by count, not by work. The instant a health check and a 10-second export both count as "one request," equal counts stop meaning equal load. Fairness you can't measure isn't fairness.
• "Least-connections needs an expensive global ranking." True least-connections does — and worse, run several balancers off that ranking and they'll herd the same box. Power of two choices gets nearly the same balance from two random peeks, with no global state, and no herd. Cheaper and safer.
• "IP-hash gives me sticky sessions." It gives you affinity by IP, which evaporates the moment you add a box (plain % N), and a whole office or mobile carrier behind one NAT'd IP collapses onto a single hot server. Real, durable stickiness means externalizing state to a shared store — a different tool, coming later.
• "A smarter algorithm will fix my overloaded fleet." No algorithm creates capacity. If all four servers are pinned at 100%, every algorithm on Earth is just choosing which box drops the next request. Balancing decides where load goes; it never reduces how much there is. When the fleet is full, the answer is more servers, not a cleverer dispatcher.

Ten minutes and you'll see the whole lesson happen on real processes. The trick is to make your requests uneven on purpose — because with uniform requests, every algorithm looks identical, and that's exactly the trap.

1. Stand up three tiny servers with one deliberately uneven endpoint — a handler that sleeps a random 0–2 seconds before replying (that random sleep is your heavy tail). Any language; even three python -m http.server shims with a sleep will do.
2. Put a load balancer in front and start on the default. In nginx, an upstream block is round-robin unless you say otherwise; in HAProxy it's balance roundrobin. Fire a flood of concurrent requests with hey, wrk, or ab — say 200 in flight — and watch per-server CPU or in-flight count. You'll catch one box pinned while another coasts: equal count, unequal work, live.
3. Now flip one line — least_conn; in the nginx upstream (or balance leastconn in HAProxy), reload, and fire the identical flood. The pinned box relaxes; the fleet evens out. That one-line diff is this entire lesson.
4. Bonus: switch to random two; (nginx) / balance random(2) (HAProxy) and confirm you get least-connections-grade balance with none of the shared bookkeeping — power of two, in production, in one config line.

If you don't have a load balancer handy, the same experiment runs against any managed one (an ALB's least outstanding requests vs round-robin). The lesson isn't the config syntax — it's the muscle memory of inducing unevenness and watching the algorithm matter.

The load balancer's real job isn't "spread requests" — it's choose well when the world is uneven, and now you can pick on purpose:

• Round-robin — perfect when requests and servers are uniform; dangerous exactly because it looks fair when they aren't.
• Weighted round-robin — the same thing with a capacity dial for mismatched boxes.
• Least-connections — close the loop, route by the live in-flight signal; the right default when request costs vary.
• Power of two choices — least-connections' balance with none of its global-state cost or herd risk; the modern default across many balancers.
• Consistent hashing (+ virtual nodes, bounded loads) — when you need the same client on the same box without a deploy nuking every cache.

The thread through all of it: algorithms move load around; they never manufacture it. Match the algorithm to the kind of unevenness you actually have.

There's still a question we dodged: what is the load balancer even allowed to look at when it decides? A round-robin dispatcher can work blind at the transport layer; a "send this user to the cart service" rule has to read the request itself. That split — fast-and-blind L4 versus smart-and-content-aware L7 — is the next lesson.