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.
“Design a distributed in-memory cache like Redis. Support GET and SET operations. The cache should be fast, scalable, and handle node failures gracefully.”
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)?
- 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.
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.
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.
Comments
Nothing yet. Say the first thing.
Sign in to join the conversation.