Design a distributed cache
A shared in-memory key-value cache, like Redis or Memcached, spread across many machines.
Why interviewers ask it
It tests partitioning, consistent hashing, eviction, replication and failure handling — the building blocks of most large systems.
Functional requirements
- get, set and delete, with TTLs.
- Grow capacity by adding nodes.
Non-functional requirements
- Reads in under a millisecond; very high throughput.
- Survive node failures with limited data loss.
From version 1 to the final design
- Version 1: one cache server with a hash map and LRU eviction.
- Version 2: several servers using hash % N routing.
- Version 3: consistent hashing with virtual nodes.
- Version 4: replicas, failover, hot-key handling and stampede protection.
The design, step by step
- Clients, or a proxy, route each key to a node with consistent hashing and virtual nodes.
- Each node: an in-memory hash table with LRU eviction and TTL expiry.
- Each shard has a replica for failover.
- Cluster membership comes from a configuration service, or nodes gossip with each other.
Deep dives
- Hot keys: replicate them, or add a small local cache inside the app.
- Cache stampede: let one request rebuild a key while the others wait.
- Node failure: promote the replica; the misses fall on the database, so warm the cache gradually.
- Optional persistence (snapshots or an append-only file in Redis).
Common mistakes
- hash % N routing, which causes mass misses whenever servers change.
- Having no plan for hot keys: one very popular key can overload the single cache node that holds it.
- No warm-up after a failure: an empty cache sends every request to the database at once.
Not true: Routing: hash % N keeps most keys on the same server when a server is added.
In fact: Changing N changes the answer for almost every key, so nearly all lookups miss at once. Consistent hashing moves only about 1/N of the keys.
In the interview
Keys are spread across nodes with consistent hashing and virtual nodes, so adding a node moves only a small share of the keys. Each node is an in-memory hash map with LRU eviction and TTLs, replicated for failover. Hot keys get extra replicas or a local cache, and stampedes are prevented by letting one request rebuild a key.
Part of Unit 8: High-level design questions in the free System Design course.