Stateless vs Stateful Load Balancing

Same traffic, two different questions

Every load balancer answers one question: which backend should handle this request? A stateless load balancer answers that fresh, from the request alone, every single time. A stateful load balancer additionally answers a second question — "have I seen this client before, and did I already promise them a particular backend?" — and that second question only works if something, somewhere, remembers the answer between requests.

That "somewhere" is the axis this lesson actually cares about. Stateless vs. stateful is the label people use, but the engineering decision underneath it is where does the remembered binding live — nowhere, in the client, or in the load balancer itself — because that location is what determines how each approach scales, and how it breaks.

Stateless load balancing: no memory required

A stateless load balancer makes every routing decision as a pure function of the request itself — client IP, URL, headers — with nothing looked up and nothing written down. The canonical example is IP-hash routing:

backend = hash(client_ip) mod N

Given the same client IP and the same backend count N, this formula always lands on the same backend — not because anyone remembered the client, but because the arithmetic is deterministic. Any load balancer instance, including one that just booted and has never seen this client before, computes the identical answer. That is what "stateless" means in practice: no shared table, no session store, no coordination between load balancer replicas — each one independently agrees with every other one just by running the same formula on the same input.

This is also why stateless load balancers scale so well horizontally: you can add or remove load balancer instances freely, because none of them hold client-specific state that would need to be replicated or migrated when the fleet changes shape.

Stateful load balancing: three different places to hide the memory

Stateful load balancing pins a client to one backend across multiple requests — useful when the backend holds something the client needs back, like an in-memory session or a live WebSocket. But "stateful" is doing a lot of work as a single label, because there are three genuinely different ways to implement pinning, and only two of them actually store anything.

1. Computed pinning — this is still stateless, don't let the name fool you

It's tempting to look at backend = hash(client_ip) mod N again and call it "stateful affinity," since it has the effect of always sending the same client to the same backend. Resist that label. Nothing about the mechanism changed from the stateless example above — it is the identical formula, recomputed fresh on every request, with no table and no memory anywhere. The only thing that changed is what we're using it for.

That reuse is also its weakness. The pinning only holds as long as N — the backend count — stays fixed. Scale the fleet up or down and most clients get silently remapped to a different backend mid-session, because the same arithmetic now produces different answers. (Consistent hashing exists specifically to soften this: it remaps only roughly 1/N of clients on a resize instead of nearly all of them — but the mechanism is still a stateless computation, not stored state.)

2. Cookie affinity — the state lives in the client

Here the load balancer makes a routing decision once, then writes that decision into a cookie it hands back to the client, e.g. Set-Cookie: lb-backend=srv-2. On every later request the client presents the cookie, and the load balancer just reads it — no lookup, no table, no memory of its own. The load balancer stays just as horizontally scalable and memory-less as a stateless one; the binding is stored client-side, not server-side. The catch is that it only works where there's a cookie (or an equivalent client-carried token, like a URL parameter) to carry it: plain HTTP/HTTPS with a client willing to store and return it. It's a poor fit for raw TCP/UDP load balancing or clients that strip cookies.

3. A server-side binding table — genuine stored state

The third option is what people usually picture when they hear "stateful": the load balancer, or a shared store behind it, keeps an explicit map — client_ip → backend or session_id → backend — and consults it on every request. This is real, stored, server-side state. It has to be sized, kept consistent across load balancer replicas (or centralized in something like Redis), and rebuilt or failed over carefully if the load balancer restarts — costs the first two options don't carry at all.

So the honest taxonomy isn't "stateless (hash) vs. stateful (everything else)." It's three buckets, separated by where the binding lives: nowhere (computed), the client (cookie), or the server (binding table). Only the last one is "stateful" in the sense of costing the load balancer memory and operational overhead — the first is stateless doing double duty, and the second keeps the load balancer stateless while the client carries the memory.

The state you keep even without affinity: the flow table

Every proxying L4 balancer holds one more kind of state that has nothing to do with sessions: a connection (flow) table mapping each live 5-tuple to its chosen backend, consulted per packet so a TCP stream isn't sprayed across backends mid-connection. Its lifetime is one connection, not one user session — but it is real server-side state: if the LB instance dies, its flow table dies with it, and every connection it was carrying resets even though the backends are healthy.

That is why horizontally-scaled L4 tiers behind ECMP either replicate flow state between instances or — the Maglev approach — make the flow table recomputable: hash the 5-tuple with consistent hashing so any replica, receiving any packet of the flow, independently derives the same backend, turning per-flow state back into a stateless computation.

Worked example: a router's ECMP rebalance reshuffles a long-lived flow from LB replica A to LB replica B mid-connection. With a local-only flow table, B has no entry for this 5-tuple, picks a different backend, and the mid-stream segments land on a server with no such connection — RST, the client's transfer dies. With consistent 5-tuple hashing, B computes the same backend A would have, and the flow survives the reshuffle without A and B ever talking to each other.

Notice what happened: this is bucket 1 (computed) applied at the packet level — the same nowhere/client/server taxonomy resolves it. The flow table is bucket-3 state with a per-connection lifetime; Maglev-style consistent hashing moves that binding back into the "lives nowhere" bucket.

Choosing: source-IP affinity vs. cookie affinity

Both mechanisms achieve the same visible behavior — a client keeps landing on the same backend — but they fail in opposite situations, which is exactly why the choice matters more than the fact that both are commonly grouped under "session affinity."

The practical recommendation: prefer cookie affinity for ordinary HTTP/HTTPS applications where you control the client and can rely on it returning a cookie — it survives the client IP changes that matter more often than people expect, since mobile carriers rotate IPs mid-session and corporate NAT can put thousands of users behind a single address that a naive source-IP hash would then unfairly pile onto one backend. Fall back to source-IP hashing only when you can't inject a cookie at all — raw TCP/UDP load balancing, non-browser clients, or an L4 tier in front of a non-HTTP protocol. And where the architecture allows it, prefer neither: push session state into a shared store such as Redis so any backend can serve any request, and go back to plain stateless load balancing — it's simpler to operate and never needs to worry about remapping when the fleet resizes.

Sources: NGINX documentation on the ip_hash and sticky-cookie modules for reverse-proxy load balancing; AWS Elastic Load Balancing documentation on duration-based and application-controlled (cookie) sticky sessions; HAProxy configuration manual, sections on balance source and cookie-based persistence; Google Cloud Load Balancing documentation on session affinity types (client IP, generated cookie, and HTTP cookie); and standard consistent-hashing references (Karger et al., "Consistent Hashing and Random Trees," 1997) for the remapping-on-resize behavior of hash-based affinity.