Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Hot keys & cache stampedes

When one hot key expires, every request that misses at the same moment goes off to recompute it. How coalescing, a shared lock, stale-while-revalidate and early refresh hold the database to one recompute or close to it, and what to do when a key is too hot for a single cache node.

20:04:05.000

Election night. The results page polls one cached value, results:national, the vote totals for every party, about 40,000 times a second. Building it is an aggregate query over every counting district that takes PostgreSQL about 800 ms, so the value lives in Redis with a 5-second TTL, short enough to keep the totals fresh.

At 20:04:05.000 the key expires. The next request misses and starts the query. In the 800 ms before anything is written back, about 32,000 more requests arrive, every one of them misses, and every one starts the same query. PostgreSQL, sized for one of these every five seconds, now has thousands queued, so the first one takes seconds instead of 800 ms, and for all that time the key stays empty and new requests keep joining the queue.

That is a cache stampede, also called a thundering herd: a very hot key expires, every concurrent request misses at once, and all of them go to the database to recompute the same value. The database was sized for the hit rate and now takes the full read load for that key. The recompute slows down, which keeps the key missing, which lets more requests through. The cache that protected the database has become the trigger.

Nothing about the hit rate warned anyone: with one recompute per expiry, this key would miss once in 200,000 requests. A 99.9% hit rate still stampedes if the 0.1% all happens in the same instant on the same key. What matters is how many requests miss at the same moment, and what each of those misses costs.

Let one request through

The fix is to make a miss a turn-taking event: one request recomputes, and the others wait for its answer. That is request coalescing, often called single-flight after the Go package of that name. Inside one process it is a map of loads in progress. The first caller for a key starts the query, and later callers for the same key wait on the same result.

The site runs 60 app servers, though, and in-process coalescing only works inside each one: 60 queries per expiry instead of 32,000. Better, and still 60 copies of an 800 ms aggregate every five seconds. To get down to one, the turn has to be taken somewhere every server can see, such as a lock key in the cache itself. A server that misses runs SET results:national:lock with a random value and the options NX PX 2000: set the key only if it is absent, and expire it after two seconds. The server that gets it checks the key once more, in case a previous winner has just filled it, then runs the query and writes the value. It releases the lock only if the lock still holds its random value, checking and deleting in one atomic step (a short Lua script), so it never frees one that expired and passed to another server. The others wait a few tens of milliseconds and read the key again, repeating until the value is there or the lock is free to take.

The expiry on the lock is what keeps a crashed winner from leaving the key empty for good. A winner that stalls past its expiry while a second one takes over is one of the hazards of any lock held over a network, and Distributed locks & leader election goes through them. Here the worst case is an extra recompute of a read-only query, and perhaps an older total written over a newer one until the next refresh: a far cheaper failure than two writers corrupting one resource.

Single-flight on a miss

Drawn with the lock inside a caching layer that loads for its readers (read-through), the way an HTTP cache such as nginx with proxy_cache_lock coalesces misses on a new entry. In cache-aside, the lock is a key in Redis and the winning app server runs the one query.

Waiting is a cost too

With the lock, the 32,000 requests no longer reach the database, but each one waits until the query finishes, up to the whole 800 ms: a latency spike every five seconds on the most watched page of the night. For vote totals, a copy a few seconds older is fine; a spinner is not.

Stale-while-revalidate removes the wait. Store the value with two clocks: a soft expiry at 5 seconds and a much longer hard TTL, say 60 seconds. After the soft expiry, the request that wins the lock starts the refresh, and every request, the winner included, is answered at once with the copy it already has. Readers see a miss only if the key outlives its hard TTL or is evicted. The trade: during a refresh the totals are slightly older than the soft expiry promises, so the page shows when they were counted. HTTP caches spell the same idea as a header, Cache-Control: max-age=5, stale-while-revalidate=55, which HTTP caching: Cache-Control, ETags & revalidation explains.

Refreshing early, by chance

Probabilistic early expiration needs no lock at all: as a key nears its expiry, each read rolls a die, and the closer the expiry and the slower the recompute, the likelier it is to recompute now (XFetch, published in 2015, is one such formula). It only pays when the TTL is long compared to the recompute. For this key it would misfire: at 40,000 reads a second with an 800 ms recompute, with XFetch's standard setting the first early roll is likely to win about 8 seconds before expiry, longer than the key's whole 5-second life, so dozens of readers a second would decide to recompute from the moment the value is written. Reloading a key before it expires, on a timer or on a read late in its life, is refresh-ahead, which belongs to Cache read and write strategies; here, the tally process could simply write new totals into the cache as they change, so no reader ever recomputes. Many keys warmed together with one TTL can also stampede as a group, the whole cache expiring at once an hour later; the spread-out fix, TTL jitter, is in Cache eviction: TTL, LRU, LFU.

A key too hot for one home

Even with no misses at all, results:national is one key, and in a sharded cache one key lives on one node (how keys find their node: Consistent hashing). At 21:00 the page reaches 400,000 reads a second. The value is about 20 KB, so that one node has to send 8 GB a second, 64 Gbit/s, more than a 25 Gbit/s network card can carry, while the other nodes sit idle. No policy and no lock helps with that: it is a capacity problem for one key, and the answer is more copies of it.

  • A local copy in every app server. Each of the 60 servers keeps the value in its own memory for one second and coalesces its own misses, so Redis sees about 60 reads a second for the key. Servers can disagree for up to that second.
  • Several copies under different keys. Write the totals as results:national#1 to results:national#8, names chosen to hash to different places in the cluster, and have each reader pick one at random. Every update now writes eight keys, and for a moment some copies are newer than others.
  • Replicas of the node. Spread the reads over the node's replicas, which can lag behind it (see Replication & read replicas).

All three spread reads. A key that is hot for writes, a like counter for instance, needs the opposite kind of tool, and Counting at scale is where those live.

Where this shows up in practice

Neither Challenge says "stampede" in its brief, and that is the realistic version: the hot key is rarely announced. In Distributed Cache, consistent hashing and coherent replicas are asked for by name, and the hot key hides behind them; a strong design says what happens on its miss path and how its reads get spread, and admits what the extra copies cost in coherence. Trending Topics has the opposite answer: the list every user reads is hot by design, and the design that never stampedes is the one where the stream job writes it into Redis and no reader recomputes it.

Practice this