Design a distributed cache

Build the cache that every other design leans on: an in-memory key-value service spread over many machines, answering in well under a millisecond, surviving node failures, and growing without downtime. The model is Redis Cluster (and Valkey, its open-source fork). The interesting parts are routing keys to nodes, failing over without split brain, what clients experience while data moves, and the hot keys and stampedes that hurt the databases behind it. It follows the interview framework phase by phase.

1. The prompt

"Design a distributed cache like Redis or Memcached that many services share. Clients set and get values with expiry times; it must grow beyond one machine."

A cache looks simple until you ask what happens when nodes are added, when one dies, when one key gets a hundred times the traffic of the rest, and when the whole thing restarts empty in front of a database that can't take full load. Those questions are the interview.

2. Frame the problem

3. What it must do

1. A client can set, get and delete values, with an optional expiry (TTL).
2. The cache evicts the least useful keys when memory is full.
3. Operators can add or remove nodes while clients keep working.

Not now:

• Durable database guarantees: if data can't be lost, it belongs in a database.
• Cross-region replication: each region runs its own cache, warmed from its own database replicas.
• Scripting and pub/sub: they work per node; not core to the design.

4. How well it must do it

5. Numbers that change the design

6. The nouns

• Key and value, with a TTL.
• Hash slot: one of 16,384 buckets a key falls into.
• Primary and replica nodes.
• Slot map: which node owns which slots.
• Configuration epoch: a version number that settles which view of the slot map wins.

slot(key)   CRC16(hash tag or whole key) mod 16384
slot map    slot ranges → primary (+ replica), with a config epoch per owner
per node    keys in memory, maxmemory + eviction policy, async replication stream to its replica

7. The contract

The Redis protocol over TCP. Clients cache the slot map and handle two kinds of redirection.

GET key            → value | nil
SET key value EX 600
DEL key
CLUSTER SLOTS      → which node serves which slot range (clients cache this map)
-MOVED 12182 10.0.3.7:6379    (that slot lives elsewhere now: update your map)
-ASK   12182 10.0.3.9:6379    (slot is mid-migration: try there, just this once)

8. First working version

Start with several independent cache servers and let clients pick a server for each key.

8.1 Setting and getting

Each client hashes the key and takes it modulo the number of servers, then talks to that server directly. A get that misses reads from the database and sets the value (cache-aside).

8.2 Eviction

Each server has a memory limit; when it's full, it evicts keys it considers least useful. Redis approximates LRU or LFU by sampling a few keys and evicting the best candidate, which costs far less than a perfect ordering.

8.3 Adding a server

Add it to the list every client uses.

9. Make it hold up

9.1 Routing keys to nodes scale · protects the database

Smart clients or a proxy? Clients that cache the slot map go straight to the right node: no extra hop, which keeps p99 under 1 ms. A proxy tier (Envoy, twemproxy) makes every client simple and hides topology changes, at a little latency and one more tier to run.

9.2 Moving data while clients keep working scale

Adding capacity means moving slots. Press Play to move one slot from node A to node D while clients keep reading and writing.

During the move, keys already copied live on D and the rest on A. A client asking A for a key that has already moved gets -ASK ("try D, just this once"); once the slot is fully moved, the slot map changes and clients with old maps get -MOVED ("update your map").

9.3 Failover without split brain self-healing · never very stale

• Detection: nodes gossip heartbeats. When a majority of primaries agree a primary is unreachable for longer than the node timeout, it's marked failed.
• Promotion: its replica asks the primaries for votes and is promoted with a new, higher configuration epoch, which beats the old owner's claim to the slots.
• Lost writes: replication is asynchronous, so writes acknowledged just before the crash may be lost. For a cache, that's acceptable.
• Minority partitions: a primary cut off from the majority stops accepting writes after the node timeout, which limits how much data diverges before it's demoted. If correctness truly matters, the data doesn't belong only in a cache.

9.4 Multi-key operations speed

A command touching several keys only works if they live in the same slot. Hash tags make that possible: only the part inside {…} is hashed, so {user:42}:cart and {user:42}:profile share a slot (try it in section 13). Use them sparingly: putting too much under one tag creates a hot slot.

9.5 Hot keys, stampedes and big keys protects the database · speed

9.6 Cold starts, persistence and tenants protects the database

• Cold starts: an empty cache sends the database 20× its normal load (section 5). Options: snapshots (RDB) to restart warm, an append-only file (AOF) for less loss, or no persistence plus a warm-up that preloads hot keys before taking traffic. Persistence costs disk I/O and fork time; many large deployments rely on replicas and warm-up instead.
• Rolling restarts: restart replicas first, fail over, then restart the old primaries, so a shard is never empty.
• Tenants: give large teams their own clusters, or at least separate key prefixes with per-tenant memory budgets and big-key alerts, so one team's mistakes don't evict everyone else's data.

9.7 The whole design after the deep dives

A read with a stale client map, a hot key absorbed locally, and a failover, through the final design.

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• Hash slots with an authoritative map (coordinated moves) over client-side consistent hashing.
• Smart clients over a proxy (no extra hop).
• Asynchronous replication (fast, may lose recent writes).
• Approximate LRU/LFU by sampling.
• Warm-up instead of heavy persistence.

What we'd watch:

• Hit rate and p99 latency per node.
• Operations per slot.
• Memory and evictions.
• Replication lag.
• Failovers.
• Database load during incidents.

At 10×:

• More primaries.
• Clusters split by workload.
• More in-process caching.

Common mistakes:

• Modulo hashing.
• Sizing by memory only.
• Treating the cache as a database.
• Ignoring the database during failures.
• No answer for hot keys or stampedes.
• Restarting cold.

13. Try it, check yourself, read more

Type a key to see its real Redis Cluster hash slot (CRC16 in the XMODEM variant, mod 16384) and which of 4 nodes owns it. Try {user:42}:cart and {user:42}:profile.

Check: the Redis cluster specification says "foo" maps to slot 12182 and the CRC16 of "123456789" is 31C3; this calculator reproduces both.