Design a Distributed Cache

A Redis-like cache as a service: hundreds of nodes, terabytes of memory, sub-millisecond gets, and a cluster that survives losing a machine mid-request.

Last updated 2026-09-22. Difficulty: hard. Patterns: consistent-hashing, eviction, replication, hot-keys. Reported at Anthropic and 6 more with Pro.

Functional requirements

• Get, set and delete a key. Values are opaque bytes up to a few hundred KB. Set takes an optional TTL. This is the whole hot path and it must be one network round trip.
• Expiry by TTL. A key disappears at its deadline whether or not anyone reads it. Lazy expiry on read plus background sampling, because scanning every key is not affordable.
• Eviction under memory pressure. When the node is full, admit the new key by evicting others. Policy is per namespace: LRU by default, LFU for skewed read patterns, or reject writes for a cache that must not lose data.
• Atomic numeric and structural operations. Increment, compare-and-set, list and set operations. These are why teams pick a cache with data structures over a plain memcached; they also keep counters correct without a read-modify-write race.
• Namespaces with independent limits. One cluster serves many teams. Each namespace has a memory quota, an eviction policy, a default TTL and its own rate limit so one tenant cannot evict another out of memory.
• Online resharding. Add or remove nodes without downtime and without invalidating the whole keyspace. Slots migrate; clients follow redirects while a migration is in flight.
• Replication and failover. Each shard has a primary and at least one replica in another availability zone. A primary failure promotes a replica in seconds without operator involvement.
• Observability per key class. Hit rate, evictions, memory, p99 latency and hot keys, broken down by namespace and key prefix, because "the cache is slow" is otherwise undebuggable.
• Out of scope. Durable storage semantics (this is a cache, not a database), cross-region active-active writes, and a query language over cached values.

Non-functional requirements

• Latency (p99 < 1 ms in-zone). A cache that is sometimes slow is worse than no cache, because callers have already paid for the lookup. Single-digit milliseconds at p999 including a retry.
• Throughput (10 M ops/s per cluster). Driven by a fleet of application servers, each doing thousands of gets per second. Per-node ceiling is what sets the cluster size.
• Capacity (10 TB of hot data). Memory is the expensive resource; the design lives or dies on bytes per entry and on eviction picking the right victims.
• Availability (99.99 % for reads). The cache is on the critical path of every product. Losing it must degrade to a slower origin, never to an outage, which pushes work onto the client library.
• Consistency (best-effort, bounded staleness). A cache may return stale data and may lose data on failover. This is the requirement that lets the rest of the design be fast, and it must be stated out loud.
• Durability (none guaranteed). A cold start after losing a whole cluster must not take the origin down; warming is part of the design rather than an afterthought.
• Isolation (no cross-tenant blast radius). A tenant that writes 2 GB/s or fills memory with 10 MB values must be throttled, not allowed to evict everyone else.
• Elasticity (resize in minutes, no cold cache). Traffic doubles for a sale; adding nodes must not invalidate the existing keys, which is the argument for consistent hashing over modulo.

Back-of-envelope estimates

• Operations per second: ~10 M. 5 000 application servers × 2 000 cache ops/s each = 10 M ops/s. Reads are roughly 20:1 over writes, which is what makes replicas useful for read offload.
• Nodes needed for throughput: ~60–100. A single-threaded Redis-style process on modern hardware handles ~150 k ops/s with pipelining and small values; budget 120 k to leave headroom. 10 M ÷ 120 k ≈ 84 primaries, round to 100 for growth.
• Memory for the working set: ~13 TB usable. 10 TB of values plus per-entry overhead: key (~40 B) + value header, TTL and LRU metadata (~50–100 B) + allocator fragmentation (~10–20 %). 10 TB × 1.3 ≈ 13 TB of RAM before replication.
• Machines for memory: ~90 primaries. 13 TB ÷ ~144 GB of usable cache memory per machine (a 192 GB box, leaving headroom for replication buffers and a fork) ≈ 90. With one replica each, ~180 machines. Memory, not CPU, is the binding constraint at this value size.
• Network per node: ~1.2 Gbps. 120 k ops/s × ~1.2 KB average value ≈ 144 MB/s ≈ 1.2 Gbps on a 10–25 Gbps NIC. Fine, until someone caches 1 MB objects: the same op rate would need 120 GB/s, which is why per-value size limits exist.
• Hit rate and origin load: 95 % → 500 k/s to origin. At 10 M ops/s with a 95 % hit rate the origin databases absorb 500 k/s. Moving to 99 % cuts that to 100 k/s. Every point of hit rate is worth five times its weight in database capacity, which is the argument for spending on memory.
• Cold start cost: ~20 min at safe refill. Refilling 10 TB from origin at a rate the databases survive (say 200 k fills/s at 1.2 KB = 240 MB/s) takes 10 TB ÷ 240 MB/s ≈ 12 h for everything, but only the hot 5 % matters, so ~20 minutes to get back above a 90 % hit rate. The lesson: never restart a whole cluster at once.
• Failover impact: ~1 % of keys, seconds. One primary of 100 holds ~1 % of the keyspace. A failure loses whatever was not replicated (milliseconds of writes with async replication) and makes that slice miss for the 5–15 s of detection and promotion. Expressed as origin load: a 5 % bump for a few seconds.

Components

• Application (smart client library): Runs the cache-aside pattern and holds the cluster topology in memory, so a get is one hop to the right node rather than a proxy round trip. Owns the tight timeouts, the single retry, the circuit breaker and the fallback to origin. Also does client-side batching and, for the very hottest keys, a small in-process cache.
• Cache proxy (optional · thin routing tier): For clients that cannot embed a smart library (other languages, serverless, external teams). Terminates connections, keeps pools warm to every node, and does the same slot routing. Costs a hop of latency, saves a connection explosion: 5 000 clients × 100 nodes is 500 k connections without it.
• Cache node (in-memory · single-threaded core): Owns a set of hash slots. Keeps an in-memory hash table with per-entry TTL and LRU/LFU metadata, serves gets and sets from the event loop, and handles its own expiry sampling and eviction. Rejects values over the size limit and tracks per-namespace memory so one tenant cannot consume the node.
• Replica (async replication · other AZ): Streams writes from its primary and can serve reads for clients that accept staleness. Exists mainly so a machine loss costs seconds rather than a cold slice, and so a planned restart is a promotion rather than an outage.
• Topology store (etcd / ZooKeeper · slot map): The small strongly consistent store of truth: slot → primary, primary → replicas, migration state and epoch. Read on client start and watched for changes; never on the request path. A few kilobytes of data protected by consensus.
• Control plane (placement · resharding): Decides where slots live. Runs cluster creation, scale up and down, slot migration, rebalancing after failure, and rolling upgrades one node at a time. Every action is a change to the slot map plus orchestration of the nodes involved, so the data path stays simple.
• Failure detector (gossip + quorum): Nodes gossip liveness; a primary is declared dead only when a quorum of peers agrees and the control plane confirms. Deliberately conservative: a false positive causes an unnecessary failover and a small data loss, so detection is tuned for a few seconds rather than a few hundred milliseconds.
• Origin store (the database being protected): The source of truth behind the cache. The design exists to keep this from being hit 10 M times a second; every failure mode is judged by how much load it pushes here.
• Warmer (top-key replay): Rebuilds the hot set after a cold start. Consumes the sampled key log, replays the most frequent keys against the origin at a rate the origin can absorb, and reports hit rate as it climbs. The reason a restart is not an incident.
• Key sample stream (sampled · 1 in 1000): A 0.1 % sample of operations emitted by the nodes: key prefix, namespace, size, hit or miss. Feeds hot-key detection, working-set estimation and the warmer. Sampling keeps this at a few thousand events a second instead of ten million.
• Hot-key detector (count-min sketch): Maintains approximate top-K per namespace from the sample stream. When a key exceeds a threshold share of a node, it publishes it to clients, which then cache it locally for a second or two, and to the control plane, which can replicate that slot more widely.
• Metrics & quotas (per namespace): Aggregates hit rate, memory, evictions, expirations, latency percentiles and bandwidth per namespace and key prefix. Enforces quotas by telling nodes to throttle or reject a namespace that is over its memory or bandwidth budget, which is what keeps tenants isolated.
• Dashboards & alerts (on-call view): Where hit-rate regressions, eviction storms, memory fragmentation and failovers surface. The metric people page on is client-observed latency and error rate, not node CPU.

User flows

1. A cache hit, and a miss that fills. The path that runs ten million times a second. What matters is that a hit is one hop with no coordination, and that a miss cannot turn into a stampede.
   1. Client hashes the key to a slot and picks the node that owns it from its local topology map. CRC16 of the key modulo 16 384 slots. Slots, not keys, are the unit of placement: the map is 16 384 entries instead of billions, and moving data means moving slots. Hash tags ({user:123}:profile) let related keys land together so multi-key operations stay on one node.
   2. Client sends the get on a pooled connection and waits with a tight timeout. Connections are long-lived and pipelined; a new TCP handshake per operation would cost more than the lookup. The timeout is a few milliseconds, because the whole point of the cache is that slow is failed.
   3. Node looks the key up in its hash table, checks the TTL, and updates the recency metadata. Expiry is checked lazily on read: an entry past its deadline is deleted and reported as a miss, so no reader ever sees an expired value even though nothing scanned it. The access also touches the LRU clock or the LFU counter, which is what eviction will use later.
   4. On a miss, the client reads the origin under a per-key lock so only one caller does the work. The stampede guard: a short-lived lock key (SET NX with a 5 s TTL) means one request fills while the others wait briefly or serve stale. Without it, a popular key expiring turns 50 k requests a second onto one database row.
   5. Client writes the value back with a jittered TTL, and the node admits or evicts to make room. TTL jitter of ±10 % stops keys written together from expiring together. If the namespace is at its memory limit, the node evicts according to policy before storing.
   6. Callers that cannot embed the library send the same operation through the proxy tier instead. One extra hop of a few hundred microseconds, in exchange for pooled connections and a routing map the caller does not have to understand. Serverless functions and other languages use this path; the routing logic is identical, so the two paths cannot disagree.
   7. Node samples the operation into the key stream for hot-key and working-set analysis. One in a thousand operations, with the key prefix rather than the full key where the key contains user data. This is how the system knows its hit rate per prefix and which keys are hot, without paying to log ten million events a second.
2. A write and its invalidation. Keeping a cache close to correct is mostly about what the writer does. The chosen pattern is write-through to the database and delete the key, with a version to block a stale fill.
   1. Application writes the new value to the origin database in a transaction. The database remains the source of truth. Nothing about the cache is allowed to change the fact that a committed write is durable.
   2. Application deletes the cache key rather than overwriting it. Delete, not set: two concurrent writers that each set their own value can leave the losing value behind forever, while delete leaves only a miss, which repairs itself. The cost is one extra origin read on the next request.
   3. The next reader misses, reads the origin, and stores the value with its version. Storing the version inside the cached value makes the classic race detectable: a slow reader that fetched before the write can only overwrite with an older version, and the node rejects that with a compare-and-set.
   4. Node replicates the mutation to its replica asynchronously. Asynchronous because a synchronous replication round trip would double the write latency for data that is, by definition, reconstructible. The window of loss is sub-millisecond and the consequence is a miss.
   5. A delayed second delete guards against a fill that raced the write. Delayed double delete: schedule another DEL a second later for the rare interleaving where a reader fetched an old row just before the write and stores it just after the first delete. Cheap insurance on the few key classes where a stale read is expensive.
3. Add nodes without losing the cache. Scaling up must not invalidate the keyspace. Slots move one at a time, and clients are redirected mid-migration rather than being told to stop.
   1. Operator asks the control plane to grow the cluster; it computes the slots to move. Going from 90 to 100 primaries moves roughly a tenth of the slots. With modulo hashing nearly every key would move; with slots plus consistent hashing only the arcs assigned to the new nodes do.
   2. Control plane marks a slot as migrating: source is MIGRATING, destination is IMPORTING. Both nodes now know about the migration, which is what makes the next step safe. Only one slot is in flight at a time per node pair, so the blast radius of a failure is one slot.
   3. Keys in the slot are copied in batches while the source continues serving reads and writes. Each batch is copied atomically and deleted from the source, so a key exists in exactly one place. The slot stays available throughout; only the individual keys in flight are briefly locked.
   4. A client that asks the source for a key already moved is redirected to the destination. This is why migration needs no client downtime. A MOVED response updates the client topology permanently; an ASK response redirects only this one request, because the slot is still migrating. Clients that ignore redirects see misses, not errors.
   5. When the slot is empty, the control plane commits the new owner into the topology store and bumps the epoch. The epoch is how a client or node with an old map recognises that it is stale. Watching clients pick up the change within a second; the rest learn on their next redirect.
   6. Migration continues slot by slot with a rate limit while the metrics show hit rate holding. The safety check is hit rate and client-observed latency, not migration speed. If either degrades, the plan pauses: a resharding that halves the hit rate has pushed the difference onto the origin database.
4. A primary dies mid-traffic. The failure case that decides whether the cache is safe to depend on. Detection is deliberately slow, promotion is fast, and the client absorbs the gap.
   1. Peers stop receiving gossip from the node and mark it suspect. A single missed heartbeat means nothing: a garbage collection pause, a NIC blip and a dead machine look identical for the first second. Suspicion requires several missed intervals, typically a few seconds in total.
   2. A quorum of peers agrees the node is down and the failure detector tells the control plane. Quorum, not one observer, because a partitioned observer would otherwise trigger a failover and create two primaries. This is the split-brain guard, and the epoch on the slot map is the second one.
   3. Meanwhile clients time out, retry once against the replica, and then treat the key as a miss. This is what keeps the failure invisible to users: the client library degrades to the origin instead of failing the request. Origin load rises by the share of traffic on that node, which is why 1 % slices matter.
   4. Control plane promotes the replica, assigning it the failed primary's slots with a new epoch. The promoted replica holds everything that was replicated before the failure, so most of the slice is still warm. Writes that were in flight are lost, which is acceptable for a cache and must be stated as a property, not discovered in an incident.
   5. Clients watching the topology store switch within a second; stragglers learn through MOVED. Two paths to the same outcome: push for the fast case, redirect for the ones that missed the push. A client with a stale map is never wrong for long, and never writes to the old primary because it fences on the epoch.
   6. A fresh replica is built for the new primary in the background, rate limited so it does not disturb reads. Until it finishes, the shard is a single point of failure, so this is the step the on-call engineer watches. Building a replica streams the keyspace, which is bandwidth the primary is also using to serve traffic.
   7. The warmer refills whatever the promoted node is missing, replaying the top keys against the origin at a safe rate. The sampled key log knows which keys were hot on that slice, so refilling is ordered by popularity rather than random. The fill rate is capped by what the origin can absorb, which is the whole point: recovery must not become a second outage.
5. One key takes a whole node down. The failure mode unique to caches: a single key so hot that its owning node saturates while the rest of the cluster is idle. Sharding cannot help, because the key is indivisible.
   1. A product launch makes one key the target of 2 M requests per second. Consistent hashing spreads keys, not requests for one key. The owning node is now at 2 M ops/s against a 150 k ceiling: latency climbs for every key it owns, not just the hot one.
   2. Node latency and bandwidth for that namespace spike, and the alert fires before anyone files a ticket. The alert is on client-observed p99 and per-namespace bandwidth, not on node CPU: a single-threaded cache node saturates on one core long before the machine looks busy, so CPU utilisation is the metric that hides this failure.
   3. The sample stream shows one prefix dominating; the detector flags it as hot. A count-min sketch over the sampled stream gives an approximate top-K per namespace in a few kilobytes. Approximate is fine: the decision is "is this key more than a few percent of a node", and the answer is obvious when it happens.
   4. The hot key is published to clients, which cache it in process for a second or two. This is the fix that actually works: 5 000 clients each holding the value for 1 s turns 2 M remote gets per second into 5 000. The cost is up to a second of extra staleness on that key, which is a product decision, and the mechanism is why the client library exists at all.
   5. For keys that cannot tolerate local staleness, the control plane replicates the slot more widely and clients read from replicas. Adding read replicas multiplies read capacity for that slot at the cost of memory and replication bandwidth. It is slower to take effect than local caching, so it is the second lever, not the first.
   6. The client library also spreads the key across N aliases when writes are rare. Key splitting: store the same value under product:hero#0 … #9 and have each client read a random alias, so the load lands on up to ten different slots. Writes must update all copies, which is why this is reserved for read-mostly values.
   7. Quotas throttle the namespace if it is still saturating the node, protecting the other tenants. The last line of defence. A tenant over its bandwidth budget gets errors that its own client library degrades on, rather than being allowed to make the cache slow for everyone. Isolation beats fairness during an incident.

Deep dives

Related

• Run this question for a friend: the interviewer kit