00. Design a Distributed Cache¶
~20 min read · Level: advanced · Part 1 of 4 (Overview → HLD → LLD → Q&A)
Problem¶
A distributed cache is an in-memory key-value layer that sits between an application and its slow backing store, absorbing the reads so the store never sees them. This is the product behind Redis Cluster, Memcached fleets, Amazon ElastiCache, and the caching tier inside almost every large web service. The application asks the cache for user:8842 first; on a hit it gets the value back in under a millisecond, and on a miss it reads the database, writes the value into the cache, and moves on. Because one machine's memory cannot hold the working set of a large service, the cache is spread across many nodes, and the interesting problems all come from that spreading: deciding which node owns which key, surviving a node that dies, and stopping a single popular key from melting one machine.
The job looks like "a hash map on the network," and for a single node it nearly is. What makes it a system-design question is that the node count changes — machines are added for capacity, lost to hardware failure, and cycled during deploys — and every change threatens to move keys around. Move too many and you invalidate most of the cache at once, which dumps the entire read load onto the store that the cache existed to protect. So the real design target is not raw speed; it is staying fast while the cluster underneath you keeps changing shape.
To keep the reasoning concrete, thread one scenario through the whole design: a 100-node cache cluster serving 10 million operations per second at peak, and one node dies mid-peak. The requirement that pins down every decision below is this — when that node drops, only about 1/100th of the keys should have to move, and no stampede should reach the origin database. A design that reshuffles 99% of keys on a single failure, or that lets the failover send a wall of cold reads at the store, is a design that turns one dead machine into a site-wide outage.
Functional requirements¶
- Get / Set / Delete a value by key, with an optional per-key TTL after which the entry expires on its own.
- Partition the keyspace across many nodes so the dataset can exceed one machine's memory, and route each key to its owning node.
- Replicate each key to at least one other node so a single node loss does not create a cold spot.
- Evict under memory pressure using a configurable policy (LRU / LFU), because the cache is deliberately smaller than the full dataset.
- Rebalance with minimal key movement when nodes join or leave the cluster.
- Atomic primitives — at minimum a compare-and-set and atomic counters — so callers can build correct read-modify-write loops on top.
De-scoped for this round, and worth saying out loud so the interviewer hears a choice rather than a gap: cross-node transactions and multi-key atomicity across shards, secondary indexes and query languages, on-disk durability as the primary contract (this is a cache, not a database of record), and geo-distributed active-active replication. Each is real; none changes the core of a single-region cache tier.
Non-functional requirements¶
The dominant constraint is predictable sub-millisecond latency while the cluster topology keeps changing. A cache that is only a little faster than the database is worthless — its whole reason to exist is to be one to two orders of magnitude faster — and it must hold that speed through node loss, rebalancing, and hot spots. Everything downstream follows from that.
- Latency: a
GETshould complete server-side in well under 1 ms (p99), so end-to-end from the app it is single-digit milliseconds, dominated by the network hop, not the lookup. - Availability: the tier should survive single-node (and single-AZ) loss without a visible dip. It does not need to survive with zero stale reads — see consistency.
- Consistency: weak and self-healing. The origin database is the source of truth; a cache entry may be stale or briefly missing, and the fix is to re-read from origin. This buys the availability and speed above.
- Durability: explicitly not a goal. Losing a cache node's contents on crash is acceptable because the data is reconstructible from origin. We spend replication on availability, not on preventing data loss.
- Elasticity under churn: adding or removing a node must move a small, bounded fraction of keys — proportional to the change, not to the whole keyspace.
Scale estimation¶
Take the threaded scenario: 100 nodes, 10 million operations/second at peak, spread evenly. That is 10M / 100 = 100,000 ops/second per node — comfortably within a single Redis or Memcached process, which handles a few hundred thousand simple ops/second per core. The cluster is sized for headroom and blast radius, not because any one node is maxed.
For memory, assume a 1 TB hot working set — the keys worth caching — at an average value size of ~2 KB, which is 1 TB / 2 KB ≈ 500 million keys. At replication factor 2 (each key on a primary plus one replica) the cluster holds 2 TB, or 2 TB / 100 = ~20 GB per node. That fits a commodity 32–64 GB cache instance with room for overhead and fragmentation, and it makes the cost of replication explicit: RF=2 doubles the memory bill from 1 TB to 2 TB of RAM to buy the failover behavior the scenario demands.
The number that actually shapes the design is what reaches the origin. At a 99% hit ratio, misses are 1% × 10M = 100,000 QPS to the backing database — already a serious load, and the reason the database is provisioned for roughly a 150,000 QPS ceiling with little to spare. This is the budget the failover must not blow. When our node dies, its ~100,000 ops/second of traffic redistributes to the 99 survivors (about 100k / 99 ≈ +1,010 ops/second each, a ~1% bump — a non-event on the cache side). The danger is on the origin side: if the dead node's keys land cold on their new owners with no replica, those 100,000 ops/second all miss and hit the database, pushing it from 100k to 200k QPS — well past its 150k ceiling — and it browns out. Holding the origin flat through that failover is the whole game, and it is why replication and stampede control, not raw cache throughput, are the load-bearing choices.
Bandwidth is a secondary bound worth naming: 100,000 ops/second × 2 KB ≈ 200 MB/second per node, about 1.6 Gbit/s, well inside a 10 GbE link — but a service with 100 KB values would hit the NIC long before the CPU, which is why value size, not op count, is the first thing to ask about.
API sketch¶
GET key → value | MISS # sub-ms point read
SET key value [EX ttl] → OK # optional expiry
DEL key → count_removed
MGET key1 key2 ... → [value|MISS, ...] # batched multi-get
CAS key old_value new_value → OK | CONFLICT # compare-and-set
INCR key [by] → new_value # atomic counter
# control-plane / topology (not on the hot path)
CLUSTER SLOTS → [ {slot_range, primary, replicas}, ... ]
CLUSTER FAILOVER <node> → promote a replica to primary
Solutioning¶
Start from placement, because every other decision hangs off it. The keyspace has to be split across 100 nodes, and the naive answer — node = hash(key) % N — is a trap: it is fast and even, but the moment N changes from 100 to 99, hash(key) % 100 and hash(key) % 99 disagree for about 99% of keys, so a single node loss remaps almost the entire cache. The whole cache goes cold at once and the resulting miss storm buries the origin. The fix is consistent hashing: place nodes and keys on a hash ring, and a key belongs to the first node clockwise from it. Removing a node hands off only the arc it owned — its 1/N ≈ 1% of keys — to its ring neighbor, and every other key stays put. This is the memory hook for the whole study: a dead node is not a rehash-the-world problem; it's a reassign-one-arc problem. Layer virtual nodes on top (each physical node owns ~160 points on the ring) so that the departing 1% spreads evenly across all 99 survivors instead of dumping onto a single unlucky neighbor.
The second decision is replication cost versus durability, and a cache resolves it differently from a database. Each key lives on a primary and at least one replica; when the primary dies, the replica is promoted and its keys are already warm, so the origin sees nothing. That costs real money — RF=2 doubles RAM from 1 TB to 2 TB — but it is the difference between a failover the origin never notices and the 100k→200k QPS spike computed above. Crucially, the replication is asynchronous: a SET returns as soon as the primary has it, and the replica catches up a moment later. Synchronous replication would add a full network round-trip (~0.5–1 ms) to every write, which alone breaks the sub-millisecond target. The trade we accept is that a failover can lose the last few milliseconds of writes — and that is fine, because replication here buys availability, not durability; the origin is the source of truth, so a lost cache write self-heals on the next read.
The third tension is eviction policy, forced by the deliberate choice to size the cache smaller than the full dataset. Under memory pressure something must go, and the policy decides what. LRU (evict least-recently-used) is cheap and usually right, but a single large scan — a backup job reading every user once — can walk the entire working set through the cache and evict the genuinely hot keys, collapsing the hit ratio from 99% to something disastrous. LFU (evict least-frequently-used) protects the hot set from that scan because a once-touched key never out-ranks a key hit thousands of times, at the cost of tracking access frequency and adapting more slowly to genuine shifts in what is hot. The resolution is to default to LFU for skewed, scan-prone workloads and reserve plain LRU for uniform ones — and either way, to isolate the third failure that neither policy addresses.
That third failure is the hot key: one key — a viral post, a global feature flag — drawing a disproportionate share of traffic. Consistent hashing does not help here, and this is the second memory hook: a hot key is not a sharding problem; it's a fan-out problem. Sharding spreads distinct keys across nodes; it does nothing for a million requests aimed at one key, which by definition all land on that key's single owner and saturate it while 99 nodes idle. The answer is to replicate the value — a small client-side cache for the hottest keys, or writing the key under several suffixed names so reads fan out across nodes — not to split the keyspace further.
The result is a tier whose placement is a hash ring with virtual nodes, whose availability comes from asynchronous replicas that a failover promotes warm, whose memory is defended by a frequency-aware eviction policy, and whose worst-case — a node dying at peak — moves only 1% of keys and, thanks to warm replicas plus request coalescing on any residual cold reads, holds the origin flat. The following files take each decision down to components (HLD) and then to ring math, eviction internals, and failover races (LLD).