Invalidation by Deletion and by Versioned Key

A cache entry is a copy with no owner. Nothing in the cache knows that a row in the source changed, so the change must be communicated, and every mechanism for communicating it is either a message that can be lost or a naming scheme that cannot. The two families that matter are deletion-based invalidation, where a writer removes the affected key, and versioned keys, where a writer changes the address at which the value is found.

Deletion is the usual first choice because it is cheap and because it fails safe: a deleted key becomes a miss, and a miss reads the source. Versioning is used where the race below is unacceptable, at the cost of an indirection and permanent key churn.

Delete after write, and the race that follows

The common sequence is: commit the write to the source, then delete the cache entry. The ordering is deliberate — deleting before the commit lets a reader repopulate from the pre-commit state — but the same interleaving defeats it from the other side:

1. Reader misses on key K and loads the current value v1 from the source.
2. Writer commits v2 to the source and deletes K from the cache.
3. Reader, still holding v1, writes it to K.
4. The cache now holds v1, which is arbitrarily old, until the TTL expires.

This is not a narrow window in the sense that matters. Step 1 and step 3 are separated by a source round trip plus serialization of the value, which on a large object can be milliseconds; step 2 has to land in that gap. Under load, a hot key has many readers in that gap continuously, so a write to a hot key will hit the race with meaningful probability.

Deleting rather than updating is still preferable in the common case, because the update variant has a worse race in the opposite direction: two writers, W1 with v1 and W2 with v2, commit in that order but reach the cache in the opposite order, and the cache permanently holds v1. Deletion cannot lose an update this way, since both deletes are idempotent and the eventual repopulation reads whatever the source holds at that time.

The remedies and what each assumes

A delayed second delete closes the common window: delete, wait longer than the maximum time a reader could be holding a stale load, delete again. It works when the delay bound is real, which requires knowing the tail of the read path’s source latency and serialization time. It fails when a reader is stalled by a garbage collection pause or a scheduler delay longer than the delay chosen, and it doubles the invalidation traffic for every write. It also assumes the second delete lands after the reader’s populate, which is probable and not guaranteed.

A lease closes it with information rather than timing. The reader that misses receives a token along with the miss, and is permitted to populate only while the token is valid; a writer that invalidates the key revokes outstanding tokens. The memcache deployment described in “Scaling Memcache at Facebook” uses exactly this mechanism, with a 64-bit token bound to the specific key the client requested. The cost is state: the cache must track outstanding tokens per key, which makes the miss path a read-modify-write rather than a read.

A version counter stored beside the value, with a populate that only overwrites when its version is newer, converts the cache set into a conditional write. That requires the cache to support one — a Lua script that compares the stored version, or a compare-and-set token that fails if the entry changed since it was read — and it requires the reader’s loaded value to carry the version it was read at. A source schema can carry such a column, or the version can be derived from one it already has, and the comparison itself is a few instructions.

Versioned keys: invalidation as a change of address

The alternative removes the race structurally. Instead of caching under user:42, the system caches the value under a derived key, user:42:v7, where v7 is a version that changes whenever the user row changes. A writer that changes the row bumps the version; readers that compute the version before loading will populate and read only the new address. Old entries become unreachable garbage and age out.

The property this buys is strong: a populating reader can only write under a version it read from the source, and if the source has moved on, the written entry is at an address nobody will consult again. The interleaving that loses an update in deletion-based invalidation cannot occur, because there is no shared address to lose it at.

The cost is an extra lookup. The reader needs the current version before it can construct the key, so either the version is cheap to obtain — stored in a small, long-TTL entry, or derivable from a value the request already has — or the scheme has added a round trip to every read. When the version lives in the cache as user:42:version, the cache now has a key that must itself be invalidated, which moves the problem rather than solving it. Making the version derivable from something the client already knows, such as a monotonically increasing sequence carried in an authorization token or a session record, avoids the extra hop but constrains how versions can be assigned.

The second cost is key churn. Every write creates a new key, and the old ones stay until evicted. For a hot, frequently updated row, the cache accumulates a trail of dead versions proportional to the write rate times the eviction horizon. That is fine in a cache with an LRU policy and a memory ceiling — dead entries are simply the coldest — but it breaks hit-ratio accounting unless versions are excluded, and it defeats any scheme that relies on counting distinct keys.

The third cost is that the old version remains servable to anyone who already knows the address. A request that read the version at the start of a long operation will keep reading the old value for the duration. That is usually desirable — the request sees a consistent snapshot — but it means the versioned key does not by itself bound staleness for a request that caches the version too aggressively.

Where the version has to come from

A version does not have to be a counter. A content hash of the value works if the writer can compute it cheaply and the reader can too; the address becomes document:sha256-prefix. A timestamp of last modification works when the source guarantees monotonicity per row. A per-entity epoch maintained in a small table works if that table is itself read on the same path.

Each choice has a failure mode. A hash requires the writer to hash the full value at write time and the reader to hash it again to know the address, which doubles the CPU for large values — unless the source stores the hash, which is the practical form. A timestamp depends on clock monotonicity, and two writes in the same clock tick produce the same address. An epoch table is a single hot row unless sharded, and it reintroduces the invalidation problem for its own value.

The scheme also needs a rule for deletion. A deleted entity has no version, so the reader needs a tombstone version or must cache the absence under the last known version. Caching absence is covered in caching absence: negative entries and bloom filters.

Choosing between them

Deletion-based invalidation is appropriate when the write rate is low relative to reads, when a short staleness window is tolerable, and when the cache protocol offers no conditional write. It is the only option when the cache is a shared remote store that many services write to with no shared notion of version.

Versioning is appropriate when staleness of a specific entity is unacceptable and the version is cheap to obtain — typically because the source already exposes one, or because the entity is small and its version can be carried in a token. It is also the natural fit for immutable content: if the value never changes, its content hash is its identity, and invalidation disappears entirely because there is nothing to invalidate.

The hybrid used by many systems is deletion plus a version guard in the value: the entry stores the version it was loaded at, and a populate compares against any version already present. That requires a conditional set and gives most of the guarantee without the key churn. Whatever the mechanism, the TTL remains as the backstop, and its length is the true bound on how wrong the cache can be when the mechanism fails — see TTL expiry and the two ways an entry dies.