Worked Example 15.9 · 9 of 15

Design a distributed cache (Memcached/Redis-class)

📖 4 min read · 10 sections · May 2026

Asked at: Meta Google Netflix Twitter/X

The setup

"Build a distributed in-memory cache. Get/set/delete by key; TTL support; horizontally scalable; tolerant to node failures. 100 GB working set; 1M ops/sec aggregate; sub-millisecond p99 latency."

Single-node design first

Hashmap + LRU eviction (we covered this extensively in Storage Engines and Caching chapters). Concurrent access via:

Single-threaded event loop (Redis approach): simplest; no locks; one core per process; can run N processes for parallelism
Multi-threaded with striped locks (Memcached approach): higher throughput per process; more complex
Thread-per-core shared-nothing (KeyDB, Dragonfly): linear scaling with cores; most modern approach

For new builds: thread-per-core, shared-nothing. Linear scale, no lock contention.

Design Decision 1: distribution via consistent hashing

Naive hashing fails on rebalance (most keys move on add/remove node). Consistent hashing with virtual nodes:

Each physical node has ~150 virtual nodes on the ring
Key location: hash(key) → ring position → nearest clockwise vnode → physical node
Adding a node: only that node's vnodes' worth of keys move (~1/N of total)

Why vnodes vs single-position-per-node: smooth load distribution. With single positions, adding one node steals all keys from one neighbor; with vnodes, it steals proportionally from many neighbors.

Design Decision 2: client-side routing

Approach	Pros	Cons
Smart client (knows topology)	Direct connection to owner node; lowest latency; no proxy	Topology updates must propagate to all clients; fat client library required
Proxy tier (e.g., Twemproxy, Envoy)	Dumb clients; centralised retry/circuit-breaker	Extra network hop (~0.2ms); proxy is itself a tier to operate

For new in-house cache with controlled clients: smart client. For polyglot ecosystems where many languages need cache access: proxy. Memcached + sidecar proxy is common pattern.

Design Decision 3: replication

For HA: each key is replicated to R nodes (R=2 typical). Choices:

Mode	How	Tradeoff
Primary-replica (async)	Writes go to primary; async replication to N replicas	Fast writes; potential data loss on primary failure (recent writes not yet replicated)
Quorum write (W of N)	Write succeeds when W replicas ack	Higher durability; higher write latency
No replication	Single copy; node failure = lost data	Cheapest; only acceptable for pure cache (data is reproducible from origin)

For a pure cache: primary-replica async is sufficient. Data loss on failure means cache miss → fetch from origin → repopulate. Annoying briefly; not a correctness issue.

For session storage or other "cache-like but matters" data: quorum write or external durability (separate persistence layer).

The architecture

Clients (smart, know ring topology)
   │
   │ Hash key → identify owner node
   │
   ▼
[Cache Cluster — 10-30 nodes]
   ├── Each node: hashmap + LRU + concurrent in-memory
   ├── Each key replicated to 1 primary + 1 async replica
   ├── Topology change propagation via gossip or central config service
   └── Failures: replica promoted; client retries on MOVED redirect

Cross-examination round 1: hot key

Interviewer: One key is read 1M times/sec. That's one node hammered. Walk through.

Multiple mitigations:

L1 cache in each application server (Caffeine, sync.Map): nanosecond access; for top-N hot keys, almost all reads served locally. Reduces cache cluster QPS dramatically.
Read from replicas: send hot-key reads to multiple replicas, not just primary. Spreads load across N replicas. Eventually-consistent for the brief inconsistency between writes and replication.
Key replication: replicate hot key to multiple distinct shards (different from primary-replica HA replication — these are independent copies). Read from any.
Singleflight on writes: if hot key write is also concentrated, coalesce concurrent writes to one upstream call.

Combine: L1 cache eliminates 99% of upstream calls; remaining reach the cluster's replicas; sufficient.

Cross-examination round 2: topology change

Interviewer: Add a 4th node to a 3-node cluster. Walk through what happens.

New node registers with the cluster (via config service or gossip). Topology change: new node has 150 vnodes on the ring. Keys in those vnodes' ranges should migrate from current owners to new node.

Lazy migration (Memcached-style): no explicit migration. When clients query, they ask the wrong (old) owner; old owner responds with MOVED redirect; client refreshes topology and retries on new owner. Brief misses while caches warm.
Active migration (Redis Cluster): explicitly stream keys from source to destination. During migration, source serves reads but redirects writes; once complete, ownership flips atomically.

For pure cache, lazy is simpler and fine — temporary miss rate spike, but cache repopulates. For data-bearing systems (Redis-as-database), active migration preserves data.

Cross-examination round 3: failure scenarios

Interviewer: A node fails completely. Walk through.

Other nodes detect failure via heartbeat/gossip (~5-10 sec). Cluster removes the dead node from topology. Replicas of the dead node's data are promoted to primary. Clients receive new topology; retry failed requests on new primary. Some recently-written data on the failed node that hadn't replicated yet is lost — acceptable for cache. Re-warming: as clients miss the dead node's data, they fetch from origin and repopulate to new primary.

Takeaway

Distributed cache is the simplest distributed system to design well. The pieces are clear: consistent hashing for placement, replication for HA, in-memory data structures for speed. The interesting subtleties are eviction and concurrency. When asked to design more complex systems, this same pattern recurs: figure out where state lives, how clients find it, and how it survives failures.

The deeper lesson: caching's role in a larger architecture is to absorb hot spots. The cache isn't the source of truth; it's a performance layer. Design it for high throughput, predictable latency, graceful failure (cache misses are fine), and operational simplicity. Don't try to make it a database.