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.

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

1. Requirements

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. High-level architecture

Three logical layers:

1. Data plane — cache nodes hold key-value pairs in memory, each owning a slice of the keyspace determined by the ring. Stateless of each other; no node needs to talk to another to serve a request.
2. Routing layer — the client-side library that maps every key to its node using a local copy of the ring. No network hop for routing.
3. Control plane — ZooKeeper (or etcd) tracking cluster membership and the authoritative ring state. Slow, small, and rarely touched — only during topology changes.

flowchart TD
  Client[App client] --> Ring[Routing layer · client-side ring]
  Ring --> N1[(Cache node · data plane)]
  ZK[(ZooKeeper · control plane)] -.->|topology push| Ring
  N1 -.->|on miss| DB[(Origin DB)]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class N1 store

The separation that matters: the data plane must not depend on the control plane being healthy. Clients cache their ring copy locally; ZooKeeper going down means topology can’t change, but the cache keeps serving. A data plane that blocks on control-plane availability defeats the sub-millisecond latency goal.

4. Architecture evolution

A distributed cache in production evolves through recognizable levels:

The design in this walkthrough is Level 4: consistent hashing with virtual nodes, async replication for availability, and an explicit control plane for membership.

I’d say out loud: “I’m targeting Level 4. The reason Level 2 is a non-starter at any real scale is that adding a node remaps almost every key — the cluster pays a full cold-cache penalty for every topology change. Levels 3 and 4 preserve the cluster’s warmth. The step from 3 to 4 is about load balance and availability, not the partitioning primitive itself.”

5. Core design choice: how to partition keys

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.

Architecture decisions

6. 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:

1. 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.
2. 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.
3. 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.
4. Remove a node. Remove its 100 virtual positions. Keys in those arcs 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 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.

7. 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

• 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.
• 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:

1. 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.
2. 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. ZooKeeper pushes the new ring version; clients subscribe and update locally.

8. Write path

Client
  │  set(key, value, ttl)
  ▼
Client ring lookup → primary node for key
  │
  ▼
Primary node
  │  1. Store in memory (slab/jemalloc allocation)
  │  2. Update TTL index (sorted by expiry_ts)
  │  3. Update eviction index (LRU list / LFU counter)
  │  4. Fan out async to secondaries
  ├──────────────────────┐
  ▼                      ▼
Secondary A           Secondary B
  │ ack (async)          │ ack (async)

Primary returns OK immediately after local write.

Step by step:

1. Client resolves the key to its primary node via local ring lookup.
2. Primary stores the value in memory with the TTL and returns OK immediately — no waiting on secondaries.
3. Primary replicates to secondaries asynchronously. A secondary that hasn’t received the update yet will serve NOT_FOUND or an older value; this is the accepted staleness window.
4. If a secondary is temporarily down, the write lands only on the primary (and any remaining secondaries). When it recovers, it can be warm-loaded from the primary or left cold (repopulated from the DB on the next miss for those keys).

9. Replication

For availability, every key lives on R nodes (typically R=2 or R=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 go to the primary (always fresh) or 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 small 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.

10. 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.

11. 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 nuances worth saying out loud:

• Hot keys. A single key 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. For most workloads (a) covers it.
• Re-balancing on add/remove. When a node joins, keys newly belonging to it can be cold-loaded (repopulated from the DB on miss) or warm-loaded (fetched from the predecessor). Cold-loading is simpler but causes a brief thundering herd; warm-loading is more complex but smoother. Cold-loading is the right default — cache misses are cheap relative to the complexity of a warm-load protocol.
• 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.

12. 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.
• 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. Say so explicitly — interviewers sometimes probe.

13. Data model and storage

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 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. 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 raw throughput.
• ZooKeeper or etcd for cluster metadata. Topology changes are rare (minutes between events) but must be linearizable. 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.”

14. Failure modes

I’d proactively walk through what breaks. The pattern: name what fails, name what degrades, name what doesn’t. A cache is supposed to fail gracefully; a cache that takes the database down with it is a worse system than no cache.

A cache node crashes

Fails: its primary-owned keys, unavailable until failover. Degrades: the next replica in ring order is promoted to primary (~seconds); clients detect the TCP error and retry against the replica. Doesn’t degrade: keys not on that node; ZooKeeper coordination. The miss spike after failover is bounded by the key count on that node’s arcs.

ZooKeeper is unavailable

Fails: topology changes — no new nodes can join, no dead nodes can be removed. Degrades: nothing visible to clients — the ring cached at each client and node stays valid and keeps serving. Doesn’t degrade: any in-flight reads or writes. The data plane must never block on the control plane.

Network partition splits the cluster

Fails: cross-partition key consistency — the two halves can diverge on replicated keys. Degrades: 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. Doesn’t degrade: either partition’s availability to its own clients. This is acceptable because the cache lives downstream of the database.

Hot key saturates one node

Fails: latency on the saturated node — not just the hot key, but every key that node hosts (collateral damage). Degrades: with client-side caching of the hot key, the read storm is absorbed before it hits the cache. Doesn’t degrade: cluster-wide capacity. The signature is a cluster with plenty of headroom where one node’s CPU is at 100%.

Thundering herd (three variants, one fix)

All three share the same root cause — many clients hitting the origin simultaneously for the same key:

Cold cache after deploy/restart: all keys are cold; every read misses to the DB at once.

Hot key TTL expiry: a popular key expires; thousands of clients miss simultaneously.

Node addition during peak traffic: ~1/N keys move to the new node; all cold at once.

Unified fix: request coalescing (only one miss per key triggers a DB read at a time) + jittered TTLs (add ±10% random offset so identical-TTL keys don’t expire together). For node additions, warm-load from a predecessor replica rather than cold.

15. 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 — 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. 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 you’ve thought about them.

Saying “I’d skip this, and here’s why” is a strong signal. It shows you know the full surface and are making deliberate scoping choices.

16. Interview flow summary

Architecture at a glance

READ                                    WRITE (SET)

get(key)                                set(key, value, ttl)
 ↓ client ring lookup                    ↓ client ring lookup
 ↓ TCP to primary node                   ↓ TCP to primary node
 → HIT: return value                     ↓ store in memory + TTL index
 → MISS: return NOT_FOUND                ↓ return OK immediately
 ↓                                       ↓ async → secondaries
Client → origin DB
Client → backfill cache with TTL        (secondaries may lag briefly)

The walkthrough order for your whiteboard

1. Requirements        — read/write ratio; consistency; TTL discipline; persistence
2. Capacity estimate   — working set fits in N nodes; eviction is steady-state
3. Architecture        — data plane / routing / control plane separation
4. Evolution           — mod-n trap → consistent hashing → vnodes
5. Partitioning        — consistent hashing with vnodes; why mod-n fails at scale
6. Read path           — client-side routing; cache-aside; MGET fan-out
7. Write path          — primary write; async replication; why not synchronous
8. Replication         — async for general writes; sync (SET_SYNC) for locks/counters
9. Eviction            — LRU default; LFU for stable hot sets; name TinyLFU
10. API                — binary protocol; MGET; SET NX; no cross-shard transactions
11. Failure modes      — thundering herd (3 variants + unified fix); hot key; ZK down

If the interviewer pushes deeper

17. 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 levels 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.

Further reading

• Designing Data-Intensive Applications — Kleppmann. Chapter 6 (partitioning) and Chapter 5 (replication) are the relevant ones.
• System Design Interview Vol. 1 — Alex Xu. Chapter 5 covers consistent hashing; chapter on distributed cache is shorter but the right starting reference.
• Dynamo paper — consistent hashing with virtual nodes, vector clocks, and the eventual-consistency model that shapes how we think about distributed caches.
• Memcached architecture — the canonical client-side-routing-only design. Reading the protocol spec is worth an afternoon.
• Redis Cluster spec — the alternative design, with hash slots instead of a hash ring. Worth comparing against what we built above.
• calm.rocks: Reference: Cache Access and Invalidation Patterns — the cheatsheet for the patterns named in §7 (cache-aside, write- through, write-behind).
• calm.rocks: Designing a URL Shortener — the canonical use case for a cache like this one; the read path there shows how a caller composes against the design above.