Design a Distributed Cache: System Design Interview 2026

A distributed cache looks like a remote hash map until ownership changes, one key goes viral, invalidation races a refill, or a shard failure turns misses into an origin outage. This walkthrough designs a disposable cache-aside tier whose authoritative data lives elsewhere. Redis is also used as an authoritative store under different persistence, durability, and consistency choices; that is not the contract assumed here.

This walkthrough assumes the 6-step system design framework and applies it at senior depth. It is Part 4 of a system design series.

Table of Contents

1. The Problem
2. Step 1 - Clarify Requirements
3. Step 2 - Estimate Scale
4. Step 3 - API and Data Model
5. Step 4 - High-Level Design
6. Step 5 - Deep Dive: Consistent Hashing and Cache Correctness
7. Step 6 - Bottlenecks and Trade-offs
8. Reference Architecture
9. Common Mistakes in the Interview
10. Quick Reference
11. Frequently Asked Questions
12. Sources
13. Related Articles

The Problem

We are designing a distributed in-memory cache - the infrastructure behind Memcached or Redis Cluster - that many application servers share to hold hot data and offload the database. We are designing the cache system, not using one.

The first interview task is to define whether this system is only a read optimization. Here the database is authoritative, cached entries may disappear, and each data class declares a maximum acceptable staleness. Data that cannot tolerate stale or missing reads may bypass this cache or use a different protocol. “It is a cache” is not permission to return an old price, authorization decision, or deleted account indefinitely.

Step 1 - Clarify Requirements

Functional requirements:

• GET, SET, and DELETE by key.
• Per-key TTL / expiration.
• Eviction when a node runs out of memory.

Non-functional requirements:

• Latency: propose a p99 target for the actual network path and value size, then benchmark it. Sub-millisecond may be a goal inside one data center, not a universal guarantee.
• Throughput: millions of operations per second across the cluster.
• Horizontal scalability: adding nodes adds capacity, without flushing the cluster.
• Availability: losing one node should cost only that node's share of the data, never the whole cache.
• Entry loss is acceptable. The origin remains authoritative; the cache must fail in a way the origin and callers can survive.

The key clarifying questions are cache-aside or read-through, allowed staleness per key class, miss cost, negative caching, maximum value size, and whether multi-key operations must be co-located. We will design cache-aside: the application reads the origin on a miss and attempts to populate the cache. Persistence is not required for cached entries, but invalidation events may need a durable outbox/stream so a database commit is not followed by a permanently missed delete.

Step 2 - Estimate Scale

A cache is sized by usable memory, CPU, network, operation mix, value distribution, replication, and origin protection. Memory often dominates capacity, but it is not the only limit.

Memory and node count. Suppose the hot working set is 10 TB. With 64 GB of usable RAM per node:

• 10 TB / 64 GB ≈ ~160 nodes at impossible 100% occupancy. At 70% target utilization it is about 224 nodes before replication, allocator overhead, reserved memory, zone headroom, and skew.

Throughput per node. At 10 million operations/sec across 200 nodes, the average is 50,000 ops/sec. That number proves nothing by itself: TLS, serialization, large values, pipelining, writes, expiration, replication, hot keys, and tail latency determine whether it is comfortable.

Latency budget. Measure DNS/service routing, connection pools, TLS, queueing, serialization, network, and server work. A topology-aware client often reaches the owner directly in the steady state, but resharding and stale maps require redirects or retries. Design for a bounded extra hop rather than claiming every request is always one hop.

Step 3 - API and Data Model

The external API is deliberately tiny:

GET(key)              -> value | MISS
SET(key, value, ttl)  -> ok
DELETE(key)           -> ok

Values are opaque bytes with a configurable size cap and cost-aware admission, so a few large values cannot dominate memory, network, or event-loop time.

Inside each node, three structures cooperate:

The hard part is not any single node - it is which node a key lives on, and what happens to that mapping as the cluster changes. That is the deep dive.

Step 4 - High-Level Design

Clients reach cache nodes through a topology-aware routing layer—either a maintained client library or a proxy tier. A replicated control plane publishes versioned ownership maps. Clients can temporarily hold stale maps, so data nodes return a redirect or topology-version error and clients refresh/retry with a strict budget.

flowchart TD
    App[Application Servers] --> Router[Smart Client / Proxy<br/>consistent-hashing router]
    Router --> N1[(Cache Node A)]
    Router --> N2[(Cache Node B)]
    Router --> N3[(Cache Node C)]
    Member[Replicated Control Plane<br/>versioned ownership map] -.topology.-> Router
    N1 -.heartbeat.-> Member
    N2 -.heartbeat.-> Member
    N3 -.heartbeat.-> Member
    App -.miss falls back to.-> DB[(Database - source of truth)]

Figure 1. A smart client or proxy routes from a versioned ownership map. During movement or failover a stale client may receive a redirect and refresh its map. The control plane must itself be replicated and fenced; one unversioned membership process would be a single point of failure.

The steady-state path should be direct, but ownership changes are a protocol, not an instantaneous map swap. The design needs topology epochs, conditional ownership changes, migration states, redirects/forwarding, capacity headroom, and limits that prevent retry storms while maps converge.

Step 5 - Deep Dive: Consistent Hashing and Cache Correctness

This is the core. Two themes carry it: how keys are partitioned across nodes so the cluster can grow without flushing, and how the cache stays useful and correct under hot keys, expiry storms, and node failure.

Part A - Why not modulo

Plain node = hash(key) % currentNodeCount works until the node count changes. Moving from 100 to 101 nodes changes the owner for roughly 100/101 of uniformly hashed keys, producing a near-total cold-cache event if there is no migration. Modulo itself is not forbidden: Redis Cluster, for example, hashes into a fixed 16,384-slot space and moves slots between nodes. The mistake is coupling the modulus directly to a changing list of physical nodes.

Part B - Consistent hashing

Consistent hashing fixes this by mapping both nodes and keys onto a hash ring - a circular space, say 0 to 2^32. Each key is owned by the first node encountered moving clockwise from the key's position.

With uniform hashing and equal-capacity nodes, adding one node to N existing nodes changes ownership for about 1/(N+1) of the keyspace; removing one moves roughly that node's share. Virtual nodes make those ranges less uneven. This minimizes ownership change, but it does not move bytes by itself: a real resize still needs copy/warm, dual-read or forwarding behavior, topology epochs, cutover, cleanup, and origin-load protection.

lookup(key):
    pos  = hash(key)
    node = first node clockwise from pos on the ring
    return node

Part C - Virtual nodes

Plain consistent hashing with one token per physical node can distribute a small ring unevenly, and a failed node's entire interval transfers to one successor.

Virtual nodes assign multiple ring positions to each physical node so the ring interleaves them:

flowchart LR
    A1((A)) --- B1((B)) --- C1((C)) --- A2((A)) --- B2((B)) --- C2((C)) --- A3((A)) --- W(("...wraps to A1"))

Figure 2. Virtual nodes interleave each physical node many times around the hash ring. With three physical nodes (A, B, C) appearing at multiple ring positions each, load distributes evenly and the data owned by any failed node fans out to many successors instead of crashing onto one - which is why vnodes turn a node loss from a thundering herd into a smooth handover.

More tokens generally reduce random keyspace imbalance and spread failed ranges across successors. Weighted token counts can represent different node capacities. More is not always better: the map, movement planning, failure blast radius, and per-range metadata grow. Select the count from simulation and production key/value distributions. Fixed slots, rendezvous hashing, and jump hashing are valid alternatives with different movement and control-plane properties.

Part D - Replication

With no replication, losing a node loses its ~1/N of the cached data, and those keys all miss until repopulated. Whether that is acceptable is a quantitative decision: a node loss produces an instant 1/N spike in database read traffic. If the database can absorb that spike, skip replication - this is exactly why Memcached classically does not replicate. If it cannot, replicate each key to the next R nodes clockwise on the ring.

Replication trades memory and write bandwidth for a warmer failure path. It is not seamless by definition: asynchronous replicas can lag, the promoted node has less spare capacity, clients need the new topology, and correlated zone loss can remove both copies if placement is poor. For R=1, admission control and origin load shedding must keep the expected miss surge survivable. For R>1, define placement, write acknowledgement, replica-read freshness, and promotion behavior rather than calling a factor mandatory.

Cache correctness: consistency model

Cache freshness is a product contract, not simply “eventual consistency.” Consider this cache-aside race:

1. Reader R misses and reads origin version 1.
2. Writer W commits version 2 and deletes the cache key.
3. R finishes later and stores version 1 after the delete.

“Update the database, then delete the key” reduces common stale windows but does not close this one. Choose a strategy per data class:

• Accept bounded staleness and use a TTL derived from business tolerance, with jitter to avoid synchronized expiry.
• Publish invalidations from a transactional outbox or change-data-capture stream so a committed write cannot silently skip notification. Make consumers idempotent and monitor lag.
• Include the source version in cache records and keep a version/generation watermark so a conditional populate cannot install an older value after a newer invalidation.
• Use immutable versioned keys when callers already know the authoritative version; old objects may expire naturally.
• For a genuinely strict read contract, use an authoritative/read-through or write-through design with an appropriate transactional boundary, or bypass the cache. Two independent systems do not become strongly consistent through wishful ordering.

Replica reads add another freshness dimension. If replication is asynchronous, route only data classes that tolerate lag or compare a required version/watermark before serving.

Cache correctness: hot keys

Consistent hashing balances keys across nodes - it does nothing for load within a single key. One viral key sends all of its traffic to one node, and that node hotspots no matter how good the ring is. Three mitigations stack:

• A bounded L1. An in-process cache absorbs hot reads, but it needs a short TTL, version validation, or server-assisted invalidations. On invalidation-channel disconnect, fail safe by flushing or revalidating affected entries.
• Hot-key read replication. Replicate immutable or staleness-tolerant values and select among healthy copies. Updates and invalidations must reach every copy, so this is not free capacity.
• Deliberate copy splitting. Store K versioned copies (key#1 ... key#K) and choose one at read time. This spreads reads but multiplies fill/invalidation work and needs cleanup.
• Admission and degradation. Coalesce fills, cap per-key concurrency, shed low-priority traffic, and protect the origin. Caching cannot manufacture origin capacity during a total miss.

Cache correctness: the stampede

When a popular key expires, every concurrent request misses simultaneously and they all hit the database together - a cache stampede.

sequenceDiagram
    participant C1 as Client 1
    participant C2 as Client 2
    participant CN as Client N
    participant Cache as Cache shard
    participant DB as Database
 
    Note over Cache: hot key K just expired
    C1->>Cache: GET K
    Cache-->>C1: miss
    C2->>Cache: GET K
    Cache-->>C2: miss
    CN->>Cache: GET K
    Cache-->>CN: miss
    Note over Cache: single-flight - elect one leader for K, others wait
    C1->>DB: read K (leader)
    DB-->>C1: value
    C1->>Cache: SET K = value (TTL)
    Cache-->>C2: value (woken)
    Cache-->>CN: value (woken)
    Note over C1,CN: 1 DB query, not N - stampede absorbed

Figure 3. A cache stampede neutralised by single-flight. N concurrent clients all miss on a just-expired key; instead of N parallel database reads, one client is elected leader and the rest wait for its result. This is what stops a single popular key's TTL from cascading into a database outage.

Four defenses, often combined:

• Request coalescing (single-flight). Within one process, only one request loads a key and peers await the same bounded promise. Fleet-wide coalescing needs a coordinator or lease; process-local single-flight still allows one origin query per application instance.
• A bounded distributed lease. One owner refreshes while others wait briefly or use stale data. Give the lease an expiry and ownership token, and prevent a slow former owner from overwriting a newer version after its lease expires.
• Probabilistic early recomputation and TTL jitter. Spread refreshes before the hard boundary; a principled probability can incorporate remaining TTL and recomputation time rather than choosing one fixed random moment.
• Stale-while-revalidate. Store separate freshUntil and staleUntil semantics so expired-but-servable data remains available while one worker refreshes. Never use stale fallback for data whose contract forbids it.

Failure modes

• Node down. Failure detection is imperfect and delayed. A quorum-backed control plane advances the topology epoch, assigns ranges, and clients refresh on redirect/error. With R=1, cold ranges hit the origin under a rate limit; with replicas, promotion still depends on lag, placement, capacity, and map convergence.
• Stale topology. Clients will temporarily disagree during resharding or failure. Nodes compare epochs/ownership, reject or redirect stale writes, and cap retries. Duplicate cache entries are repairable; retry storms and stale invalidations are the larger operational risk.
• Rebalance overload. Copying ranges competes with live traffic and warms the origin. Throttle movement, reserve capacity, migrate incrementally, and abort safely.
• Memory pressure. Eviction lowers effective hit rate and raises origin load. Admission control can reject low-value objects before they displace a valuable working set.

Eviction

When a node reaches its memory target, it may reject writes or evict according to policy. LRU favors recent reuse but scan traffic can pollute it. LFU favors repeated popularity and needs aging. Exact policies require metadata and mutation work; Redis, for example, documents sampled approximations rather than a perfect LRU list. Also choose admission policy, whether only TTL keys are eligible, and whether large objects should be penalized by cost. Expiration can combine lazy checks with active sampling/scheduling, but the exact mechanism is implementation-specific.

stateDiagram-v2
    [*] --> Cached: SET / repopulate on miss
    Cached --> Cached: GET (refresh recency / frequency)
    Cached --> Expired: TTL elapsed
    Cached --> Evicted: memory full (LRU / LFU victim)
    Cached --> [*]: DELETE on write
    Expired --> [*]
    Evicted --> [*]

Figure 4. The local lifecycle of one entry. A terminal delete does not close the distributed race: an older in-flight origin read can populate the key again. Version-aware population, commit-driven invalidation, or an explicitly bounded TTL policy is what controls that stale re-entry.

Multi-region

Run independent regional cache clusters when cross-region access would violate latency or availability targets. A write in region A, an asynchronous database replica in region B, and an invalidation stream can race: region B may delete, then refill from its still-old database replica. Carry source versions/commit positions, delay or reject refills below the invalidation watermark, route strict reads to an authoritative region, or accept a documented stale window. Use a durable invalidation stream when missing an event matters; plain pub/sub may not retain it for a disconnected consumer.

Evolution path

Adopt a routing abstraction and stable logical partitions early; the implementation may use a ring, fixed slots, rendezvous hashing, or a proxy. A cache flush can be acceptable during an early migration if the origin is protected and warmed deliberately. Defer replication, L1, and multi-region until their measured benefit exceeds their consistency and operational cost.

Observability

Track hit ratio and byte hit ratio by key class, plus weighted miss cost and origin requests; a 99% hit ratio can still hide a catastrophic 1% of expensive misses. Measure p50/p99/p99.9 latency by value size and outcome, fill latency, coalescing waiters, stale serves, invalidation/CDC lag, rejected stale populates, evictions/expirations, admission rejects, memory fragmentation, per-node and per-key load, replication lag, redirects/retries, topology epoch skew, range-migration rate, and origin saturation.

Step 6 - Bottlenecks and Trade-offs

• Hot keys are the bottleneck partitioning cannot fix—it balances ownership, not request frequency—so coalescing, selective L1/replication, admission control, or degradation is separate.
• A node loss can create an origin miss surge proportional to its warm working set; replicas reduce cold misses but add lag, memory, write, and promotion costs.
• Memory, network, CPU, and allocator overhead can each be the ceiling; admission and eviction decide which objects deserve scarce capacity.
• Expiry stampedes turn a popular key's TTL into a synchronised database flood unless coalescing or jittered expiry is in place.
• Topology convergence needs epochs, fencing/conditional ownership, redirects, and retry budgets; clients cannot switch maps atomically.
• Invalidation correctness spans the origin, outbox/CDC, cache versions, regional replica lag, and L1 copies. TTL is a fallback policy, not an atomic transaction.

Treat keys and values as untrusted inputs. Enforce tenant namespacing, ACLs and network identity, maximum key/value and decompressed sizes, command/time limits, encryption where required, and log redaction. Prevent cache poisoning by deriving keys from canonical authorized inputs and never cache one user's authorization-sensitive response under a shared key missing tenant/user/vary dimensions.

Reference Architecture

The pattern this problem teaches, reusable well beyond caching:

A disposable, partitioned read-optimization tier with versioned ownership, controlled migration, explicit freshness/invalidation policy, hot-key and stampede protection, and an authoritative origin protected from cache failure.

flowchart LR
    subgraph Client["Per client"]
        L1[L1 in-process cache]
    end
    subgraph Ring["Stable logical partitions"]
        direction TB
        R1[(Node + vnodes)]
        R2[(Node + vnodes)]
        R3[(Node + vnodes)]
    end
    L1 -->|miss| Ring
    Ring -->|miss| Auth[(Authoritative store)]
    Member[Versioned control plane] -.ownership map.-> Client

Figure 5. A versioned control plane maps stable logical partitions to nodes. Optional L1 caching helps selected hot reads, while the authoritative origin remains protected by coalescing, admission, rate limits, and warm migration. Every additional copy participates in the freshness protocol.

The same ownership problem recurs in sharded session stores, counters, and search indexes, but a disposable cache has a special escape hatch: it may miss and rebuild from its origin. Authoritative systems need stronger migration, replication, and write-consistency guarantees. Consistent hashing with virtual nodes is one useful partitioning choice, not the universal default.

Common Mistakes in the Interview

• Partitioning with hash(key) % N, which turns every cluster resize into a near-total cache flush.
• Omitting virtual nodes, leaving load imbalanced and a node loss dumping entirely onto one successor.
• Treating consistent hashing as a hot-key fix - it balances keys, never load within a key.
• No cache-stampede story, so a popular key's expiry floods the database.
• Treating topology as an instantaneous shared map, without epochs, redirects, online migration, or retry control.
• Assuming DB commit then cache DELETE closes every race, ignoring an older in-flight read that repopulates after deletion.
• Calling R=2 seamless failover, without replica lag, placement, promotion, remaining capacity, or topology convergence.
• Using a disposable cache for authoritative state without redefining durability and consistency requirements.
• Adding L1 or hot-key copies without invalidation/disconnect behavior, multiplying stale-read paths.
• Picking LRU or LFU by reflex, without reasoning from the access pattern.

Quick Reference

Frequently Asked Questions

What is consistent hashing and why does a distributed cache need it?

Classic consistent hashing maps nodes and keys to a ring so adding or removing one evenly weighted node remaps only its share of the keyspace. A cache needs controlled ownership changes, not necessarily a ring: fixed slots, rendezvous hashing, or jump hashing are alternatives. Every option still needs an online migration and stale-client protocol.

What are virtual nodes in consistent hashing?

Virtual nodes are multiple ring positions assigned to one physical node. They smooth random imbalance, spread failed ranges across successors, and can express weights. There is no universal count; choose it from topology overhead, movement cost, node capacities, and measured balance.

Should you use LRU or LFU cache eviction?

Measure the workload. LRU favors recency but can suffer scan pollution; LFU retains repeatedly popular objects but needs aging. Exact policies are expensive—Redis documents approximate sampled LRU/LFU—so compare hit ratio, byte hit ratio, and weighted origin miss cost with realistic traces.

How do you prevent a cache stampede?

Use process-local single-flight and, only when needed, a bounded fleet-wide lease/coordinator. Combine it with TTL jitter, probabilistic early recomputation, or a deliberate stale-while-revalidate window. Cap waiters and refresh time, and prevent an expired lease owner from installing an older result.

Does a distributed cache need to be strongly consistent?

This disposable cache-aside tier does not, but the answer depends on the data contract. Database-then-delete alone has a stale-repopulation race. Choose bounded staleness, durable outbox/CDC invalidation, version-aware population, immutable versioned keys, or a stronger authoritative design according to business risk.

How do you handle a hot key in a distributed cache?

Partitioning cannot split requests for one key automatically. Use a bounded L1 with invalidation, selective versioned read copies, fill coalescing, per-key concurrency limits, admission, and load shedding. Extra copies multiply invalidation paths, so apply the policy only to suitable data classes.

Sources

• Redis Cluster specification: slots, redirects, migration, and configuration epochs
• Redis Cluster scaling and the 16,384 hash-slot model
• Redis key eviction and approximated LRU/LFU
• Redis client-side caching and invalidation tracking
• Redis replication semantics and limitations
• Redis cache-aside pattern
• Vattani, Chierichetti, Lowenstein: Optimal Probabilistic Cache Stampede Prevention

Related Articles

• System Design Interview Problems: A Senior's Roadmap - the full series index and pattern library.
• System Design Interview Guide: The 6-Step Framework - the method this walkthrough applies.
• Design a URL Shortener - Part 1; the cache-aside read path this cache sits behind.
• Design a News Feed - Part 5; the feed store and post cache build directly on this distributed cache.
• Redis Caching Interview Guide - eviction, clustering, locking, and replication in Redis.

This is Part 4 of the system design series. Next: Design a News Feed.

Frequently Asked Questions

What is consistent hashing and why does a distributed cache need it?

Classic consistent hashing maps nodes and keys onto a ring and assigns a key to the next node clockwise. With an even ring, adding or removing one of N equal-capacity nodes changes ownership for roughly 1/N of the keyspace, unlike plain hash(key) modulo the current node count. A cache does not strictly require a ring: fixed hash slots, rendezvous hashing, or jump hashing can also provide stable partitioning. The real requirement is controlled remapping plus a migration protocol.

What are virtual nodes in consistent hashing?

A virtual node is a ring position assigned to a physical cache node. Multiple positions per node reduce random keyspace imbalance, spread a failed node's ranges across several successors, and can represent heterogeneous capacity with weights. There is no universal count such as 100 or 200: choose it from balance targets, node count, topology size, movement cost, and load tests. Fixed-slot designs provide a similar operational indirection without a vnode ring.

Should you use LRU or LFU cache eviction?

Choose from measured miss cost and access distribution. LRU favors recent reuse but a scan can pollute it; LFU retains repeatedly popular keys but needs aging so old popularity decays. Exact policies cost metadata and mutation work, so products such as Redis use sampled approximations. Also decide whether eviction applies to all keys or only expiring keys, and test hit ratio and origin-load impact rather than declaring one universal default.

How do you prevent a cache stampede?

Coalesce concurrent misses within a process and, when necessary, across instances with a bounded lease or coordinator. Add TTL jitter, probabilistic early recomputation based on remaining TTL and refresh cost, or a stale-while-revalidate window that deliberately retains stale data while one worker refreshes. Bound wait time and fall back safely if the leader fails; a distributed lock without lease ownership and stale-write protection can create another correctness bug.

Does a distributed cache need to be strongly consistent?

It depends on the cached data and freshness contract. This design is a disposable cache-aside tier, so it may lose entries and serve bounded staleness; it must not become the authority for balances, locks, sessions, or rate-limit state without a different design. Database-then-delete alone still has a stale-repopulation race. Use commit-driven invalidation through an outbox or CDC, version-aware writes or generation keys when required, and a TTL as a bounded-staleness backstop.

How do you handle a hot key in a distributed cache?

Consistent hashing balances key ownership, not requests for one key. Options include a bounded L1 with server-assisted or versioned invalidation, read replicas for immutable or carefully invalidated values, request coalescing, and deliberate replicated/suffixed copies selected at read time. Every extra copy increases invalidation and stale-read risk, so isolate hot-key policy by data class and keep origin protection, admission control, and load shedding.