Load Balancing
One server can only do so much. When a website outgrows a single machine — too many requests, or the
need to survive a machine dying — the answer is to run many identical servers and spread the
traffic across them. The thing that does the spreading is a load balancer: a traffic
cop sitting in front of a fleet of backends, deciding, request by request, "you go to server 3, you go
to server 7." Done well, it is invisible — the site just feels fast and never goes down. Done badly, it
sends everyone to the one server that is on fire, or scatters a user's shopping session across five
machines that each remember nothing.
Load balancing is where the
client–server model meets
fault
tolerance: it is simultaneously how you scale out (add capacity by adding
machines) and how you stay up (route around a dead machine). This page is about how it actually
decides — the layers it can work at, the algorithms it uses, and one algorithm, consistent
hashing, so elegant it is worth building from scratch.
Layer 4 vs layer 7: how much does the balancer understand?
Load balancers come in two broad kinds, named after the
OSI layer
they operate at — and the difference is essentially how much of the traffic they bother to read.
-
Layer 4 (transport-level). The balancer works with TCP/UDP connections. It sees IP
addresses and ports, not the contents. When a connection arrives it picks a backend and forwards
every packet of that connection there, blindly and very fast — it never parses the HTTP inside. Think
of it as sorting sealed envelopes by weight without opening them. Cheap, extremely high throughput,
but it cannot make decisions based on what the request is asking for.
-
Layer 7 (application-level). The balancer terminates the connection and reads the
actual HTTP request — the URL path, headers, cookies. Now it can route intelligently:
/images/* to the image servers, /api/* to the API fleet, a request carrying
a certain cookie to a specific backend. It can also do TLS termination, compression, and rewriting.
More work per request, but far smarter. This is what an
HTTP-aware balancer or
reverse proxy (nginx, HAProxy, Envoy) does.
The rule of thumb: L4 for raw speed and protocol-agnostic forwarding; L7 when routing decisions depend
on the content of the request.
The algorithms: how to pick a backend
Given a fleet of healthy backends, which one gets the next request? Several strategies, in rough order
of sophistication:
-
Round robin. Hand requests out in rotation: 1, 2, 3, 1, 2, 3, … Dead simple, and
fine when all backends are equal and all requests cost about the same.
-
Weighted round robin. Give beefier servers a bigger share — a machine with twice the
cores gets weight 2 and receives twice as many requests. Handles a heterogeneous fleet.
-
Least connections. Send the next request to whichever backend currently has the
fewest open connections. This adapts to reality: if one request happens to be slow and ties
up a server, that server stops receiving new work until it catches up. Better than round robin when
request costs vary a lot.
-
Hashing. Compute a hash of some key (the client IP, or a cache key) and use it to
pick the backend deterministically, so the same key always lands on the same server.
This is essential for caches and sticky routing — and it is where the interesting problem lives.
The trap in hash % N
Suppose you have N cache servers and you want each key to have a fixed home so you can find it
again. The obvious scheme:
\text{server}(\text{key}) = \operatorname{hash}(\text{key}) \bmod N
It works beautifully — until N changes. Add one server (N: 4 → 5), or lose one to a crash
(N: 4 → 3), and the modulus changes for almost every key at once. A key that hashed to
17 was on server 17 mod 4 = 1; now it is on 17 mod 5 = 2. Do the
arithmetic across all keys and you find that roughly all but 1/N of them move to a different
server. For a cache, that is a catastrophe: nearly every lookup suddenly misses, every miss
stampedes the origin database, and the moment you needed to add capacity — a traffic spike — is exactly
when you trigger a cache-wide meltdown.
Consistent hashing fixes this with a lovely geometric idea. Instead of mapping keys to
N buckets, map both keys and servers onto the same circle — a ring of
hash values, say 0 to 360°. To find a key's home, start at the key's position and walk
clockwise until you hit the first server; that server owns the key. When a server is
added or removed, only the keys in the arc between it and its neighbour are affected —
everything else keeps its home. Adding one node to a ring of N disturbs only about
1/N of the keys, not all of them.
Build consistent hashing and see the difference
Talk is cheap; let's measure it. Below we place nodes and keys on a ring, map each key to the next node
clockwise, then add one node and count how many keys changed owner — for
both schemes. Watch hash % N reshuffle almost everything while consistent hashing
moves only a small slice.
// A tiny deterministic string hash → an integer in [0, RING).
const RING = 3600;
function hash(s: string): number {
let h = 2166136261;
for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = (h * 16777619) >>> 0; }
return h % RING;
}
const keys = Array.from({ length: 2000 }, (_, i) => "key" + i);
// ---- Scheme 1: hash % N (map keys straight into N buckets) ----
function mapMod(nodeCount: number): Map<string, number> {
const m = new Map<string, number>();
for (const k of keys) m.set(k, hash(k) % nodeCount);
return m;
}
// ---- Scheme 2: consistent hashing (nodes + keys on the same ring) ----
function ringPositions(nodes: string[]): { node: string; pos: number }[] {
return nodes.map((n) => ({ node: n, pos: hash(n) })).sort((a, b) => a.pos - b.pos);
}
function mapRing(nodes: string[]): Map<string, string> {
const ring = ringPositions(nodes);
const m = new Map<string, string>();
for (const k of keys) {
const h = hash(k);
// first node clockwise (pos >= h); wrap to the first node if none
const owner = ring.find((r) => r.pos >= h) ?? ring[0];
m.set(k, owner.node);
}
return m;
}
function moved<T>(before: Map<string, T>, after: Map<string, T>): number {
let n = 0;
for (const k of keys) if (before.get(k) !== after.get(k)) n++;
return n;
}
// Start with 4 nodes, then ADD a 5th, and compare the churn.
const nodes4 = ["A", "B", "C", "D"];
const nodes5 = ["A", "B", "C", "D", "E"];
const modBefore = mapMod(4), modAfter = mapMod(5);
const ringBefore = mapRing(nodes4), ringAfter = mapRing(nodes5);
const modMoved = moved(modBefore, modAfter);
const ringMoved = moved(ringBefore, ringAfter);
const pct = (x: number) => ((100 * x) / keys.length).toFixed(1) + "%";
console.log(`Adding one node to a fleet of 4, over ${keys.length} keys:\n`);
console.log(` hash % N moved ${modMoved} keys (${pct(modMoved)}) ← almost everything!`);
console.log(` consistent hash moved ${ringMoved} keys (${pct(ringMoved)}) ← only ~1/N`);
console.log(`\nIdeal churn when going 4 → 5 nodes is about 1/5 = 20%.`);
The numbers speak for themselves: hash % N typically moves ~80% of keys, while consistent
hashing moves close to the theoretical minimum of ~1/N. That single property is why consistent hashing
underpins distributed caches (memcached clients), sharded databases, and
Dynamo-style
stores.
Plain consistent hashing has a wrinkle: with only a handful of nodes hashed onto the ring, their
positions are uneven, so one node might own a giant arc (and get hammered) while another owns a sliver.
The fix is virtual nodes: hash each physical server to the ring many times
(say 150 points each, "A#1", "A#2", …). Now each physical node owns 150 small scattered arcs instead
of one big one, the load evens out by the law of large numbers, and when a node dies its share is
redistributed smoothly across all the others rather than dumped entirely on its single
clockwise neighbour. Real systems always use virtual nodes.
Health checks, sticky sessions, and where the balancer lives
Choosing a backend is only half the job. Three more concerns make a load balancer real:
-
Health checks. A balancer must not send traffic to a dead server. So it continually
probes each backend — a periodic
GET /health or a TCP connect — and takes any backend
that fails out of the rotation, adding it back only once it passes again. This is the mechanism that
turns "a server crashed" into "nobody noticed": the balancer simply stops routing there. It is the
concrete face of fault tolerance.
-
Session affinity (sticky sessions). If a server keeps a user's session
in its own memory, then that user's every request must return to the same backend,
or they'll appear logged out. A balancer can pin a user to a backend (by a cookie or by hashing their
IP). But stickiness fights scalability: a pinned user cannot be moved off a hot server, and if that
server dies the session is lost. The better cure is to make servers stateless —
push session state into a shared store (a database or Redis) so any backend can serve
any request, and stickiness becomes unnecessary. Statelessness is what makes a fleet freely
load-balanceable.
-
Where the balancing happens. It can live at several places at once:
DNS-based (return different server IPs to different clients — cheap and global, but coarse
and slow to react because DNS is cached); a dedicated load balancer (a box or service in
front of the fleet — precise, health-aware, the workhorse); and anycast (many data centres
announce the same IP, and the internet's routing delivers each user to the nearest one —
used by CDNs and big DNS providers to steer traffic geographically). Large systems layer all three.
The seductive thing about server = hash(key) % N is that it works perfectly in
every test, every demo, every steady-state day. It only detonates at the exact moment you change
N — add a shard to grow, or lose one to a crash — and then it moves nearly every
key at once. For a cache that means a near-total miss storm slamming your origin database
precisely when you were already under load; for a sharded datastore it means moving almost all your
data to rebalance a single new node. The mistake is invisible until the worst possible moment. Reach
for consistent hashing (with virtual nodes) whenever keys must map to a
changing set of servers — it caps the churn at ~1/N instead of ~all. Plain
hash % N is only safe when N genuinely never changes.