Design a Distributed Cache (Redis-like)

Three things: placement, eviction, hot keys/stampedes

A distributed cache is the workhorse that sits in front of your database and absorbs the read load that would otherwise crush it. The interview tests three things: how you spread keys across nodes, how you evict when memory fills, and how you survive a hot key or a cache stampede.

Placement: consistent hashing

The naive approach is node = hash(key) % N. It works until you add or remove a node, at which point almost every key maps somewhere new and your hit rate collapses to near zero while the whole fleet stampedes the database. Consistent hashing fixes this: map both keys and nodes onto a fixed ring (say a 2^32 space), and a key belongs to the first node clockwise from its hash. Adding a node only steals keys from its immediate neighbor, so only about 1/N of keys move. Raw consistent hashing gives lumpy load because node positions are random, so use virtual nodes: give each physical node 100 to 200 points on the ring. Now load evens out and, when a node dies, its keys spread across many survivors instead of dumping onto one neighbor.

Interview nuance: if you say "hash mod N" and do not immediately catch that adding a node reshuffles the world, that is a red flag. Lead with consistent hashing plus virtual nodes.

Eviction and caching patterns

You cannot hold everything, so pick a policy. LRU (least recently used) is the default and fits most workloads because recency predicts reuse. LFU (least frequently used) beats LRU when a small set of keys is popular over a long window and you do not want a scan to evict them. TTL-based expiry is orthogonal and almost always on too. Redis actually samples a handful of keys and evicts the best candidate rather than maintaining a perfect LRU list, trading exactness for O(1) writes.

Cache-aside (the app reads cache, on miss reads the DB and populates the cache) is the common default and keeps the cache out of the write path. Write-through writes cache and DB together for freshness at the cost of write latency. Write-back writes cache first and flushes to the DB asynchronously for speed, at the risk of data loss on crash.

Stampedes and hot keys

A cache stampede happens when a hot key expires and thousands of concurrent requests all miss and hit the DB at once. Fix it with request coalescing (a single in-flight fetch per key, others wait for its result), a short randomized TTL jitter so keys do not all expire together, or serving stale-while-revalidate. A hot key is a single key so popular it saturates one node's CPU or network. Consistent hashing alone does not help because it is one key on one node, so replicate the hot entry across several nodes and randomize which replica a client reads, or add a small local in-process cache in front of the distributed tier.

Replication gives availability: each shard has a primary and one or more replicas, with async replication for speed (and a small window of lost writes on failover) or sync for safety. On primary failure a sentinel or the cluster gossip promotes a replica.

GET k -> hash(k) -> ring -> node N3 (primary)
   miss -> coalesce -> DB read -> SET k (jittered TTL) -> return
hot key: replicate k to N3,N5,N7 -> client picks a random replica

Recap: place keys with consistent hashing plus virtual nodes (never hash mod N), evict with LRU or LFU plus TTL, choose cache-aside by default, and defend hot keys with replication and stampedes with coalescing plus TTL jitter.