How to Design a Distributed Cache
Learn how to design a distributed cache: consistent hashing, LRU eviction, replication, cache-aside pattern, and stampede prevention.
Expected Interview Answer
A distributed cache is designed as a cluster of in-memory nodes that partition keys via consistent hashing, apply an eviction policy like LRU per node, and offer a client library that routes reads and writes directly to the owning node for low-latency lookups.
Keys are distributed across nodes using consistent hashing (with virtual nodes) so that adding or removing a node only reshuffles a small fraction of keys instead of the whole cache. Each node holds its shard fully in memory and enforces an eviction policy, typically LRU or LFU, plus a TTL per entry so stale data expires automatically. Clients (or a thin proxy layer) hash the key to determine the owning node and talk to it directly, avoiding a central bottleneck; replication (e.g., primary-replica per shard) protects against node failure and can serve reads with relaxed consistency. On a cache miss the client falls back to the source of truth (a database), populates the cache, and returns the result, while write-through or write-behind strategies keep the cache and database in sync depending on the consistency needs.
- Consistent hashing minimizes reshuffling when nodes are added or removed
- In-memory storage with LRU/TTL eviction keeps hot data fast and bounded in size
- Direct client-to-node routing avoids a single proxy bottleneck
- Replication per shard protects against node failure without full data loss
AI Mentor Explanation
A distributed cache is like a network of regional practice nets where players warm up close to home instead of everyone traveling to one central facility. Each net (cache node) holds equipment for its region, and a fixed assignment rule sends each player to the nearest net based on which zone they belong to, mirroring consistent hashing routing keys to nodes. If a net gets full, the oldest unused equipment is cleared out to make room for current players, just like an LRU eviction policy. When a net closes for renovation, only players assigned to that one net need reassigning to the next-nearest net, not the whole country, matching how consistent hashing limits reshuffling on node changes.
Step-by-Step Explanation
Step 1
Partition keys with consistent hashing
Map both cache nodes and keys onto a hash ring so each key is owned by one node, and node changes only remap a small fraction of keys.
Step 2
Store in memory with eviction and TTL
Each node holds its shard fully in memory, evicting via LRU/LFU when full and expiring entries via TTL.
Step 3
Route client requests directly to owning nodes
A client library or thin proxy hashes the key to find the owning node and talks to it directly, avoiding a central bottleneck.
Step 4
Replicate and handle cache misses
Replicate each shard for failover, and on a miss fall back to the database, populate the cache, and return the result.
What Interviewer Expects
- Explains consistent hashing (with virtual nodes) for key-to-node mapping
- Names an eviction policy (LRU/LFU) and TTL handling
- Addresses replication for fault tolerance per shard
- Discusses cache miss handling and write strategy (write-through/write-behind/cache-aside)
Common Mistakes
- Using naive modulo hashing that reshuffles nearly all keys on scaling events
- Forgetting an eviction policy, causing unbounded memory growth
- Not addressing what happens to availability or consistency during node failure
- Ignoring cache stampede risk when a hot key expires and many requests hit the database at once
Best Answer (HR Friendly)
“A distributed cache spreads frequently accessed data across many memory-based servers so that reads and writes are extremely fast compared to hitting a database every time. It uses a smart way of assigning data to servers so that adding or removing a server does not disrupt everything, and it automatically clears out old, unused data to make room for new data.”
Code Example
def get(key):
node = ring.get_node(key)
value = node.cache_get(key)
if value is not None:
return value
value = database.query(key)
node.cache_set(key, value, ttl_seconds=300)
return value
def put(key, value):
database.write(key, value)
node = ring.get_node(key)
node.cache_set(key, value, ttl_seconds=300) # write-throughFollow-up Questions
- How would you handle a cache stampede when a very hot key expires under heavy load?
- What is the trade-off between write-through and write-behind caching strategies?
- How does replication within a shard affect consistency guarantees on reads?
- How would you monitor and rebalance hot shards that receive disproportionate traffic?
MCQ Practice
1. Why does a distributed cache use consistent hashing instead of key modulo N?
Consistent hashing ensures only a small fraction of keys move when the cluster size changes, avoiding a mass cache miss storm.
2. What does LRU eviction do when a cache node runs out of memory?
LRU (Least Recently Used) eviction removes the entry that has gone the longest without access, keeping hot data in cache.
3. What is a “cache stampede”?
When a hot key expires, many simultaneous requests can miss the cache and hit the database together, causing a load spike.
Flash Cards
How does a distributed cache assign keys to nodes? — Via consistent hashing (often with virtual nodes) so scaling events remap only a small fraction of keys.
What is LRU eviction? — A policy that removes the least recently accessed entry first when a cache node runs out of space.
What is cache-aside? — A pattern where the application checks the cache first, and on a miss reads from the database and populates the cache.
What is a cache stampede? — A surge of requests hitting the database simultaneously after a hot cached key expires.