Session affinity, consistent hashing, and the right fix

A user logs in. Their session lives on backend B2. The next request routes to B3. Session not found. They are logged out mid-flow. This is what happens when your application stores state on a single backend and you rely on session affinity to hide it — until affinity breaks.

Why sticky sessions exist

Some applications store session state on the backend — in memory, or in a local file. If the next request routes to a different backend, the state is missing: the user is logged out, the shopping cart is empty, the upload context is gone.

Sticky sessions (session affinity) make the LB route all requests from one client to the same backend. The client’s requests are “pinned” to one server.

Cookie-based affinity

The LB sets a cookie on the first response:

Set-Cookie: LB_ROUTE=backend_2; Path=/

On every subsequent request, the browser sends this cookie. The LB reads it and routes to backend_2.

Advantages:

• Survives client-IP changes (mobile handover, NAT failover).
• Allows graceful failover: if backend_2 is unhealthy, the LB can pick a new backend and update the cookie.

Disadvantage: Cookie-based affinity requires HTTP. Non-HTTP protocols cannot use it.

IP-hash affinity

Route by Hash(client_IP) % num_backends. No cookie needed — works for any protocol.

Disadvantages:

• Breaks when the client IP changes (mobile handover, VPN reconnect).
• Clusters badly: 50 clients behind one corporate NAT all hash to the same backend — that backend gets 50× the load of others.

The right fix: externalized session state

Store session data in a distributed cache (Redis, Memcached, DynamoDB) keyed by session ID. Every backend reads from and writes to this store.

Now the LB can route requests freely using power-of-two-choices. No affinity needed. No pinning. Session data survives backend failures because it is in Redis, not in memory on one backend.

This is the pattern used at Netflix, Airbnb, Shopify, and any service that scales horizontally.

Consistent hashing: for cache locality, not session state

Session affinity is about user state. Consistent hashing is about cache locality: routing a cache key to the same backend so you get a cache hit instead of a miss.

Problem with round-robin for caching:

• Request user:42 → B1 (cached there).
• Next request user:42 → B2 (cache miss, fetches from DB).
• No locality, no benefit from caching.

Consistent hashing maps each key to a point on a hash ring. Backends are also mapped to points (with many virtual nodes per backend to spread them evenly, ~150–300). A key routes to the nearest backend clockwise on the ring.

Key property: When a backend joins or leaves, only ~1/N keys remap. All other keys stay on the same backend. This minimizes cache disruption on topology changes.

Lookup cost: O(log N) with a sorted tree (binary search over virtual node positions).

Use consistent hashing for:

• Distributed caches (Memcached shards, Redis cluster).
• Database sharding (route by shard key).
• Sticky request routing for cache locality (media encoding jobs, analytics aggregations).

Do not use consistent hashing for general request balancing — power-of-two-choices adapts to real-time load, consistent hashing does not.

Rendezvous hashing (highest-random-weight)

Alternative to ring-based consistent hashing:

1. For each backend, compute Hash(key, backend_id).
2. Route to the backend with the highest hash value.

No ring, no virtual nodes — simpler to implement. O(N) per lookup but for small N (<100 backends) the difference is negligible. Hash distribution is often more uniform than ring-based consistent hashing in practice. Some CDNs and Facebook’s TAO use rendezvous hashing for sharding.