Stale Values Made by Invalidation Order

In one line

How long a cache serves a value different from the DB is decided not by "whether you invalidated" but by in what order read and write operations cut in. Even the same strategy is wrong for only a few ms under one ordering, and with no TTL it stays wrong until the next write arrives.

Why this was needed

In cache-aside, a read is three steps, "check the cache → on a miss read the DB → put it in the cache," and a write is two steps, "commit to the DB + handle the cache." Steps of other requests can cut in between steps. The most cited record is Facebook's Scaling Memcache at Facebook (NSDI 2013). On the write path they do not update the cache but delete it, and give the reason as "deletes are idempotent."

Even so, a problem remains. The paper defines a stale set as "the case where the value a web server puts into the cache is not the latest value it should have put," and explains that it arises when concurrent updates are reordered. The fix is a lease. On a cache miss, memcached hands out a 64-bit token tied to that key, the client sends the token along when it sets the value, and if a delete arrives in the meantime, the token becomes invalid and the set is rejected.

The patterns themselves, namely cache-aside, invalidation, stampedes, TTL jitter, and stale-while-revalidate, are covered by the "Redis and Caching" course. This module is the layer beneath that: the place where you reproduce the cut-in orders deterministically and count the stale reads.

How it works

These are the three representative cut-ins (R is a read and W is a write).

Name	Order	What remains
Set by a late-arriving read	R misses → R reads v0 from the DB … W commits (v1) → W deletes … R sets v0	v0 that arrived later than the delete
Delete first, commit later	W deletes … R misses → reads v0 → sets v0 … W commits (v1)	v0 refilled before the commit
Reversed sets by two writes	W1 commits (v1) … W2 commits (v2) → sets v2 … W1 sets v1	v1 that arrived late

The first row is not stopped even by "write then delete." A delayed double delete (delete → commit → delete again a moment later) stops it only when the late set arrives before the second delete. It is useless if the waiting time is shorter than the read's latency. And the worst-case latency of the read path (a GC pause, a retry, a slow network) does not show up in the median of the usual metrics, so this strategy is usually fine and collapses only rarely. The second row is why "delete then write" is not safe: in the window between the delete and the commit, a read refills the old value.

Version comparison (CAS). If you put the DB version into the cache along with the value, and check atomically inside the cache "overwrite only when it is strictly greater than the version currently in the cache," a late-arriving old version cannot overwrite the new one. The Redis transactions documentation says that Redis provides check-and-set with WATCH. If a watched key changes before EXEC, the whole transaction is aborted and null is returned. Since 8.4 there are also comparison options such as IFEQ for SET on string keys. The memcache lease is the same idea, and the paper likens it to load-link/store-conditional. If you write the comparison direction backward, exactly what you wanted to prevent happens.

A TTL is an upper bound, but not one measured from the commit. A TTL is counted from the moment the value is put into the cache. If an old value arrives late, it lives for the TTL from the time it arrived. So the upper bound of staleness is not the TTL but "the delay of the late set + the TTL." With no TTL, the old value that cut in stays until the next write arrives. The caching article in the Amazon Builders' Library also says to choose the TTL according to how much staleness the client can tolerate and how static the data is.

What to measure. This module defines staleness relative to the commit time: the time the read ended − the time of the commit that replaced the version the read returned. If you measure from the time the write started, the time before the commit gets mixed in, and during that time the DB also held the old value, so the cache was not lying.

What it looks like in the field

The same paper gives alleviating the thundering herd as the second use of leases, and reports that for keys vulnerable to this problem the peak DB query rate dropped from 17K to 1.3K per second; the stampede side of the story continues in the "Redis and Caching" course. Designs that flow cache invalidation as events (the outbox) are covered by the "Microservice Architecture" course, and the scenes where a message arrives twice or out of order are covered by the "The order arrived twice, and once it vanished" course. The five scenarios in the lab have their times and latencies picked by hand to reproduce the orders in the table above one by one, and the hidden scenarios the grader uses are randomly shuffled versions made with the same rules. Either way, the questions to ask here are the same: in this order, how long was the cache wrong, and does it fix itself?

What you will do in the next lab

You will plug write and read strategies, as generators, into a deterministic simulator. You will measure the number of stale reads and the maximum staleness of six strategies in five scenarios, pick out the combinations that never get fixed, and then choose one strategy by the numbers.