system-design

Design a Distributed Cache (like Redis Cluster / Memcached)

Difficulty: Tier 3 Asked at: Amazon, Google, Meta, senior loops Time budget: 45 min

You’ve used a cache in every other design. Now build one. This question tests whether you understand what happens inside the box everyone hand-waves: how keys are distributed across nodes, what happens when a node joins or dies, eviction, and replication. It’s a focused distributed-systems question built around consistent hashing and eviction policies.

Prerequisites: Caching, Consistent Hashing, Replication

1. Requirements

Functional:

get(key), set(key, value, ttl), delete(key).
Distributed across many nodes (data exceeds one machine’s memory).
Configurable eviction when memory fills.
Optional TTL/expiration.

Non-functional:

Very low latency — sub-millisecond gets (it’s in front of the DB to save latency).
High throughput — millions of ops/sec.
Scalable — add/remove nodes with minimal disruption.
Available — a node failure shouldn’t lose the whole cache or cause a stampede.

Out of scope: durability (a cache can lose data — the DB is the source of truth), complex queries.

2. Estimation

Cache 1 TB of hot data across nodes with, say, 64 GB RAM each → ~16 nodes (plus replicas).
10M ops/sec across the cluster → each node handles a share; in-memory ops are sub-ms, so throughput is bounded by network and CPU, not disk.
The interesting numbers: how keys distribute (evenness), and how many keys move when the cluster resizes.

3. Core design: partition + place keys

🚨 Distribute keys across nodes with consistent hashing. Hash each key onto a ring; the key lives on the next node clockwise. Virtual nodes (each physical node owns many ring positions) keep load even and make add/remove cheap.

Why not hash(key) % N? Because changing N (a node joins/dies) remaps almost every key → mass cache misses → a stampede onto the database. 🚨 Consistent hashing moves only ~1/N of keys on a membership change — this is the entire reason to use it here.

flowchart LR
    Client -->|get/set key| Router[Client lib / proxy<br/>hashes key -> node]
    Router --> N1[Cache Node 1]
    Router --> N2[Cache Node 2]
    Router --> N3[Cache Node 3]
    Ring[Consistent hash ring<br/>+ virtual nodes] -.-> Router

Routing can live in a smart client (client hashes the key and connects directly — fewest hops) or a proxy layer (simpler clients, extra hop). State the trade-off.

4. Deep dives

4a. Adding/removing nodes gracefully

When a node joins, it takes over a slice of the ring from its neighbors; only those keys move. When a node leaves (or dies), its keys are now served by the next node (cache misses that repopulate from the DB, or copied from a replica). Virtual nodes spread the moved slice across many nodes so no single neighbor is overwhelmed. 🚨 Elastic resizing without a full flush is the headline feature.

4b. Eviction policies

Memory is finite; when full, evict. Know the policies:

LRU (least recently used) — the common default; evict what hasn’t been touched longest.
LFU (least frequently used) — better for skewed popularity, harder to implement exactly (approximate LFU is used in practice).
FIFO / random / TTL-based. 🚨 Discuss why LRU (temporal locality: recently used is likely to be used again) and its weakness (a big scan evicts hot keys — “cache pollution”; mitigate with LRU-K / segmented LRU). (Caching)

4c. Replication & availability

A pure cache can lose data (DB is source of truth), but losing a node’s data causes a stampede (all its keys miss at once → DB overload). Mitigate:

Replicas: each key on a primary + replica; on primary failure, promote the replica → no mass miss.
Trade-off: replication doubles memory and adds write cost for availability. Worth it for large clusters where a node loss would stampede the DB.

4d. Handling the thundering herd

When a hot key expires or its node fails, thousands of concurrent requests miss and hit the DB simultaneously. Defend with request coalescing (only one request rebuilds the key; others wait) and staggered TTLs / jitter so keys don’t all expire at once. (Thundering Herd)

4e. Consistency: cache vs source of truth

The cache can go stale vs the DB. Strategies: write-through (write cache + DB together — consistent, slower writes), write-back (write cache, async to DB — fast, risk of loss), cache-aside / write-around (app manages it; invalidate on write). Most systems use cache-aside + TTL and accept brief staleness. 🚨 “There are only two hard things… cache invalidation” — name the trade-off explicitly.

5. Bottlenecks & scaling further

Key distribution / resizing → consistent hashing + virtual nodes.
Node failure stampede → replicas + coalescing + TTL jitter.
Hot key → a single key on one node hotspots; replicate the key or use client-side caching. (Hot Keys)
Throughput → add nodes; smart-client routing to avoid a proxy hop.
Memory pressure → eviction policy tuned to the access pattern.

6. Trade-off summary

Decision	Chosen	Alternative	Why
Key placement	Consistent hashing + vnodes	hash % N	Resize moves ~1/N keys, not all
Routing	Smart client	Proxy	Fewer hops; proxy trades simplicity for a hop
Eviction	LRU (approx)	LFU / FIFO	Temporal locality; simple and effective
Availability	Replicas	No replication	Avoid DB stampede on node loss; costs memory
Consistency	Cache-aside + TTL	Write-through	Fast; accept brief staleness

7. Follow-up questions

Why consistent hashing instead of modulo hashing for key placement?

Because a cache's cluster size changes — nodes are added to grow capacity and removed when they fail — and the placement scheme determines how disruptive that is. With `hash(key) % N`, the node for a key depends on N, so changing N remaps almost every key to a different node; in a cache that means a near-total miss storm where practically every lookup misses and slams the backing database at once — potentially taking it down. Consistent hashing places nodes and keys on a ring so that adding or removing a node only reassigns the keys in the arc between that node and its neighbor — about 1/N of the keys — leaving the rest exactly where they were. Virtual nodes spread each physical node across many ring positions so load stays even and the reassigned slice is distributed rather than dumped on one neighbor. Minimizing key movement on membership change is precisely what a distributed cache needs, which is why consistent hashing is the standard choice.

A cache node dies. What happens, and how do you avoid taking down the database?

Without protection, every key that node held instantly misses, and all those requests fall through to the database simultaneously — a thundering herd that can overwhelm it. The defenses are layered. Replication is the main one: keep each key on a primary plus a replica, so when the primary dies the replica is promoted and serves the keys with no mass miss. On top of that, request coalescing ensures that when many requests do miss the same key, only one goes to the database to repopulate it while the others wait for that result, collapsing a stampede into a single fetch. Staggered TTLs with jitter prevent large sets of keys from expiring at the same instant. Together, replicas prevent the mass-miss on failure, and coalescing plus jitter bound the database load when misses do happen.

How do you decide what to evict when memory is full?

You pick an eviction policy matched to the access pattern, with LRU (least recently used) the common default because it exploits temporal locality — data used recently tends to be used again soon, so evicting the least-recently-touched item is usually evicting the least-valuable one. LFU (least frequently used) can be better when popularity is very skewed and stable, since it keeps persistently-hot keys even if not touched in the last moment, but exact LFU is costlier so approximate versions are used. LRU's weakness is cache pollution: a large one-off scan touches many keys once and can evict genuinely hot data; segmented or LRU-K variants mitigate this by requiring multiple accesses before an item is considered "hot." TTL-based expiration complements any policy by bounding staleness. The choice is a trade-off between hit rate, implementation cost, and resistance to pollution.

Smart client vs proxy for routing — which and why?

Both hash the key to find its node; they differ in where that logic lives. A smart client embeds the hashing and cluster topology in the application's cache library, so the app connects directly to the correct node with no intermediary — the lowest latency (one hop) and no extra infrastructure, at the cost of fatter clients that must all know and track topology changes. A proxy layer sits between clients and cache nodes, so clients are dumb (just talk to the proxy) and topology/rebalancing logic is centralized and easy to update, at the cost of an extra network hop and the proxy itself becoming something to scale and keep available. High-performance systems often prefer smart clients for the latency win; environments valuing operational simplicity and polyglot clients prefer a proxy. It's a latency-vs-simplicity trade-off.

8. What junior / mid / senior answers look like

Junior: treats the cache as one Redis box with get/set; may use modulo hashing and not consider node failure or eviction deeply.
Mid: consistent hashing with virtual nodes for distribution, LRU eviction, TTLs, understands node add/remove moves only a slice.
Senior: all that plus replicas to prevent DB stampede on node loss, coalescing + TTL jitter for thundering herd, the eviction-policy trade-offs and cache pollution, smart-client-vs-proxy routing, and the cache-consistency strategies (write-through/back/aside) with their trade-offs — treating the cache as a real distributed system, not a magic box.