Prompt
Design an in-memory key-value cache (think Redis/Memcached) that supports
get,put, and TTL, scales across many nodes, stays fast (sub-millisecond), and survives node failures without losing the whole cache.
It's the bridge from the LRU cache you code in LLD to a distributed system. SDE-1: the single-node design (hash map + eviction). SDE-2: sharding with consistent hashing and TTL/eviction policy. SDE-3 / Staff: replication, failure handling, hot keys, and client- vs server-side routing. Asked at Amazon, Meta, Microsoft, Snowflake; also the backbone of the URL-shortener read path.
1. The single node first
One cache node is a hash map for O(1) lookup plus an eviction policy for when
memory fills — exactly the LRU cache: a hash map paired with a doubly
linked list so get, put, and evict-the-least-recent are all O(1). Add a TTL per
entry (expiry timestamp; treat expired as a miss, plus a background sweeper).
1/8Empty LRU cache, capacity 3. A hit is served from memory; a miss must fetch from the slow store, then cache it — evicting the least-recently-used key once the cache is full.
2. Scaling out — how do keys find a node?
The whole problem is routing a key to the right node, and surviving the node count
changing. Naive hash(key) % N remaps almost every key when N changes (a node added
or lost), causing a mass cache miss — a "cache stampede" against the database.
Consistent hashing fixes it: nodes and keys are hashed onto a ring; a key belongs to the next node clockwise. Adding or removing a node moves only ~1/N of keys, not all of them. Virtual nodes (many points per physical node) smooth out uneven distribution.
1/83 nodes on the ring. Each key belongs to the next node clockwise from its hash position — that's the whole rule.
3. Replication & availability
A pure cache miss isn't fatal (you reload from the DB), but losing a node full of hot keys is — every one of those keys now stampedes the database. So replicate:
- Primary–replica per shard: each shard's keys live on a primary plus one or more replicas. If the primary dies, a replica is promoted; reads can also fan out to replicas.
- Gossip / membership: nodes track who's alive (gossip protocol) so the ring updates and only the failed node's ~1/N slice rehashes.
4. Eviction & consistency
- Eviction policy: LRU (default) or LFU for skewed access; some workloads use random or TTL-based. (Same policy you implement in LRU cache.)
- Write strategy: a cache sits in front of a DB — see the caching strategies page for cache-aside vs write-through and invalidation, the genuinely hard part.
- It's a cache, not a database: it can drop data under memory pressure; never treat it as the source of truth.
5. The hot key
Consistent hashing balances many keys, but one ultra-popular key still lands on a single node and can overload it. Mitigate by replicating that key across several nodes, or adding a small client-local cache in front of the distributed tier for the hottest entries.
Client-side vs server-side routing
- Client-side (Memcached-style): the client library knows the ring and picks the node — no extra hop, but every client must agree on membership.
- Server-side (Redis Cluster-style): any node can redirect a request to the right one, or a proxy routes — simpler clients, one possible extra hop.
Design drills
Whiteboard each one out loud for 5–10 minutes before you reveal what a strong answer covers — the gap between your sketch and the checklist is your study list. Progress is saved on this device.
Explain why hash(key) % N is a disaster when a node is added, and what to use instead.
A cache node dies holding the hottest keys. Limit the blast radius.
One key (a viral item) overwhelms its single node despite balanced hashing.