Design a Distributed Cache: Interview Answer
On this page
The problem: design a distributed cache
"Design a distributed in-memory cache, something like Memcached or Redis Cluster." There are three problems inside it: spreading keys across nodes, surviving a node failure, and one key that's far more popular than the rest. Try them yourself first.
Distributed cache requirements
Functional: get(key), set(key, value, ttl), delete(key).
Non-functional: a few milliseconds or less per operation; capacity beyond one machine's RAM, so data is split across nodes; losing one node shouldn't send a flood of misses to the database; nodes can be added as traffic grows.
Consistent hashing vs modulo hashing
The obvious approach: node = hash(key) % N. It's even and simple, until you add a node. Changing N changes almost every key's node, so the whole cache effectively empties at once and the database takes the full load.
Consistent hashing fixes that. Place nodes on a ring of hash values; a key belongs to the first node clockwise from the key's hash. Adding a node only takes over the keys in its slice of the ring. Each physical node is placed at many points, called virtual nodes, so its slices are spread around the ring and the load evens out.
A quick simulation with 100,000 keys, growing from three nodes to four:
# ring.py: how many keys move when a fourth cache node joins, modulo vs consistent hashing
import bisect, hashlib
def h(s: str) -> int:
return int(hashlib.md5(s.encode()).hexdigest(), 16)
class Ring:
def __init__(self, nodes, vnodes=100):
self.points = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))
self.hashes = [p for p, _ in self.points]
def owner(self, key: str) -> str:
i = bisect.bisect(self.hashes, h(key)) % len(self.points) # next point clockwise
return self.points[i][1]
keys = [f"user:{i}" for i in range(100_000)]
old, new = ["a", "b", "c"], ["a", "b", "c", "d"]
moved_mod = sum(old[h(k) % 3] != new[h(k) % 4] for k in keys)
r3, r4 = Ring(old), Ring(new)
moved_ring = sum(r3.owner(k) != r4.owner(k) for k in keys)
print(f"modulo: {moved_mod / len(keys):.0%} move, hash ring: {moved_ring / len(keys):.0%} move")modulo: 75% move, hash ring: 22% moveThe ideal is 25 percent, the new node's fair share, and the ring gets close. Modulo moves three quarters of all keys. Redis Cluster takes a related approach with 16,384 fixed hash slots assigned to nodes, which gives the same small-movement property.
Surviving a cache node failure
Without replicas, every key on the failed node becomes a miss and those requests hit the database. Give each key a replica on the next node or two around the ring, written asynchronously. When a node fails, clients read from the replica. Asynchronous copies can be slightly stale, which a cache usually tolerates.
Membership needs to be known by every client: which nodes are alive, and the ring layout. Either a coordination service such as ZooKeeper or etcd holds it, or nodes exchange it with a gossip protocol: every second or so, each node swaps what it knows with a few random peers, so a membership change reaches every node within a few rounds without any central server. Redis Cluster nodes gossip this way over their cluster bus. For more on rings and virtual nodes, see the roadmap's consistent hashing lesson.
Cache eviction: LRU vs LFU
Each node has a memory limit. When full, evict. LRU (least recently used) is the standard default; LFU (least frequently used) holds up better when a scan of old data would otherwise push out popular items. Expired keys are removed lazily on access and by a periodic sweep.
If you name Redis, know its default: maxmemory-policy is noeviction, which rejects writes once memory is full instead of evicting anything. For a cache, set allkeys-lru or allkeys-lfu. Redis's LRU is also approximate: it samples a few keys and evicts the least recently used of those, which saves memory and behaves almost like true LRU (Redis docs).
Handling a hot key
Even a perfectly balanced ring has a weakness: one key, a viral post or a flash-sale item, can get more traffic than its node can serve. Spreading keys doesn't spread load for one key. Options:
- Copy that key to several nodes under suffixed names (
item:9#1toitem:9#8) and have clients read a random copy. - Cache it inside the application servers for a second or two.
- Detect hot keys by sampling request counts per key, so the fix applies automatically.
A hot key causes a second problem when it expires: every request misses at once and all of them hit the database for the same value, a cache stampede. Let one request rebuild the value while the others wait for it or get the old copy (request coalescing), or refresh popular keys shortly before they expire.
Check yourself
When N changes from, say, 4 to 5, almost every key maps to a different node, so most lookups suddenly miss their cache and fall through to the database at once. Consistent hashing moves only about 1/N of the keys when a node is added, which keeps the database load manageable.
With one point per node, the ring's slices are uneven and one node can get a much larger share. Many points per node spread each node's share around the ring and even out the load.
A hot key: one item, such as the launch product, gets so many reads that the single node owning it is overwhelmed, however even the overall distribution is. Replicate that key to several nodes and read a random copy, or cache it briefly inside the application servers.
A cache stampede: every request missed at once and went to the database for the same value. Let one request rebuild it while the others wait or serve the stale copy, or refresh hot keys before they expire.
Its keys miss and fall through to the database until they're cached again on the nodes that now own them. With consistent hashing only that node's share of keys is affected, and replicas or a warm standby can reduce the spike.