Design a Distributed Cache (Redis / Memcached) — System Design

🟠 High-Level Design · Senior → 🔴 sharding & HA deep dive

"Design a distributed cache like Redis or Memcached." You already know why we cache (RAM is ~1000× faster than disk); this question is about building the cache itself when the data is too big for one machine and must survive failures. It ties together several fundamentals — consistent hashing, replication, eviction — into one clean design. Let's build it.

Step 1 — Requirements

• Functional: get(key) and put(key, value); data lives in memory; support expiry (TTL) and eviction when full.
• Non-functional: very low latency (sub-millisecond — the whole point), scalable (add nodes as data grows), highly available (a node failure shouldn't take the cache down), and it should degrade gracefully.

Step 2 — Single node first

A single cache node is just a big in-memory hash map (O(1) get/put) plus an eviction policy for when RAM fills. The standard policy is LRU (Least Recently Used) — evict whatever hasn't been touched longest, since the recently-used is most likely to be used again. LRU is implemented with a hash map + a doubly-linked list so both lookup and "mark most-recent" are O(1). That's one node; the interview is about many.

Step 3 — The core problem: distributing keys

🔴 The data won't fit on one machine, so we shard across many nodes. The question: given a key, which node holds it? The naive answer hash(key) % N breaks catastrophically when you add or remove a node — almost every key remaps at once, so the entire cache misses and the database gets crushed.

🔴 The right answer is consistent hashing: place nodes and keys on a ring; each key belongs to the next node clockwise. Now adding or removing a node only remaps ~1/N of the keys, not all of them — so scaling the cluster causes a small dip, not a meltdown. Use virtual nodes to keep the load evenly balanced. Naming consistent hashing here is the single most important point of this question.

Step 4 — Where does the routing happen?

🟠 Two common models for "which node?":

• Client-side (like Memcached): a smart client library knows the ring and hashes the key to pick the node directly. Simple servers, no extra hop.
• Cluster-aware (like Redis Cluster): nodes know the topology; a client can hit any node and be redirected to the right one. More built-in coordination.

Either way, the key idea is the same consistent-hashing map from key → node.

Step 5 — High availability: replication

🔴 If a node holding a shard dies, you lose that slice of the cache. To stay available, replicate each shard: a primary plus one or more replicas on other nodes. If the primary fails, a replica takes over (promoted, often via a consensus/failover mechanism), so the cache keeps serving. This is the classic availability-vs-consistency trade: cache replication is usually asynchronous (fast, but a replica might lag slightly) because for a cache, speed and availability matter more than perfect consistency — a rare stale/missed entry just falls back to the database.

Step 6 — Cache correctness details

• Expiry (TTL): entries carry a time-to-live and expire automatically, so stale data self-cleans.
• Invalidation & write policy: on a data change, update or invalidate the cache — via write-through or write-around strategies — so readers don't get stale values.
• Hot keys: one wildly popular key can overload its single node. Mitigate by replicating that key to several nodes or adding a small local (client) cache in front. Spotting the hot-key problem is a senior signal.
• Thundering herd: when a hot key expires, thousands of requests miss at once and stampede the DB. Guard with a lock/"single-flight" so only one request rebuilds it.

The interview-ready walkthrough

"Each node is an in-memory hash map with LRU eviction. To scale beyond one machine I shard with consistent hashing (plus virtual nodes for balance), so adding/removing a node only remaps ~1/N of keys instead of everything. For availability I replicate each shard to other nodes with async replication and failover, accepting slight staleness for speed. I'd use TTLs and a write-through/invalidation policy for correctness, and handle hot keys (replicate them) and the thundering-herd on expiry (single-flight lock). Clients find the node via a smart library or a cluster-aware protocol." That connects consistent hashing, replication, eviction, and the real-world gotchas — exactly what's being tested."

What to read next

• Design a Key-Value Store — the durable big sibling of a cache
• Consistent Hashing — the sharding scheme at the core
• Caching Strategies — eviction and write policies in depth
• ← The complete System Design guide (hub)

← Design a web crawler · Design a key-value store →