Understanding the problem
A distributed cache stores data as key-value pairs in memory across a cluster. Unlike a single-node cache bounded by one machine, the cluster partitions and replicates data so you can grow horizontally and survive node failures.
SET · GET · DELETE.
Expire + janitor.
Map + DLL.
Ring · hot keys.
Pair with Delivery framework, Redis, Consistent hashing, Caching strategies, and Scaling reads.
Functional requirements
Non-functional requirements
Entities and API
Entities are trivial: keys and values (plus expiry metadata once we add TTL). In a real interview, skip or rush this — challenges live elsewhere.
POST /:key { "value": "...", "ttl": 60? }
GET /:key -> { "value": "..." }
DELETE /:keyHigh-level design
Build an MVP that satisfies functional requirements on one node. Layer distribution for NFRs in deep dives.
1) SET / GET / DELETE
A cache is a hash table — O(1) lookups and inserts. Host one Cache instance behind an API process.
class Cache:
data = {} # hash table
get(key):
return self.data[key]
set(key, value):
self.data[key] = value
delete(key):
delete self.data[key]
2) TTL
Store (value, expiry). On get, if expired, delete and return null. On set, expiry = now + ttl when provided.
get(key):
(value, expiry) = data[key]
if expiry and currentTime() > expiry:
delete data[key]
return null
return value
set(key, value, ttl):
expiry = currentTime() + ttl if ttl else null
data[key] = (value, expiry)
cleanup(): # janitor — expired keys never accessed still waste RAM
for key, entry in data:
if entry.expiry and currentTime() > entry.expiry:
delete data[key]
3) LRU eviction
Need O(1) lookup and O(1) recency updates. Combine a hash map (key → Node) with a doubly linked list (MRU at head, LRU at tail). On get/set move to front; when over capacity, evict tail.prev.
get(key):
node = data[key]
if node.expiry and currentTime() > node.expiry:
delete data[key]; delete node; return null
move_to_front(node)
return node.value
set(key, value, ttl):
expiry = currentTime() + ttl if ttl else null
if key in data:
node = data[key]
node.value, node.expiry = value, expiry
move_to_front(node)
else:
node = Node(key, value, expiry)
data[key] = node; add_node(node)
if size > capacity:
lru = tail.prev
delete data[lru.key]; delete lru
Single-node spine: hash map + DLL + TTL janitor. All hot-path ops stay O(1). Distribution comes next.
Deep dive: high availability
One node dying takes the whole cache down. Replicate. Open questions: how many copies, which nodes, how to sync, what on partition?
Deep dive: scalability
1TB and 100k RPS will not fit one box. Shard keys across nodes. (In interviews "partitioning" usually means the same idea as sharding across machines.)
Deep dive: even key distribution
hash(key) % N works until N changes — then almost every key remaps. Consistent hashing places keys and nodes on a ring; walk clockwise to the first node. Add/remove only remaps the adjacent arc.
Deeper ring mechanics: Consistent hashing and Cassandra's partitioner story in Cassandra.
Deep dive: hot reads
Hot keys are often a client traffic property, but interviewers still ask. Viral content pins one shard. Distinguish hot reads vs hot writes.
See also Scaling reads and celebrity/hot-key notes in Caching strategies.
Deep dive: hot writes
Deep dive: performance
Local O(1) is not enough once every op crosses the network. Reuse what you already designed:
Final design
What interviewers expect by level
Mid: correct data structures. Senior: distribute with judgment. Staff: usually pick a harder infra problem.
Wrapping up
Distributed cache interviews reward starting simple (map + LRU + TTL) then earning scale: replication for HA, a ring for shards, napkin math for node count, and honest hot-key tactics. Say durability is out unless they pull it in — caches are allowed to forget.
Related: Delivery framework · Redis · Consistent hashing · Caching strategies · Scaling reads · Rate limiter · Common patterns.