Every entry is a claim about the past

In which currencies can the gap between a cache and the truth be closed, and why is verification underused?

CaseConstructed case · Ifeoma at Dawnpost

The 09:00 stampede and the missing correction

Three things go wrong in one week.

At 09:00 every morning the homepage entry in the article cache expires. This Monday, about 3,000 requests arrive in the same two seconds. Every one of them finds the entry missing, and every one of them runs the expensive homepage query against Postgres. The database slows down, the queries take even longer, and the homepage stays slow for several minutes.
An editor saves a correction to an article and reloads the page. She still sees the old text. She files a bug: "my save did not work".
A write fails half way: Postgres has the new article text, but the cache update was lost. Cache and database now disagree, and the disagreement does not heal.

None of these is a coding mistake. Each one is a bill that comes due because the cache is a second copy. What makes data cacheable and The derivation ladder priced the benefit of a cache. This article is the invoice.

How it ends →

The constraint that creates all the cost was stated in The second copy. Now we have to pay it:

People often list the tools for this problem as if they were five settings of one dial: TTL, versioned keys, write-through, write-back and write-around. They are not one dial. They are two independent dimensions, and mixing them up is a real design error. (An error of the same kind: treating two independent dimensions as one spectrum because their common cases happen to go together.) When you separate the dimensions, the empty cells of the resulting table turn out to be the most informative part.

There is also a third instrument that is missing from the usual list, and it is the one most worth knowing.

The three currencies of freshness

The gap between a cache and the truth can be closed in exactly three currencies. There is no fourth.

Currency	Mechanism	Cost scales with	Who pays
Coordination	write-through, invalidation broadcast, a coherence protocol	write rate × number of caches	the writer
Staleness	TTL, asynchronous invalidation, serve-stale	nothing: it is free	the reader, silently
Verification	leases, ETag or version revalidation, conditional GET	read rate, but at the price of a round trip, not a payload	the reader, cheaply

Here is how to read the table with a little background from transaction processing. A database that lets many users change data at once needs concurrency control, a rule for who may touch what. There are two classic styles. Pessimistic control takes locks first, so conflicts cannot happen: that is coordination. Optimistic control lets everyone proceed and checks for conflicts at the end: that is verification. The third option, proceeding and never checking, is unsound in a transaction system, because it loses updates. But a cache is allowed to be wrong. So:

Verification is the instrument practitioners use too little, because it changes the unit of the cost. A revalidation that answers "unchanged" costs one round trip and carries no payload. Where an entry is large compared with a round trip, verification gives near-coherence at a small part of the price of coordination. Three familiar mechanisms are all this one move:

HTTP's ETag header: the client sends "I have version abc123", and the server replies 304 Not Modified with no body if it is still current (a conditional GET).
AFS-style callbacks: a distributed file system in which the server promises to tell the client when a cached file changes.
A database buffer pool's LSN check: each page carries a log sequence number (the position in the write-ahead log of the last change to it), and a reader compares it with the expected one.