Design a Distributed Cache

One cache node has run out of room and speed at the same time. The working set no longer fits in one machine's memory, and the read rate is past one machine's single-threaded ceiling. Both problems have the same shape: too much for one box. So the answer has the same shape too — use more boxes. The only real question is how you decide which key lives on which box, and that decision is less obvious than it looks. The keys have to split across many cache nodes, the app server has to know which node holds a key without asking every node, and the fleet is not fixed — nodes get added as load grows and removed when they fail.

Follow the obvious answer first, because it is what most people reach for: hash the key and take the result modulo the number of nodes. With ten nodes, key hashes land in buckets zero through nine, and each bucket is a node. It is simple, it is direct, and the app server computes the node itself with no lookup. The attraction is real. But watch what happens when the fleet changes. Add one node, going from ten to eleven, and now every key is hashed modulo eleven instead of ten — which means almost every key maps to a different node than before. The cache does not gently rebalance; it effectively empties, because nearly every key is now being looked up on a node that does not have it. Every one of those lookups is a miss, and every miss falls through to the database at the same time. Adding a single node to relieve load triggers a fleet-wide cache-miss storm that slams the database — the exact thing the cache exists to prevent, caused by the routine act of growing the fleet. The same happens, unavoidably, every time a node fails and drops out.

So the requirement sharpens: adding or removing a node must move only a small fraction of the keys, not almost all of them. That is exactly what a consistent-hash ring gives you, and it is why the ring wins over mod-N. Mod-N was simpler, but its fleet-change behavior was a self-inflicted stampede; the ring pays a little complexity to make membership changes cheap, which is the property that matters at fleet scale.

A consistent-hash ring with virtual nodes — keys and nodes on one circle, a membership change moves only one arc. Map both keys and nodes onto the same fixed circle of hash values. A key belongs to the first node found walking clockwise from the key's position on the circle. When a node is added, it drops onto one arc of the circle and takes over only the keys in that arc — every other key stays exactly where it was. When a node leaves, only its arc's keys move, to the next node clockwise. A membership change moves a small fraction of the keys instead of nearly all of them. To keep each node's share even, each physical node is placed at many points around the circle rather than one — virtual nodes — so load and the cost of a membership change spread smoothly across the whole fleet instead of dumping onto one unlucky neighbor. This is the sharding scheme Amazon's Dynamo uses and the norm across distributed key-value systems.

Now size the fleet, and this is where the both-sizings habit earns its keep, because a cache has to be sized two different ways that give two different answers, and you take the larger. The throughput sizing is the read rate divided by a node's ops ceiling — a million reads a second over about a hundred and eighty thousand a node is about six nodes just to serve the rate. The capacity sizing is the working set held in memory, and the working set is not just its raw bytes: take a hundred million items averaging a kilobyte each, about a hundred gigabytes raw, replicate it three ways so a single node loss does not cold-cache a whole slice, and add the memory allocator's ten-to-twenty-percent rounding overhead, for about three hundred and forty-five gigabytes of actual fleet RAM — roughly three nodes on a hundred-and-twenty-eight-gigabyte machine. So throughput wants about six nodes and capacity wants about three, and the honest answer is the larger of the two. A fleet that can hold the working set but cannot answer the read rate is just as broken as one that can answer the rate but cannot hold the set.

The ring spread the keys across the fleet, and for the millions of ordinary keys it works exactly as promised. Then one key stops being ordinary. A celebrity posts, a post goes viral, one product lands on the front page, and suddenly a single key is being asked for far more than any other — a thousand times an average key, say. That key hashes to exactly one shard on the ring, and it stays there. So every request for it lands on that one shard, and that shard's single-node ceiling is the ceiling for that one key. The fleet has sixty nodes, but fifty-nine of them are doing nothing for this key.

The instinct — and it is a strong, natural instinct, the one nearly every engineer reaches for — is to add more shards. The cache is overwhelmed, so make the fleet bigger. But walk it through and it does nothing, because the problem is not fleet-wide capacity; it is one key's placement. That hot key hashes to one shard regardless of how many shards exist. Double the fleet from sixty nodes to a hundred and twenty, and the hot key is still on exactly one of them, still capped at that one node's ceiling, while the hundred and nineteen others carry none of its traffic. Adding shards spreads different keys onto different machines; it cannot spread one key, because one key is one hash is one shard.

And the arithmetic is counterintuitive. The unevenness is Zipfian, and Zipf has a hard ceiling on what sharding can buy. With a realistic popularity skew, the most sharding can ever multiply your total throughput is roughly ten times a single shard's ceiling, and that is with an infinite number of shards — not a hundred times, not a thousand. Past a point every new shard is carrying cold keys nobody wants while the hot key stays pinned. And the practical onset is earlier than intuition says: model a key drawing about a one-percent traffic share, and a naive one-percent-divided-by-shard-count estimate predicts you would be fine out to about a hundred shards, but the requests do not spread evenly — that one percent concentrates on the single shard holding the key — so errors actually start appearing around fifty shards, roughly half the naive prediction. The myth is that a hot key is a capacity problem you solve by adding capacity. The truth is that a hot key is a placement problem, and adding capacity leaves the placement untouched.

Replicate the hot shard, and promote the hottest keys into an app-local near cache checked before the ring. The fix cannot be more of the same shard. It has to be a different path for the hot key, and it comes in two parts. The first is hot-shard replication: instead of the hot key living on one shard, replicate that shard across several nodes, so reads for the hot key fan out across the copies instead of all hitting one. This is Facebook's default topology in effect — every frontend cluster gets its own full copy of the cache, so the hottest items are implicitly replicated across clusters, with a deliberate opt-out reserved for large, cold items where replicating would waste memory. The second part goes further and is the more powerful move: a near cache. Detect that a key is hot, and promote it into a small cache that lives inside the app server itself, checked before the ring is ever touched. Now the hottest key is answered in-process, on every app server, so the vast bulk of its traffic never reaches the ring at all — it is served from local memory on the very machine that wanted it.

The one key that could overwhelm any shard is exactly the key that is cheapest to keep a copy of everywhere, because it is one key and it is small. The near cache turns the worst key on the ring into the easiest key to serve. And the near cache is not free or automatic-forever: the system samples request traffic to detect which keys have crossed a hotness threshold, and only those cross into the near cache — it is deliberately tiny, a few megabytes per app server, holding just the top of the distribution. Because a promoted value lives in many app servers, it is kept fresh with a short time-to-live and treated as best-effort; the ring and the database remain authoritative. The detection has to keep up as the distribution shifts — yesterday's hot key cools and today's spikes — which is exactly the mechanism the Twitter incident later shows getting subtly, and expensively, wrong.

The cache holds a copy of a value. The database is the source of truth, and it just changed — a user updated their profile, a count ticked up. The copy in the cache is now stale, and cache-aside on its own has no idea. Left alone, that stale copy is served to every reader until something removes it. And this has to work at fleet scale: a single logical write can touch a cached copy in many clusters, and the write path cannot slow to a crawl to keep them all in lockstep.

The simplest answer is a time-to-live: stamp every cached value with an expiry, and let it fall out on its own after, say, a few minutes. It is trivial to implement and it bounds the staleness — nothing is ever more than the TTL out of date. But a TTL is a blunt instrument. Set it short and you throw away good cached values constantly, dropping the hit ratio and re-exposing the database; set it long and readers see stale data for the whole window. A TTL alone means choosing between a poor hit ratio and visible staleness, with no way to react to an actual change.

The next answer is write-through: on every database write, synchronously update or delete the cached copy in the same breath. Now the cache is never stale — the write path keeps it in lockstep. The cost is that every write now pays a cache round-trip, to every place that copy might live, and at fleet scale a single logical write can touch a cache copy in many clusters. The write path, which was simple, becomes a fan-out to the whole cache tier, and it blocks on it. For a read-heavy system, paying that on the write path on every write is a lot of coupling to buy freshness — which is why the move that scales is to invalidate off the write path, driven by the database's own commit log, with a short TTL underneath as the backstop.

Invalidate on commit — tail the database commit log and broadcast batched deletes, with a short TTL as the backstop. Drive the invalidation off the write path, from the database itself. Put a component next to the database that watches its commit log — the ordered stream of changes the database already writes for its own replication, called the binlog in MySQL — and, whenever a committed change touches a key, that component broadcasts a delete for that key to every cache cluster. Facebook's version is a daemon that tails each MySQL commit log, extracts the keys touched by committed deletes, batches them, and broadcasts the batch to every frontend cluster. The freshness is event-driven — a change in the database causes a delete in the cache — but it happens asynchronously, at commit granularity, off the write path, so the write stays fast and the invalidation fan-out is batched rather than paid per-write-per-cluster.

The write path just writes the database; the database's own change stream drives the cache back toward truth a moment later. Underneath it, keep a modest time-to-live as a backstop, so anything the invalidation stream misses still ages out on its own. That leaves a bounded moment of staleness between the commit and the broadcast — which is exactly the staleness a cache is designed to tolerate. A blunt TTL alone forced a bad trade between hit ratio and staleness; a synchronous write-through bought freshness by coupling every write to the whole cache tier. Invalidate-on-commit gets event-driven freshness while keeping writes fast.

The cache's memory is finite, and the working set plus everything recently touched will eventually overflow it. When a new value needs room and there is none, some existing value has to be evicted. Which one? Get it wrong and you evict a value that is about to be asked for again, turning a would-be hit into a miss and a database read. And the access pattern here is not uniform — it is the same Zipfian skew that produced the hot key, a few keys steadily hot and a long tail of cold ones.

The default reflex is least-recently-used: evict whichever value has gone longest without being touched. It is the standard, it is cheap, and most of the time it is right. But under heavy skew it has a specific failure. A key that is steadily hot — asked for constantly but not in the single most recent instant — can get evicted during a burst of one-off accesses to other keys, simply because it was not the most recent touch, even though it is one of the most frequently wanted values in the whole cache. Evicting a steady-state hot key is exactly the wrong move, because it will be asked for again immediately and now it is a miss.

The alternative is least-frequently-used: evict whichever value is asked for least often, tracking a frequency count per key rather than just a last-touch time. Under Zipf, LFU protects the steadily-hot keys that LRU would drop, because it is measuring the thing that actually predicts a future hit. The historical objection was cost — an exact frequency count per key is expensive — and Redis answers it with an approximated, decaying counter, so LFU is cheap and cold-but-once-popular keys still age out. Neither is universally right, but under this problem's skew LFU is the better default.

Least-frequently-used, with an approximated decaying counter. Evict by least-frequently-used: throw away whichever value is asked for least often, tracking a frequency count per key rather than just a last-touch time. Under Zipf, this protects the steadily-hot keys that recency-based eviction would drop, because it is measuring the thing that actually predicts a future hit — how often a key is wanted, not how recently. The catch used to be cost: an exact frequency count per key is expensive. Redis solves that with an approximated counter — a probabilistic counter that also decays over time, so a once-popular key that has gone cold does not stay artificially protected forever.

Neither policy is universally right, and that is worth saying plainly. Least-recently-used is the better default when recency really does predict the next access; least-frequently-used wins under skew where a small set of keys stays hot regardless of recency. It is a read-pattern decision, and Redis ships both precisely because there is no single right answer. And the physical memory layout is worth naming because it fed the capacity sizing two use cases ago: memory is carved into fixed-size slab classes stepping up by about a factor of one and a quarter across roughly forty classes, and each value rounds up into a class, which is where the ten-to-twenty-percent overhead in the capacity math came from.

A popular key's cached copy expires, or is invalidated. In the very next instant, every one of the many callers who wanted that key misses at the same time. With plain cache-aside, each of those callers independently does the miss thing — reads the database and refills the cache. So instead of one database read to refill the key, the database gets a thousand simultaneous reads for the same value, a thundering herd, precisely on the popular keys and precisely when the cache was supposed to be shielding the database.

The mechanism is a lease. When a caller misses a key, the cache hands exactly one of them a short-lived token that says you go get it from the database, everyone else waits. Facebook's cache issues a sixty-four-bit lease to the first misser and will not issue another for that same key for ten seconds, so the later missers wait briefly and retry rather than all stampeding the database; when the first caller refills the value, the waiters get it from the cache. N concurrent misses on one key become one database read plus a batch of short waits.

There is a complementary approach worth knowing, XFetch, which attacks the same herd from the other side: instead of everyone missing at expiry, each caller independently and probabilistically decides to refresh the value a little before it expires, with the probability rising as expiry approaches, so the recomputes spread out over time and the value rarely expires with a crowd waiting on it. Leases coordinate the herd at the moment of the miss; XFetch avoids the synchronized miss in the first place. Either way, the popular key's refill stops being a database flood — and plain cache-aside, which lets every concurrent miss hit the database, is the thing both of them beat.

A lease — one misser refills, the rest wait, so a hot key's expiry costs one database read. Hand out a lease. When a caller misses a key, the cache hands exactly one of them a short-lived token — a lease — that says you go get it from the database, everyone else waits. Facebook's cache issues a sixty-four-bit lease to the first misser and will not issue another for that same key for ten seconds, so the later missers are told to wait briefly and retry rather than all stampeding the database; when the first caller refills the value, the waiters get it from the cache. N concurrent misses on one key become one database read plus a batch of short waits. And because a hot key expiring is exactly the moment the offload is most at risk, taming the herd is directly protecting the number the whole design is built around.

One more failure closes this use case, because it is the failure that most directly threatens the database. When a cache node dies, every request that would have hit it now misses. With nothing in between, all those misses fall through to the database at once — a node loss becoming a database load spike, the same shape as the herd. The fix is a small standby pool: dedicate roughly one percent of the fleet as spare cache servers, and when a client gets no answer from its assigned node it retries against the standby pool instead of the database. Facebook calls this the Gutter pool. It is not a full replica and it does not need to be; it just has to absorb the retries from a failed node long enough that the loss costs some cache warmth rather than a flood of database reads. It is a mechanism, not a box on the board — a small reserved slice of the same fleet.

Step back and look at what is built. The near cache absorbs the hottest keys, the ring serves the working set, hot shards are replicated, the invalidator keeps copies fresh, LFU protects the steadily-hot keys, leases tame the herd, and a standby pool cushions a node loss. It is complete for the happy path. Now the premise arrives already broken, the way a real incident does — and the twist is that this is not an off-to-the-side failure that happens to touch the cache. This is the wall this whole board was built around, hitting a real company in production. In April 2018, one of the largest social platforms in the world had a partial outage lasting about an hour, severe enough to be called a SEV-0. It was not a flood of new users and not a database failure. It was a hot key in the user-data cache.

The instinct, in the room and in the moment, is to read this as a capacity shortfall and reach for the reflex from the signature dive — add more shards, spread the load. And it is exactly the wrong move, for exactly the reason the signature dive established. More shards do not un-concentrate a hot key; the key still hashes to its shard, and the concentration the bad hash created does not dissolve because the fleet got bigger. The problem was never aggregate capacity. It was that specific hot keys were pinned to specific overwhelmed shards, and the detection that was supposed to catch them was sampling too coarsely to react.

The deeper lesson is that hot-key promotion is only as good as the hot-key detection feeding it, and detection is a moving target. The set of hot keys shifts constantly as things go viral and cool off, and the sampling that finds them has to stay fine enough to catch a newly-hot key before it saturates its shard — a threshold that was safe for small values became unsafe when the values grew. The mechanism that promotes a hot key to the near cache is straightforward; keeping the detection accurate as the workload changes underneath it is the ongoing engineering, and it is precisely where this incident went wrong.

Promote the hot key to a near cache — the same fix the signature dive arrived at. Two things went wrong together. First, the system that detected hot keys sampled only about one percent of events to decide what was hot — a rate that had been fine when cache values were small, but was now too coarse to catch the hot keys quickly once the values had grown larger, so hot keys were being missed or caught late. Second, the hash function in use, an FNV1-32, happened to be poorly suited to the actual key distribution, and it concentrated a set of high-variance keys onto a small number of shards. Those few shards took a wildly disproportionate share of the traffic, and their network links — one-gigabit NICs — saturated. The cache tier buckled not because it lacked capacity in aggregate, but because the traffic had piled onto a handful of shards that could not physically move the bytes.

The mitigation that actually resolved the incident was hot-key promotion: detect the hot key, pull it out of the shared sharded tier, and serve it from a local near cache instead, alongside tuning the detection thresholds, migrating to a better hash function, and upgrading the saturated NICs. The near cache is the same box this design added in the signature dive, for the same reason: a hot key served from every app server's local memory never touches the overwhelmed shard at all. The reframe to carry out is the one the whole board is built on. A hot key is not a bigger version of the scaling problem you solve with more machines. It is a placement problem, and the answer is a different code path — promote it, replicate its shard, keep it out of the one place it would otherwise pile up. Twitter learned it the expensive way; the design learns it as the signature.