Load Balancing and Scaling
Vertical versus horizontal scaling, why stateless services scale easily, and how round-robin, least-connections, and consistent hashing spread traffic.
intermediate40 min#load-balancing#scaling#consistent-hashing#stateless
Prerequisites: A Framework for System Design, Networking Basics: TCP/IP, DNS, HTTP, TLS
Why it matters
One server has a ceiling and a single point of failure. To handle more traffic and survive machine crashes you run many copies of your service and put something in front that decides which copy handles each request. That something is a load balancer. Choosing how it decides, and designing your services so any copy can answer any request, is the foundation of nearly every scalable architecture.
Intuition
Picture a supermarket. You can make one cashier faster (a better scanner, a stronger cashier), or open more lanes. The first is vertical scaling; the second is horizontal scaling. Lanes only help if a greeter points each customer to a sensible lane, and if any cashier can serve any customer. If customers must always return to "their" cashier because only that cashier remembers their basket, you have lost most of the benefit.
How it works
Vertical scaling means a bigger machine: more CPU, memory, disk. It is simple (no code change) but has a hard ceiling, gets expensive quickly, and leaves one machine as a single point of failure.
Horizontal scaling means more machines. It has no fixed ceiling and gives redundancy, but it forces you to deal with distribution: routing, shared state, and partial failure.
Stateless services make horizontal scaling easy. A stateless server keeps nothing between requests that another server would need. Session data, uploads, and counters live in a shared store (a database or cache), so the load balancer can send any request anywhere, and you can add or remove servers freely. State does not vanish; it is pushed to a place designed to hold it.
clients --> [ load balancer ] --> app server 1 --\
| --> app server 2 ---+--> shared cache / database
| --> app server 3 --/
health checks
A load balancer also runs health checks: it probes each server and stops routing to ones that fail. It may work at layer 4 (it sees only connections, fast and simple) or layer 7 (it understands HTTP, so it can route by path or header, terminate TLS, and so on). The balancer itself must not be a single point of failure, so it is usually run as a redundant pair or provided as a managed service.
Choosing a routing algorithm
- Round-robin: hand out servers in a fixed rotation. Simple and fair when requests cost about the same and servers are identical.
- Weighted round-robin: the same, but bigger servers appear more often.
- Least connections: send to the server with the fewest in-flight requests. Better when request durations vary a lot.
- Hash-based: hash a key (user id, client IP) so the same key always lands on the same server. Useful for caches and for session affinity ("sticky sessions"), but plain
hash(key) % nreshuffles almost every key whennchanges. - Consistent hashing: place servers and keys on a ring. A key belongs to the first server clockwise from it. When a server is added or removed, only the keys in one arc move, roughly
1/nof them. Each server is placed at many virtual nodes so the load evens out.
Each strategy picks differently. Here is round-robin handing out four requests, then least-connections reacting to a request that finishes.
Round-robin ignores load and just rotates. The pointer wraps from c back to a.
Each cell shows a server and its in-flight requests. Least-connections steered request 4 to b because b had just freed up.
| Operation | Time | Notes |
|---|---|---|
| Round-robin pick | O(1) | Counter modulo n |
| Least-connections pick | O(n) or O(log n) | Scan, or keep a heap |
| Consistent-hash lookup | O(log V) | Binary search over V virtual nodes |
| Add/remove a server (ring) | about 1/n keys move | Modulo hashing moves most keys |
A ring makes the consistent-hashing idea concrete. Servers and keys sit on a circle, and each key belongs to the first server clockwise.
Code: three strategies
The hash must be the same everywhere, so we implement a small 32-bit hash (FNV-1a followed by a mixing step) instead of relying on a language's built-in one.
import bisect
def h32(text):
h = 2166136261
for b in text.encode("utf-8"):
h ^= b
h = (h * 16777619) & 0xFFFFFFFF
h ^= h >> 16
h = (h * 0x85EBCA6B) & 0xFFFFFFFF
h ^= h >> 13
h = (h * 0xC2B2AE35) & 0xFFFFFFFF
h ^= h >> 16
return h
class RoundRobin:
def __init__(self, servers):
self.servers, self.i = servers, 0
def pick(self):
s = self.servers[self.i % len(self.servers)]
self.i += 1
return s
class LeastConnections:
def __init__(self, servers):
self.active = {s: 0 for s in servers}
def acquire(self):
s = min(self.active, key=lambda k: (self.active[k], k))
self.active[s] += 1
return s
def release(self, s):
self.active[s] -= 1
class HashRing:
def __init__(self, servers, vnodes=100):
self.vnodes, self.ring = vnodes, []
for s in servers:
self.add(s)
def add(self, server):
for i in range(self.vnodes):
bisect.insort(self.ring, (h32(f"{server}#{i}"), server))
def get(self, key):
i = bisect.bisect(self.ring, (h32(key), ""))
return self.ring[i % len(self.ring)][1]
rr = RoundRobin(["a", "b", "c"])
print("round-robin:", " ".join(rr.pick() for _ in range(6)))
lc = LeastConnections(["a", "b", "c"])
first, second, third = lc.acquire(), lc.acquire(), lc.acquire()
lc.release(second)
print("least-connections:", first, second, third, "then", lc.acquire())
keys = [f"user:{i}" for i in range(1000)]
ring = HashRing(["a", "b", "c"])
before = {k: ring.get(k) for k in keys}
ring.add("d")
after = {k: ring.get(k) for k in keys}
moved = [k for k in keys if before[k] != after[k]]
modulo_moved = sum(1 for k in keys
if h32(k) % 3 != h32(k) % 4)
print("ring moved:", len(moved))
print("moved only to d:", str(all(after[k] == "d" for k in moved)).lower())
print("modulo moved:", modulo_moved)function h32(text) {
let h = 2166136261;
for (const b of Buffer.from(text, "utf8")) {
h ^= b;
h = Math.imul(h, 16777619) >>> 0;
}
h ^= h >>> 16;
h = Math.imul(h, 0x85ebca6b) >>> 0;
h ^= h >>> 13;
h = Math.imul(h, 0xc2b2ae35) >>> 0;
h ^= h >>> 16;
return h >>> 0;
}
class RoundRobin {
constructor(servers) { this.servers = servers; this.i = 0; }
pick() { return this.servers[this.i++ % this.servers.length]; }
}
class LeastConnections {
constructor(servers) {
this.active = new Map(servers.map((s) => [s, 0]));
}
acquire() {
let best = null;
for (const [s, n] of this.active) {
if (best === null || n < this.active.get(best) ||
(n === this.active.get(best) && s < best)) best = s;
}
this.active.set(best, this.active.get(best) + 1);
return best;
}
release(s) { this.active.set(s, this.active.get(s) - 1); }
}
class HashRing {
constructor(servers, vnodes = 100) {
this.vnodes = vnodes;
this.ring = [];
servers.forEach((s) => this.add(s));
}
add(server) {
for (let i = 0; i < this.vnodes; i++) {
this.ring.push([h32(`${server}#${i}`), server]);
}
this.ring.sort((x, y) => x[0] - y[0] || (x[1] < y[1] ? -1 : 1));
}
get(key) {
const target = h32(key);
let lo = 0, hi = this.ring.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.ring[mid][0] <= target) lo = mid + 1; else hi = mid;
}
return this.ring[lo % this.ring.length][1];
}
}
const rr = new RoundRobin(["a", "b", "c"]);
console.log("round-robin:", Array.from({ length: 6 }, () => rr.pick()).join(" "));
const lc = new LeastConnections(["a", "b", "c"]);
const first = lc.acquire(), second = lc.acquire(), third = lc.acquire();
lc.release(second);
console.log("least-connections:", first, second, third, "then", lc.acquire());
const keys = Array.from({ length: 1000 }, (_, i) => `user:${i}`);
const ring = new HashRing(["a", "b", "c"]);
const before = new Map(keys.map((k) => [k, ring.get(k)]));
ring.add("d");
const after = new Map(keys.map((k) => [k, ring.get(k)]));
const moved = keys.filter((k) => before.get(k) !== after.get(k));
const moduloMoved = keys.filter((k) => h32(k) % 3 !== h32(k) % 4).length;
console.log("ring moved:", moved.length);
console.log("moved only to d:", moved.every((k) => after.get(k) === "d"));
console.log("modulo moved:", moduloMoved);Both versions print:
round-robin: a b c a b c
least-connections: a b c then b
ring moved: 241
moved only to d: true
modulo moved: 748
Adding a fourth server moved only keys that now belong to the new server, a number close to the ideal quarter, while modulo hashing moved most keys. For a cache cluster that difference is the gap between a small blip and a flood of cache misses.
Common pitfalls
- Hidden state. Local files, in-process caches, and in-memory sessions quietly break statelessness. A request that works on server 1 fails on server 2.
- No health checks. A balancer that keeps routing to a dead server turns one failure into user-visible errors.
- Modulo hashing with a changing pool.
hash % nremaps nearly everything whennchanges. Use consistent hashing or fixed slots. - Too few virtual nodes. With one point per server the arcs are uneven and one server can take far more than its share.
- The balancer as a bottleneck. It needs redundancy and capacity too; it is just another service.
- Scaling the wrong tier. Adding app servers does not help if the database is the bottleneck.
Practice
Weighted round-robin easy
Hint
Expand each server into the list according to its weight.
Show solution
Given weights a:3, b:1, build the rotation a a a b and cycle through it. This is correct but bursty; smoother variants interleave the picks. Either way each pick is O(1).
When is least-connections better than round-robin? easy
Hint
Think about requests with very different durations.
Show solution
If some requests take milliseconds and others take seconds, round-robin can pile several slow requests on one server by chance. Least-connections sees the in-flight count and steers new work to idle servers. When all requests cost about the same, the two behave almost identically.
Remove a server from the ring medium
Hint
Delete its virtual nodes. Where do its keys go?
Show solution
Remove every (hash, server) entry for that server. Each key that was on its arcs now falls to the next virtual node clockwise, so its load spreads across the remaining servers rather than dumping on a single neighbor. Keys on other servers do not move.
Make a session service stateless medium
Hint
Where should the session live if no server owns it?
Show solution
Store the session in a shared cache keyed by a session id carried in a cookie, or use a signed token that carries the data itself. Any server can then read it. The trade-off is an extra network hop per request, or a larger token that cannot be revoked easily.
Interview questions
- Vertical or horizontal scaling? Vertical is simplest and fine early; horizontal removes the ceiling and adds redundancy but requires stateless design and routing.
- What does a stateless service mean and why does it matter? No request-specific state lives on the server between requests, so any instance can serve any request and instances are interchangeable.
- Why consistent hashing? It limits how many keys move when the server set changes, which protects caches and shards from mass reshuffles.
- How does a load balancer detect a failed server? Active health checks (periodic probes) and passive checks (watching real request failures), then it stops routing there.
Interviewers look for: recognizing state as the real obstacle to scaling out, knowing at least two balancing algorithms and when each fits, and spotting that the load balancer needs its own redundancy.
Quick check
A cache cluster has 4 nodes and keys are routed with hash(key) % 4. You add a fifth node and switch to % 5. What happens?
Finished this lesson?
Further resources
- Load balancing (Wikipedia) (article)
- Consistent hashing (Wikipedia) (article)
- NGINX: HTTP load balancing (docs)