Almost every read-heavy system ends up with a cache in front of its database. In this question the interviewer flips it around: don't use Redis, build the thing Redis Cluster or a Memcached fleet is. Where does a key live? What happens when a node dies, when you add one, or when one key gets a tenth of all traffic?
The distributed-cache interview end to end: get, set with TTL and delete at 1M ops/s under 1 ms; about 1 TB of hot data on 20 primaries plus replicas; smart clients hashing keys to 16,384 fixed slots for one hop and cache-aside on a miss. Deep dives show why mod-N resizing remaps ~95% of keys while slots move ~5%, and how a local L1 cache, replica reads and single flight tame a hot key; failover promotes a replica under a new epoch.
Phase 1: Requirements (5 minutes)#
"Is this a cache in front of a database, or a store that has to keep data on its own?"
"A cache. The database is the source of truth. If you lose a key, the application can reload it, but if you lose a lot of keys at once the database falls over."
That one answer sets the tone for everything: we can trade durability for speed, but we cannot let a failure turn into a flood of misses.
get(key)returns the value or a missset(key, value, ttl)stores a value that expires after its TTLdelete(key)removes a key (used for invalidation when the database changes)- Eviction when memory is full: drop the least valuable keys first (LRU or LFU)
- Nice to have: atomic
incrand compare-and-set for counters and locks - Out of scope: queries by value, multi-key transactions, being the system of record
- Latency: p99 under 1 ms for a get, inside one region
- Throughput: 1M ops/s at peak, about 90% reads
- Scale out: add capacity by adding nodes, without remapping most keys
- Availability: a node failure loses at most a small slice, briefly
- Consistency: eventual is fine (it's a cache), but staleness is bounded by TTL and explicit deletes
Phase 2: Estimation (5 minutes)#
"Let me size memory first, because memory decides the node count, and then check that throughput and network fit."
- Keys in the hot set: 500 million (assumed)
- Average key + value + per-item metadata: ~2 KB
- Hot data: 500M × 2 KB = ~1 TB
- Usable RAM per node: a 64 GB machine keeping ~20% headroom for fragmentation and replication buffers: ~50 GB
- Primaries: 1 TB ÷ 50 GB = 20 shards; with one replica each: 40 nodes
- Throughput per primary: 1M ops/s ÷ 20 = 50,000 ops/s, comfortably inside what one in-memory node does for small values (on the order of 100,000 ops/s), with 2x headroom
- Network per primary: 50,000 × 2 KB = ~100 MB/s (~0.8 Gbps) on a 10 Gbps NIC
- The warning sign: if one key takes 10% of all reads, that is 90,000 ops/s and ~1.4 Gbps on one node, more than the whole shard's normal load
The estimate tells you where the design will be tested: memory is easy to buy, but traffic is never evenly spread. Hot keys get a deep dive of their own.
Phase 3: API (3 minutes)#
The cache speaks a compact binary or text protocol over long-lived TCP connections (an HTTP round trip would eat most of the 1 ms budget). The operations:
get(key) -> value | MISS
set(key, value, ttl_seconds) -> OK
delete(key) -> OK
incr(key, delta) -> new_value
cas(key, value, version) -> OK | CONFLICT # set only if unchanged since read
mget(keys[]) -> values[] # client splits by shard, runs in parallelKeys are opaque strings with a namespace, such as user:42:profile, capped at a few hundred bytes. Values are capped too (say 1 MB), because one huge value blocks a single-threaded node for everyone behind it.
Phase 4: High-level design (10 minutes)#
%% title: Distributed cache: smart clients, hash slots, primary + replica shards
flowchart TD
APP@{ icon: "sd:servers", label: "App servers<br/>cache client library" }
CFG@{ icon: "tech:etcd", label: "etcd · cluster map<br/>slot ranges → nodes" }
APP -->|"hash(key) → slot → node"| SA@{ icon: "sd:cache", label: "Shard A · primary<br/>slots 0–819" }
APP --> SB@{ icon: "sd:cache", label: "Shard B · primary<br/>slots 820–1,638" }
APP -.->|"… 20 shards"| SN@{ icon: "sd:cache", label: "Shard T · primary" }
SA -->|"async replication"| RA@{ icon: "sd:cache", label: "A · replica" }
SB -->|"async replication"| RB@{ icon: "sd:cache", label: "B · replica" }
HM["Failure detector<br/>heartbeats, promotes replicas"]:::core
HM --> CFG
CFG -.->|"map updates"| APP
APP -->|"on miss"| DB@{ icon: "sd:database", label: "Database<br/>source of truth" }
class APP client
class CFG store
class SA,SB,SN,RA,RB cache
class DB storeHow a request flows:
- Hash the key. The client library computes
slot = crc16(key) mod 16,384(a fixed number of slots, the scheme Redis Cluster uses). - Find the node. It looks the slot up in its local copy of the cluster map (slot ranges → node addresses), fetched from the config store and refreshed on change.
- One hop. It sends
getstraight to that shard's primary over a pooled connection. No proxy, no extra network hop. - Miss path. On a miss the application reads the database and writes the value back with a TTL (cache-aside).
- Map changed? If the slot moved, the node answers "moved to X"; the client updates its map and retries once.
The key decision is smart client vs proxy tier:
Smart client
- One network hop: lowest latency
- No extra fleet to run and scale
- Every language needs a correct client library
- Thousands of clients each hold connections to every node
Proxy tier
- Clients stay dumb: any language, simple protocol
- Proxies pool connections, so nodes see far fewer
- An extra hop on every request (often ~0.1–0.3 ms)
- The proxy fleet is one more thing to scale and to fail
"I'll start with smart clients for the latency budget, and add a proxy layer only if connection counts become the bottleneck."
Phase 5: Deep dives (15 minutes)#
Deep dive 1: Partitioning, and what happens when the cluster changes#
Why not just hash(key) mod N?
With 20 nodes, node = hash(key) mod 20 spreads keys evenly. What fraction of keys land on a different node when you grow to 21? What does that do to the database?
One strong answer
- Almost all of them move. A key stays put only if
hash mod 20equalshash mod 21, which happens for about 1 key in 21. Roughly 95% of keys now point at a node that doesn't have them. - The database pays. A cache that suddenly misses 95% of reads sends nearly the whole read load to the database at once: adding capacity causes an outage.
- The fix: decouple keys from nodes. Hash keys onto a fixed space (a hash ring with virtual nodes, or a fixed set of slots), and map that space to nodes. Adding a node then moves only about 1/21 ≈ 5% of keys.
Two standard ways to get there:
- Consistent hashing with virtual nodes. Each node owns many points on a hash ring (say 100–200 each); a key belongs to the next point clockwise. Many points per node smooth out the load, and a new node takes small slices from everyone instead of half of one neighbour.
- Fixed hash slots. Hash keys into a fixed 16,384 slots and assign slot ranges to nodes. Rebalancing is explicit: move slot 812 from A to the new node U, key by key, while both answer. During the move, A answers "ask U" for keys already migrated. This is easier to reason about and to operate: the map is small and the moves are visible.
"I'd pick fixed slots. The cluster map is a few kilobytes, a rebalance is a list of slot moves an operator can pause, and the client logic is a table lookup."
Deep dive 2: Hot keys and the stampede#
Even with perfect partitioning, traffic isn't uniform. A celebrity profile, a flash-sale product or a config blob can take a big share of reads, and all of them land on one shard. From the estimate: 10% of reads on one key is 90,000 ops/s and about 1.4 Gbps on a single node.
1. A small local cache in the client (L1)
Keep the hottest few thousand keys in each app server's memory for 1–5 seconds. 200 app servers each asking once per second turns 90,000 ops/s into ~200. The cost is up to a few seconds of extra staleness.
2. Read from replicas
For keys flagged hot, spread reads across the primary and its replicas. That multiplies capacity by the replica count, at the price of reading slightly behind the primary.
3. Split the key
Store N copies as product:9:copy1 … copyN, which hash to different shards. Reads pick a random copy; writes update all N (or delete all N). Use it for the handful of truly extreme keys.
4. Detect it
Nodes sample their top keys and report them; the client library marks those keys hot and switches on the defences above automatically.
The other half of the hot-key problem is expiry. When a hot key's TTL runs out, every request that misses goes to the database at the same moment: a thundering herd.
- Request coalescing (single flight): the first miss takes a short lock (
set lock:key NX EX 5) and loads the value; everyone else waits briefly or gets the stale value. - Stale-while-revalidate: keep serving the old value for a few seconds past its TTL while one background refresh runs.
- Jittered TTLs: expire keys at
ttl ± 10%so a batch written together doesn't expire together.
Phase 6: Trade-offs and failure modes (5 minutes)#
A primary dies
Heartbeats miss for a few seconds; the failure detector promotes the replica and bumps the map's epoch. Writes the old primary acknowledged but hadn't replicated yet are lost. Acceptable for a cache, and the reason a cache is never the system of record.
Split brain
A network partition can leave the old primary alive and accepting writes. Every map change carries an epoch number, and nodes reject requests stamped with an older epoch, the same idea as a fencing token.
Cache and database disagree
Cache-aside has a race: a reader loads an old value from the database, a writer updates the database and deletes the key, and the reader then writes its old value back. Delete on every write, keep TTLs as a safety net, and for critical keys use versioned writes (cas).
Cold restart
After a full restart the hit ratio is 0% and the database takes everything. Restart nodes one at a time, warm hot keys from a snapshot or a key list, and rate-limit the miss path.
Memory pressure
When memory fills up, eviction takes over. Exact LRU costs a linked list per key; sampled LRU (check a few random keys, evict the oldest, which Redis does) gets close for almost no memory. LFU suits workloads where a scan of one-off keys would otherwise flush the hot set.
| Decision | We chose | We gave up |
|---|---|---|
| Replication | Async, 1 replica | A few seconds of acknowledged writes on failover |
| Routing | Smart client, fixed slots | Simplicity for non-standard languages |
| Hot keys | L1 local cache + replica reads | A few seconds of extra staleness |
| Consistency | Delete-on-write + TTL | Strong consistency with the database |
Go deeper in the course#
- Week 4, Day 1: Caching patterns: cache-aside, read-through, write-through and write-behind, and when each fits
- Week 4, Day 2: Invalidation strategies: the delete-on-write race and how TTLs, events and versions close it
- Week 4, Day 3: Thundering herd: single flight, stale-while-revalidate and early expiry in depth
- Week 4, Day 5: Multi-tier caching: the L1 local cache in front of the distributed one
- Week 1, Day 1: Partitioning deep-dive: mod-N, consistent hashing and the resharding problem
- Week 1, Day 4: Hot keys and skew: detecting hot keys and splitting them
- Week 1, Day 2: Replication trade-offs: async replication, lag and correct failover
- Week 5, Day 5: Leader election: fencing tokens, the idea behind the cluster epoch
- Week 4 capstone: global product catalog: a whole system designed around a cache
Check yourself#
Distributed cache
Q1/4 A 20-node cache uses node = hash(key) mod N. You add a 21st node. Roughly what share of keys now map to a different node?
Answer & explanation
Answer: C
A key stays put only when hash mod 20 equals hash mod 21, about 1 in 21. With a ring or fixed slots, only ~1/21 of keys move.
Q2/4 One product key takes 10% of all reads and its shard saturates. What is the cheapest first fix?
Answer & explanation
Answer: A
More shards don't help: one key still hashes to one shard. A 1–5 second L1 cache turns tens of thousands of reads a second into roughly one per app server per second.
Q3/4 A primary fails and its async replica is promoted. What can be lost, and why is that acceptable here?
Answer & explanation
Answer: D
Async replication acknowledges before the replica has the write. For a cache that's fine: a lost key is a miss, and the database is the source of truth.
Q4/4 A hot key expires and 5,000 requests miss at once. Which technique stops them all hitting the database?
Answer & explanation
Answer: B
Single flight (or stale-while-revalidate) lets one request rebuild the value while the rest wait or read the stale copy.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.