This question is asked as a standalone (”design a distributed cache”) and as the deep-dive in almost every other system design question (”you mentioned adding a cache — walk me through how you’d build that”). It tests whether you understand cache eviction, consistent hashing, replication, and what happens when a cache node fails.
The Question
“Design a distributed in-memory cache like Redis. Support GET and SET operations. The cache should be fast, scalable, and handle node failures gracefully.”
Step 1 — Clarify
1. Capacity? Total data size to cache. This determines how many nodes you need. A single Redis instance handles ~10–25 GB of working memory effectively.
2. Eviction policy? LRU (least recently used) is the most common. Also: LFU (least frequently used), FIFO, TTL-based expiry. State which one unless the interviewer specifies.
3. Write policy? Write-through (update cache and DB simultaneously — strong consistency, higher write latency) vs write-around (bypass cache on writes, populate on read) vs write-back/write-behind (write to cache first, async persist to DB — lower latency, risk of data loss).
4. Read policy? Cache-aside (application checks cache first, populates on miss) vs read-through (cache automatically fetches from DB on miss). Cache-aside is the default; read-through requires the cache to know the DB schema.
5. Replication? Single leader + replicas (Redis Sentinel model) or leaderless (Redis Cluster model)?
Step 2 — Estimate
- 10 TB of data to cache across the cluster
- Target: < 1ms p99 for GET/SET
- Each node: 25 GB RAM → 400 nodes for 10 TB
- Throughput: 500K ops/sec per node → 200M ops/sec cluster capacity - Network: 1 Gbps per node, each GET returns avg 1 KB → 1M GETs/sec per node on bandwidth alone
The key insight: at 400 nodes, the routing layer (consistent hashing) must direct each request to the right node in < 0.1ms overhead, leaving < 0.9ms for the actual lookup.
Step 3 — Core Data Structures
Hash table with LRU eviction:
The cache is essentially a hash map + a doubly-linked list for LRU tracking.
- Hash map: key → (value, pointer to LRU list node) — O(1) GET
- Doubly-linked list: most-recently-used at head, least-recently-used at tail - On GET: move the accessed node to the head of the list — O(1)
- On SET: add to head. If capacity exceeded: remove from tail (evict LRU) — O(1) - On eviction: remove from hash map and list simultaneously — O(1)
This O(1) for both GET and eviction is the data structure insight interviewers test. A naive LRU using a sorted list would be O(N) on every access.
Step 4 — Consistent Hashing (the probe)
With 400 nodes, how do you decide which node stores key K?
Naive modulo hashing: node = hash(key) % N. Simple. But when you add or remove a node (N changes), nearly every key remaps to a different node. A node failure or scale event causes a cache stampede — every miss hits the DB simultaneously.
Consistent hashing:
Place nodes on a circular ring (0 to 2³² - 1). Each node is assigned a position by hashing its identifier. To find the node for key K: hash K, find the nearest node clockwise on the ring.
Preparing for a distributed systems interview?
→Download the free Interview Pack
→ Subscribe now to access source code repository - 200 + coding lessons
