Interview Walkthrough: Design a Distributed Cache

The distinction to establish first, because everything follows from it: a cache is defined by the fact that losing it is acceptable. The data exists somewhere else. That single property is what makes eviction a feature rather than a bug.

Minute 0–4: Cache or store?

Interviewer: "Design a distributed cache."

"Functionally: get, set, delete, with a TTL. Non-functionally: sub-millisecond reads, horizontal scalability, and availability — with the caveat that a cache miss is a degradation, not an error.

Worth saying up front: the API is identical to a key-value store, which is why the distinction gets lost. The difference is what it means to lose the data. Here it's acceptable — which is why we can evict aggressively, keep everything in memory, and treat durability as optional. A store cannot make any of those choices."

Minute 4–8: Why memory, and why distributed

"RAM because the whole point is to be an order of magnitude faster than the thing behind it, and that gap comes from avoiding disk entirely. The cost is that memory is expensive and finite, which is what forces eviction.

Distributed for two independent reasons, and it's worth separating them: capacity, because the working set exceeds one machine's RAM, and availability, because one cache node holding everything is a single point of failure whose loss lands entirely on the database.

That second reason is the one people skip, and it changes the design — it's why we replicate, not just shard."

Minute 8–16: The design

Placing keys

"Consistent hashing, and the justification is specifically about failure. With modulo hashing, losing one node of ten remaps roughly 90% of keys — so a single node failure doesn't cost you a tenth of your cache, it costs you almost all of it, and the resulting miss storm hits the database exactly when you've already lost capacity.

Consistent hashing bounds that to the failed node's own range. Virtual nodes on top, because with a small number of servers the ring is lumpy and one server ends up owning a disproportionate arc.

The client resolves the key to a node itself, using a server list kept current by a configuration service. That keeps a proxy hop off the read path."

Eviction and invalidation are different questions

"These get conflated constantly. Eviction asks what do I drop to make room? Invalidation asks what is no longer true? One is about capacity, the other about correctness.

LRU for eviction, because it encodes locality of reference and that assumption usually holds — recent access predicts future access. LFU is the tempting alternative and has a specific failure: something enormously popular last year keeps its slot forever, outranking what's hot today. That's cache pollution, and it's why LFU needs aging to be usable.

For invalidation, TTL as the baseline, with active expiry sweeping in the background and passive expiry checking on read. Passive alone means an untouched expired entry occupies memory indefinitely."

Minute 16–28: Deep dives

"A popular key expires. What happens?"

"Thundering herd, and I'd flag it unprompted because it's the failure that only appears under load. The cache was absorbing thousands of reads a second for that key; the instant it expires they all become database queries simultaneously.

Three fixes, and they compose.

Request coalescing is the highest-value one: let the first miss fetch and make every concurrent miss for the same key wait on that fetch. That caps origin load at one query per key regardless of arrival rate.

Probabilistic early expiry — each read decides, with rising probability as the TTL nears, to refresh early. Refreshes stagger and the cliff never forms.

Serve stale while revalidating — return the expired value and refresh in the background, so readers get slightly old data instead of a latency spike.

It's the same shape as synchronized retries after an outage, and the fixes rhyme: stagger the timing, or elect one actor to do the work for everyone."

"What about a hot key?"

"First the thing people get wrong: resharding doesn't help. Sharding splits key ranges, and a single key is the atom of the scheme — it lives on one node no matter how you slice the ring.

Hot reads: replicas let reads spread, but that's a fixed multiple like 3x, not scalable. Beyond it you replicate the key itself under suffixed names and have clients pick one at random — real application-code work, and worth saying so rather than waving at it.

Hot writes are a different problem and replicas do nothing, since every replica applies every write anyway. The fix is client-side batching — buffer for tens of milliseconds and apply one consolidated update. That works when only the final value matters, like counters, and fails when every individual event must be observable."

"How does the cache stay fast as it grows?"

"The counter-intuitive part: the in-memory lookup is already the cheapest thing in the request. Latency lives in the network round trip and serialization around it.

So the wins are pooled connections, batching many keys into one round trip, and co-location — not a faster hash table. Optimizing the data structure buys nothing once you're distributed."

"What are the honest limits?"

"Cross-data-center consistency. Within one data center you can replicate synchronously and get strong consistency. Across data centers synchronous writes are too slow, so you go asynchronous and accept eventual consistency — which means a read in one region can return a value another region has already invalidated.

Most caching systems accept that, and the reason is the framing we opened with: a stale cache entry is a correctness problem for the application, not for the cache — which is why invalidation is famously hard and why short TTLs are the pragmatic backstop."

If you only have five minutes

"A cache is defined by losing it being acceptable — that's what makes eviction a feature and durability optional.

Consistent hashing with virtual nodes, justified by failure: modulo hashing remaps nearly every key when one node dies, turning a partial failure into a total cache wipe and a miss storm.

LRU for eviction because locality of reference usually holds; TTL for invalidation with both active and passive expiry.

The follow-up to volunteer is the thundering herd — when a hot key expires every request misses at once, and the fixes are request coalescing, probabilistic early expiry, and serve-stale-while-revalidating.

And hot reads and hot writes need different fixes: replicas for reads, client-side batching for writes."