Back to System design
Design a Distributed Cache
mediumA cache holds recently used data in memory so you do not have to fetch it from a slower database. A distributed cache spreads that memory across many machines, because one machine does not have enough.
Scale100K-1M ops/s per node; <1ms p99
StorageRAM × N nodes; cluster total = working set
Key Concepts
1
Using one is easy. This question asks you to build one, and it turns on three things: how a client finds
the right machine, what happens when a machine dies, and what to do about one extremely popular key.
2
Finding the right machine. The usual answer is that the client works it out itself. Each client knows
the list of cache machines and runs the same hashing rule, so it contacts the right one directly. One
network hop, no middleman.
Finding the right machine.
3
The alternative is a proxy in front that does the routing. That costs an extra hop but means clients do not
need to know the layout. Managed cache services do this, because keeping thousands of clients agreeing on
one list is harder than running a proxy.
4
A dead cache machine should not matter, and the danger is not the lost data. Everything in a cache can
be rebuilt from the database, so losing it costs nothing permanent.
A dead cache machine should not matter, and the danger is not the lost data.
5
The danger is the sudden load. If you have ten machines and lose one, 10% of requests now miss and go
straight to the database.
6
100,000 requests/second, 95% hit rate
Normal database load 5,000/second
One machine of ten lost:
extra misses 100,000 x 10% 10,000/second
database now sees 15,000/second (3x)
7
Three times normal load, arriving instantly. Whether the database survives that is the real question, and
it is worth saying out loud.
8
Without consistent hashing it is far worse. Plain modulo hashing remaps almost every key when the machine
count changes, so nearly all 100,000 requests miss at once — around nineteen times normal load, which is an
outage rather than a spike.
9
Should you keep copies of cached data? Copying every entry to a second machine doubles your memory to
protect data you could rebuild anyway. It is worth it only when the database cannot absorb the miss storm
above. Otherwise spend that memory on a bigger cache and a better hit rate, and say which condition you are
choosing on.
Should you keep copies of cached data?
10
One popular key defeats all of this. Sharding spreads keys across machines. It cannot spread a single
key, because a key lives in exactly one place.
One popular key defeats all of this.
11
If 30% of your traffic is for one item — a celebrity profile, a flash sale — that machine takes 30% of all
requests while the others idle. Adding machines does nothing at all.
12
Two fixes. Store the key under several names —
item:99#1 through item:99#10 — and have clients pick one
at random, which spreads the load across ten machines at ten times the memory for that key. Or let each
application server keep its own copy in memory for a few seconds, so most requests never leave the process.
Both accept slightly stale data in exchange for surviving.item:99#1item:99#10
13
Eviction and expiry are different things. Eviction is what you throw out when memory is full. Expiry is
how long you are willing to serve something possibly out of date. Size the cache from the data people
actually use, and set expiry from how wrong you can afford to be.
Eviction and expiry are different things.
14
What the interviewer is probing.
What the interviewer is probing.
15
1. "How does a client find the right machine?" Probing: routing. Stalls: "It asks the cluster."
Moves up: the client computes it from the same hash rule, or a proxy does it and costs a hop.
1. "How does a client find the right machine?"
16
2. "A cache machine dies." Probing: the load, not the data. Stalls: "The cache rebuilds itself."
Moves up: 10% of traffic hits the database at once — work out whether it survives 3x load.
2. "A cache machine dies."
17
3. "One key gets 30% of the traffic." Probing: the limit of sharding. Stalls: "Consistent hashing
spreads it." Moves up: one key is one machine; store it under several names or cache it in the
application.
3. "One key gets 30% of the traffic."
18
4. "Should you replicate the cache?" Probing: whether it is automatic. Stalls: "Yes, always."
Moves up: it doubles memory for rebuildable data; do it only if the database cannot take the miss storm.
4. "Should you replicate the cache?"
19
5. "How big should the cache be?" Probing: sizing from evidence. Stalls: "As big as possible."
Moves up: measure how much data is actually touched each day; the first slice buys most of the hit rate
and the last slice costs the most.
5. "How big should the cache be?"
High-level design
Client → (proxy?) → consistent-hash route → shard.
Per-shard: in-memory store (Memcached / Redis).
Optional per-shard replica for HA.
Client SDK handles retry, failover, batch fetch.
Hot-key detector emits alerts; load balancer for replicated hot keys.
Cold-start: shadow traffic from old cluster or replay from persistent log.
Components
- Client library with consistent hashing + retry.
- Cache nodes (Memcached, Redis).
- Optional proxy layer (mcrouter, twemproxy, KeyDB).
- Hot-key detector (top-K with Misra-Gries or count-min sketch).
- Metrics: hit rate, evictions, memory, latency, hot-key alarms, slow-log.
- Capacity planner: sizing by working-set estimate.
Miss storm on node loss, worked
Cache nodes 10 Total traffic 100,000 req/s Hit rate 95% -------------------------------------------------------------- Normal database load 100,000 x 0.05 = 5,000 req/s
One node lost (consistent hashing, no replication)
Share of keys now missing 1/10 = 10%
Extra misses 100,000 x 0.10 = 10,000 req/s
Database load 5,000 + 10,000 = 15,000 req/s
= 3x normal Same failure WITHOUT consistent hashing (modulo)
Keys remapped = ~90%
Extra misses = 90,000 req/s
Database load = 19x normal
-- an outage. Recovery
Misses repopulate the cache, so the spike decays over the time
it takes to touch the hot keys again -- typically seconds to
minutes. The question is whether the database survives the peak,
not the average. Mitigations, in order of cost
1. Consistent hashing (already assumed)
2. Request coalescing so 10,000 misses on the same key become 1
3. Serve-stale during repopulation
4. Replication of cache entries (doubles memory)Hot key handling
The problem
Key placement is per key. A key taking 30% of 100,000 req/s is
30,000 req/s on ONE node, whatever the ring looks like. Fix 1 -- suffixed replicas
Store as key#1 .. key#10, client picks one at random.
Effect: 30,000 req/s spread across 10 nodes.
Cost: 10x memory for that key; invalidation must touch all
copies, so staleness is bounded by how fast you can fan out. Fix 2 -- client-local cache
Cache the hot key in the application process for 1-5 seconds.
Effect: nearly all reads never leave the process.
Cost: staleness up to the local TTL, and each process holds its
own copy. Fix 3 -- detect and promote automatically
Track per-key request rates at the client; when a key crosses a
threshold, switch it to local caching for a window.
Cost: complexity; but it handles keys that become hot without a
human noticing. What does NOT work
Adding nodes. The key still lives on one of them.Failure modes in production
Topology disagreement between clients
Symptom: hit rate halves after a membership change.
Cause: clients hold different ring views; the same key routes to
two nodes.
Fix: version the ring, distribute through one control plane, and
accept that a brief disagreement costs hit rate, not correctness.
Cache used as a database
Symptom: a restart loses data nobody expected to lose.
Cause: values written only to the cache.
Fix: be explicit about reconstructibility; if it cannot be
rebuilt, it needs a durable home. Eviction thrash
Symptom: hit rate collapses while memory is full; CPU high.
Cause: working set exceeds capacity; every insert evicts
something that is about to be needed.
Fix: measure the working set and size for it, or admit only keys
seen more than once (admission policy) so one-off scans do not
evict the head. Connection storm on failover
Symptom: the replacement node is overwhelmed as it comes up.
Cause: every client reconnects and repopulates at once.
Fix: jittered reconnect, slow-start on the new node, and request
coalescing so concurrent misses for one key become one origin
read.