A search platform of Baidu's kind caches rendered result snippets. One key begins serving a value older than the database and keeps serving it until someone deletes the key by hand. Walk the interleaving that produces it, and give a fix that does not depend on TTL.

The interleaving

Four steps, and the order is the whole bug:

1. Reader R finds the key missing and queries the database, reading value v1.
2. R is delayed - a slow network hop, a garbage-collection pause, a rescheduled container.
3. Writer W updates the row to v2 and deletes the cache key, which is the correct write-path behaviour.
4. R finally completes and sets the key to v1.

The cache now holds a value older than the database, written after the invalidation that was supposed to remove it. No component misbehaved. The invalidation was simply overtaken by a read that had already started. Every subsequent reader is served v1 until the entry expires or someone intervenes.

Why TTL is not the fix

A TTL bounds the damage; it does not prevent it. And the bound is poor exactly where it matters: a hot key read 50,000 times a second with a 60-second TTL serves three million wrong answers before it self-heals. Shortening the TTL to fix this trades the cache's whole purpose - a 1-second TTL on a hot key is close to no cache at all, and it makes the stampede problem worse.

The fix: a lease on the miss

The mechanism is documented in the 2013 NSDI paper on Facebook's memcache deployment, and it is small:

• On a miss, the cache returns "miss" plus a short-lived token and tells the client it may go to the database.
• A set is accepted only if the token is still valid. An intervening delete invalidates the token, so R's late write is rejected and the key stays empty - which is correct, because the next reader will fetch v2.
• The same token serves a second purpose: other readers that miss the key while a token is outstanding are told to wait briefly and retry the cache rather than all querying the database. The paper's evaluation reports the database query rate for a stampeded key falling from roughly 17,000 per second to about 1,300.

One mechanism closes the stale-set race and the thundering herd, which is why it is worth knowing by name.

The alternatives, and what each costs

• Versioned keys. Include a monotonically increasing row version in the cache key. A stale read writes to a key nobody will request again. Cost: the version must be readable cheaply, and old entries accumulate until they expire.
• Compare-and-set on a version. Store the version with the value and accept a set only if it is not older than what is present. Cost: the cache must support CAS and the value grows.
• Write-through. The writer populates the cache, so no reader ever sets a value. Cost: the write path now depends on the cache, and a failed set must not fail the write.
• Delayed double delete - delete the key, then delete it again after a short interval. Cheap and probabilistic: it shrinks the window rather than closing it, and it is the right answer only when the data tolerates occasional staleness.

How you would even notice

Nothing errors, so the only reliable detector is a staleness probe: sample keys, compare the cached value with the source, and emit the mismatch rate. Without it, this failure is reported by a customer, weeks later, about a value nobody can reproduce.

When this is the wrong fix to build

If the data is tolerant - a view count, a recommendation list, a cached aggregate refreshed every minute - a short TTL and no invalidation at all is the correct engineering choice, and leases are complexity with no payoff. The lease mechanism earns its place when the value is read far more often than written and a stale read is visible to a user or a payment.