Design a distributed cache: the system design interview guide
The request to design a distributed cache sounds like one line — store key→value in memory so reads are fast — and that one line hides the whole interview. On one box it is a hash map: put(key, value), get(key), done. Doing it across a cluster, so it survives a node dying, spreads load evenly, and stays fast while nodes join and leave, turns a data structure into a distributed cache system design problem with a dozen sharp edges. This is one of the most common infrastructure prompts in a system design interview because it forces two muscles at once: how a single node stays O(1), and how a caching system spreads keys so churn barely moves them.
The round turns on two decisions. First, what lives inside one node: a hash map for O(1) lookup is obvious, but eviction when memory fills is the trap — you need a second structure so picking a victim is also O(1), not a scan. Second, how keys map to nodes: naive modulo hashing reshuffles the entire keyspace every time the cluster changes size, so you reach for consistent hashing and a hash ring. This guide follows the path a strong candidate draws on the whiteboard — requirements, estimate, API and data model, high-level design, then the deep dives — and at each step it names the follow-up the interviewer uses to tell a memorized answer from an engineer who understands the tradeoff.
How the distributed cache round is actually run
A distributed cache round runs about 60 minutes on a shared canvas — you draw the boxes and arrows while you talk, and the interviewer interrupts. It is a favorite infrastructure prompt because the one-line problem opens onto deep water fast: the moment you say "store it in memory," the question becomes across how many boxes, and what happens when one of them dies, and every answer after that (eviction, sharding, replication) compounds. Get the distribution and eviction spine clean and you have shown the whole loop in one problem.
The interviewer rarely lets "hash the key, pick a node" stand. "You have a ten-node cluster and you add an eleventh. With plain
hash(key) % N, how many keys move? Now do it so almost none move." That question — minimal reshuffle on churn — is the one a copied answer can never rehearse, and the one this round is really testing.
The rounds here are modelled on how the loop runs, not scraped from any candidate's recall. What matters for prep is the shape: a blank canvas, a clock, and a follow-up after every decision you make.
The five-step framework for any HLD round
Every high-level design answer fits the same spine. Say it out loud at the start so the interviewer knows you have a plan, then walk it:
- Clarify requirements — functional and non-functional, and what you are explicitly not building.
- Estimate — data volume, nodes, and how many keys move on churn, to justify every later choice.
- High-level design — the boxes and arrows: client, hash ring, cache nodes, replicas, backing store.
- Deep dive — the two or three decisions that actually decide this system.
- Follow-ups — bottlenecks, failure modes, and what you would change at ten times the scale.
What the debrief measures
The score is not "right or wrong design." A good HLD debrief reads on four dimensions, and every move below maps to one: problem solving (did you reach consistent hashing for sharding and a hash-map-plus-linked-list for O(1) eviction), communication (did you say why modulo hashing fails in a sentence), technical execution (virtual nodes for even load, persist-before-forward is not your concern but replication and cache-aside are), and time management (did you spend your 60 minutes on hashing and eviction, not on the serialization format). Reading a guide teaches the design; it does not teach you to deliver it on the clock while someone pushes back.
Step 1 — Requirements: what a distributed cache must do
Spend the first few minutes here. Jumping to boxes before you have scoped the problem is the fastest way to design the wrong system.
| Type | Requirement |
|---|---|
| Functional |
get(key) and put(key, value) with O(1) average latency; TTL / expiry on entries; eviction when a node is full; scale horizontally by adding nodes. |
| Functional (optional) | Persistence to disk, pub/sub or change notifications, secondary-index lookups — call these out, then scope most of them for later. |
| Non-functional | Very low latency (sub-millisecond on a hit); high availability (a dead node must not take the cache down); even load distribution across nodes; minimal disruption when nodes join or leave. |
The sentence that earns points: "A cache fronts a database to absorb read-heavy traffic, so the core of the design is spreading keys across nodes with minimal reshuffle on churn, plus O(1) eviction on each node — the lookup itself is the easy part." Say that and you have framed the entire design before drawing a box.
Step 2 — Capacity estimation (back of the envelope)
Estimation here is about proving one thing: the hard axis is key movement on churn, not raw storage.
| Quantity | Assumption | Result |
|---|---|---|
| Data to cache | ~1 TB of hot keys | — |
| Memory per node | ~64 GB usable | ~16 nodes just to hold the set |
| Read traffic | ~1M get/sec at peak | must stay sub-millisecond per hit |
| Keys moved when one node is added | consistent hashing | ~1/N of keys (one arc), not all of them |
Two conclusions fall out, and you should say both out loud. First, the keyspace is large and the cluster is elastic — you add and remove nodes as hot data grows and shrinks, so any scheme that moves most keys on every change is a non-starter. Second, each node is a straightforward in-memory key-value store, so the per-node problem is not storage but eviction — when 64 GB fills, choosing a victim must be O(1). You have now pointed the interview at the two real deep dives — consistent hashing across nodes and O(1) eviction inside a node — before anyone asked.
Step 3 — API and data model
The API is tiny — that is the point. The complexity lives in distribution, not in the surface the client sees.
| Command | Operation |
|---|---|
get(key) |
Return the value for key, or a miss. The client hashes key to find its node. |
put(key, value, ttl?) |
Store key → value, optionally with a time-to-live; evict if the node is full. |
delete(key) |
Remove key from its node. |
The data model is thin. Entries carry just enough metadata for expiry and recency, and each node owns the keys that hash to its arc of the ring:
| Entity | Notes |
|---|---|
entry |
key, value, expires_at (for TTL), plus a pointer used for recency ordering inside the node. |
node |
A cache server: an in-memory map plus its position(s) on the hash ring. |
ring |
The ordered set of node positions (including virtual nodes) that maps any key to its owning node. |
Step 4 — High-level design: the ring-and-nodes architecture
Now the boxes. An application calls a cache client that knows the hash ring; the client hashes the key, finds the owning cache node, and talks to it directly. Around that sit the pieces that make distribution and availability work:
- Cache client (ring-aware): hashes the key and routes the request to the node that owns that key; holds a view of the ring so it needs no central hop on the read path.
-
Cache nodes (in-memory): each is a hash map plus a recency structure for O(1)
get/put/ evict, holding the keys in its arc of the ring. - Replicas: each shard is copied to one or more follower nodes, so a node failure does not lose its keys or its traffic.
- Backing database: the source of truth the cache fronts; read on a miss, written through on the chosen write pattern.
- Coordinator / config service: tracks cluster membership and publishes ring changes when nodes join or leave.
Say explicitly that the cache client, not a central router, owns the ring — the read path is client → node with no middle hop, which is what keeps a hit sub-millisecond. That single observation is what sets up the sharding deep dive, and naming it unprompted is a signal the interviewer is listening for.
Deep dive: single-node cache internals
This is the first decision that actually decides the round, and the one most candidates wave past. A hash map gives you O(1) get and put — but when the node is full, which key do you drop, and how do you find it without scanning?
The clean answer pairs two structures. A hash map maps each key to a node in a doubly linked list that orders entries by recency: most-recently-used at the head, least-recently-used at the tail. Every access does two O(1) moves — look the key up in the map, then unlink its list node and splice it to the head. On put into a full node, you evict the tail (the least-recently-used key) in O(1), because the tail is always the eviction victim and the map lets you delete its key without a search. TTL rides alongside: each entry carries an expires_at, and an expired entry is treated as a miss and lazily unlinked (a background sweep reclaims the rest).
| Structure | What it gives you | Why it is needed |
|---|---|---|
Hash map (key → node) |
O(1) lookup, insert, delete | The cache contract — find any key in constant time. |
| Doubly linked list (recency order) | O(1) move-to-front, O(1) tail removal | Pick and remove the LRU victim without scanning. |
expires_at per entry |
Lazy TTL expiry | Drop stale keys on read; a sweep reclaims the rest. |
Keep it conceptual — the interviewer wants to hear why the combination is O(1), not a full implementation. The map alone cannot tell you what to evict; the list alone cannot find a key; together they give O(1) get, put, and evict. LRU is the safe default eviction policy; mention LFU or TTL-based eviction as alternatives if pressed.
"Your node is full and a
putcomes in — which key do you drop, and how fast?" The least-recently-used one, in O(1): the doubly linked list keeps the victim at the tail and the hash map deletes it by key without a scan. Naming both structures and why neither works alone is the senior move.
System Design
HLD · Infrastructure · 60 min
Design a distributed cache out loud, with follow-ups
Deep dive: consistent hashing and sharding
This is the decision the whole round is built around. You have more data than one node holds, so keys must spread across nodes — and the cluster size changes, so the mapping has to survive churn.
Start by showing why the obvious scheme fails. Naive modulo hashing picks a node with hash(key) % N. It is even while N is fixed, but the moment you add or remove a node, N changes and almost every key maps somewhere new — a near-total reshuffle that stampedes the backing database as the whole cache re-warms. That is disqualifying for an elastic cluster.
Consistent hashing fixes it. Map both keys and nodes onto the same circular hash space — a hash ring. A key belongs to the first node you meet going clockwise from the key's position. Now add a node: it lands at one point on the ring and takes over only the arc between it and its predecessor — about 1/N of the keys move, from a single neighbor, and everything else stays put. Remove a node and its arc simply folds into the next node clockwise.
| Scheme | Keys moved when a node joins/leaves | Load balance | Verdict |
|---|---|---|---|
Modulo hash(key) % N
|
~all keys remap | even while N is fixed |
reshuffles the world on every change — rejected |
| Consistent hashing | ~1/N (one arc, one neighbor) | can be lumpy with few nodes | minimal reshuffle — the standard answer |
| Consistent hashing + virtual nodes | ~1/N, spread across many neighbors | even, and smooths heterogeneous node sizes | the production answer |
The catch with a plain ring is lumpiness: with few nodes, arcs are uneven, so some nodes own far more keyspace than others. Virtual nodes fix it — each physical node is placed at many points around the ring (say 100–200 tokens each), so the keyspace splits into many small arcs that average out. Virtual nodes also let a bigger machine take proportionally more tokens, and they spread a departing node's load across many neighbors instead of dumping it all on one.
"You add one node to a ten-node cluster — how many keys move?" About 1/N — roughly a tenth — and only from the neighbor whose arc the new node splits, not the whole keyspace. With virtual nodes that tenth is drawn evenly from many nodes. Contrast that with modulo, where nearly everything moves. Saying the number and the mechanism is what lands it.
System Design
HLD · Consistent hashing · 60 min
Defend consistent hashing on the ring out loud
Deep dive: replication, consistency, and failures
This is the decision that keeps the cache up. A node dies — its keys and its share of traffic must not vanish — and some keys get hammered far harder than the rest.
Replicate each shard to a follower. Every node's keyspace is copied to one or more replica nodes, so when a node fails its replica serves the arc and the ring repartitions the load to neighbors with minimal churn. Then decide how writes propagate between the cache and the backing database, because that choice is the consistency tradeoff the interviewer wants named:
| Write pattern | How it works | Tradeoff |
|---|---|---|
| Cache-aside (lazy) | App reads cache; on a miss it loads from the DB and populates the cache. Writes go to the DB and invalidate the key. | Simple and resilient; first read after a miss or invalidation is slow, and stale reads are possible between write and invalidation. |
| Read-through | The cache itself loads from the DB on a miss, transparently to the app. | Cleaner app code; the cache must know how to fetch. |
| Write-through | Writes go to the cache and the DB synchronously before acking. | Cache and DB stay consistent; every write pays the DB latency. |
| Write-back (write-behind) | Writes hit the cache and are flushed to the DB asynchronously. | Fast writes, absorbs bursts; risk of data loss if a node dies before the flush. |
Then name the two failure modes that bite a cache specifically. A hot key — one key read a million times a second — overloads the single node that owns it; you mitigate by replicating that key to several nodes, letting clients hold a short-lived local copy, or coalescing requests. A cache stampede (thundering herd) happens when a popular key expires and thousands of concurrent misses hit the database at once; you mitigate with request coalescing (one fetch fills the key while the rest wait), slightly randomized TTLs, or serving a stale value while one worker refreshes.
"One key is being read a million times a second — what breaks, and what do you do?" The single node owning that key saturates. Replicate the hot key across several nodes or let clients cache it briefly, and coalesce concurrent misses so only one request refills it. Naming both the hot-key node overload and the stampede on expiry is the senior move.
The follow-ups that decide the distributed cache round
Scan the probes from each deep dive and they rhyme. Master these five and you are ready for a version of the question that is not drawn exactly like this one.
-
"Why not just
hash(key) % N?" → Because changingNremaps almost every key and stampedes the database; consistent hashing moves only ~1/N on churn. (communication) - "Add a node to a ten-node cluster — how many keys move?" → About a tenth, from the neighbor whose arc the new node splits, not the whole keyspace; virtual nodes spread that tenth evenly. (problem solving)
- "A node dies — what happens to its keys and traffic?" → Its replica serves the arc and the ring repartitions the load to neighbors; nothing is lost if the shard was replicated. (technical execution)
- "Your node is full — which key do you evict, and how fast?" → The LRU key, in O(1): a doubly linked list keeps the victim at the tail, a hash map deletes it by key with no scan. (technical execution)
- "One key is read a million times a second — what breaks?" → The node owning the hot key saturates; replicate the key, cache it client-side briefly, and coalesce concurrent misses to beat the stampede. (problem solving)
Each maps to a debrief dimension. Reading this list teaches you the answers; it does not teach you to deliver them while someone interrupts — that only comes from saying them out loud.
How to prepare: a one-week plan
You do not need fifty systems. You need this one cold and the framework automatic, so the next "design X" is just new nouns in the same five steps.
- Days 1–2: Learn the five-step framework until it is reflex. Do the distributed cache end to end on paper — requirements, estimate, API, data model, the ring-and-nodes boxes.
- Days 3–4: Drill the single-node internals and consistent hashing: hash map plus doubly linked list for O(1) LRU, the hash ring, modulo vs consistent hashing, virtual nodes. Say each tradeoff in one sentence.
- Days 5–6: Own replication and failures — replicas, cache-aside vs write-through vs write-back, hot keys, and cache stampede. Answer each of the five follow-ups out loud.
- Day 7: A full timed 60-minute round, narrating the whole way, with someone (or something) interrupting. This is the rep that counts.
This guide is the deep walkthrough behind one row of the broader Top 25 system design interview questions — once the distributed cache is automatic, the same spine carries the rest of the list.
Frequently asked questions
How do I design a distributed cache step by step?
Follow the five-step HLD framework. Clarify requirements (get / put at O(1), TTL, eviction when full, scale by adding nodes; low latency, high availability, even load, minimal churn); estimate to show the hard axis is key movement on churn, not raw storage; define the tiny get / put / delete API and a thin entry / node / ring model; draw the architecture (a ring-aware client routing keys to in-memory cache nodes with replicas, a backing database on a miss, a coordinator for membership); then deep-dive the decisions that matter — single-node O(1) eviction, consistent hashing for sharding, and replication with write patterns. Finish on the follow-ups about churn and hot keys.
Why use consistent hashing instead of modulo hashing for a cache?
Because modulo hashing reshuffles the whole keyspace whenever the cluster changes size. With hash(key) % N, adding or removing a node changes N, so almost every key maps to a new node and the cache has to re-warm from the database all at once — a stampede. Consistent hashing places keys and nodes on a circular hash ring and assigns each key to the next node clockwise, so adding or removing a node only moves the keys in one arc — about 1/N of them, from a single neighbor. Virtual nodes keep that movement evenly spread.
How does an LRU cache get O(1) eviction?
By pairing a hash map with a doubly linked list. The hash map gives O(1) lookup, insert, and delete by key; the doubly linked list orders entries by recency with the most-recently-used at the head and the least-recently-used at the tail. On every access you move the entry to the head in O(1), and when the node is full you evict the tail in O(1) — the map lets you delete the victim's key without scanning. Neither structure alone is enough: the map cannot tell you what to evict, and the list cannot find a key.
What are virtual nodes in consistent hashing?
Virtual nodes are multiple positions on the hash ring that all map to the same physical node. A plain ring with few nodes produces uneven arcs, so some nodes own far more keys than others. Giving each physical node many tokens — say 100 to 200 points around the ring — splits the keyspace into many small arcs that average out to even load. They also let a larger machine take proportionally more tokens and spread a departing node's load across many neighbors instead of dumping it on one.
How does a distributed cache handle a node failure?
By replicating each shard and repartitioning on the ring. Every node's keyspace is copied to one or more follower replicas, so when a node dies its replica keeps serving that arc and no keys are lost. The ring then folds the dead node's arc into the next node clockwise, which moves only that arc's keys rather than the whole keyspace. With virtual nodes, the failed node's load spreads across many neighbors, so no single survivor is overwhelmed.
How do I practise a system design interview out loud?
Reading a guide is not the same as defending a design while someone interrupts. On Zynter, the HLD track runs live voice rounds modelled on how real system design loops run — you talk through a shared design on the canvas, and a voice interviewer pushes with the follow-ups above one at a time, then gives you a debrief on problem solving, communication, technical execution, and time management. The score is a practice signal, not a hiring decision.
Practise it on Zynter
You can read every arc of the ring. The round is won on the reshuffle math and the hot key.
Pick the Distributed Cache round, draw the ring-and-nodes design on the canvas, and defend it out loud to a voice interviewer that keeps asking "add a node — how many keys move?" and "one key is read a million times a second — what breaks?" — then read the debrief. Zynter.ai is on-demand mock interviews modelled on real company loops, with 150+ rounds across 20 companies including the HLD system design track (Sep 2026).
Practise the Distributed Cache round →
Browse all interview tracks
Top comments (1)
One distinction I'd make in the LRU section: O(1) to evict one entry doesn't necessarily mean O(1) for the whole put. With a byte budget and differently sized values, one large insert may require evicting several small entries. I'd state the per-victim cost separately from the worst-case write cost. That also gives the interviewer a useful follow-up beyond the usual map-plus-list explanation.