Reference · quick sheet

The Cache Miss Playbook

Two failures live in the gap between a miss and the write-back. They look alike on a dashboard and need different fixes.

Telling them apart

	Thundering herd	Stale set
Kind of problem	Load	Correctness
Cause	Many clients miss the same key at once and all fetch	A slow fetcher writes back a value invalidated while it was in flight
Ends up	Cache correct, database overwhelmed	Database correct, cache lying
Symptom	Loud — database load spikes, someone is paged	Silent — no error, no latency, just wrong data
Duration	As long as the traffic lasts	Until the next invalidation, which may be hours
Fix family	Admission control / coalescing	Arbitration of the write-back (a token)

Thundering herd: Heavy read and write activity on one key: each write invalidates it, so every reader arriving before the refill takes the expensive path. Pumped by writes, which is why it recurs rather than happening once.
Stale set: A write-back that lands after the value it holds has already been superseded. Every individual step is correct; only the interleaving is wrong.
Lease: A 64-bit token bound to one key, handed out on a miss, and required to set the value back. A delete invalidates outstanding tokens, so a late set is rejected. Optimistic concurrency — load-link/store-conditional for a cache refill. Not a lock: the loser is told no, not blocked.
Optimistic concurrency: Read a value together with a witness that it has not changed, do the slow work with nothing held, then make the write conditional on the witness still being valid. The lease token is one witness; an HTTP ETag with If-Match, a SQL WHERE version = ?, and the compare in compare-and-swap are others. The question it always poses: what is my witness, and who may invalidate it?
Admission control: Limiting how many callers reach the expensive path at all, rather than making that path faster. One lease per key per 10 seconds caps database queries for that key at one per window.
Serve stale: Keeping a deleted value briefly and handing it back marked out-of-date, so a caller can proceed without waiting. Only valid where an old value is an earlier truth, not a wrong one.

Fix	Lives in	Solves	Price
Request coalescing (Discord)	A service in front of the store	Herd	A service to run; needs routing so identical requests meet
Leases (Facebook)	The cache server	Herd and stale set	A modified cache; clients must handle "wait and retry"
Rate-limited leases	The cache server	Herd, hard cap	Added latency for everyone who is told to wait
Serve stale on miss	The cache server	The waiting, not the cause	Callers act on old data — check that is safe first
Locking the key	Anywhere	Herd, badly	Blocks callers, must be released, and a crashed holder stalls the key until a timeout. A lease blocks nobody, is never released, and a vanished holder costs at most one window.

Herd-prone keys at Facebook: peak database query rate 17,000/s without leases, 1,300/s with.
Default lease rate limit: one token per key per 10 seconds.
Why it matters: "Since we provision our databases based on peak load" — you buy capacity for the worst moment, so a fix that only touches the worst moment cuts the bill in full. Same argument as watching a p99 rather than a mean.

On a miss, who is allowed to fetch? If the answer is "everyone who asks", you have a herd waiting for the traffic that reveals it.
What stops a slow fetcher from writing back a value that was invalidated while it was in flight? If the answer is "nothing", you have a stale set waiting.
Is this key both popular and frequently written? That combination is the herd's fuel.
Would an out-of-date value here be an earlier truth or a wrong answer? Only the first can be served stale.
Can the fix live in the store, or only in front of it? That is decided by what you own — you cannot patch a database you did not write.