DevPath
Tracks

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
Before: one big serversingle point of failure
Clients
Load balancer
App 1
App 2
App 3
Shared cache / databasestate lives here
Scaling out: the top box is the vertical-scaling ceiling, the rest is horizontal scaling. Because state sits in the shared store at the bottom, the balancer can send any request to any app server.

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) % n reshuffles almost every key when n changes.
  • 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/n of 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.

a
0
next
b
1
c
2
Round-robin over servers a, b, c. The counter points at a.
step 1 / 5

Round-robin ignores load and just rotates. The pointer wraps from c back to a.

a: 0
0
b: 0
1
c: 0
2
Least-connections starts with no requests in flight.
step 1 / 6

Each cell shows a server and its in-flight requests. Least-connections steered request 4 to b because b had just freed up.

OperationTimeNotes
Round-robin pickO(1)Counter modulo n
Least-connections pickO(n) or O(log n)Scan, or keep a heap
Consistent-hash lookupO(log V)Binary search over V virtual nodes
Add/remove a server (ring)about 1/n keys moveModulo 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.

Au1Bu2u3Cu4
A, B, C are servers; u1 to u4 are keys, drawn in clockwise order from the top. Each arrow goes to the first server clockwise. Add a server between u3 and C and only u2 and u3 would move to it; u1 and u4 stay put.

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)

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 % n remaps nearly everything when n changes. 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

  1. Vertical or horizontal scaling? Vertical is simplest and fine early; horizontal removes the ceiling and adds redundancy but requires stateless design and routing.
  2. 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.
  3. Why consistent hashing? It limits how many keys move when the server set changes, which protects caches and shards from mass reshuffles.
  4. 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

Related lessons