Design a Distributed Cache

Redis-style In-Memory Cache System Design

Overview

A distributed cache keeps a working set of data in memory, spread across many servers, so that repeated reads are fast. The classic use: a popular query's result — say the profile of a celebrity, or the rendered top-of-feed — is expensive to compute from the database, so you compute it once, store it in the cache, and serve the next million reads from memory in under a millisecond instead of hammering the database. Redis and Memcached are the well-known implementations.

It is labeled "Medium" because the single-server version is trivial (a hash map with a size limit), but the moment the data no longer fits on one machine, three hard problems appear at once. First, you must spread keys across many nodes so that adding or removing a node doesn't scramble everything — this is where consistent hashing comes in. Second, a node will die, so each shard needs a replica and a story for what happens to its keys when it's lost. Third, memory is finite, so the cache must evict old keys and stay roughly in sync with the database it caches — without which you serve stale data.

The single most important framing, which we'll return to throughout: the cache is a derived, rebuildable copy of a durable store — never the source of truth. That single decision is what makes almost every hard tradeoff easy. A lost node, a dropped write, a stale replica read — all of them are acceptable because the real data still lives safely in the database, and the cache can always be refilled from it.

In this walkthrough you'll scope the system, size it, pick the data model, design the client contract, draw the read and write paths, then go deep on sharding with consistent hashing, replication and failure handling, and eviction plus keeping the cache consistent with the source of truth.

Out of scope (say so): this is the in-memory, best-effort cache, not a durable database. A durable, quorum-replicated key-value store (Dynamo-style, with quorum reads/writes and the full CAP tradeoff) is the sibling problem — we mention where it differs but do not design it here.

Functional requirements

• Get. Given a key, return its value if present in the cache (a hit), or signal absence (a miss) so the caller can load from the database.
• Set. Store a key → value pair, optionally with a TTL (time-to-live) after which it expires automatically.
• Delete. Remove a key — used to invalidate an entry after the underlying data changes in the database.
• Route. The client (or a proxy) must find which node holds a given key, without a central directory on the hot path.
• Scale out. Adding or removing a node must move only a small fraction of keys, not the whole keyspace.

Out of scope (state it): durability guarantees, transactions across keys, and complex server-side data structures. This system stores simple key → value entries in memory and serves them fast; it is not a system of record.

Non-functional requirements

• Very low latency. A cache exists to be fast — sub-millisecond in-memory reads, p99 in the low single-digit milliseconds including the network hop. If a cache read is slow, it has no reason to exist.
• High throughput. The cache must absorb far more reads than the database could — hundreds of thousands to millions of reads/sec across the cluster.
• Horizontally scalable. The working set outgrows one machine's RAM, so keys must spread across many nodes, and the cluster must grow by adding nodes.
• Available over strongly consistent. A cache is typically AP / best-effort: on failure it should degrade to a miss (fall back to the database), not return an error. A replica read may be slightly stale, and a lost node may drop not-yet-replicated writes — acceptable, because the durable store is the source of truth.
• Bounded memory. Each node has a hard memory cap; the cache holds a working set, not everything, and evicts under pressure.

Estimations

State assumptions; the goal is to justify how many nodes you need and how the working set fits in RAM, not to be exact.

Rounded assumptions

• Read QPS: ~1M reads/sec across the cluster (the whole point is to shield the database from this).
• Write/Set QPS: ~100K sets/sec — an order of magnitude below reads, since a cache is read-heavy by design.
• Working set: ~1 TB. Suppose ~1 billion hot entries at ~1 KB each (a serialized object, a rendered fragment). That's ~1 TB of values that must live in RAM. This is the number that decides the node count.
• RAM per node: ~64 GB usable for cache data (a typical cache instance).
• Node count: ~1 TB ÷ ~64 GB ≈ ~16 nodes for the data, before replication. With one replica each, ~32 nodes. Round up for headroom and hot spots.
• Hot keys. Traffic is not uniform — a handful of keys (a viral celebrity's profile) may each take tens of thousands of reads/sec, far more than one node can serve for a single key. Hot keys need special handling beyond plain hashing.

How the numbers affect the design

Core entities / data model

Two things exist: the cache entry (the key → value pair a node stores in memory) and the ring / shard map (how the cluster decides which node owns a key).

The cache entry. On each node, entries live in an in-memory hash map for O(1) lookup by key. Each entry carries its value plus a little metadata: an expires_at timestamp so a TTL'd entry can be dropped, and eviction bookkeeping (recency or frequency) so the node knows which entries to discard first when it hits its memory cap (deep dive 3).

The ring / shard map. The cluster's routing table: which nodes are alive and where each sits on the hash ring (deep dive 1). It changes only when a node joins or leaves — rarely, compared to the millions of reads/sec — so it can be distributed to all clients/proxies and cached, then updated on membership change. It is small (a list of nodes and their virtual-node positions), not per-key.

Client contract

A cache exposes a small command interface, not REST endpoints — a client library (or a proxy) speaks it. The three operations plus routing are the whole contract.

Get a key

GET <key>
Returns: value bytes, or a MISS sentinel if absent/expired

Look the key up in memory on the node that owns it. A hit returns the value in well under a millisecond. A miss (absent, or expired past its TTL) tells the caller to load from the database and (usually) SET it back — the cache-aside pattern (deep dive 3). The client does not error on a miss; a miss is normal and expected.

Set a key (optionally with TTL)

SET <key> <value> [TTL <seconds>]
Returns: OK

Store or overwrite the key → value pair on its owning node. The optional TTL sets expires_at = now + seconds, after which the entry is treated as absent. TTL is the safety net for staleness: even if you forget to invalidate an entry after a database write, it self-corrects when it expires (deep dive 3).

Delete a key

DELETE <key>
Returns: OK (whether or not the key was present)

Remove the key from its owning node. The primary use is invalidation: after the underlying row changes in the database, delete the cached copy so the next read misses and reloads the fresh value. Idempotent — deleting an absent key is a harmless no-op.

How the client finds the node

The client (or a proxy in front of the cluster) holds the ring map and computes the owning node itself — no central lookup on the hot path:

node = ring.locate(hash(key))     // walk the ring to the owning node
send GET/SET/DELETE to node

ring.locate is deep dive 1. The key insight: routing is a local computation from a cached ring map, so a GET is one hash plus one network hop — there is no directory server to consult per request.

High-level architecture

Two flows matter: the read path (get, with hit vs miss), and the write path (set / invalidate). We'll walk each, then combine them into the cluster with client-side routing.

1. Read path (hit vs miss)

The read path is the common case, and its whole job is to answer from memory when it can, and fall back to the database when it can't.

flowchart LR
    App["Application"] -->|"1. GET key"| Node["Cache Node<br/>(owner of key)"]
    Node -->|"2a. HIT: value"| App
    Node -.->|"2b. MISS"| App
    App -.->|"3. load on miss"| DB[("Database<br/>source of truth")]
    App -.->|"4. SET key = value (TTL)"| Node

1. The application computes the owning node from the ring and sends GET key to it.
2. Hit: the node has the entry (and it hasn't expired) → returns the value in under a millisecond. This is the fast path the cache exists for.
3. Miss: the entry is absent or expired → the node returns a MISS, and the application loads the value from the database (the source of truth).
4. The application writes the freshly loaded value back with SET key = value and a TTL, so the next read hits. This lazy-load-on-miss is cache-aside (deep dive 3).

2. Write path (set / invalidate)

Writes are rarer than reads. The important write is not "put data in the cache" but "keep the cache from serving stale data after the database changes."

flowchart LR
    App["Application"] -->|"1. write row"| DB[("Database<br/>source of truth")]
    App -->|"2. DELETE key (invalidate)"| Node["Cache Node<br/>(owner of key)"]
    Node -.->|"3. next GET → MISS → reload fresh"| App

1. The application writes the new value to the database first — the durable store is always updated as the source of truth.
2. It then invalidates the cached copy: DELETE key on the owning node (rather than trying to overwrite it with SET, which is easy to get wrong under concurrency — deep dive 3).
3. The next GET misses and reloads the fresh value from the database via cache-aside. The stale copy is gone; the reader sees the new value.

The rule: write the database, then invalidate the cache. TTL is the backstop — even if the invalidation is lost, the stale entry expires on its own.

3. Combined architecture (cluster with client-side routing)

Putting it together: many cache nodes each own a slice of the keyspace via the hash ring; clients route to the owning node themselves using a cached ring map; each shard has a replica; and the database sits behind as the source of truth that every miss falls back to.

flowchart TB
    subgraph Clients["Application servers (each holds the ring map)"]
        C1["App server<br/>ring.locate(key)"]
    end
    subgraph Cluster["Cache cluster (keyspace split by hash ring)"]
        direction LR
        S1["Shard A<br/>primary + replica"]
        S2["Shard B<br/>primary + replica"]
        S3["Shard C<br/>primary + replica"]
    end
    C1 -->|"GET/SET/DELETE<br/>routed by hash"| S1
    C1 --> S2
    C1 --> S3
    S1 -.->|"miss → reload"| DB[("Database<br/>source of truth")]
    S2 -.-> DB
    S3 -.-> DB
    Coord["Membership / config<br/>(gossip or coordinator)"] -.->|"ring map updates"| C1

1. Each shard owns a contiguous slice of the hash ring and is a primary + one or more replicas (deep dive 2).
2. App servers hold the ring map and compute the owning shard locally — one hash, one hop, no per-request directory lookup.
3. A membership layer (a gossip protocol, or a small coordinator like ZooKeeper/etcd) tracks which nodes are alive and pushes ring-map updates when a node joins or leaves — off the hot path.
4. Every miss falls back to the database, and the loaded value is written back into the cache. The database is the source of truth; the cluster is a fast, rebuildable copy of its hot subset.

Deep dives

1. Sharding with consistent hashing (the headline)

The working set is ~1 TB — far more than one node's RAM — so keys must spread across N nodes. The question is which node owns which key, and the answer has to survive nodes being added and removed as the cluster grows or a machine dies. Here are the approaches, worst to best.

key "user:42"  hash=100 → 100 % 4 = 0   → 100 % 5 = 0   (stayed)
key "user:99"  hash=101 → 101 % 4 = 1   → 101 % 5 = 1   (stayed)
key "post:7"   hash=102 → 102 % 4 = 2   → 102 % 5 = 2   (stayed)
key "img:3"    hash=103 → 103 % 4 = 3   → 103 % 5 = 3   (stayed)
key "user:50"  hash=104 → 104 % 4 = 0   → 104 % 5 = 4   (MOVED)
key "user:51"  hash=105 → 105 % 4 = 1   → 105 % 5 = 0   (MOVED)
...

Ring (clockwise):  NodeA@10 ── NodeB@40 ── NodeC@75 ── (wrap to 10)

key "user:42" hash=12 → walk cw → first node ≥12 is NodeB@40  → NodeB
key "post:7"  hash=55 → walk cw → first node ≥55 is NodeC@75  → NodeC
key "img:3"   hash=90 → walk cw → wraps past 75 → NodeA@10    → NodeA

Add NodeD@60:
  key "post:7" hash=55 → first node ≥55 is now NodeD@60       → MOVED to D
  everything else unchanged — only keys in (40,60] moved from C to D

flowchart LR
    K["key → hash position"] --> R["Hash ring<br/>walk clockwise"]
    R --> V["Owning virtual node<br/>(one of a physical node's ~150 tokens)"]
    V --> P["Physical cache node"]
    classDef good fill:#dcfce7,stroke:#16a34a,color:#14532d;
    class R good

2. Replication & failure handling

Nodes die. With ~32 nodes, a machine failing is a weekly event, not a rare one. If a shard has no replica, losing its node means losing that whole slice of the working set at once — a large miss storm on the database. So each shard is a primary plus one or more replicas, and you need a story for how writes propagate and what happens on failover.

Synchronous vs asynchronous replication. When a SET reaches the primary, how does the replica get it?

SET user:42 → primary applies → forward to replica → replica acks → OK to client
              (client's SET latency = primary + network to replica + replica apply)

SET user:42 → primary applies → OK to client (fast)
                              ↘ background: forward to replica (a few ms later)

Failover and promotion on node loss. The membership layer (gossip or a coordinator) detects the dead primary via missed heartbeats and promotes a replica to primary. Crucially, one node noticing a missed heartbeat must not be enough to promote: a primary that is alive but network-partitioned from one observer is still serving writes, so a single miss that triggers promotion yields two primaries accepting writes — split-brain. Promotion must require a quorum to agree the primary is gone: a majority of nodes, a coordinator like ZooKeeper/etcd, or a quorum of sentinels. With that agreement in hand, clients get an updated ring map pointing at the new primary. With async replication, the promoted replica may be missing the last few unreplicated writes — those keys simply miss and reload from the database.

flowchart LR
    P["Primary (Shard B)<br/>DIES"] -.->|"heartbeat lost"| M["Membership layer<br/>detects failure"]
    M -->|"promote"| Rep["Replica → new Primary"]
    M -->|"push ring map"| Cl["Clients route to<br/>new primary"]
    classDef bad fill:#fee2e2,stroke:#dc2626,color:#7f1d1d;
    classDef good fill:#dcfce7,stroke:#16a34a,color:#14532d;
    class P bad
    class Rep good

What happens to a shard's keyspace on node loss. If a shard has a replica, failover promotes it and the keys survive (minus any unreplicated tail). If a node is lost with no healthy replica, its share of the ring is redistributed to the neighboring virtual nodes — those nodes now own the failed node's keys, but they don't have the values, so those reads miss and refill from the database. Consistent hashing makes this graceful: only the failed node's ~1/N slice is affected, and virtual nodes scatter that slice across all survivors rather than dumping it on one. The database sees a bounded, localized burst of misses — not a cluster-wide storm.

3. Eviction & keeping the cache consistent with the source of truth

The cache holds a working set, not everything — ~1 TB of hot keys, not the whole database. Two problems follow: memory is capped, so you must decide which keys to evict when full; and the cached copy can drift from the database, so you must decide how to keep it fresh.

Eviction under a memory cap. Each node has a hard RAM limit. When a SET would exceed it, the node must drop existing entries to make room. The policy decides which:

• TTL expiry — every entry can carry a TTL; expired entries are removed lazily (on access) and/or by a background sweep. TTL is the simplest freshness and memory control: cold or stale data ages out on its own.
• LRU (least-recently-used) — evict the entry not touched for the longest time. The standard default: recency predicts reuse well for most caches. In practice, exact LRU (a strict access-ordered list) is costly to maintain, so implementations approximate it by sampling a few random entries and evicting the least-recently-used among the sample (this is what Redis does with its allkeys-lru policy) — nearly-LRU quality at a fraction of the bookkeeping.
• LFU (least-frequently-used) — evict the entry accessed the fewest times. Better than LRU when a stable set of keys is popular over a long window and you don't want a one-off scan to evict them (Redis offers allkeys-lfu).

Pick LRU as the sensible default, reach for LFU when popularity is stable and long-lived, and layer TTL on top of either for freshness.

Cache patterns — how the cache and database stay in sync. The pattern decides when the cache is written relative to the database.

write user:42 → cache updated → OK to app (fast)
                             ↘ background: flush to DB seconds later

write user:42 → update DB AND update cache (both) → OK to app

READ  user:42 → cache MISS → load from DB → SET cache (TTL) → return
WRITE user:42 → UPDATE DB → DELETE user:42 from cache
NEXT READ     → cache MISS → load fresh from DB → SET cache → return fresh

The invalidation / staleness problem. After a database write, the cached copy is stale until you remove it. Two tools together keep staleness bounded: explicit invalidation (delete the key right after the database write) removes it immediately in the common case, and TTL guarantees an upper bound on staleness even if an invalidation is dropped. Neither alone is enough — invalidation can be lost or race, and TTL alone can serve stale data for the whole TTL window. Use both.

The thundering herd / cache stampede. When a hot key expires (or is invalidated), the next wave of reads all miss simultaneously, and every one of them stampedes the database to reload the same value — a thundering herd. For a key taking 50K reads/sec, that's 50K identical database queries in the instant after expiry.

flowchart LR
    E["Hot key expires"] --> M["50K concurrent reads<br/>all MISS at once"]
    M --> SF{"single-flight?"}
    SF -->|"no"| DB1["50K identical DB queries<br/>database overwhelmed"]
    SF -->|"yes"| DB2["1 DB query reloads,<br/>others wait for result"]
    classDef bad fill:#fee2e2,stroke:#dc2626,color:#7f1d1d;
    classDef good fill:#dcfce7,stroke:#16a34a,color:#14532d;
    class DB1 bad
    class DB2 good

Fixes:

• Single-flight / request coalescing — let only one request per key reload from the database; the rest wait for that one result and share it. 50K misses collapse into 1 database query.
• Early / probabilistic recompute — refresh a hot key before it expires (e.g. asynchronously when it's close to TTL, or with a small random probability on each read), so it never fully expires under load.
• Slightly randomized (jittered) TTLs — so many keys don't expire at the same instant, spreading the reload load out.

The cache is a derived, rebuildable view. Every one of these decisions — async replication, evicting under a cap, invalidation, refilling misses from the database — is safe for the same reason: the cache is a derived copy of a durable store, never the source of truth. A lost entry, a stale replica read, a dropped write: all recoverable by reloading from the database. Hold onto that framing and the consistency story stays simple.

Tradeoffs & bottlenecks

• Cache as rebuildable copy vs source of truth. The defining choice: treating the cache as a derived, best-effort copy of the database makes availability, async replication, eviction, and lossy failover all acceptable. Give that up and you've built a database. This buys speed and simplicity at the cost of consistency guarantees the cache doesn't need.
• Consistent hashing vs modulo. Consistent hashing (with virtual nodes) moves only ~1/N of keys on a membership change and gives smooth failover, at the cost of a ring map that clients must hold and keep fresh. Modulo is simpler but remaps the whole keyspace on any change — unusable at scale.
• Async vs sync replication. Async keeps writes fast but can serve stale replica reads and drop unreplicated writes on primary loss; sync avoids loss but pays a replica round trip per write. Async is the cache default because the database backstops any loss.
• Eviction policy vs hit rate. LRU (approximated by sampling) is the pragmatic default; LFU protects a stable popular set from one-off scans; TTL bounds staleness and memory. The wrong policy silently lowers the hit rate and pushes load onto the database.
• Cache pattern vs freshness. Cache-aside caches only hot keys and stays a pure copy but has a first-read miss and an invalidation-window race; write-through is fresher but caches cold data and slows writes; write-back is fastest but risks losing un-flushed writes.
• Hot keys. A single hot key can't be split by hashing and remains a per-node bottleneck; replicating it or client-side near-caching spreads the load at the cost of a little more staleness.

Extensions if asked

If the interviewer wants to push beyond the core system, add only the extension that changes the design discussion:

• A durable quorum key-value store (the sibling problem). If the requirement becomes a durable, strongly-consistent store rather than a best-effort cache, that's a Dynamo-style system with quorum reads/writes (R + W > N) and the full CAP tradeoff — a different design where the store is the source of truth. Worth naming as the boundary of this problem, not building here.
• Rich server-side data structures. Redis supports lists, sets, sorted sets, and atomic server-side operations (e.g. leaderboards via sorted sets) — extends the value model beyond opaque bytes.
• Persistence / warm restart. Optional snapshotting or an append-only log so a restarted node reloads its data instead of starting cold — narrows, but doesn't remove, the "cache is rebuildable" framing.
• Multi-region caching. Replicating hot keys across regions for low-latency global reads, with region-local invalidation — a separate replication-topology concern.
• Cross-key transactions / consistency. Atomic updates spanning multiple keys push toward a transactional store; usually out of scope for a cache.

What interviewers look for & common mistakes

What interviewers usually reward:

• Framing the cache as a derived, rebuildable copy of a durable store — never the source of truth — and using that to justify AP / best-effort behavior everywhere.
• Sharding with consistent hashing + virtual nodes, and explaining why hash(key) % N is wrong (mass remap → miss storm) and how virtual nodes give even load and smooth failover.
• Replicating each shard with async replication, and giving the honest consistency story (slightly stale replica reads, possible loss of unreplicated writes on failover — recoverable from the database).
• Eviction under a memory cap (LRU as default, approximated by sampling; LFU when popularity is stable) plus TTL, and knowing the cache holds a working set, not everything.
• Cache-aside + invalidation + TTL for freshness, and handling the thundering herd on a hot key's expiry with single-flight / request coalescing.
• Naming hot keys as the limit hashing can't fix, and handling them by replication or client-side near-caching.

Before you finish, do a quick mistake check:

• Did you treat the cache as a rebuildable copy of the database, not the source of truth?
• Did you shard with consistent hashing (and virtual nodes) instead of hash(key) % N?
• Did you explain why modulo hashing causes a cluster-wide miss storm on any membership change?
• Did you give each shard a replica and state the async-replication staleness/loss tradeoff honestly?
• Did you say what happens to a lost node's keys (redistributed via the ring; miss and refill)?
• Did you choose an eviction policy (LRU/LFU/TTL) under a memory cap, and size the cache as a working set, not the whole database?
• Did you keep the cache fresh with cache-aside + explicit invalidation + TTL, not TTL alone?
• Did you name the thundering herd on a hot key's expiry and fix it with single-flight / early recompute?
• Did you handle hot single keys, which hashing cannot split, with replication or client-side caching?