Designing a distributed cache

Every system in this series leans on a cache, and most of them lean on the same one: a few hundred gigabytes of memory, spread over a dozen machines, answering a million operations a second in under a millisecond. This article builds that machine. It starts inside a single node, because the memory layout and the eviction policy decide almost everything, and only then spreads it across a cluster, where the interesting problems are failover and the keys everybody wants at once.

The map

Read this first when short on time. Every branch is a section below.

What a cache must do, and at what size

The interface is four operations — GET, SET with an optional TTL, DELETE, and atomic increments — plus, in a Redis-shaped cache, a handful of data structures such as hashes, sorted sets and lists that let a client do server-side work instead of read-modify-write round trips.

What it must not do is promise durability. A cache is allowed to lose data: that single permission is what lets it keep everything in memory, replicate asynchronously and fail over in seconds. The corresponding obligation on every caller is that correctness must never depend on a hit, which is the rule that most cache incidents come down to.

Working set   500 GB hot data, average value ~2 KB  -> ~250 million keys
Overhead      ~90 B per key (object header, table entry, expiry)
              250M x 90 B ~= 22 GB of pure overhead
Throughput    1,000,000 ops/s at peak, ~95% reads
Per node      ~100k ops/s of simple commands per core-thread
              -> ~10 primary shards, each ~50 GB, plus 10 replicas
Latency       server-side p99 under 1 ms
              in-datacenter round trip ~0.5 ms  -> end to end ~1.5 ms
Miss cost     a miss is a database read, 5-50 ms -> hit rate is the product

Two numbers shape everything that follows. Overhead per key is around 90 bytes before the data itself, so a cache of many tiny values is mostly bookkeeping — twenty-two gigabytes here just to remember that the keys exist. And per-node throughput is bounded by one thread's worth of command execution plus the network card, which is why the answer to more load is always more shards rather than a bigger machine.

flowchart TD
  A["application"] --> C["cache client, holds the slot map"]
  C --> S1["shard 1 primary"]
  C --> S2["shard 2 primary"]
  C --> S3["shard 3 primary"]
  S1 -.->|"async replication"| R1["shard 1 replica"]
  S2 -.-> R2["shard 2 replica"]
  S3 -.-> R3["shard 3 replica"]
  A -->|"on miss"| D[["database"]]

Inside one node

A cache node is a hash table with an eviction policy and a network loop. The details of those three decide its memory efficiency and its tail latency.

Memory is the resource being managed, so a cache spends real effort on encodings: integers are stored inline rather than as strings, short strings are embedded in the object header instead of being a separate allocation, and small collections are held as flat arrays until they outgrow a threshold. The consequence for an operator is that resident memory is not the sum of the values — it is that plus per-key overhead plus allocator fragmentation, and the ratio between allocated and resident memory is a metric worth alerting on.

Threading is the design decision people find most surprising: the command loop is single-threaded. Every command runs to completion before the next begins, which makes every operation atomic for free, removes all locking from the data structures, and gives predictable latency. The cost is that one slow command blocks everything — a KEYS * over a million keys, or deleting a collection with a million elements, is a multi-second stall for every client. Modern versions push socket reads and writes onto helper threads, which raises throughput without reintroducing locks, and newer engines such as Dragonfly and KeyDB shard the keyspace across cores inside one process instead.

Eviction: LRU, LFU and what actually gets implemented

When memory fills, something must go. The policy decides which, and the choice between the two main families matters more than any tuning within them.

LRU evicts the least recently used key. It is the intuitive answer, it adapts instantly when the working set changes, and it has one well-known failure: a single large scan — a nightly job touching every key once — evicts the entire useful working set in favour of data nobody will read again. LFU evicts the least frequently used key, which survives that scan because one touch does not outrank a key read a thousand times an hour. Its own failure is the mirror image: without decay, a key that was hot last month keeps outranking one that is hot today.

Neither policy is implemented literally. A true LRU needs a doubly linked list threaded through every object, updated on every read — that is two pointer writes per GET and sixteen bytes per key, and it turns a read-only workload into a write-heavy one. Real caches approximate: they store a coarse timestamp in the object header and, when they need to evict, sample a handful of random keys and drop the oldest of the sample. Sampling five keys gets close to true LRU; sampling ten is closer still, and the remaining error costs less than the bookkeeping would.

LFU is approximated harder, because a true counter would saturate and would never forget. The standard trick is a logarithmic counter in a single byte, incremented probabilistically so that the higher the count the less likely another increment is, paired with a decay that halves counters over time. Eight bits then represent a range from one access to millions, and yesterday's hot key fades on its own.

The last decision is the scope: evict from all keys, or only from keys that carry a TTL. Restricting eviction to keys with a TTL lets an application keep some data pinned — a configuration blob, a feature flag set — while the rest competes for space. The trap is that if the pinned set grows past the memory limit, writes start failing rather than evicting.

Scan pollution

A one-off pass over many keys evicting the useful working set, because every key it touches looks recently used.

Sampled eviction

Choosing a victim from a small random sample instead of maintaining a globally ordered structure. Nearly as good, and far cheaper.

Counter decay

Periodically reducing frequency counters so that historic popularity fades and newly hot keys can compete.

Expiry: two mechanisms, neither exact

A TTL says when a key stops being valid, not when its memory is released. Those are different events, and the gap between them is a common source of confusion.

Expiry works two ways at once. Lazily: when a key is read, its expiry is checked, and if it has passed the key is deleted and a miss returned. That is exact from the client's point of view and costs nothing, but a key nobody reads is never noticed. Actively: a background cycle samples a batch of keys that carry TTLs, deletes the expired ones, and — if more than a quarter of the sample had expired — immediately repeats, on the theory that there is probably a lot to clean up. The loop is deliberately bounded so it cannot starve command processing.

Three consequences follow. Memory is held for some time after logical expiry, so used_memory lags reality. A replica does not expire keys on its own — it waits for the primary's delete, so that primary and replica cannot disagree — which means a read from a replica can briefly return a key the primary has already dropped. And if a large number of keys are given the same TTL, they all expire in the same second, and every one of them misses at once.

Spreading across nodes

One node holds fifty gigabytes and serves a hundred thousand operations a second. The dataset needs ten of those, so something must decide which node owns a key, and that decision must survive nodes being added and removed.

Plain modulo hashing is disqualified immediately: hash(key) mod N remaps almost every key when N changes, so adding one node to a nine-node cluster invalidates the whole cache at once. Consistent hashing fixes that by placing nodes and keys on a ring so that adding a node moves only the keys between it and its predecessor.

Production caches usually go one step further and insert a fixed layer of slots between keys and nodes: hash the key into one of a fixed number of slots — 16,384 is the usual choice — and assign ranges of slots to nodes. The slot count never changes, so rebalancing is a matter of moving slots between nodes, which is explicit, resumable and easy to reason about.

Routing then has two shapes. A smart client caches the slot-to-node map and connects directly to the owner, so every operation is one round trip; when the map is stale the node replies with a redirect naming the correct owner, and the client refreshes. A proxy hides all of this behind a single endpoint, which simplifies clients in many languages at the cost of an extra network hop on every request — meaningful when the budget is one millisecond.

Sharding breaks one thing: multi-key operations. A transaction or a multi-get touching keys on different nodes has no atomic implementation, so clusters simply refuse them. The workaround is a hash tag: put a substring of the key in braces and hash only that, so user:{42}:profile and user:{42}:sessions land on the same node by construction. It works, and it reintroduces the possibility of skew, since anything co-located is also concentrated.

Replication, failover and the writes you lose

Each shard has a primary and one or more replicas. Replication is asynchronous: the primary acknowledges a write to the client and streams it to replicas afterwards. That is the right default for a cache — synchronous replication would put a network round trip inside every SET — and it has a consequence that must be stated plainly rather than discovered.

sequenceDiagram
  autonumber
  participant C as Client
  participant P as Primary
  participant R as Replica
  participant S as Cluster peers
  C->>P: SET session:9f2
  P-->>C: OK
  P--xR: replication stream lost, primary dies
  S->>S: primaries agree the node is unreachable
  S->>R: promote, take over the slots
  R-->>C: redirect, the replica now owns the slot
  Note over C,R: session:9f2 was acknowledged and is gone

Failover is four steps: peers notice the primary is unreachable for longer than a timeout, a majority agrees rather than trusting one observer, a replica is promoted, and clients are redirected. The middle step is what prevents split brain: without a majority requirement, a primary that is merely partitioned would keep accepting writes while its replacement also accepted them, and the two histories could never be reconciled. A partitioned primary must also stop serving on its own, after a timeout, since it cannot tell the difference between being isolated and everyone else being dead.

The whole process takes seconds, most of it the detection timeout. For a cache that is fine: clients see errors, fall back to the database, and recover. It is also the reason replicas are not primarily a read-scaling device here — reading from a replica gives you stale data and saves nothing, since the primary was not the bottleneck.

Using it correctly: cache-aside and its rivals

Most cache bugs are not in the cache. They are in the pattern the application uses around it, and there are only a few patterns.

sequenceDiagram
  autonumber
  participant A as Application
  participant C as Cache
  participant D as Database
  A->>C: GET user:42
  C-->>A: miss
  A->>D: SELECT the row
  D-->>A: row
  A->>C: SET user:42 with a jittered TTL
  Note over A,D: on update: write the database, then DELETE the key
  A->>D: UPDATE the row
  A->>C: DEL user:42

Cache-aside is the default: read from the cache, and on a miss read the database and fill the cache. On a write, update the database and then delete the key. Deleting rather than updating matters more than it looks. Two concurrent writers that both update the cache can leave it holding the older value forever, because the ordering of their cache writes need not match the ordering of their database writes; two writers that both delete leave the cache empty, and the next reader repopulates it correctly.

There is still a race: a reader that misses, fetches an old row, and is then paused long enough for a writer to update the database and delete the key, will fill the cache with the stale value afterwards. It is narrow, and three things bound it — a short TTL, a versioned key so a new write is a new key, or a lease in which the cache hands one client the right to fill a key and makes others wait.

Whatever the pattern, every key gets a TTL. Not because the data expires, but because a TTL is the bound on how wrong the cache can be when an invalidation is missed — and invalidations are missed, whenever a deployment has a bug or a message is dropped. A cache with no TTLs has no upper limit on staleness.

Stampedes, hot keys and penetration

Three failure modes share a shape: the cache stops absorbing load and passes it straight through to whatever is behind it.

Stampede. A popular key expires, and every request that arrives in the next few milliseconds misses and goes to the database for the same row. At ten thousand requests a second for one key, that is ten thousand identical queries. The fix is to let one request through and make the rest wait for its result, either with a short-lived lock in the cache or with in-process coalescing so each server issues at most one load per key.

flowchart TD
  R["request misses the key"] --> L{Lock acquired?}
  L -- yes --> F["load from the database"]
  F --> W["write the key, release the lock"]
  L -- no --> S["wait briefly, then read the key"]
  S --> H{Present now?}
  H -- yes --> D["serve it"]
  H -- no --> O["serve stale or degrade"]
  W --> D

A gentler variant avoids the expiry cliff entirely: store the logical expiry inside the value and have readers probabilistically refresh it shortly before that time, so the key is replaced while it is still valid and never has a moment of absence.

Hot key. One key — a celebrity profile, a viral post, a global configuration blob — receives more traffic than one node can serve, and sharding does not help because all its requests hash to the same slot. Three remedies, usually combined: replicate the key under several suffixed names and have clients pick one at random; put a small local cache in front of the remote one so that a second of staleness eliminates almost all remote reads; or, for genuinely global data, accept that it belongs in the application's own memory and not in a shared cache at all.

Penetration. Requests for keys that do not exist anywhere miss the cache by definition and reach the database every time — the cheapest denial of service there is. Cache the negative answer with a short TTL, and, when the keyspace is huge and the miss traffic malicious, put a Bloom filter in front so that a definitive "no such key" can be given without touching either store.

Persistence and the cold restart

A cache is allowed to lose data, but losing all of it at once is a different event: an empty cache sends one hundred percent of traffic to a database provisioned for two percent of it, and that is how a cache outage becomes a full outage.

Two mechanisms mitigate it. A snapshot writes the whole dataset to disk periodically, cheaply, by forking and letting the copy-on-write page table do the work; it restores fast and loses everything since the last snapshot. An append-only log records every write, is replayed on start, and is compacted in the background; it loses at most a second with a per-second flush, at the cost of writing every mutation twice.

Neither turns a cache into a database, and it is worth being explicit about why: both are asynchronous, so an acknowledged write can still be lost, and a cache's value is bounded by the store behind it anyway. What they genuinely buy is a warm restart.

What breaks first

1. Memory. The first limit, and it arrives as a rising eviction rate and a falling hit rate rather than as an error. Watch the hit rate and the eviction counter together: evictions with a high hit rate are healthy, evictions with a falling hit rate mean the working set no longer fits.
2. One node's CPU. With a single-threaded command loop, a shard saturates at its thread's throughput. The symptom is latency, not errors, and the fix is more shards — or fewer, larger operations through pipelining and multi-key commands.
3. The network card. Easy to forget: a million operations a second at 2 KB per value is four gigabytes a second, which is real hardware. Large values hit this before they hit CPU.
4. Failover time. The availability floor. Detection timeout plus election plus client redirect is seconds, during which that shard is down. Shortening the timeout trades false failovers against faster recovery.

At ten times the traffic, the shape is unchanged: more shards each holding a smaller share, client-side caching for the hottest keys, and batching to amortise the per-operation network cost. The one thing that does not scale by adding nodes is a single hot key, which is why it gets its own section above.

Recap