# Distributed Caching

## 1. When 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).

## 2. Partitioning 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.

## 3. Client-Side vs Proxy vs Cluster-Aware Routing

| Approach | How keys find nodes | Examples |
|---|---|---|
| client-side sharding | the client library hashes keys to a node list | Memcached clients (ketama), ioredis with manual shards |
| proxy | clients talk to a proxy that routes | twemproxy, Envoy Redis proxy, mcrouter |
| cluster protocol | nodes know the slot map; wrong node replies `MOVED` | Redis Cluster |

```
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)
```

## 4. Replication 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").

## 5. Hot 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.

| Problem | Mitigation |
|---|---|
| hot key (reads) | in-process L1 cache in front of it (short TTL); replicate the key under N suffixed names (`hot:{k}:1..8`) and read a random copy; read from replicas |
| hot key (writes) | shard the counter (`likes:post1:shard{0..15}`) and sum on read |
| big key (MB-sized value or million-member set) | split into smaller keys; avoid `KEYS`, `SMEMBERS` on huge sets; use `SCAN`/`HSCAN` |

## 6. Consistency 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 Hood: Why 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.

![Keys and virtual nodes sit on a hash ring and each key belongs to the next node clockwise; when a new node joins it takes over only the arcs just before its points, so about one Nth of keys move instead of almost all with modulo hashing](diagrams/01-consistent-hash-ring.svg)

## 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

| Need | Use |
|---|---|
| spread keys, minimal movement | consistent hashing with vnodes / Redis Cluster slots |
| same-node multi-key ops | hash tags `{...}` |
| survive node loss | replicas + automatic failover |
| hot read key | L1 cache, key replication, read replicas |
| hot counter | sharded counters |
| iterate keys safely | `SCAN` (never `KEYS`) |