41. Design a Distributed Cache

Tests: consistent hashing, replication, eviction, hot keys, cluster membership, failure handling.

41.1 Requirements

Functional

GET k / SET k v [TTL] / DELETE k.
High throughput; low latency (sub-ms).
Optional: TTL, atomic counters, list/set operations.

Non-functional

Sub-millisecond P99 read.
1M+ ops/sec total.
Survive node failure with no data loss for cache (or small loss tolerable).
Easy to scale out.
Multi-tenant.

This is essentially: design Memcached / Redis Cluster.

41.2 Architecture

[ Client ]──hashes key──→[ Node N (selected via consistent hashing) ]
                                    │
                            in-memory hash map
                            optional persistence
                            optional replication to N+1
[ Cluster membership service ] (gossip or coord)

41.3 Partitioning: consistent hashing

(See chapter 17.) Hash both keys and nodes onto a ring; key → first node clockwise.

Virtual nodes (vnodes): each physical node maps to many ring positions → smooth load distribution + better rebalancing.

When a node joins/leaves: only ~K/N keys move. With vnodes, work distributed evenly.

Alternative: rendezvous (HRW) hashing

For each key, score hash(key, node_i); pick max. Same K/N rebalancing, no ring needed, supports node weights naturally.

41.4 Routing

Client-side

Client knows the cluster topology (membership map). Hashes locally; sends to right node directly. Used by Memcached, Redis Cluster smart clients.

Pros: 1 hop. Cons: every client must know topology; rebalancing means client refresh.

Proxy

Client sends to any proxy; proxy routes. (Twemproxy, Envoy.)

Pros: clients don't care about topology. Cons: extra hop.

Server-side redirect

Client sends to any node; if not local, node forwards or returns redirect (Redis Cluster MOVED/ASK).

41.5 Storage on each node

In-memory hash map (concurrent; sharded per CPU core to reduce locks).
Doubly linked list for LRU eviction.
Slab allocator (Memcached) or jemalloc (Redis) to manage memory fragmentation.

Eviction

When memory full:

LRU (default Memcached).
LFU.
Random sampling (Redis approximate LRU/LFU).
TTL-based (volatile-ttl).

Threading

Memcached: multi-threaded per connection.
Redis: single-threaded for ops; multi-threaded I/O optional. Single-thread = simple atomic semantics, no locks; CPU-bound ceiling per node.

41.6 Replication

Cache often runs without replication (loss is tolerable). For higher durability:

Async replication to N+1 (next node clockwise).
On primary failure, replica promotes.

Redis: master/replica per slot; cluster auto-failover via gossip + voting.

41.7 Cluster membership

Nodes need to know each other. Two approaches:

Coordinator (etcd / ZooKeeper)

Membership stored centrally; nodes watch for changes.

Pros: simple; consistent view. Cons: coordinator is critical infra.

Gossip

Each node periodically exchanges state with random peers. Eventually consistent view.

Pros: no central dependency; scales. Cons: convergence takes time; transient inconsistencies.

Redis Cluster uses gossip. Cassandra too.

41.8 Hot keys

Same key getting hammered (a viral product page).

Single shard becomes the bottleneck.
CPU + network saturated.

Mitigations:

Replicate hot keys to multiple shards; clients shard sub-key (hash of key + random suffix).
Local in-process cache in clients for top-N.
Detect hot keys via sampling at the proxy/client; auto-promote to client-side cache.

41.9 Failure handling

Node failure

Detect via heartbeat / gossip.
Mark down.
Reroute requests.
For cached data: requests miss → backing store handles.
For replicated data: promote replica.

Network partition

Minority side may serve stale or refuse.
Cache typically AP (serve possibly-stale during partition).

Split brain

Can occur during rebalance + partition.
Versioning (epoch) on cluster topology resolves.

41.10 Persistence (optional)

Pure caches usually skip; lose data on restart, repopulate from DB.

If durable:

Snapshot (RDB): periodic memory dump. Cheap; loses recent writes.
AOF (append-only file): every write logged. Replay on startup. fsync per write expensive.
Tiered storage: hot in RAM, cold in SSD. Used by Anna, Pelikan.

41.11 Multi-tenancy

Many users sharing one cache cluster:

Per-tenant memory quotas (no one starves).
Per-tenant rate limits.
Namespaced keys (tenant:foo:key) for accounting and eviction.

Without isolation, one bad tenant evicts everyone else's data.

41.12 Read-through / write-through (recap)

Some caches integrate with DB:

Read: cache miss → cache reads from DB → caches → returns.
Write: client writes to cache; cache writes to DB.

Most production caches are dumb stores; app handles read-through / write-through.

41.13 TTL & eviction policies (recap from chapter 9)

TTL per key (or default).
Active expiration: scan and remove expired (Redis does sample-based).
Lazy expiration: check on access.
Default eviction: LRU; configurable.

41.14 Sketch for interview

[Client] → hash(key) → ring → node N
                                  │
                         [in-mem hashmap + LRU + TTL]
                                  │
                         [async repl to N+1]
                                  │
                  cluster membership: etcd or gossip

Hot key path:
  client noticed key X very hot → cache locally with short TTL → only on miss → cluster lookup

41.15 What an interviewer wants

Consistent hashing with vnodes.
Per-node in-memory hash map + LRU eviction + slab allocator.
Replication trade-off (cache often tolerates loss).
Hot key strategies: local cache + replication + sampling.
Membership: gossip or coordinator.

41.16 Real systems to reference

Memcached: simple, multi-threaded, no persistence, client-side routing.
Redis Cluster: rich data types, gossip, slot-based partitioning.
DynamoDB DAX: managed cache for DynamoDB; write-through.
Anna: Berkeley research cache; tiered + autoscaling.
Twitter cache (Pelikan): high-perf C++ cache server.

Key takeaways

Consistent hashing + vnodes = scalable, smooth rebalancing.
In-memory hash map + LRU = single-node engine.
Hot keys are the killer; replicate + local cache + sampling.
Membership: gossip (Redis Cluster, Cassandra) or coordinator.
Cache is usually AP; durability optional.