Stampedes and consistency

A cache in steady state is easy. The failures happen at edges: the moment a popular entry expires and every request misses at once, the moment a write and a read overlap, the moment one key carries a third of all traffic. Each of those has a name, a measurable effect, and a fix that costs something.

The experiments here ran against Redis 7.4, with Java clients in a separate container and a simulated slow query standing in for the database.

#The stampede

A home page is built from an expensive query — 300 ms — and cached for a minute. At the moment its entry expires, 200 requests arrive together. Every one of them misses the cache, and every one of them runs the query:

cache-aside, no protection             database loads 200   p50  313 ms   p99  328 ms

Two hundred copies of the most expensive query in the system, at the same instant. In this experiment the simulated database took them in its stride. A real one does not: the expensive query gets slower under concurrency, requests time out, clients retry, and the cache never gets repopulated because every attempt to rebuild it is itself timing out. This is also called the thundering herd, and it is how a cache expiring can take a database down.

Its relatives have their own names:

• Cache avalanche — many keys expiring at the same moment, typically because they were written together with the same TTL, or because the cache itself restarted empty.
• Cache penetration — requests for keys that do not exist, which never populate the cache. The caching patterns lesson measures negative caching against it.

#Defence one: only one rebuild

The fix is to make sure only one caller rebuilds the entry, while the rest wait for it or use something else.

Single-flight inside each instance — a lock per key in the JVM, so concurrent misses on one instance share one load. With four application instances:

single-flight per instance (4 instances) database loads   4   p50  282 ms   p99  318 ms

Four loads instead of two hundred: one per instance, because each instance's lock only coordinates its own threads. For many systems that is enough, and it needs nothing but a local lock — or a loading cache such as Caffeine, which does this for you.

A rebuild lock in Redis — SET key:lock 1 NX PX 5000 — so that across all instances only the caller that gets the lock rebuilds, and the rest poll the cache until the value appears. Two runs:

rebuild lock in Redis (SET NX), wait   database loads   1   p50  302 ms   p99  323 ms
rebuild lock in Redis (SET NX), wait   database loads   2   p50  299 ms   p99  326 ms

One load — and then, in the second run, two. The implementation allows exactly one way for that to happen, and it is worth understanding: a waiting request checks the cache just before the rebuilder stores the new value, finds it empty, and tries the lock just after the rebuilder releases it — so it gets the lock and rebuilds again. The fix is a second check of the cache after acquiring the lock, before loading. Double-checked locking, the same pattern as in concurrent Java code.

Notice the latency, though. With waiting, every request still took about 300 ms: they were not hitting the database, but they were waiting for the one request that was.

#Defence two: serve stale while rebuilding

If a slightly old value is acceptable — and for a home page it almost always is — the waiting requests do not need to wait. Keep a longer-lived copy of the previous value; when the fresh entry is missing, one request takes the lock and rebuilds, and every other request is served the old copy immediately:

rebuild lock, serve stale while rebuilding database loads   1   p50    0 ms   p99    2 ms

One database load, and a p99 of 2 ms. A single request paid the 300 ms rebuild; 199 were served in a couple of milliseconds from the stale copy. HTTP has a name for the same idea — Cache-Control: stale-while-revalidate — and CDNs implement it.

Two related techniques avoid the moment of expiry altogether:

• Refresh ahead of expiry. A background job, or the first request after an entry is, say, 80% of the way through its TTL, rebuilds it before it expires. Hot entries never go missing.
• Probabilistic early expiry. Each read decides at random whether to rebuild early, with a probability that rises as the entry nears expiry and with how long the rebuild takes. Across many requests, one of them rebuilds a little before the deadline and the herd never forms — without any lock.

#Consistency: the cache that stays wrong

The caching patterns lesson's update path — write the database, then delete the cache entry — looks correct, and it has a race. A reader misses the cache and reads the old row; a writer updates the row and deletes the cache entry; the reader, delayed for a moment, stores the old row it read. Nothing in any single step is wrong, and the cache now holds a value older than the database, until its TTL expires.

How often? An experiment that deliberately makes the reader and writer overlap, with random pauses of 0–3 ms on each side, 400 times per strategy, twice:

delete         153 of 400 races left a stale price in the cache (until its TTL expires)
write-through  139 of 400 races left a stale price in the cache (until its TTL expires)
versioned        0 of 400 races left a stale price in the cache (until its TTL expires)
 
delete         147 of 400 races left a stale price in the cache (until its TTL expires)
write-through  136 of 400 races left a stale price in the cache (until its TTL expires)
versioned        0 of 400 races left a stale price in the cache (until its TTL expires)

The rates are high because the experiment forces every read to overlap a write; in production the overlap is rare per request and certain at scale. What matters is the comparison:

• Delete on write left a stale value in more than a third of overlapping races.
• Write-through — the writer stores the new value instead of deleting — was barely better. The delayed reader simply overwrites the writer's fresh value with its old one.
• Versioned writes left none. Each cached value carries the row's version, and every write to the cache — from the reader and the writer alike — goes through a small Lua script that refuses to replace a newer version with an older one:

local cur = redis.call('GET', KEYS[1])
if cur then
  local v = tonumber(string.match(cur, '^(%d+):'))
  if v >= tonumber(ARGV[1]) then return 0 end
end
redis.call('SET', KEYS[1], ARGV[1] .. ':' .. ARGV[2], 'EX', 3600)
return 1

The script runs atomically inside Redis, so the check and the set cannot be separated by another client's write. The cost is a version column in the table and a script call instead of a plain SET.

#Hot keys

Hashing spreads keys evenly across Redis shards. It does not spread traffic when one key gets far more requests than the rest — a trending product, a celebrity's profile, the home page. Redis can find them: with an LFU eviction policy, it keeps a frequency counter per key, and redis-cli --hotkeys scans for the highest. After the skewed workload from the caching patterns lesson:

hot key found with counter: 43	keyname: "product:0"
hot key found with counter: 39	keyname: "product:1"
hot key found with counter: 32	keyname: "product:2"
hot key found with counter: 25	keyname: "product:3"

The counters are logarithmic and decay over time, so they rank keys rather than count requests. In a Redis Cluster, every one of those keys lives on one shard; if a hot key gets a large share of traffic, that shard's CPU and network saturate while the others idle, and adding shards does nothing for it.

The remedies are the same as for a hot database partition:

• A local cache in front for just the hottest keys, with a short TTL — the caching patterns lesson's two-level cache. Most requests never reach Redis.
• Replicas for reads, so one hot key's reads are served by several nodes.
• Key splitting — store copies under product:0#1 … product:0#8 and pick one at random on read — at the cost of updating all the copies on write.