Walkthrough: Designing a Distributed Cache

The problem

You’re asked to design a distributed cache — Memcached, Redis Cluster, the cache layer behind every high-traffic web property. The interviewer says something like: “Design a distributed in-memory cache that applications can use to store hot data, scaling horizontally to hundreds of nodes.”

Sounds like “Redis, but with sharding.” It isn’t. This is the question where SDE II answers say “consistent hashing” and stop. The trap is that a real distributed cache has to make four hard choices — how to partition keys, how to handle node failure without redistributing the universe, what eviction policy to run when a node fills up, and what consistency guarantees to give callers when a key is replicated. Get any one of those wrong and the cache becomes a worse problem than the database it was supposed to protect.

Important

The core tension: A cache is supposed to fail gracefully — when it fails, traffic falls through to the database. But a cache that causes the database to fail (thundering herd, stampede, incorrect invalidation) is worse than no cache. Every design decision — partitioning, eviction, replication, failure handling — should be evaluated against this invariant: does it make the system more graceful, or does it introduce new ways to take the origin down?

Below is how I’d walk through this, roughly in the order I’d speak the words.

1. Clarify before you design

First 3–5 minutes. Resist the urge to start drawing.

Questions I’d ask:

What’s the read/write ratio? Caches are usually >95% reads. If the question is unusual (a write-heavy cache), the design changes a lot.
What’s the value size distribution? A cache for 100-byte session tokens is a very different system from a cache for 5MB rendered pages. Affects the eviction story and the network model.
Single-region or global? A globally replicated cache has to answer questions a single-region cache never has to ask.
Consistency requirements. Is stale data okay? For how long? Most cache use cases tolerate eventual consistency, but some (rate limiting, session validation) don’t.
Persistence. Pure in-memory, or do we need to survive a node restart? Memcached doesn’t persist; Redis does. The choice changes the storage model.
Write pattern. Cache-aside (app populates), write-through (cache populates from app writes), or write-behind (cache writes back to DB)? Affects who owns invalidation.
TTL discipline. Are TTLs short (seconds, for hot data), medium (minutes, for sessions), or long (hours, for content)? Drives the eviction policy choice.

Say the interviewer confirms: 99% reads, average value size 1KB (p99 100KB), single-region with 3 AZs, eventual consistency acceptable, no persistence required, cache-aside pattern, TTLs ranging from seconds to hours.

Functional Requirements

Store and retrieve key-value pairs with sub-millisecond read latency
Support TTL on every key — expired keys are evicted automatically
Support SET NX (set-if-not-exists) for atomic operations like distributed locking
Multi-get (MGET) for fetching multiple keys in one round trip

Non-Functional Requirements

p99 read latency < 1 ms end-to-end from the application client
High availability: survive single-node failures without application-visible errors
Horizontal scalability: add nodes to increase capacity without full data redistribution
Eventual consistency for replicated values is acceptable — the cache is downstream of the authoritative database

2. Capacity estimate

Brief. The point is to check the constraint that drives the architecture.

1M reads/sec average, 5M peak. 10K writes/sec.
Working set: 1TB total cache size — 1B keys at ~1KB average.
A single node holds ~64GB usable (after overhead) → ~16 nodes minimum just to fit the working set. With replication factor 2 (every key on 2 nodes), 32 nodes. Round up to 50 for headroom.
Per-node load: 5M reads/sec / 32 nodes ≈ 150K reads/sec/node. Comfortable for Redis (single-thread, ~200K ops/sec) or Memcached (multi-threaded, much higher).

I’d say out loud: “This tells me three things. One — the cluster is medium-sized, not huge; routing complexity matters less than at 1000-node scale. Two — replication is for availability, not load distribution; reads can pin to the primary. Three — eviction will happen constantly because the working set is exactly at capacity, so the eviction policy is a first-class design question.”

3. API design

The cache exposes a small surface, but a few decisions matter.

GET key
  returns: value | NOT_FOUND

SET key value [EX ttl_seconds] [NX | XX]
  returns: OK | NOT_SET

DEL key
  returns: count_deleted

MGET key1 key2 ... keyN
  returns: [value | nil, ...]

Decisions worth saying out loud:

Binary protocol, not HTTP. Cache lookups happen in the microsecond range; HTTP framing overhead would dominate. Memcached and Redis both use compact binary protocols; we’d do the same. Connection-pooled, persistent TCP from clients.
MGET is a real primitive, not just a loop. A common cache pattern is “read 50 hot keys for one page render.” If the client has to round-trip 50 times, latency multiplies. With a smart client, MGET fans out to the right shards in parallel and returns results in order. Worth naming because it’s the kind of thing that distinguishes a cache that scales from one that doesn’t.
SET NX (set-if-not-exists). Critical for distributed-lock and rate-limit use cases. Without it, callers have to do read-then-write, which is racy.
No multi-key transactions across shards. A single-shard transaction is fine; cross-shard transactions in a cache aren’t worth the complexity. I’d say so explicitly — interviewers sometimes probe.

4. Core design: how to partition keys

This is the question. Every distributed cache decision flows from this one.

Important

The partitioning choice is irreversible. Once a cache cluster is deployed with a given partitioning scheme, migrating to a different one requires a full cache-flush (instant thundering herd) or a complex dual-read migration. Get this right in the design phase.

Three approaches:

(a) Modulo hashing. node = hash(key) % N.

Pros: Trivially simple. O(1) routing.
Cons: Adding or removing a node changes the modulus, which remaps almost every key. For a cache, “remap” means “miss,” and a 95% cold cache is a thundering herd onto the database. This is why modulo hashing is a non-starter for caches at any real scale.

(b) Consistent hashing. Keys and nodes both placed on a hash ring. A key is owned by the nearest node clockwise on the ring. Adding or removing a node only moves the keys on one arc.

Pros: Adding/removing a node only invalidates ~1/N of the keyspace instead of all of it. The classic answer.
Cons: Without virtual nodes, load is uneven (some nodes own large arcs by chance). With virtual nodes (each physical node has 100–500 ring positions), load smooths out.

(c) Rendezvous hashing (highest random weight). For each key, compute hash(key, node_i) for every node and pick the highest. The winner owns the key.

Pros: No ring required. Load is naturally balanced. Adding a node also only invalidates ~1/N of keys.
Cons: O(N) lookup for each key on the client. Acceptable at small N, problematic at large N. Less standard, fewer client libraries support it.

The SDE III answer is: consistent hashing with virtual nodes. Each physical node gets ~100 virtual positions on the ring. Adding a node adds 100 small arcs; removing a node removes 100 small arcs and spreads the load to neighbors instead of one unlucky neighbor. This is the Dynamo paper’s contribution to distributed-system literacy and it’s exactly the right tool here.

5. Algorithm deep-dive: consistent hashing with virtual nodes

Worth walking through, because the interviewer is checking whether you actually understand why this works.

The mechanics:

Build the ring. A hash function (MurmurHash, xxHash) maps any string to a 64-bit integer. The ring is the integer space [0, 2^64) wrapped into a circle. Each physical node n_i is placed at 100 positions on the ring: hash("n_i:0"), hash("n_i:1"), ..., hash("n_i:99"). Sort all virtual node positions in a list.
Route a key. For key k, compute h = hash(k). Binary-search the sorted list for the smallest virtual node position >= h (wrapping around if needed). Return the physical node that virtual position belongs to. Cost: O(log N) per lookup.
Add a node. Compute the new node’s 100 virtual positions, insert them into the sorted list. The keys that move are exactly those whose hash falls in arcs newly owned by the new node — about 1/(N+1) of the keyspace. Other keys are untouched.
Remove a node. Remove its 100 virtual positions. The keys that moved-to-other-nodes are the ones in arcs that now belong to the next clockwise virtual position, again about 1/N of the keyspace.

Worked example: 4 physical nodes, each with 100 virtual nodes, total 400 virtual positions on the ring. A new node joins → 500 virtual positions, the ring is now ~20% denser, and exactly the keys that fall in the 100 new arcs (~20% of keys) move. The other 80% stay where they are. The cache survives the topology change because four out of five lookups still hit warm data.

The state on each client (or on a proxy layer) is just the sorted list of virtual positions and a map from virtual position → physical node. Tiny. Updated when the cluster topology changes; otherwise immutable.

The reason this beats modulo hashing isn’t subtle: it preserves the investment the cluster has made in being warm. Modulo hashing throws that investment away every topology change.

6. Data model and storage

The cache itself stores small entries; metadata is also small.

cache_entry (in-memory, per node):
  key          (binary string)
  value        (binary blob)
  expiry_ts    (uint64 epoch ms, 0 = no expiry)
  flags        (client-defined, 16 bits)

cluster_metadata (replicated, e.g., in ZooKeeper / etcd):
  nodes:
    node_id, host, port, status, last_heartbeat
  ring:
    [{virtual_position, node_id}, ...]
  version (monotonic, incremented on topology change)

Storage choices:

In-process memory for cache_entry. No surprise. The whole point is fast access; durable storage is the wrong layer. Memory layout matters: a slab allocator (Memcached’s approach) groups same-size objects together and eliminates fragmentation. Redis uses jemalloc with a different trade-off. Either works; the choice affects fragmentation under churn more than it affects raw throughput.
ZooKeeper or etcd for cluster metadata. Topology changes are rare (minutes between events) but must be linearizable. ZooKeeper’s zab or etcd’s Raft provides this. A cache cluster doesn’t need its own consensus layer; piggyback on a general-purpose one.

I’d say explicitly: “The cache nodes themselves don’t run consensus. Membership and ring state are coordinated through ZooKeeper. The data plane is dumb and fast; the control plane is small and slow. This separation is what lets the data plane stay in the microsecond latency budget.”

7. The read path

At 5M reads/sec across 50 nodes, the path has to be lean. No proxy hops, no synchronous coordination, no network beyond the one TCP round-trip from client to cache node.

flowchart LR
  Client[App client] --> Ring[Client-side ring lookup]
  Ring --> Node[(Cache node)]
  Node -->|hit| Client
  Node -->|miss| Client
  Client -.->|on miss| DB[(Origin DB)]
  Client -.->|backfill| Node

A few layers worth naming:

Client-side routing. The client library holds the ring, looks up the node for each key, and sends the request directly. No proxy layer. Adds complexity to clients but eliminates a network hop and a SPOF.
Cache miss flows to origin DB. Cache-aside pattern: the application reads the cache, gets NOT_FOUND, reads the DB, populates the cache, returns. The cache itself doesn’t know about the DB. This is the pattern Memcached canonicalized and is right for almost every read-heavy use case.
Backfill on miss. The application writes to the cache after reading from the DB. With a TTL. The cache doesn’t need write-back logic.

Why client-side routing instead of a proxy layer? Two reasons specific to a cache:

Latency budget. A proxy adds ~200μs end-to-end. For a cache where the entire op should complete in 500μs, that’s 40% of the budget gone to one hop.
Failure isolation. A proxy is a SPOF (or a tier of SPOFs); a client-side ring puts each client in charge of its own routing.

The trade-off is operational: the ring has to be propagated to every client when topology changes. We come back to this in §10.

8. Replication, consistency, and the eviction policy

Two distinct concerns that interact and confuse candidates: how multiple copies of a key behave, and how a node decides which key to evict when full. Talk about both.

Replication

For availability, every key lives on R nodes (typically R=2 or 3). The first node in ring order is the primary; the next R-1 are secondaries.

Two modes:

Async replication (eventual consistency). The primary takes the write, returns OK immediately, and replicates to secondaries in the background. Reads can go to the primary (always fresh) or to any replica (potentially stale). This is the right choice for a cache because (a) the data is already a copy of the truth in the DB, (b) staleness is bounded by TTL anyway, and (c) the alternative is much slower writes.
Synchronous quorum write. Write returns OK only after R/2+1 replicas acknowledge. Stronger consistency, slower writes. Only worth this for the tiny set of cache use cases (distributed locks, rate-limit counters) that genuinely need it. For those, expose a separate SET_SYNC op, don’t make every write pay.

I’d commit explicitly: “For the general path, async replication. The cache is an optimization layer over a database that’s the actual source of truth. Trying to make the cache strongly consistent is solving the wrong problem — the cache lives downstream of TTLs and invalidations and will be slightly stale anyway.”

Note

Interview signal: Arguing for strong consistency in a cache is a design anti-pattern — and a sign of over-engineering. The data in the cache is already a copy of data that lives in a database. A cache that’s strongly consistent with the database is just… a slow database replica. Commit to eventual consistency with TTL as the staleness bound, and name it explicitly.

Eviction policy

When a node hits its memory budget, it must drop something. Which?

LRU (least recently used). Drop the entry not touched longest. Simple doubly-linked list + hashmap implementation. Default for most caches. Failure mode: a single batch scan that touches everything evicts the actually-hot data (“LRU thrashing”).
LFU (least frequently used). Drop the least-accessed entry. Better for stable workloads with a clear hot set; worse for time-shifting workloads where last week’s hot keys aren’t this week’s.
TinyLFU / W-TinyLFU. A hybrid that uses a small admission filter (frequency sketch) to decide whether a new entry is hot enough to displace an existing one. The current state of the art; used by Caffeine.
Random. Drop a random entry. Surprisingly competitive with LRU on real workloads; trivially cheap.

For our cache, I’d default to LRU with a configurable per-node override to LFU for caches with stable hot sets. The reasoning is specific: most of our value sizes are small and TTLs are short, so churn is high and LRU’s simplicity wins. The teams running session caches with longer-lived hot sets benefit from LFU; expose the knob rather than mandate one.

9. Sharding, replication, and the full architecture

Extending the architecture to show replication and the metadata layer:

flowchart LR
  Client[App client] --> Ring[Client-side ring lookup]
  Ring --> N1[(Cache · primary for key)]
  N1 -.->|async replicate| N2[(Cache · replica)]
  N1 -.->|async replicate| N3[(Cache · replica)]

  ZK[(ZooKeeper · cluster metadata)] -.->|topology pushes| Ring
  ZK -.->|membership| N1
  ZK -.->|membership| N2
  ZK -.->|membership| N3

  Client -.->|on miss| DB[(Origin DB)]

  classDef new fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class N2,N3,ZK new

Each key lives on one primary plus two replicas (R=3 in this diagram). ZooKeeper holds the ring; on topology change, it pushes the new ring to clients and to nodes. Clients re-route accordingly.

A few sharding nuances worth saying out loud:

Hot keys. A single key being accessed millions of times per second can saturate one node. Mitigations: (a) client-side caching of read-mostly keys (a tiny in-process LRU in the application), (b) replicating hot keys to all nodes for read scale-out, (c) splitting the value across multiple keys (key-range partitioning within one logical entry). For most workloads (a) covers it.
Re-balancing on add/remove. When a node joins, the keys that newly belong to it can be cold-loaded (let them be repopulated from the DB on miss) or warm-loaded (the node fetches them from its predecessor). Cold-loading is simpler but causes a brief thundering herd; warm-loading is more complex but smoother. For most caches, cold-loading is the right default given how cheap cache misses already are relative to a permanent failure.
AZ awareness. With 3 AZs, place the primary and the two replicas in different AZs. An AZ failure takes out at most one copy of any key. ZooKeeper’s awareness of node metadata makes this a constraint on ring placement.

10. Failure modes

I’d proactively walk through what breaks. This section is where SDE III differentiates on this question.

A cache node crashes. All keys it primarily owned are unavailable for the duration of the failover. Mitigations: the next replica in ring order is promoted to primary (~seconds), clients detect the failure (TCP error or timeout) and retry against the replica. Keys whose primary just changed will see brief miss spikes until clients refresh the ring from ZooKeeper.
ZooKeeper is unavailable. Topology can’t change, but the cache keeps serving. The ring at the clients and at the nodes is cached; it just can’t be updated. This is by design — the data plane should not depend on the control plane being healthy.
Network partition splits the cluster. Half the nodes can’t reach the other half. Both halves continue serving from their current ring view. When the partition heals, ZooKeeper resolves the conflicting topology view (the side that lost membership has to rejoin). During the partition, clients on each side may see inconsistent results for replicated keys; this is acceptable because the cache lives downstream of the database.
Hot key saturates one node. Symptom: that node’s CPU pegs at 100%, latency on every key it owns climbs. Mitigations: hot-key detection (count keys exceeding a per-second threshold), promote to client-side cache, alert the team. The signature is that the cluster as a whole has plenty of headroom but one node is on fire.
Thundering herd on cold cache after deploy / restart. A cold node sees every read miss to the DB simultaneously. Mitigations: request coalescing (only one miss per key triggers a DB read at a time), gradual warmup from neighboring replicas, stampede protection in the client library.
TTL expiry stampede. A popular key expires; thousands of clients miss simultaneously. Same mitigation as the cold-cache case: in-flight request coalescing, plus jittered TTLs (add ±10% random offset so identical-TTL keys don’t expire together).

Caution

The thundering herd is the single most common cache-related production incident. It shows up in at least three forms: cold cache after deploy, hot key TTL expiry, and node addition during peak traffic. All three have the same root cause (many clients hitting the origin simultaneously for the same key) and the same mitigation (request coalescing + jittered TTLs). Name all three variants and the unified fix.

The pattern to notice: name what fails, name what degrades gracefully, name what doesn’t. A cache is supposed to fail gracefully; the database is the source of truth. A cache that takes the database down with it is a worse system than no cache.

11. What I’d skip, and say I’m skipping

Time check: five minutes left. Things I’d explicitly defer:

Persistence (RDB / AOF in Redis terms). Not needed for our use case — we said the cache doesn’t have to survive node restart. Worth mentioning as a knob; not designing for it.
Cross-region replication. A single-region cache. If we globalized it, we’d add a regional cache layer per region, populated independently from the regional database. We wouldn’t try to keep cache state consistent across regions; that solves the wrong problem.
Auto-scaling on read pressure. Caches can scale, but reactive scaling fights itself: adding a node redistributes ~1/N of the keyspace, which causes a brief miss spike, which looks like more load. Predictive scaling on time-of-day patterns is the better default for caches. Worth mentioning, not designing.
Encrypted keys / values, audit logs, multi-tenant isolation. Real systems need these. They’re orthogonal to the distributed- cache question; calling them out shows I’ve thought about them.

Saying “I’d skip this, and here’s why” is a strong SDE III signal.

12. Wrap-up

One crisp sentence:

This design optimizes for raw read latency and graceful failure by keeping the data plane stateless of cluster topology and pushing all coordination into a small slow control plane — the cache exists to protect the database, and any complexity that compromises that goal is solving the wrong problem.

That framing — naming the cache as a system whose job is to fail better than the database — is what lands.

What separates SDE II from SDE III on this question

SDE II names consistent hashing, mentions Redis or Memcached, draws a sharded cache in front of a DB, says “use LRU.”
SDE III walks through consistent hashing with virtual nodes at re-implementation depth, separates replication consistency from eviction policy and addresses both, calls out hot-key and thundering-herd as workload-specific failure modes, names the control-plane / data-plane split as the architectural decision that enables low latency, and explicitly defers persistence and cross-region as out of scope.
Staff/Principal asks the questions that surface hidden system-level risks: “What’s the cache hit rate required to prevent the origin DB from being overloaded — have we validated that the cluster size and working-set fit actually achieve that?” They think about the operational model: how does on-call know which cache keys are hot, which are being evicted at high rates, and when a specific application team’s TTL configuration is causing system-wide impact? They reason about the long-term evolution: as the data model changes, how do we handle cache invalidation at scale — per-key DELETE, pattern-based flush, or version-tagged keys? Each has a different operational footprint. They identify missing requirements: “if this cache is shared by multiple teams, we need tenant isolation to prevent one team’s miss storm from evicting another team’s hot keys — that’s a fundamentally different design.”

The difference isn’t knowledge of the buzzwords. It’s separating the data plane from the control plane, then committing to a topology that lets the data plane stay simple.