Versioned keys are MVCC, and the bill goes somewhere new

Who pays for old versions in a versioned cache, and which session guarantees come for free?

MVCC (multi-version concurrency control) is how many databases let readers and writers work at the same time: each change creates a new version of a row, old versions stay until nobody needs them, and a reader sees a consistent snapshot. A versioned cache is the same thing. The mapping is exact, not just an analogy:

This is one more appearance of the pattern "immutable storage + an indirection layer + a garbage collector", now inside a cache. It has the same failure mode: the collector falls behind exactly when most garbage is produced. High churn produces dead versions fastest, and high churn is exactly when the hit rate matters most.

But the question who pays for old versions? gets a new answer here. PostgreSQL bills the writer: old row versions stay in the table and cause bloat. Oracle bills the reader: if a reader needs a version that has been purged, it fails with the error ORA-01555 ("snapshot too old"). A versioned cache bills neither. Dead versions simply use capacity, so the effective capacity falls from C to C/V, where V is the average number of stored versions per key. By The second copy's arithmetic (h ≈ ln C / ln N), the hit rate falls by

That cost is spread over the whole population of readers as a slightly worse experience. It is the clearest example of a cost that is relocated onto everybody, diffusely (costs are conserved and only move). It is also the hardest kind of cost to attribute, so it is the kind most likely to last for years. Nobody files a ticket about five points of hit rate they never knew they had.

Session guarantees come for free

Versioned keys also give you two session guarantees at no extra cost:

• Read-your-writes: after you write, your own reads see your write. If the client keeps the version token from its last write and puts it in the key, then a cache that does not have that version simply misses and goes to the store.
• Monotonic reads: you never see data go backwards in time. The client refuses to accept a version lower than the highest it has already seen.

Both use only client-side state, which is why they are cheap. They are also the only sound way to get session guarantees over an incoherent cache. Sticky routing (always sending one user to the same cache node) is the weaker substitute. It breaks at the first rebalance, and Making it fit shows that rebalances are routine, not exceptional.

Compression: Versioned keys are MVCC with eviction as the vacuum. The retention cost is shared by all readers as ln V / ln N points of hit rate. The version token in the client's hand buys read-your-writes.