Design Distributed Cache

Assume the cache sits in front of the main product database for a large consumer app. Peak load is 3M operations a second, about 85% reads, across 2.4 billion keys with values averaging around 1.2 KB.

Clients speak a compact binary or text protocol over long-lived TCP connections, usually through a library that knows the cluster layout. The core operations look like this.

The keyspace is divided into a fixed number of hash slots, 16,384 in Redis Cluster. A key belongs to slot CRC16(key) mod 16384, and each primary node owns a set of slot ranges. The slot count never changes; only which node owns each slot does. That indirection is what makes rebalancing manageable: you move slots, not individual key ranges.

Clients are cluster-aware. They download the slot map, compute the slot locally and send each command straight to the owning primary, with no proxy hop. If the map is out of date, the node replies with a redirect naming the new owner, and the client refreshes its map. Each primary streams its writes to one or more replicas in other availability zones. Nodes exchange heartbeats and state over a gossip bus, and when most primaries agree a primary is unreachable, its replica is promoted.

The database stays the system of record. Applications use the cache in a cache-aside pattern: read the cache, on a miss read the database and fill the cache with a TTL, and on writes update the database first and then delete the cached key.

Plain hash(key) mod N breaks the moment N changes: adding one node to 60 remaps almost every key, and the hit ratio falls to near zero. Two schemes avoid this. Consistent hashing places nodes and keys on a ring and moves only the keys between a new node and its neighbour; with many virtual nodes per server, load evens out. Fixed slots go one step further and keep an explicit table from slot to node, which an operator or autoscaler can change slot by slot.

Moving a slot while serving traffic works in steps. The target marks the slot as importing, the source as migrating, and keys are copied in small batches. During the move, a request for a key that has already left the source gets an ASK redirect to the target for that single request; once every key is copied, ownership flips and clients receive a permanent MOVED redirect.

Multi-key commands need all their keys in one slot. Hash tags solve that: only the part of the key inside braces is hashed, so {cart:9031}:items and {cart:9031}:totals share a slot and can be used in one transaction.

True LRU needs a linked list through every key, which costs memory and cache misses on each access. Production caches approximate it: each key keeps a small access clock, and when memory is needed the node samples a handful of keys, say ten, and evicts the oldest of them, keeping a small pool of good candidates between rounds. With sensible sample sizes, the result is very close to real LRU at a fraction of the cost.

LFU is often better for caches. A burst of one-off reads, such as a batch job scanning user ids, pushes popular keys out of an LRU but not out of an LFU, which counts how often keys are used with a counter that decays over time. Choose the policy per cluster: allkeys-lfu for a pure cache, volatile-* variants when some keys must never be evicted, and noeviction when data loss is worse than refusing writes.

Expiry runs two ways. Reading an expired key deletes it on the spot (lazy expiry). A background task also samples keys with TTLs several times a second and deletes expired ones, repeating quickly when it finds many, so memory held by keys that are never read again is reclaimed.

Forking a large process is the hidden cost. Copy-on-write means pages that change during the snapshot are duplicated, so a write-heavy node can briefly need far more memory. That is why the sizing above leaves a third of RAM free.

Replication is asynchronous: the primary acknowledges a write before the replica has it. That keeps writes fast, and it means a failover can lose the last few milliseconds of writes. Replicas track an offset into the primary's replication stream; after a short disconnect, they resume from their offset using a backlog buffer, and only a long gap forces a full resync with a new snapshot.

Failure detection is a vote. Each node pings others, marks a silent peer as possibly failed, and spreads that opinion by gossip. When a majority of primaries agree, the failed primary's replicas start an election, and the one with the most recent data wins. A primary cut off on the minority side of a partition keeps accepting writes until it notices it has lost contact with the majority; setting a minimum number of connected replicas for writes shortens that split-brain window.

Hot keys. One celebrity profile or flash-sale item can send 300K reads a second to one slot, more than any one node can serve. Spot them with per-key sampling on each node, then serve them from the client L1 cache with a TTL of a second or two, or copy the key under several suffixes (item:77#0 to item:77#7) on different nodes and pick one at random on each read.

Stampedes. When a popular key expires, thousands of requests miss at once and all go to the database. Let only one caller rebuild the value, using a short SET NX lock or in-process request coalescing, while others briefly serve the old value. Refreshing a little before expiry with a probability that grows as the TTL nears zero spreads rebuilds out further, and adding random jitter to TTLs stops many keys written together from expiring together.

Stale data. Deleting the key after a database write leaves a small race: a reader that loaded the old row just before the write can put it back after the delete. Short TTLs bound the damage. For stricter needs, feed invalidations from the database's change stream, or store a version with each value and refuse to write an older version over a newer one.