Design a Distributed Cache (Redis-like)

Design a Key-Value Store built a Dynamo-style store where losing data is unacceptable. This problem looks similar on the surface — the same GET/SET shape, the same need to partition across nodes — but starts from the opposite non-functional requirement: this store is a cache, sitting in front of another system that's already the source of truth, so losing its data is an acceptable, recoverable event, and that one difference changes almost every decision that follows. It's the system Distributed Caching already describes conceptually; this problem builds it. Following the framework from How to Answer a System Design Interview Question.

1. Requirements

Functional:

• GET/SET/DEL, with an optional TTL after which a key expires automatically.
• Evict keys automatically when a node's memory fills up, favoring keeping the most useful data resident.

Non-functional:

• Extremely low latency — sub-millisecond — since this sits directly on the critical path of every cache-consuming request.
• Data loss on a node crash is acceptable: the real data still lives in the origin database, so a lost cache node just means a burst of cache misses, not lost information. This is the sharpest possible contrast with the Key-Value Store's core requirement.
• Must handle a small number of extremely popular keys ("hot keys") without one node buckling under disproportionate traffic.

Scale estimate: assume a cluster holding 500M keys, averaging 1KB each (~500GB total, spread across many nodes' memory), serving 2M reads/sec at peak — a workload defined entirely by memory capacity and per-operation speed, not by durability.

2. API Design

GET key
SET key value [TTL seconds]
DEL key

3. Data Model

Same partitioned shape as the Key-Value Store — keys hashed onto nodes via Consistent Hashing — but each node's local storage is now explicitly just memory, with no durable write-ahead log or disk persistence required by default, since nothing downstream depends on this store surviving a restart.

node's local state (in-memory only)
  key -> { value, expires_at, last_accessed }

4. High-Level Design

System Design Lab

5. Deep Dive: eviction and hot keys at cluster scale

Each node needs an eviction policy for when it runs out of memory — Cache Eviction Policies covers the general tradeoffs (LRU, LFU, TTL), and the practical choice at this scale is almost always an approximate LRU: tracking exact last-access order for every key is itself real memory and coordination overhead, so real systems (Redis included) sample a small random subset of keys and evict the least-recently-used among just that sample — nearly as effective as true LRU, at a small fraction of the bookkeeping cost.

The harder problem Distributed Caching already named is hot keys: consistent hashing spreads keys evenly on average, but one extremely popular key still lives on exactly one node, and no partitioning scheme fixes that, because the problem isn't uneven key placement — it's uneven traffic to one key. The standard mitigation is replicating a hot key's value onto several nodes (or into each application server's own small local cache) once its request rate crosses a threshold, so reads for it are spread across multiple places instead of funneling through the one node consistent hashing happened to assign it to.

System Design Lab

6. Deep Dive: why this system can skip what the Key-Value Store couldn't

This is the deep dive that's actually specific to being a cache rather than a general-purpose store, and it's worth stating as its own explicit design decision: because losing data just means a cache miss (recoverable by re-fetching from the origin database), this system doesn't need Data Replication for durability at all — unlike the Key-Value Store, where replication was mandatory because there was no other copy of the data anywhere. Some real caches still replicate lightly, but for a different reason than durability: to avoid a cold cache after a restart causing a sudden burst of cache misses (a "thundering herd" against the origin database the moment a node comes back empty) rather than to prevent data loss itself. Naming this distinction — replication here is optional and serves availability/warm-restart concerns, not correctness — is the single clearest way to demonstrate this problem has actually been understood as different from the Key-Value Store, not solved by copying that answer.

7. Tradeoffs

Skipping replication entirely keeps the system simpler and faster (no replication traffic, no consensus needed for writes), and is a perfectly valid choice given the requirements — but it means every node restart or crash starts that node fully cold, sending a burst of traffic to the origin database for every key that node used to hold. Light replication avoids that burst at the cost of real ongoing replication overhead for data that, by design, was never required to be durable in the first place.

The approximate-LRU eviction from the deep dive above carries a smaller version of the same accuracy-vs-cost tradeoff: sampling more keys per eviction gets closer to true LRU's ideal (always evict the actual least-recently-used key) at the cost of more work done on every eviction, while sampling fewer keys is cheaper but risks evicting a key that's still genuinely useful, just because it wasn't in the small sample checked. Neither choice is free — this system is explicitly trading a small, bounded amount of eviction accuracy for memory and CPU headroom that goes straight back into serving the sub-millisecond reads this cache exists for.

No replication vs. light replication for a pure cache: pros and cons

No replication

• ✓Simpler system with no replication traffic or consensus needed for writes
• ✓Lower latency per write — nothing to wait on beyond the local node
• ✓Matches the actual requirement — durability was never needed for a pure cache

Light replication

• ✕A restarted node comes back completely cold, missing every key it held
• ✕Can cause a burst of cache misses hitting the origin database at once
• ✕Adds real replication overhead for data that was never required to be durable

Further Reading

• Redis Docs — LRU/LFU key eviction — a concrete reference for approximate eviction as actually implemented.
• Facebook Engineering — Scaling Memcache at Facebook — a widely cited real-world account of hot-key mitigation and cache warming at large scale.