Distributed Caching

1When One Cache Node Isn't Enough

A single Redis or Memcached node eventually runs out of one of three things:

• memory — the working set no longer fits in one machine's RAM
• throughput — one node (and, for Redis, one main thread) can't serve the request rate
• availability — when the only node restarts, every request becomes a miss and the database takes the full load (04-caching_strategies/ §6)

A distributed cache spreads keys across many nodes (for capacity and throughput) and/or copies them (for availability).

2Partitioning Keys Across Nodes

Every client must agree on which node owns a key.

Naive modulo hashing — node = hash(key) % N — is simple and balanced, but adding or removing one node changes N, and almost every key moves:

N=4 → N=5: a key stays put only if hash % 4 == hash % 5  → ~20% stay, ~80% move

For a cache, "moved" means "miss" — growing the cluster triggers a near-total cache flush and a database stampede.

Consistent hashing places nodes and keys on the same hash ring (0 … 2³²−1); a key belongs to the first node clockwise from it. Adding a node only takes over the keys between it and its predecessor — about 1/N of keys move. Virtual nodes (each physical node placed at 100–200 points on the ring) smooth out the uneven arcs you'd get with a few random points, and let bigger machines take proportionally more vnodes.

Hash slots (Redis Cluster) — a fixed 16,384 slots: slot = CRC16(key) mod 16384; each master owns a range of slots. Resharding moves slots, not individual keys, and clients cache the slot → node map. Keys can be forced into the same slot with a hash tag: only the part inside {...} is hashed, so user:{42}:cart and user:{42}:profile live together and can be used in one multi-key command or Lua script.

3Client-Side vs Proxy vs Cluster-Aware Routing

client → node A: GET user:{42}:cart
node A → client: -MOVED 5474 10.0.0.12:6379     (slot 5474 lives on node C)
client → node C: GET user:{42}:cart             (and updates its slot cache)

4Replication and Failover

Partitioning alone means losing a node loses its 1/N of the cache. Replication adds copies:

• Redis: each primary has replicas (asynchronous replication). Sentinel (non-cluster) or the cluster itself detects a failed primary and promotes a replica. Writes acknowledged by the old primary but not yet replicated are lost on failover — acceptable for a cache, worth knowing if Redis holds sessions or locks.
• Memcached: no built-in replication; nodes are independent, and losing one is just losing that shard's cached data (by design — "it's a cache").

5Hot Keys and Big Keys

Partitioning spreads keys, not load. One celebrity key (product:iphone-launch, a global config blob) still lives on one node and can saturate it.

6Consistency Across Many Nodes and Many App Instances

• Multi-key operations work only when all keys are on the same node (hash tags).
• There's no cross-node transaction; invalidating 50 related keys across nodes is 50 independent operations — design for partial failure (05-cache_invalidation/).
• App-instance L1 caches must be invalidated by broadcast (pub/sub) — a sharded Redis Cluster supports sharded pub/sub (SPUBLISH) to keep that traffic from going to every node.

Under the HoodWhy Consistent Hashing Moves Only ~1/N of Keys▾

Map each node to several points on a ring by hashing "nodeA#0", "nodeA#1", …, and sort the points. To place a key, hash it and binary-search the sorted array for the first point ≥ the hash (wrapping around to index 0). Lookup is O(log V) for V virtual nodes.

When node E joins, it inserts its points. Each new point takes over exactly the arc between the previous point and itself — keys that previously belonged to whichever node owned the next point clockwise. No other arc changes. With V vnodes per node and N nodes, E ends up owning ≈ 1/(N+1) of the ring, so ≈ 1/(N+1) of keys move, all to E. Removal is the mirror image: only the departing node's keys move, scattered to its clockwise neighbours — which is why vnodes matter: without them, all of a dead node's load would land on a single neighbour.

Redis Cluster avoids the ring altogether by fixing the number of slots: membership changes are explicit slot migrations (CLUSTER SETSLOT … MIGRATING/IMPORTING, MIGRATE key by key), during which the source answers ASK redirections for keys already moved — so clients keep working while data is in transit.

⚠️ Common Pitfalls

1. hash % N sharding for a cache — scaling the cluster flushes most of the cache.
2. Multi-key commands across slots (MGET a b in Redis Cluster) → CROSSSLOT errors; use hash tags deliberately.
3. Hash-tagging everything into one slot — you've rebuilt a single node, now with extra steps.
4. Ignoring hot keys — one node melts while the rest idle.
5. Treating Redis replication as synchronous — acknowledged writes can vanish on failover.
6. KEYS * in production — blocks the node while it walks every key.

📋 Quick Reference

🎤 Interview Q&A

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

✅ Check yourself

Source: cache_distributed_caching_theory.md · generated by tools/build_lessons.py