Distributed Cache System Design Interview Guide

A key-value question arrives in two flavours, and the first thing you should do is ask which one is on the table. "Design a cache" (think Redis, Memcached) means speed is everything and durability is optional: a lost entry is a slower request, not lost data. "Design a persistent key-value store" (think DynamoDB, Cassandra, RocksDB) means the opposite, an acknowledged write that disappears is a bug. They share their distribution primitives, consistent hashing and replication among them, but their tradeoff trees diverge from the first decision onward.

This guide designs the cache, and carries the shared machinery: partitioning and consistent hashing (§5), replication (§9), capacity (§3). The durable side is worked through in the companion guide, designing a persistent key-value store, which refers back here for the fundamentals rather than repeating them.

What makes this question deceptively hard is that the core operation, put(key, value) / get(key), is trivially solved with a single hash table. The interview is really asking: what happens when one machine isn't enough? How do you partition 10 TB of data across dozens of nodes? How do you handle node failure without service disruption? How do you deal with one key receiving 100× the traffic of any other?

Before drawing anything, nail down whether this is a cache (latency-first, data loss acceptable) or a persistent store (durability-first). These two constraints drive almost every subsequent decision.

Functional requirements

Non-functional requirements

The numbers below are working assumptions for this design, 10 TB of total data and 1M peak QPS. The estimator in the capacity section (§3) is calibrated to these defaults.

Caches are almost entirely read-dominated. The write rate matters because it determines replication pressure and invalidation fan-out. The storage number tells us how many nodes we need and whether in-memory storage is economically viable. Cache sizing is derived from the working set, not total data.

A distributed cache scales horizontally through consistent hashing: each key maps to a position on a hash ring, and the node owning that position holds the key. Adding or removing a node remaps only about 1/N of the keys rather than reshuffling everything (§5). Replication layers on top, typically one primary and two replicas per shard, but the cache replicates asynchronously: the primary acknowledges a write and the replicas catch up behind it. That single choice is what buys the sub-millisecond read and the < 5 ms write in §2.

Clients are services, web browsers, or mobile apps, anything that issues get/put calls. They connect through a load balancer that distributes requests evenly across API server instances.

API servers are stateless. They cache nothing themselves, which is what lets the load balancer treat them as interchangeable and lets the fleet be scaled on CPU alone. Every read they serve is a lookup in the cache cluster.

Cache cluster (the in-memory key-value store this guide designs) is where every read lands. It holds the working set of the data. Under the Zipf-ish access pattern real traffic follows, the top 10% of keys absorb roughly 90% of reads (§3 models this). Nodes are partitioned using consistent hashing so that adding or removing a node remaps only a small fraction of keys.

Backing store (a relational database, a document store, an object store, whatever already owns the data) is the source of truth, and cache misses fall through to it. It is drawn dashed because it is optional, and saying so out loud is a differentiator. A cache in front of a database has one by definition. But a large share of real Redis and Memcached deployments have nothing behind them at all: session state, rate-limit counters, leaderboards, feature flags, short-lived job state. There the cache is the system of record.

That distinction changes the design rather than decorating it. With a backing store, an eviction or a cold node is a miss: the data is re-read and the only cost is latency, which is why durability is "not required" here and eviction can be aggressive. Without one, the same eviction is data loss, and three things follow.

• Eviction has to be driven by TTL and capacity planning, not by LRU pressure, because evicting a live session is a user-visible bug.
• The append-only log and snapshots become the durability story rather than a restart optimisation — see the storage engine (§7).
• Replication lag becomes a data-loss window on failover, where with a backing store it would merely be a staleness window.

If the interviewer's cache has no backing store, say so early and re-derive these three. It is the fastest way to show you understand what a cache is rather than what it usually sits in front of.

Coordinator (e.g. Zookeeper, etcd) manages cluster membership, leader election, and failure detection. Nodes heartbeat to the coordinator; when a node goes silent, the coordinator triggers automatic failover to a replica.

Architectural rationale

Real-world comparison

Consistent hashing solves the key distribution problem by placing both nodes and keys on a circular hash ring. Each key maps to the nearest node clockwise on the ring. When a node is added, it takes over only the keys between itself and its predecessor — on average 1/N of the total keyspace moves, not all keys. Virtual nodes (multiple positions per physical node) even out the distribution and prevent hotspots from uneven key hashing. Without virtual nodes, a node failure can overload its successor with a disproportionate share of traffic.

Once the dataset outgrows a single machine, you need a rule for deciding which node holds which key. The rule must be stable enough that adding or removing a node doesn't remap everything, fast enough to compute on every request, and balanced enough that no single node carries a disproportionate share of the load.

The core idea of consistent hashing is placing both nodes and keys on a circular hash ring (0 to 2³²). Each key is assigned to the first node clockwise from its position on the ring. When a node is added, only the keys between the new node and its predecessor need to move. When a node is removed, only its keys move to its successor.

Virtual nodes are the fix, and the name oversells them. A virtual node is not a process, a container, or a replica — it is one more position on the ring that points back at a real machine. The ring itself is just a sorted list of (hash, owner) pairs, so giving node-A 150 virtual nodes means inserting 150 rows that all name node-A:

hash("node-A#0") = 0x0e21..  → node-A
hash("node-C#7") = 0x1a94..  → node-C   // a key hashing to 0x13.. lands here
hash("node-A#1") = 0x2f08..  → node-A
hash("node-B#3") = 0x3c7d..  → node-B
...                          // 600 rows for a 4-node cluster

A lookup gains one step of indirection: hash the key, walk clockwise to the next position, then read which physical node that position names. node-A still runs one process holding one slice of memory. Only the routing table got bigger, by a few thousand entries that every client caches.

Scattering each node's positions around the ring buys two separate things, and they are worth keeping apart:

• Balance stops depending on luck. Positions are hash outputs, which makes them random points on a circle, and a handful of random points spread badly — the four nodes below leave A owning 39% of the keyspace and B owning 11%. That is not an unlucky seed to be rehashed away, it is simply what four random points look like. Averaging is what fixes it: with 150 positions each, a node owns 150 small arcs rather than one large one, and 150 draws sum to something close to the mean.
• A failure spreads instead of landing on one neighbour. With one position per node, a dead node hands its entire arc to the single node clockwise of it, which then serves roughly twice its normal traffic and becomes the likeliest thing to fail next. With 150 positions, its 150 arcs pass to 150 different successors, so each survivor picks up a percent or two. Adding a node is the same mechanism in reverse: its positions each take a slice from whoever covered that spot, so it draws load from the whole cluster instead of halving one neighbour.

Who runs the ring

Consistent hashing settles which node owns a key. It does not settle which machine does the arithmetic, and that is a separate decision with its own latency bill. There are three places to put it:

The read budget in §2 decides it. Against a sub-millisecond target, a proxy hop spends a large fraction of the budget on routing rather than on the lookup, so the ring belongs in the client — which here means the stateless API servers of §4, since they are the only things that call the cache.

That makes the ring shared state, and §4 already has somewhere to keep it: the coordinator that owns membership and leader election. Nodes register with it, it publishes the resulting ring, and each API server watches for changes and keeps a local copy. The ring is consulted on every single request and changes a few times a year, so the one thing it must never be is a fetch on the request path.

Which leaves the case that actually matters: a client whose copy is out of date. This is not hypothetical — during the migration in §9 the ring changes and clients pick that up at slightly different moments, so for a few seconds they disagree. Stamp the ring with a version and have clients send it on every request. A node receiving a request stamped with a version older than its own refuses it instead of answering, because answering would serve data from the wrong shard, and a confidently wrong value is the one failure a cache must not produce. The client refetches the ring and retries. The cost is one extra round-trip during a window that lasts seconds; the alternative is corruption with nothing to detect it by.

If the coordinator is unreachable, clients keep serving on the last ring they saw. A cache that refuses to answer because it cannot confirm its own topology has converted someone else's outage into its own, and the stale ring is almost always still correct — the version check is there to catch the times it is not.

The interface surface area for a cache is intentionally small. Each operation needs a clear ownership of the key, explicit TTL semantics, and a defined behaviour for non-existent keys.

Core endpoints

GET /v1/keys/{key}

// Request (no body, key in path)
GET /v1/keys/user:1234:session HTTP/1.1
Authorization: Bearer <service-token>

// Response, hit
HTTP/1.1 200 OK
X-Cache: HIT
X-TTL-Remaining: 3542
{
  "key": "user:1234:session",
  "value": "eyJhbGciOiJIUzI1NiJ9...",
  "expires_at": "2026-03-29T12:00:00Z"
}

// Response, miss
HTTP/1.1 404 Not Found
{ "error": "key_not_found" }

// Response, bad or absent credential
HTTP/1.1 401 Unauthorized
{ "error": "invalid_token" }

// Response, authenticated but not entitled to this namespace
HTTP/1.1 403 Forbidden
{ "error": "namespace_forbidden", "namespace": "tenant_7" }

PUT /v1/keys/{key}

// Request
PUT /v1/keys/user:1234:session HTTP/1.1
Authorization: Bearer <service-token>
Content-Type: application/json
{
  "value": "eyJhbGciOiJIUzI1NiJ9...",
  "ttl_seconds": 3600,          // optional; 0 = no expiry
  "if_not_exists": false         // atomic set-if-absent
}

// Response
HTTP/1.1 200 OK
{ "status": "ok", "version": 42 }

// Response, conflict (if_not_exists: true, key already exists)
HTTP/1.1 409 Conflict
{ "error": "key_exists", "current_version": 38 }

DELETE /v1/keys/{key}

HTTP/1.1 204 No Content  // success (idempotent)
HTTP/1.1 404 Not Found   // key didn't exist (acceptable, idempotent)

Optional endpoints by level

incr is the one endpoint here that is not safe to retry blindly. GET, PUT and DELETE are idempotent, replaying them lands the same state, but a retried increment after an ambiguous timeout double-counts — and ambiguous timeouts are exactly what a partition produces. If the counter drives billing or rate limiting, take a client-supplied request_id and deduplicate on it for a short window; if you would rather not pay for that, say out loud that the over-count is tolerable and why.

Conditional writes & Compare-and-Swap (CAS)

The version field in the entry schema (§7) enables optimistic locking. Two clients reading the same key both receive "version": 42. If both try to write, only the first succeeds, the second gets a 409 Conflict with the current version and must re-read and retry.

// Conditional write: only update if version matches
PUT /v1/keys/user:42:balance HTTP/1.1
{
  "value": "150",
  "if_version": 42        // fails with 409 if current version ≠ 42
}

// Response on conflict
HTTP/1.1 409 Conflict
{ "error": "version_mismatch", "current_version": 43, "hint": "re-read and retry" }

CAS is the standard answer to "how do you prevent lost updates when two clients write the same key concurrently?" without requiring distributed transactions. The engine underneath has to supply the atomicity, and it comes in one of two shapes: a server-side script that runs to completion without interleaving, or an optimistic transaction that watches the key, stages the write and aborts if the key changed in between. Pick one shape per operation — a script is already atomic, so wrapping it in an optimistic check buys nothing.

Security & multi-tenancy

For a public or multi-tenant cache, three controls are non-negotiable at L6+. First, namespace isolation: prefix all keys with a tenant or service identifier (e.g., tenant_id:entity:id) and enforce this at the API layer, no cross-namespace reads should be possible at the key level. Second, authentication: every service authenticates with its own credential, the default posture is deny, and the cluster is reachable only from a private subnet, never the public internet. Third, value size limits: reject writes above a configured max (e.g., 1 MB) at the API tier to prevent a single key from monopolising a cache node's memory and triggering eviction avalanches.

Two further controls bind the moment cached values contain personal data, and they are the ones candidates skip because a cache feels ephemeral. Retention: a TTL is a performance setting, not a deletion guarantee. A key holding personal data needs a TTL short enough to satisfy the retention policy and an explicit delete path for erasure requests, one that reaches replicas and any persistence snapshot — the snapshot is where the forgotten copy usually survives. Residency: the asynchronous cross-region replication in §9 moves values across borders by default, so a multi-region deployment under GDPR-style rules needs either per-region namespaces that are excluded from replication, or field-level encryption with keys held regionally. Both are cheap to state in an interview and conspicuous by their absence.

The most important question in the read path is: what happens on a cache miss? The answer determines latency for cold or low-frequency keys, and also whether the system can defend itself against a cache stampede, where a popular key expires and thousands of requests simultaneously hit the backing store.

Cache stampede prevention

When a popular key expires, every concurrent request sees a miss simultaneously and races to query the database, a thundering herd. This is more destructive than it sounds: because the database is provisioned for only 10% of traffic (the 90% hit rate target from the capacity estimate, §3), a stampede that doubles or triples miss volume pushes it past its p99 latency SLO immediately. The tier we deliberately sized down becomes the failure point.

The standard mitigations are: (1) distributed mutex, use an atomic compare-and-set in the cache cluster to let only one request fetch from the database while others wait; (2) probabilistic early recompute (a.k.a. "XFetch"), before a key expires, randomly decide to recompute it based on how close the TTL is, spreading recomputations over time; (3) stale-while-revalidate, return the stale cached value immediately while triggering an asynchronous background refresh.

If you reach for the mutex, give the lock a unique value and release it by checking that value, not with a bare delete. The lock's own TTL — five seconds, say — is a liveness guard: it has to expire, or one crashed holder wedges the key forever. But that means a fetch slower than the TTL loses the lock while still running, a second request acquires it legitimately, and the first one then finishes and deletes a lock it no longer owns, putting two requests in the critical section and handing back the stampede the lock existed to prevent. Releasing with a short server-side script that compares the stored token before deleting closes it, provided the engine runs that script to completion without interleaving. The guarantee is narrower than it looks, and an L6 interviewer will push on exactly that: it makes release safe, but it cannot stop the first holder from still writing after its lease lapsed. For a stampede guard that is fine, the worst case is one redundant DB read. If correctness depended on mutual exclusion you would need fencing tokens checked by the resource itself, which a cache cannot provide.

Write path

The write path is simpler but the tradeoff is between write latency and consistency. Write-through updates the cache and database synchronously on every write, cache is always fresh but every write pays a database round-trip. Write-behind acknowledges the write after updating the cache, then asynchronously flushes to the database, lower write latency but risk of data loss if the cache fails before the flush. Cache-aside leaves the cache population to read time, the simplest model but means every cold-start incurs a cache miss.

A key-value store is deceptively simple at the surface, a map from strings to blobs. The interesting design decisions live in what metadata accompanies each entry, how that metadata is stored efficiently, and what storage engine sits underneath.

Access patterns

Two things jump out from this table. First, point reads dominate overwhelmingly, O(1) hash map access is the right primary structure for an in-memory store, not a B-tree or skip list. Second, TTL expiry and LRU eviction both require efficient ordering by time, which a pure hash map doesn't support. The typical solution is to maintain a hash map for O(1) lookup alongside a doubly-linked list ordered by recency, with the map storing pointers into the list. That works for LRU because every access is a move-to-front, which is O(1). It does not generalise to TTL: expiry deadlines arrive in arbitrary order, so keeping a list sorted by expires_at costs O(n) per insert. TTL wants a min-heap keyed on expiry (O(log n) insert, O(1) peek-min) or a hierarchical timing wheel. A third option is to keep no ordered expiry structure at all and expire lazily on access, with a background cycle sampling random keys to catch what is never read again.

Expiry is not the memory-pressure safeguard, though, and conflating the two is a common slip. Expiry answers "is this entry still valid?"; the eviction policy (§8) answers "what goes when memory runs out?" They decide independently, which is where the trap is: an eviction policy that only considers entries carrying a TTL will find nothing to free in a keyspace that sets none, and writes start failing while memory sits full.

Storage engine options

When memory fills up, the cache must decide what to throw away. The right eviction policy depends on the access pattern of the workload. Equally important is how the cache is populated, the caching strategy determines whether writes proactively fill the cache or leave it to reads.

Eviction policies

Caching strategies

Scaling inside one region is mostly ring arithmetic: add shards, add replicas, rebalance. This section is about what that arithmetic stops covering — keeping replicas consistent enough to serve reads, promoting one without a human in the loop, and deciding whether a second region earns what it costs. That last question is the diagram below, and it deliberately runs ahead of the requirements (§2), which set no geographic target, and the estimate (§3), which sizes a single cluster. Treat two active regions as the answer to an NFR you have actually been handed, never as the default shape of a cache.

Little of what follows is exotic. The failures that actually take a cache down are the ordinary ones: a node dies, a batch of keys expires on the same second, a client retries into a queue that is already full. What separates levels is not knowing the failure exists — it is naming the mitigation and being honest about what the mitigation costs.

Classic probes table

Every architectural decision in this article is downstream of about twenty numbers. Not one of them needs to be precise. What earns credit is knowing which number settles which argument: the reason the store is in memory at all, the reason the cluster is 41 nodes rather than 400, the reason chasing a 99% hit rate is a cost decision rather than an engineering one.

The pattern to practise is a single move: name the number, then name the decision it closes. “A spinning-disk seek is 4–10 ms and the read budget is 1 ms, so nothing on the hot path touches disk” is a complete argument in one breath. Reciting latency tables without attaching them to a choice is not.

Latency: the numbers that set the budget

Throughput and node count: the numbers that decide how many boxes

These are the ones that answer “how big is this cluster, and what happens when one node dies?” — the question that separates an architecture sized to the traffic from one sized to the diagram.

Working set and memory: the numbers that decide what fits where

LRU (Least Recently Used) is the eviction policy asked about most in interviews. The data structure is a hash map for O(1) lookup, wired to a doubly-linked list ordered by recency. On every access, the node moves to the head. On eviction, the tail is removed. The challenge is doing this in O(1) for all three operations, get, put, and evict.

Why O(1) requires both structures

type Node struct {
    key, val    string
    prev, next  *Node
}

type LRUCache struct {
    cap        int
    m          map[string]*Node
    head, tail *Node  // sentinel nodes (never evicted)
}

func NewLRU(cap int) *LRUCache {
    h, t := &Node{}, &Node{}
    h.next, t.prev = t, h
    return &LRUCache{cap: cap, m: make(map[string]*Node), head: h, tail: t}
}

func (c *LRUCache) Get(key string) (string, bool) {
    n, ok := c.m[key]
    if !ok { return "", false }
    c.moveToFront(n)     // O(1), just pointer rewiring
    return n.val, true
}

func (c *LRUCache) Put(key, val string) {
    if n, ok := c.m[key]; ok {
        n.val = val
        c.moveToFront(n)
        return
    }
    if c.cap > 0 && len(c.m) >= c.cap {
        lru := c.tail.prev       // O(1), tail sentinel's prev is LRU node
        c.remove(lru)
        delete(c.m, lru.key)
    }
    n := &Node{key: key, val: val}
    c.m[key] = n
    c.insertFront(n)
}

func (c *LRUCache) remove(n *Node) {
    n.prev.next, n.next.prev = n.next, n.prev
}
func (c *LRUCache) insertFront(n *Node) {
    n.next, n.prev = c.head.next, c.head
    c.head.next.prev, c.head.next = n, n
}
func (c *LRUCache) moveToFront(n *Node) { c.remove(n); c.insertFront(n) }

The use that matters here is cache penetration: a lookup for a key that doesn't exist anywhere misses the cache cluster and lands on the backing store, which also returns nothing. Nothing gets cached, because there is nothing to cache, so the next identical lookup repeats the entire trip. A filter in front of the cache short-circuits it on the first hop. This matters most on public APIs, where misbehaving or malicious clients probe arbitrary keys and every probe is a free shot at your database.

A Bloom filter is a probabilistic data structure: it can definitively say a key does not exist (no false negatives), but it may occasionally say a key might exist when it doesn't (false positives). The false positive rate is configurable and depends on the bit array size and number of hash functions.

False positive rate formula

For a Bloom filter with m bits, n inserted elements, and k hash functions, the false positive probability is approximately:

The optimal number of hash functions for a given m/n ratio is k = (m/n) × ln(2). In practice, using 10 bits per element with 7 hash functions achieves a false positive rate of roughly 1%. For a set of 100 million keys, that's 125 MB, orders of magnitude smaller than storing the keys themselves.

Interviewers frequently follow up "design a cache" with "would you use Redis or Memcached?" Both are in-memory key-value stores targeting sub-millisecond latency, but they are built for different workload profiles. The answer should come from requirements, not from brand familiarity.

Rate limiting with Redis atomic increment

One of the most common Redis-specific interview follow-ups is implementing a rate limiter. The simplest approach is a fixed-window counter using INCR + EXPIRE, the right first step to explain before graduating to sliding window or token bucket approaches. Name the race while you are there: issued as two round trips, a client that dies between the INCR and the EXPIRE leaves a counter with no TTL. Because the window is stamped into the key, the next window starts clean, so this is a memory leak, one orphaned key per affected user per window, not a lockout. (With an unstamped key such as ratelimit:{user_id} it would be a permanent lockout.) That is why the script below is a script, and it is a common follow-up in its own right. The non-scripted alternative is SET key 0 EX window NX followed by INCR.

-- Lua script (atomic execution in Redis)
-- Key pattern: ratelimit:{user_id}:{window_start}
-- window_start = floor(current_unix_sec / window_size)

local key    = KEYS[1]         -- e.g. "rl:user:42:1743200"
local limit  = tonumber(ARGV[1]) -- e.g. 100 (requests per window)
local window = tonumber(ARGV[2]) -- e.g. 60 (seconds)

local count = redis.call('INCR', key)
if count == 1 then
    redis.call('EXPIRE', key, window)  -- set TTL only on first request
end

if count > limit then
    return 0  -- rate limited
end
return 1      -- allowed

Everything so far distributes keys. A hot key is skew in the other dimension: one key taking orders of magnitude more traffic than the average. A viral post, a config entry every request reads, the top-seller product ID. Consistent hashing has nothing to offer here, because its entire guarantee is that a given key lands in exactly one place.

That is why hot keys appear nowhere in the architecture of §4 or the production topology of §9. There is no box to add. Follow what a request for one key actually touches: the key hashes to one slot, the slot lives on one shard, and on Redis that shard executes commands on a single thread. Adding nodes widens the ring and leaves that path untouched; adding RAM buys working-set headroom that a single key never needed. The ceiling is one core, and it is reached while the rest of the cluster sits idle.

So everything below is a workaround, and each one works by moving traffic off that path rather than widening it. That is also the shape of a good answer: name the ceiling first, then pick the workaround whose bill your workload can pay.

Detecting one

Redis ships a diagnostic for this. redis-cli --hotkeys walks the keyspace with SCAN and calls OBJECT FREQ on each key it finds. That command only exists under an LFU maxmemory-policy (allkeys-lfu or volatile-lfu), so on a cluster left at the LRU default it fails outright, which is better to learn before an incident than during one. MONITOR shows the live command stream instead, but costs a large fraction of throughput to run, making it a minute of triage rather than a monitor.

Neither is a production signal. What is: sample a fraction of requests at the API layer and feed them to a heavy-hitters structure such as a count-min sketch or a top-K counter. The threshold that promotes a key should be set relative to the per-server mean, roughly 1000× it, rather than as an absolute QPS number, because the absolute number moves every time the fleet is resized. Netflix’s EVCache does the absorbing half of this in its client library, as a near cache in front of the cluster. The detecting half can sit in that same client library, in a monitoring sidecar, or in a proxy, depending on where the system already owns the routing decision.

The mitigations, and what each one costs

L6+ candidates are expected to own the system end-to-end. That includes knowing which signals to monitor, how to diagnose degradation, and how to change the system safely in production. The six signals to instrument on any cache cluster follow directly from the NFRs in §2.

Key metrics to monitor

Safe operations playbook