System design interview
Design a distributed cache
Consistent hashing, eviction, hot keys, invalidation and stampede protection.
Press Play to follow a request through the design, or step through it.
- Client and edge
- Service
- Data store
- Cache and queue
- The client asks the app server for a value.
- The app server hashes the key and the ring says node A owns it, so it asks node A directly.
- Node A finds the value in memory and returns it in about a millisecond.
- The app server returns the value. The database was never touched.
- Client
- Ring config: nodes and health
- App server: hash ring in memory
- Database: source of truth
- Cache node A: LRU, TTL
- Cache node B: LRU, TTL
- Cache node C: LRU, TTL
On this page
In 2 minutes
I would build a cache-aside layer: app servers talk straight to a ring of cache nodes, and the cache never touches the database. Keys are placed by consistent hashing with virtual nodes, so adding or removing a node moves only about one key in N, instead of nearly all of them as with hash mod N. In our estimate the working set is 100 GB and peak load 200,000 reads a second, which needs four nodes, so I would run six for headroom.
On a miss, the app server reads the database and fills the cache with a TTL that has random jitter. On a write it updates the database and then deletes the cache key. Each node evicts with LRU and expires entries by TTL.
To stop stampedes I would coalesce requests for the same key, jitter the TTLs and serve a stale value while one request refreshes. For hot keys I would add a short-lived local cache in each app server and replicate the very hottest keys under several names. If a node dies, the config service removes it from the ring, only its share of keys reloads from the database, and the cache is never treated as the source of truth.
Step 1 of 6: Clarify the scope
Interviewer asks
Design a cache shared by many application servers, in front of a database that cannot handle every read. Say how keys are spread over cache nodes, what happens when a node dies, and how stale or overloaded keys are handled.
Questions to ask first
Ask these before you draw anything. Under each one is why its answer changes the design.
- Is the cache only for speed, or is it ever the source of truth?
If it is only a copy, losing a node is a slowdown. If it is the truth, you need durability, which is a different system.
- How stale can a value be before it is wrong?
The tolerance sets the TTL, and whether deleting on write is enough or you need stricter invalidation.
- Roughly how big is the working set, and how large is a value?
These decide how many nodes you need for memory, and whether a few huge values could cause trouble.
- Are some keys far hotter than others?
One very hot key can overload its single node even when the cluster as a whole is idle.
- Do we need a cache that survives a restart?
A cold cache sends all traffic to the database at once. Replicas or warm-up reduce that risk.
Requirements
Functional
- Get, set and delete a value by key, with an optional time to live.
- Spread keys over many nodes, and add or remove nodes without losing the whole cache.
- Evict old entries automatically when memory is full.
- Let applications invalidate keys when the database changes.
Non-functional
- Read latency: p99 under 5 ms.
- Hit ratio of at least 95% on the hot working set.
- Adding or removing one node moves only about 1 in N keys.
- No single node failure may send more than a fraction of the traffic to the database.
Step 2 of 6: Size it
Memory and throughput both point to the same small cluster, so the hard parts are not size. They are keeping rebalancing cheap, and protecting the database when keys expire or a node disappears.
Assumed for the exercise, not facts about a real system:
- 200,000 cache reads a second at peak, with a 95% hit ratio target.
- The working set is 50 million keys with an average value of 2 KB (2,000 bytes).
- One cache node has 32 GB usable memory and handles 50,000 operations a second. A database read takes about 20 ms, and a cache hit about 1 ms.
- Database reads per second
- 200,000 × (1 − 0.95)
- 10,000/s reach the database
- Working set size
- 50M keys × 2,000 bytes
- 100 GB
- Nodes needed
- Memory: 100 GB ÷ 32 GB ≈ 3.1, so 4. Throughput: 200,000 ÷ 50,000 = 4
- 4 minimum, so run 6 for headroom and failures
- Average read latency
- 0.95 × 1 ms + 0.05 × 20 ms = 0.95 + 1.0
- ≈ 2 ms
- Keys moved when going from 6 to 7 nodes
- Consistent hashing: 1 ÷ 7. Hash(key) mod N: 6 ÷ 7 of keys change node
- ≈ 14% against ≈ 86%
Step 3 of 6: Sketch the path of one request
Step through the diagram at the top of the page to watch a request move through these parts.
A Client request reaches an App server. The app server holds the cache logic: it hashes the key, finds the owning node on a ring, and talks to that node directly. There are three Cache nodes in the picture, but the same design works with dozens.
The Ring config service stores which nodes exist and whether they are healthy. App servers keep a copy of it in memory and refresh it when it changes, so no request has to ask the config service which node to use.
On a hit the node answers from memory. On a miss, or when the node is down, the app server reads the Database, returns the result to the client and writes it to the cache with a TTL. This is the cache-aside pattern: the cache never talks to the database, which keeps nodes simple and the cache easy to replace.
Other paths through the system
A cache miss
- The client asks for a value that has not been cached yet.
- The ring says node B owns the key, so the app server asks node B.
- Node B has no entry for it: a miss.
- The app server reads the value from the database. If many requests miss at once, only one of them loads it.
- It writes the value to node B with a TTL that has a little random jitter added.
- The app server returns the value, and the next reader finds it in the cache.
A node fails
- The client asks for a value owned by node C.
- The request to node C times out, because the node has crashed.
- The app server reports the node as unreachable to the ring config service.
- Once health checks agree, the config service removes C and pushes the new ring to every app server.
- C's keys now belong to the next nodes on the ring, so the app server asks node A instead.
- Node A has not seen this key yet, so it reports a miss.
- The app server reads the database and fills node A. Only C's share of keys needed reloading.
- The client gets its value, a little slower than usual.
Step 4 of 6: Go deep on the hard part
Consistent hashing with virtual nodes
Interviewer asks
How do you decide which node holds a key, so that adding or removing a node is cheap?
The obvious rule is node = hash(key) mod N.
Read moreShow less: Consistent hashing with virtual nodes
It works until N changes. Go from 6 nodes to 7 and about 6 in 7 keys land on a different node. Almost the whole cache goes cold at once, and the database takes the load.
Consistent hashing fixes this. Picture the hash space, 0 to 2^32 − 1, bent into a ring. Hash each node's name to a point on the ring, and hash each key to a point too. A key belongs to the first node you meet going clockwise. When a node joins, it takes over only the keys between itself and the node before it. When one leaves, only its own keys move, to the next node. About 1 in N keys move.
With only a few points on the ring, the gaps are uneven, and one node may own twice the share of another. Virtual nodes solve that. Each physical node is placed at many points, often 100 to 200, using names like 'node-a#17'. The shares average out. A bigger machine can get more points, so it takes a larger share. When a node dies, its keys spread across many survivors instead of landing on one unlucky neighbour.
Who does the routing? Two usual choices:
- Smart client. The app holds the ring and talks to nodes directly. It saves a hop, but every language needs a client library, and each one must pick up ring changes.
- Proxy layer. Apps talk to a thin router that holds the ring. One place to upgrade, but one more hop and one more thing to keep healthy.
Ring views will briefly disagree while an update spreads. For a cache that only means a few extra misses, not wrong data. For replication, store a key on the next one or two distinct physical nodes on the ring.
Eviction, expiry and hot keys
Interviewer asks
What do you do when memory is full, and how do you handle one key that gets a huge share of the traffic?
Memory is limited, so something must go. LRU (least recently used) evicts the entry untouched for the longest time.
Read moreShow less: Eviction, expiry and hot keys
Keep a hash map for lookup and a doubly linked list for order. On each access, move the entry to the front. Evict from the back. Both operations take constant time. Real stores often use a sampled approximation: pick a few random entries and evict the oldest, which avoids locking a global list. LFU (least frequently used) keeps entries that are used often, and resists a one-time scan of cold keys flushing out the hot ones.
TTL removes entries after a set time, so stale data cannot live forever. Expiry is lazy: check the time on read. A background task also samples keys in small batches and removes expired ones, so memory is reclaimed even for keys nobody reads again.
Hot keys break the idea that the ring spreads load evenly. If one key gets 80,000 reads a second, its node is saturated, even when the cluster is quiet. Tools, in the order I would reach for them:
- Local cache. Keep the hottest values in each app server's memory for one to five seconds. Thousands of reads become one read per app server per few seconds.
- Replicate the key. Store copies under variants such as 'key#1' to 'key#4', which hash to different nodes, and read a random variant.
- Detect early. Count accesses per key in the client, and promote a key to a local cache or replication only when it passes a threshold.
Keep values small. A single 5 MB value takes long to send and blocks other requests on that connection. Split big objects, or store them elsewhere and cache a pointer.
Writes, invalidation and stampedes
Interviewer asks
How do you keep the cache close to the database, and how do you avoid everyone hitting the database when a popular key expires?
Cache-aside is the default.
Read moreShow less: Writes, invalidation and stampedes
Read the cache, on a miss read the database and set the cache. On a write, update the database first, then delete the cache key. Deleting is safer than updating it, because two concurrent writers could leave the older value in the cache. A race remains: a reader loads the old row, a writer updates and deletes, then the reader sets the old value. A short TTL bounds the damage. Versioned keys or a second delete a moment later reduce it further.
Write-through writes the cache and the database in the same operation. Reads after a write are warm, but writes get slower and you cache data nobody asks for. Write-behind acknowledges the write in the cache and saves it to the database later. It is fast, but a node crash loses data, so only use it when losing a little is acceptable.
A stampede happens when a popular key expires and thousands of requests miss together. All of them load the same row from the database. Defences, usually used together:
- Request coalescing. Within one process, let the first request for a key do the load while the others wait for its result. Across processes, take a short lock with a set-if-absent command.
- Jittered TTLs. Add a random 10 to 20 percent to each TTL, so keys written together do not expire together.
- Serve stale while refreshing. Keep a soft expiry. After it, return the old value and refresh it in the background.
- Refresh ahead. For the hottest keys, reload a little before they expire.
Also protect against cold starts. When a whole cache comes up empty, ramp traffic up slowly or warm it from a list of popular keys, rather than letting the full load fall on the database.
Step 5 of 6: Name the trade-offs
Key placement
Consistent hashing with virtual nodes over hash(key) mod N
Changing the cluster moves about 1 in N keys, not nearly all. The cost is a ring to maintain and share with every client.
Write policy
Cache-aside, deleting the key on write over Write-through to the cache and database
Only requested data is cached and the cache can fail without losing anything. The cost is a short window where a reader can see an older value.
Routing
A smart client that holds the ring over A proxy layer in front of the nodes
One fewer network hop on every read. The cost is a client library to keep up to date in every language.
Expiry
TTL with random jitter, plus request coalescing over Fixed TTLs and no coalescing
Popular keys expire at different moments and only one request reloads each. The cost is a little extra logic in the client.
Step 6 of 6: Say what breaks next
Questions an interviewer asks once the design is on the board. Answer each one out loud first.
- Should the cache ever be the source of truth?
Not in this design. The cache can lose a node at any time, and eviction removes entries without telling anyone. If you need a fast store that is also durable, that is a key-value store with replication and a commit log, which is a different system.
- How do you replicate cache nodes?
Give each node an asynchronous replica. On failure the replica takes over, so the database does not see a cold shard. The cost is double the memory and a short window where the replica is behind, which a cache can usually tolerate.
- How do you know the cache is working?
Track the hit ratio, the eviction rate, memory use per node and the latency of reads. A falling hit ratio with a rising eviction rate says the working set no longer fits. Also track load per key to spot hot keys early.
- What do you do when many keys must be invalidated at once?
Do not scan and delete. Put a version number in the key, such as 'user:42:v7', and bump the version to invalidate all of a group. The old keys are never read again, and expire or are evicted on their own.