Design a distributed cache (Redis-style)
You've used a cache in every scaling answer so far. Now you design the cache itself — a service that stores key→value pairs in memory across many machines and answers reads in under a millisecond. It's a favorite mid-level prompt because it forces the four pillars together: eviction, sharding, replication, and consistency. Every concept from scaling primitives shows up, applied to one concrete box.
📖 Walk me through it — plain English
A cache is a coat-check for data. You hand it a ticket (a key) and it hands back your coat (the value) almost instantly, because it keeps everything in fast memory (RAM) instead of slow disk. The catch: the coat-check is small. It can't hold everyone's coat forever, so when it fills up it has to throw some out — that's eviction, and the rule for which coat to throw out is the heart of the design.
One coat-check booth can only hold so much and serve so many people, so you build many booths — that's distributing the cache. Now you need a rule for which booth holds which ticket (sharding), and you'd like a backup booth in case one burns down (replication). The whole lesson is: pick an eviction rule, spread keys across booths so adding/removing a booth is cheap, and decide how hard you'll try to keep backups in sync.
The honest truth a senior states out loud: a cache is allowed to be wrong. It can be stale or even lose data — that's acceptable because the source of truth is the database behind it. That single admission unlocks simpler, faster choices than a database would permit.
Step 1 · Clarify & API
Scope it in one breath: a key-value store, values up to a few MB, sub-millisecond reads, the cache may evict or lose data (the DB is the source of truth). The API is tiny:
The optional TTL (time-to-live) auto-expires an entry after N seconds — the simplest staleness control. Naming it here shows you know cache data must not live forever.
Step 2 · Eviction: which key to drop when full
Memory is finite, so a full cache must evict on every new write. The policies, and when each wins:
- LRU (least-recently-used): evict the key untouched for the longest. The default — it assumes recently-used keys will be used again (temporal locality), which holds for most workloads.
- LFU (least-frequently-used): evict the key used fewest times. Better when a stable hot set should survive a burst of one-off requests that would otherwise flush it.
- FIFO: evict the oldest-inserted regardless of use. Simple but ignores access patterns; rarely the right call.
- TTL-based: entries expire on a timer; eviction is just "drop whatever already expired." Often combined with LRU.
How LRU runs in O(1). The classic interview detail: a hash map + doubly-linked list. The map gives O(1) lookup from key to its list node; the list keeps keys in recency order (most-recent at the head). On get, move that node to the head. On set when full, drop the tail (the least-recently-used) and add the new key at the head. Every operation is O(1) — no scanning. This is also LeetCode #146; the design round and the coding round meet here.
Step 3 · Sharding: spread keys across nodes
One machine's RAM caps total cache size, so you run many nodes and split keys across them. The naive route — hash(key) % N — is a trap you should name and reject: changing N (a node dies, you add capacity) remaps almost every key at once, causing a cache-miss storm where every client suddenly misses and stampedes the database. The fix is the ring you learned in scaling primitives: consistent hashing, where adding or removing a node moves only ~K/N keys, so a topology change barely dents your hit rate.
Where the routing lives is its own choice: a smart client library that knows the ring (no extra hop, used by Redis Cluster), or a proxy in front (simpler clients, one more hop). Either is defensible — say the tradeoff.
Step 4 · Replication & the consistency you can skip
If a node dies, its slice of the cache vanishes — survivable (those keys just refill from the DB) but a sudden DB load spike. So you keep a replica per shard: one primary serves reads/writes, a follower stays warm to take over. Because a cache isn't the source of truth, you replicate asynchronously — the primary acks the write immediately and copies to the follower in the background. You accept that a failover might lose the last few writes, because those values can always be recomputed from the database. That's the senior insight: a cache earns the right to weaker consistency than its backing store.
Step 5 · The failure modes that actually bite
A hot key expires and 10,000 requests all miss and hit the DB at once. Fix: a per-key lock so only one request recomputes while others wait, or serve slightly-stale while one refreshes in the background.
One key (a celebrity, a viral post) overwhelms its single shard. Fix: replicate that key across nodes, or append a small random suffix to spread copies.
Requests for keys that don't exist always miss and always hit the DB. Fix: cache the "not found" result briefly, or a Bloom filter to reject known-absent keys.
DB updated, cache still old. Fix: invalidate (delete) the key on write rather than trying to update it in place — simpler and avoids races.
Takeaway: a distributed cache is the whole scaling toolkit in one box. Tiny KV API with TTL; LRU via hash map + doubly-linked list for O(1) eviction; consistent hashing to shard without a miss storm when nodes change; async replication because the cache may lose data the DB can recompute. Then name the four classic failures — stampede, hot key, penetration, staleness — and their fixes. The reusable insight: a cache is allowed to be wrong, which is exactly what lets it be fast.
→ Going deeper: this is scaling primitives made concrete — consistent hashing, replication, consistency models all reappear. The LRU mechanism is a coding problem too; the eviction-vs-staleness call is a perfect CBW rehearsal.