Cache Lease

A cached value becomes older than the database and stays that way until a human deletes the key. The interleaving that produces it is short and nothing in it misbehaves:

1. A reader misses the key and queries the database, reading v1.
2. The reader is delayed - a slow hop, a garbage-collection pause, a rescheduled container.
3. A writer updates the row to v2 and deletes the cache key, which is exactly correct.
4. The delayed reader completes and sets the key to v1.

The cache now holds a value written after the invalidation that was meant to remove it. The invalidation was not lost - it was overtaken by a read that had already started, and no amount of care on the write path prevents it.

A lease closes the gap by making the fill conditional. On a miss, the cache returns the miss plus a token, and accepts a later set only while that token is still valid. An intervening delete invalidates it, so the stale fill is rejected and the key stays empty - which is right, because the next reader will fetch v2.

Why it matters

Stale-set is uniquely nasty among cache bugs: it is permanent until intervention, it affects every reader, and nothing errors. TTL does not fix it, it only bounds it - and the bound is worst where the stakes are highest, because a key read 50,000 times a second with a 60-second TTL serves roughly three million wrong answers before healing itself.

The same token also solves a second problem for free. Readers that miss a key while a token is outstanding can be told to wait briefly and retry the cache instead of all querying the database, which is the thundering herd on a hot key. Two of the three classic cache failures closed by one mechanism is a rare thing in this field.

Implementation patterns

• Token on miss, validated on set, with a lifetime of roughly 2 to 10 seconds - long enough for a normal source read, short enough that a stalled reader does not block refills.
• Invalidate the token on delete. This is the whole stale-set fix, and it means the cache must keep a small amount of per-key state beyond the value.
• Hold-off for other readers, returning "wait and retry" rather than a miss while a token is live. Clients need a short bounded retry, which is the part that changes application code.
• Serve a stale value during the hold-off where the data tolerates it, which converts a latency spike into a slightly old answer for the few hundred milliseconds a fill takes.
• Where the cache has no lease support, approximate it: a short-lived lock key taken with "set if not exists" before filling, a version number compared on write, or versioned cache keys so a stale fill writes to a key nobody will ask for again.

Industry example

The mechanism is documented in the 2013 NSDI paper on Facebook's memcache deployment, which introduced leases for exactly these two problems and explains the stale-set interleaving in the same terms. The paper's evaluation reports the peak database query rate for a stampeded key falling from roughly 17,000 per second to about 1,300 once the lease held back the readers that would otherwise all have gone to the source.

The reason it is worth knowing by name rather than reinventing: most teams discover the herd first, build a per-key lock to fix it, and never notice they were two lines of code away from also fixing the stale set - or they build the lock and introduce a new stale-set window inside it.

Failure scenarios

• The classic stale set, as above, serving a permanently old value with no error anywhere.
• Too long a token, where a reader that died while holding one blocks refills until it expires, turning a cache miss into a user-visible stall for everyone on that key.
• Hold-off without a bound, where clients wait indefinitely and the stall propagates into the caller's thread pool - the lease must have a deadline and a fallback to reading the source.
• A write path that does not delete, relying on TTL alone, which leaves the lease with nothing to invalidate against.
• Silent divergence between cache and source, undetected because every read succeeds. Without a sampling probe that compares cached values with the source, this class of bug is reported by customers.

Trade-offs

When not to use it

When the data is tolerant, do not build this. A view count, a recommendation list, a cached aggregate refreshed every minute - a short TTL with no invalidation at all is the correct engineering choice, and leases add a protocol, per-key state and a retry path for no benefit.

When the read-to-write ratio is low, the cache is doing little work and the window is rarely hit; write-through or no cache is simpler. And if your cache has no lease primitive, prefer versioned keys over a hand-rolled locking scheme: the lock is where the subtle new races get introduced, and versioned keys are hard to get wrong.

Interview question

Q: A read-through cache occasionally serves a value older than the database and keeps serving it until the key is deleted by hand. Explain the interleaving, then give me two fixes with different cost profiles and say which one you would ship first.

What a strong answer covers: the four-step interleaving, with the point that the invalidation precedes the stale write; why TTL bounds rather than prevents and why shortening it defeats the cache; the lease mechanism and the fact that it also addresses the herd; versioned keys as the cheap alternative when the cache has no lease support; the need for a staleness probe because nothing errors; and an explicit judgement that for tolerant data the right answer is to build none of it.

Quick check

Quiz: Why does a TTL not fix a stale cache set? Because the stale value was written after the invalidation, so it is a fresh entry as far as the cache is concerned - the TTL only limits how long the wrong answer is served, and on a hot key that is still millions of reads.

Flashcard: What two questions does a cache lease token answer at once? Whether a fill may still be written - it is invalidated by any intervening delete - and whether another reader is already fetching, so the rest should wait rather than stampede the source.