Reliability & Scale · Lesson 08

Load Balancing

A single server has a ceiling. A load balancer turns many ordinary servers into one logical surface that can absorb traffic spikes, survive instance failures, and scale horizontally without clients ever knowing the difference.

Why one server is never enough

Picture a single toll booth on a highway. It works fine on a Tuesday morning. On a holiday weekend, a queue stretches for kilometres — not because the booth broke, but because one lane is a hard ceiling. The fix is to open ten booths and put a traffic officer in front who reads licence plates and waves cars to whichever lane is shortest.

That traffic officer is a load balancer. It sits in front of a group of identical server instances (the booths) and decides which one should handle each incoming request. It has three jobs: spread load evenly, steer traffic away from unhealthy instances, and do both without the caller noticing.

The four distribution algorithms

The balancer needs a rule for picking which server gets the next request. Four algorithms cover the vast majority of real deployments:

Consistent hashing: the ring trick

Ordinary hashing — server = hash(key) % N — collapses when you add or remove a server, because N changes and almost every key remaps to a different bucket. Consistent hashing places both servers and keys on a notional ring (0–2³²). A key maps to whichever server is next clockwise on the ring. Add a server? Only the keys between the new server and its predecessor shift; the rest stay put. Remove a server? Only its keys migrate to the next server clockwise. This keeps cache hit rates high during scale events.

L4 vs L7 load balancing

The OSI model layer at which the balancer operates determines what it can "see" and therefore how smart its decisions can be.

An L7 load balancer can, for example, route all requests to /api/video to a GPU-equipped fleet and everything else to general-purpose nodes — something L4 cannot do because it never looks at the URL.

Health checks and connection draining

Health checks are periodic probes the balancer sends to each instance — usually an HTTP GET /health that returns 200 when the server is ready, or a TCP handshake for L4. If an instance fails N consecutive checks, the balancer removes it from rotation and stops sending new requests to it. When it recovers, it re-enters automatically.

Connection draining (sometimes called "deregistration delay") is what happens when you intentionally take a server out of rotation for a deploy. Rather than cutting existing connections immediately, the balancer lets in-flight requests finish (typically up to 30–60 seconds) before fully removing the instance. Clients never see an abrupt disconnection.

# Minimal NGINX upstream health-check config (simplified)
upstream api_servers {
    least_conn;                    # algorithm
    server 10.0.0.1:8080;
    server 10.0.0.2:8080;
    server 10.0.0.3:8080;
}

server {
    location /api/ {
        proxy_pass http://api_servers;
        proxy_connect_timeout 2s;    # fail fast on dead instance
        proxy_next_upstream error timeout;
    }
}
# Active health checks require NGINX Plus or the health_check module

Sticky sessions

Some applications store per-user state in server memory (shopping cart, WebSocket context). If round-robin sends the same user to a different instance each time, that state is lost. Sticky sessions (also called session affinity) solve this by tagging each user — often via a cookie — and always routing them to the same instance.

The trade-off: stickiness re-introduces the uneven-distribution problem. If one "sticky" instance gets a surge of heavy users, the others sit idle. The cleaner long-term answer is to move session state out of the server (to Redis, a database, or a JWT) so that any instance can serve any user — making stickiness unnecessary.

Load balancer vs API gateway

Students often conflate these two. They overlap but are not the same. An API gateway (see the API gateway lesson) focuses on API-level cross-cutting concerns: authentication, rate limiting, request transformation, routing to different microservices, and API versioning. A load balancer focuses on distributing traffic across identical replicas of one service. In practice, modern systems often layer them: the gateway handles API logic at the edge, and a load balancer sits behind it distributing traffic within each service cluster.

Under the hood: how each algorithm actually picks a backend

Round-robin — a simple counter

The load balancer maintains a single atomic integer, the next-index counter. Every time a new connection arrives it reads next_index % N to pick the backend, then increments the counter. On a three-node pool the sequence is 0, 1, 2, 0, 1, 2, … The counter never resets — it just wraps via modulo. This is why adding or removing a server changes which backend gets the next request, but never changes the per-request cost.

Least-connections — a per-backend counter

Each backend has a live active connection count. On each new request the balancer scans the pool and picks the entry with the lowest count; it increments that counter when the connection opens and decrements it when it closes. For short HTTP requests the counters fluctuate so fast that the result approximates round-robin. The algorithm shows its value for long-lived connections (WebSockets, streaming): a slow backend accumulates a higher counter and receives fewer new connections automatically.

Consistent hashing — a worked ring example

Hash space is the integers 0–2³² (about 4.3 billion). Both servers and keys are placed on this ring by hashing their identifiers. A key maps to the first server clockwise from its position.

Setup (3 servers, ring positions simplified to 0–100):

Adding server-D at position 35:

In practice, each server is given multiple virtual nodes (typically 100–200 per real server) spread around the ring. Without virtual nodes, a 3-server ring leaves large arcs unbalanced: the server with position 10 owns arc 80→10 (30 units), while the one at 45 only owns 10→45 (35 units). Virtual nodes make the distribution statistically uniform.

Health-check mechanics and connection draining

A typical active health check sends an HTTP GET /healthz every 5–10 s. The balancer tracks a rolling window: after N consecutive failures the backend is marked unhealthy and removed from the pool; after M consecutive successes it is re-added. The thresholds (N=2, M=3 are common) prevent flapping on transient timeouts.

Connection draining runs when a backend is voluntarily taken out (deploy, scale-down). The balancer stops routing new requests to it, waits up to the drain timeout (typically 30–60 s) for in-flight requests to complete, then severs the connection. From the client's perspective no request is interrupted.

How to debug & inspect load balancing

The key insight: to know which backend served a request, the backend (or the load balancer) must add a header. Most production load balancers (AWS ALB, NGINX, HAProxy) can be configured to inject an X-Upstream-Server or X-Served-By header. Without it you are guessing.

Debug checklist for uneven distribution / hot node:

1. Add X-Upstream-Server header to responses (NGINX: add_header X-Upstream-Server $upstream_addr).
2. Run 100 requests via curl in a loop and count how many hit each backend (| sort | uniq -c).
3. Check whether persistent connections (keep-alive / HTTP/2) are routing multiple requests per connection — switch to per-request balancing or least-connections.
4. If using consistent hashing, verify the key being hashed is uniformly distributed (user IDs are; IP addresses less so — many users behind a single NAT IP collapse to one backend).
5. Inspect the load balancer's backend metric counters (e.g. nginx_upstream_requests_total in Prometheus) — a sudden drop to zero on one backend means it failed a health check.

By the numbers

Make the math concrete. Scenario: a product-search cache tier at 12,000 req/s, currently running on 4 nodes (N=4). Each node can handle at most 4,000 req/s before latency degrades.

Formula: fraction remapped when adding the (N+1)-th node

Consistent hashing remaps approximately 1/(N+1) of keys when a new node is added. Naive modulo hashing (hash(key) % N) remaps nearly all keys because N changes.

Scale-out remap table

At 12,000 req/s, each remap is a cache miss — the request falls through to the origin database. The table shows the business impact of each node addition:

With consistent hashing, a 4→5 scale-out dumps ~2,400 req/s back to the origin for one replication cycle. With modulo hashing, it dumps ~9,000 req/s — likely exceeding the origin's capacity. (Google Maglev paper demonstrates this trade-off at planetary scale.)

Virtual nodes: reducing load variance

Without virtual nodes, three servers placed arbitrarily on a 0–100 ring produce unequal arc lengths. Virtual nodes (vnodes) give each real server multiple ring positions, making the distribution approach uniform.

Source: DeCandia et al. — Dynamo: Amazon's Highly Available Key-Value Store, §4.3 (virtual node load distribution).

Hot-shard math: when one key dominates traffic

If a single key ("trending product") generates 30% of total traffic, its assigned node absorbs 30% of 12,000 = 3,600 req/s. The remaining 11 nodes split the other 70% = 8,400 req/s ÷ 11 = 764 req/s each. Consistent hashing does not solve hot shards — it only solves even distribution of normal keys.

Decision math: how many nodes to stay within capacity

Per-node load at N nodes (ignoring hot shards, assuming even distribution): per_node = total_QPS / N. Solve for the minimum N that keeps each node under its capacity limit of 4,000 req/s:

Rule of thumb: size to <80% utilisation per node at expected peak, then add one extra node as buffer for hot keys. At 12,000 req/s with a known 30%-traffic hot key, 5 nodes is the break-even; 6 gives comfortable headroom.

Sources & further reading

• Cloudflare — What is load balancing?
• NGINX — HTTP load balancing
• AWS — Application Load Balancer concepts
• Google Research — Maglev: consistent hashing at scale