Commentary: mvcc-store

“Readers don't block writers” is true. Readers block the collector — and one idle reader that touched a single key pins every version of a key it never read. A study guide for mvcc_store.py.

cd mvcc-store
python3 demo.py            # the aha (§6)
python3 test_mvcc_store.py # pins every number this page claims

1. Orientation

This toy is a key-value store in which nothing is ever overwritten. Writing b a second time does not replace the old value; it pushes a new version onto a chain and stamps the old one with the commit id at which it died. A transaction takes a snapshot — one integer — when it begins, and every read it performs is decided by two comparisons against that integer. There are no locks anywhere in the file.

That buys the property MVCC is famous for, and PostgreSQL states it in one sentence: "reading never blocks writing and writing never blocks reading." The demo confirms it. Fifty writers run to completion while a reader sits with an open snapshot, and not one of them waits.

The toy exists for what happens next. Those fifty writers left 51 versions of b behind, and 49 of them are visible to nobody at all — not to the reader, not to anyone who could start now. A real garbage collector will not touch them. Readers don't block writers; they block the collector, and they do it through a key they never read.

By the end you should be able to:

• compute, by hand, which version of a key a given transaction sees, from the version's (xmin, xmax) stamps and the transaction's snapshot integer;
• explain why a database's dead-tuple reclamation rule is deliberately cruder than its visibility rule, and what that crudeness costs;
• predict what one forgotten BEGIN in a psql window does to bloat on a table that session never opened;
• say what "time" means inside a transactional store, and why it is a counter rather than a clock.

2. The problem this mechanism exists to solve

Two transactions touch the same row at the same time. One is a 40-minute analytics scan; the other is a checkout that must commit in 3 milliseconds. Both must see a consistent database — not a half-applied transfer, not a row that changes underneath a running query.

The obvious mechanism is locking: a reader takes a shared lock, a writer takes an exclusive one, and the two are made to take turns. It is correct, and it is what pre-MVCC systems did. It has one fatal operational property: the 40-minute scan stops the 3-millisecond checkout for 40 minutes. Read and write throughput are coupled, so one analyst can take down the transactional workload.

Multi-version concurrency control breaks the coupling by refusing to destroy information. A writer never modifies the value a reader is reading, because it never modifies anything — it appends a new version and marks the old one as superseded from a certain moment on. The reader keeps reading the old version, legitimately, because "the database as of moment S" is a well-defined object as long as the bytes are still there.

That last clause is where the competing goals live, and it is the whole reason more than one design is defensible:

• Reads want history kept. A reader's snapshot is only honourable while the versions it names still exist.
• Storage wants history destroyed. Every update is a new version. A row updated a thousand times is a thousand rows on disk until something reclaims them.
• The collector wants to be cheap. Deciding "can this version go?" happens once per version per sweep, over billions of versions. Whatever test it uses must be nearly free.

3. Background you need

None of this is deep, but everything below leans on it.

The two that carry the result are the third and the fourth. The horizon is the whole aha: it is a single number, it is set by the oldest live snapshot, and it does not care which keys that transaction touched. The half-open interval is what makes the arithmetic work at all — get one of the two comparisons wrong and, as §5.1 shows by running it, either nothing is ever visible to anyone or two versions are visible at once.

4. The mental model

Before any code. Two pictures: what a key looks like, and what "visible" means.

A key is a chain, newest version first, and each version knows the commit id that created it and the commit id that killed it:

"Visible" is not a flag stored anywhere. It is an arithmetic test against the reader's snapshot, and it is easiest to see as intervals on a number line — where the numbers are commit ids, not seconds:

Three things fall out of this picture, and they are the whole toy:

• Nothing overlaps and nothing is missing. xmax of one version is exactly xmin of the next, and the interval is closed at the bottom and open at the top, so every snapshot lands inside exactly one bar per key.
• The bars between the two arrows are visible to nobody. B1 through B49 are dead to R (they began after snapshot 1) and dead to everyone else (they ended before snapshot 51). That is 49 versions of pure garbage, sitting in memory, at a moment when the store holds 52 versions in total.
• Deciding that took 49 × 2 comparisons. Deciding it cheaply means picking one threshold and comparing every version against it — and the only threshold that is always safe is the leftmost arrow, R's snapshot of 1. Under that threshold, nothing is collectable at all.

5. Reading the source

The file is 150 lines. Read it in this order: the two free functions carry all of the semantics, and the class is bookkeeping around them.

5.1 visible — the entire read path, in one line

def visible(version, snap):
    """The entire visibility rule. One line, two comparisons, no locks."""
    return version.xmin <= snap and (version.xmax is None or version.xmax > snap)

This is the line that replaces a lock manager. It reads no shared state, it takes no latch, it cannot block, and two transactions evaluating it simultaneously cannot interfere — because a Version's fields are only written once, at the commit that created it and the commit that superseded it.

The two comparators are not symmetric, and they are not interchangeable. I ran both variants against the demo scenario rather than reasoning about them.

xmin <= snap, not <. Your snapshot is "the newest commit id that exists", so the transaction that committed at your snapshot is one you must see. Tighten it and the store goes completely blind:

Not "sees an older value" — sees nothing at all, and pays a full 51-hop scan to discover it. The reason is worth holding onto: versions tile the number line with no gaps, so xmax of one equals xmin of the next. Require xmin < S < xmax and you are asking for an integer strictly inside an interval of width 1. There isn't one. Every read on every key returns None.

xmax > snap, not >=. A version dies at the commit that replaced it, so a snapshot equal to that commit id must not see it. Loosen it and one extra version stays visible in every chain:

The read results look unharmed — but they are only unharmed by luck. Both B49 [50,51) and B50 [51,∞) are now visible to snapshot 51, and this toy scans the chain newest-first, so it happens to hit B50 first and return the right answer. Reverse the chain order and the same one-character change starts returning stale data:

That is the most useful thing the counterfactuals turned up: a genuine correctness bug in visible is invisible in this toy because of an unrelated choice about list order. The number that does detect it is the GC count — 48 instead of 49 — because the collector asks the question directly instead of stopping at the first True.

5.2 retain — where the two collectors disagree

def retain(version, rule, horizon, snaps):
    """Should a sweep keep this version? The two collectors differ only here."""
    if rule == HORIZON:
        # Half of `visible`: the death test only. A version whose xmin is still
        # in the future has to be kept regardless -- some later snapshot will
        # want it -- so xmin is never consulted. One comparison per version,
        # however many transactions are running.
        return version.xmax is None or version.xmax > horizon
    # The exact test: keep it only if somebody can still see it. Costs one
    # `visible` call per live snapshot per version.
    return any(visible(version, snap) for snap in snaps)

Two rules, five lines, and the entire toy is the gap between them.

The horizon rule is literally half of visible. It checks the death side (xmax) and never looks at xmin. That asymmetry looks like an oversight and is the opposite: it is the one thing keeping the rule correct. A version whose xmin is in the future is invisible to every currently live snapshot — but a transaction beginning one millisecond from now will want it. Death before the horizon is permanent; birth after the horizon is not.

Restore the symmetry and the database eats itself. I replaced the branch with the full visible(version, horizon):

It looks like a triumph — the sweep that used to free nothing now frees 50 — and it has silently deleted B50, the current value of b. The only surviving version of the key is one that died 49 commits ago. Every new reader gets None. This is the single most load-bearing line in the file, and its correctness lives entirely in an omission.

The precise rule pays for exactness by the snapshot. any(visible(...)) is a loop over the live snapshot set — the cost of the sweep now scales with your concurrency, not just your data. §7.2 has the measured numbers.

Note also that snaps includes the snapshot a transaction beginning right now would receive, not only the ones currently held. Drop that and the precise rule commits exactly the same murder as C4, from the other direction:

"Visible to nobody" has to mean nobody who could ever exist, not nobody who happens to be running.

5.3 Version — a value and the interval it was true for

class Version:
    """One immutable value, alive for the commit-id interval [xmin, xmax)."""

    __slots__ = ("value", "xmin", "xmax")

__slots__ is here to make a point about cost, not to be clever. Version chains are the thing MVCC produces in bulk: one per update, per row, retained until a collector proves nobody wants them. Whatever a version costs, you pay it a very large number of times, which is why real systems put the two stamps in a fixed-size tuple header rather than anywhere flexible. Fifty updates to one row in this toy produced 51 live objects for one logical key.

5.4 begin and commit — time is a counter

    def begin(self):
        txn = Txn(self.next_xid, self.clock)
        self.next_xid += 1
        self.live[txn.xid] = txn
        return txn

    def commit(self, txn):
        """Publish the buffered writes under one fresh commit id."""
        del self.live[txn.xid]
        if not txn.writes:
            return self.clock  # read-only: no commit id is burned
        self.clock += 1
        for key, value in txn.writes.items():
            chain = self.chains.setdefault(key, [])
            if chain and chain[0].xmax is None:
                chain[0].xmax = self.clock  # the previous head dies here
            chain.insert(0, Version(value, self.clock))
        return self.clock

There is no clock in this file and no RNG. self.clock is a plain integer that only commit may advance, and a snapshot is a copy of it. That is not a determinism hack retrofitted for the demo — it is what MVCC actually is. A transactional store cannot order events by wall time (clocks skew, NTP steps backwards, two machines disagree), so it invents a total order by counting commits and defines "before" against that counter. Determinism is a free side effect: python3 demo.py is byte-identical on every run because the toy contains nothing that could vary, and test_demo_output_is_byte_identical_across_runs (test_mvcc_store.py lines 136–148) captures stdout twice and asserts the strings match.

Two decisions inside commit are worth stopping on.

chain[0].xmax = self.clock is what makes garbage garbage. Delete that one line and reads keep working perfectly — and both collectors stop collecting:

Zero, zero, zero, forever, on a store that reads correctly. The reason reads survive is again the chain order: scanning newest-first and stopping at the first version with xmin <= snap finds the right answer without ever consulting xmax. Under the opposite order it breaks immediately —

— so in this toy xmax is not a read-path field at all. It exists to tell the collector when the version stopped mattering. That reframes the stamp: it is not bookkeeping about the past, it is a message to the garbage collector, written 51 commits before anyone reads it.

A read-only transaction burns no commit id. if not txn.writes: return self.clock. This mirrors PostgreSQL, where a real transaction ID is assigned only "if a permanent ID is assigned to the transaction (which normally happens only if the transaction changes the state of the database)" — otherwise a session runs on a virtual transaction ID. In this toy it is also what keeps the headline arithmetic clean: R commits at the end of the demo without moving the clock, so the horizon lands on 51 and not 52.

It is, however, not load-bearing for the result. I made read-only transactions burn a commit id anyway:

Same 0, same 49, same 50. Worth knowing before writing a paragraph claiming otherwise: this line buys tidiness and real-world fidelity, not behaviour.

5.5 probe — the read path, and what a long chain costs

    def probe(self, txn, key):
        """read(), but also reporting how many versions had to be skipped."""
        if key in txn.writes:
            return txn.writes[key], 0  # a transaction sees its own writes
        chain = self.chains.get(key, ())
        for hops, version in enumerate(chain, start=1):
            if visible(version, txn.snapshot):
                return version.value, hops
        return None, len(chain)

A linear scan that stops at the first visible version. hops is not part of the mechanism; it is instrumentation, and it exists because chain length is the second bill MVCC sends you after memory. Reading a key means walking versions until one of them matches your snapshot.

The txn.writes check is read-your-own-writes. A transaction's uncommitted values live only in its own buffer, so without this line a transaction cannot see what it just wrote:

5.6 horizon, snapshots, vacuum — computing the thresholds once

    def horizon(self):
        """The oldest snapshot anyone still holds; the clock if nobody is running."""
        return min((t.snapshot for t in self.live.values()), default=self.clock)

    def snapshots(self):
        """Every snapshot that can still be used: the living ones, plus the one
        a transaction beginning right now would get."""
        return sorted({t.snapshot for t in self.live.values()} | {self.clock})

min, not max, and not an average. The horizon must be safe for the worst case — the oldest snapshot still out there — because that transaction is entitled to the versions it named. Swap it for max and the collector starts deleting versions out from under live readers:

One min() over the set of running transactions is the entire safety argument, and it is also the entire performance problem: the single oldest transaction in the system sets the threshold for everything.

    def vacuum(self, rule, dry_run=False):
        """Sweep every chain under `rule`; return how many versions it frees."""
        # Both thresholds are read once, before the sweep. That is what makes
        # the horizon rule one comparison per version rather than one scan of
        # the live transactions per version.
        horizon, snaps = self.horizon(), self.snapshots()
        reclaimed = 0
        for key, chain in self.chains.items():
            keep = [v for v in chain if retain(v, rule, horizon, snaps)]
            reclaimed += len(chain) - len(keep)
            if not dry_run:
                self.chains[key] = keep
        return reclaimed

Hoisting self.horizon() out of the loop is the only reason the "one comparison per version" claim is true — an earlier draft of this toy called it from inside retain and quietly made the cheap rule O(live × versions), which is the exact cost it exists to avoid. dry_run is there so the demo can ask "what would the other rule free, right now?" without disturbing the state the next sweep is measured against.

6. The demo, and what it proves

demo.py runs one scenario. T1 seeds a and b. A reader R begins, reads only a, and then does nothing at all for the rest of the program. Fifty writers each update b and commit.

    # --- 50 writers each update `b` and commit. ---------------------------
    for i in range(1, WRITERS + 1):
        w = store.begin()
        store.write(w, "b", f"B{i}")
        store.commit(w)

python3 demo.py

The first half is the famous half of MVCC, and it works: the writers never waited for R, R never waited for the writers, R still reads B0 while everyone else reads B50, and an uncommitted value is visible to its own transaction and to nobody else. Now the three numbers that matter.

6.1 Deriving the 0

R is live with snapshot = 1, so horizon() = min(1) = 1. The rule is keep if xmax is None or xmax > 1. Walk the store:

Every version passes. The smallest xmax anywhere in the store is 2, and the threshold is 1, so nothing in the store is dead-before-the-horizon and the sweep frees 0 of 52. One transaction, holding one snapshot, having read one key, is the sole reason.

6.2 Deriving the 49

At the same instant, the live snapshot set is [1, 51] — R's, plus the one a transaction starting now would take. A version is garbage iff visible is false for both:

• A0 = [1, ∞): visible at 1. Kept.
• B0 = [1, 2): 1 <= 1 and 2 > 1. Visible at 1 — this is the version R is actually reading. Kept.
• Bk = [k+1, k+2) for k = 1…49: at snapshot 1, xmin = k+1 <= 1 is false. At snapshot 51, xmax = k+2 > 51 is false. Invisible to both. Freed. That is exactly 49 versions.
• B50 = [51, ∞): visible at 51. Kept.

6.3 Deriving the 50, and what actually changed

R commits. It wrote nothing, so the clock does not move (§5.4) and no data changes. live is now empty, so horizon() falls through to its default and returns self.clock = 51. The identical sweep now runs keep if xmax is None or xmax > 51:

• A0: xmax is None → kept.
• B0 … B49: xmax runs 2 … 51. None of them exceeds 51. All 50 freed.
• B50: xmax is None → kept.

50 versions vanish because one idle session ended. That is VACUUM unsticking the moment somebody closes a psql window, and PostgreSQL's own documentation describes precisely this failure mode in the entry for idle_in_transaction_session_timeout: "Even when no significant locks are held, an open transaction prevents vacuuming away recently-dead tuples that may be visible only to this transaction; so remaining idle for a long time can contribute to table bloat."

Note it frees 50, one more than the precise rule's 49: B0 goes too, now that the reader who was pinning it has gone. Precision was never the horizon rule's problem. Timing was.

6.4 The other bill: chain hops

R walks all 51 versions of b to reach the one it can see; a fresh reader finds B50 at the head immediately. This toy prepends new versions, so the straggler pays. That is a real design axis — Wu et al. call the two variants N2O and O2N — and PostgreSQL picks the other one: a HOT chain's "t_ctid field links forward to the newer version", so index scans walk from the oldest tuple forward. Under that ordering the bill lands on the current readers instead, and only the collector can shorten the walk:

Either way the walk is O(chain length) and only a sweep can shorten it — which is the second reason a blocked collector hurts, and the one Wu et al. put first: "This also increases the execution time of queries because the DBMS spends more time traversing long version chains."

6.5 The tests

python3 test_mvcc_store.py

test_idle_reader_pins_a_key_it_never_read (test_mvcc_store.py lines 37–68) asserts the 52, the 0, the 49 and the 50 in sequence, so this page cannot rot quietly. test_horizon_rule_ignores_xmin_on_purpose (test_mvcc_store.py lines 122–133) pins the asymmetry from §5.2: it asserts that B50 is invisible to R and retained by both rules anyway.

6.6 The boundary condition — where the effect vanishes

Two boundaries, and the effect disappears at both ends.

50 and 50. If every transaction in your system is short, the cheap rule is not an approximation of the exact rule — it is the exact rule, and none of this matters. That is why the horizon design is the right one: it is exact on the workload databases are tuned for and degrades only under the workload that was going to hurt anyway.

Too much concurrency, no gap either. Precision also stops buying anything once enough snapshots are held, because the union of live snapshots starts covering every interval. Counting the actual visible() calls each sweep makes, on the same 52 versions:

At 51 live snapshots the precise rule frees exactly as much as the horizon rule — nothing — having done 1327 visible() calls to get there. Its advantage is largest at low concurrency, which is exactly where the total amount of garbage is smallest. The place it would pay is the narrow band where one transaction is old and everything else is young.

(The horizon rule's "0 visible() calls" is literal: it never calls the function. It does one bare xmax > horizon per version — 52 comparisons — and that count does not move no matter how many transactions are running.)

7. Design decisions and roads not taken

7.1 Why ship both collectors?

Because 0-versus-49 is the only way to see that the real rule is an approximation. A toy with only the horizon rule teaches "GC frees nothing while a reader is open," which reads as a limitation of MVCC. A toy with only the precise rule teaches a system nobody builds. Side by side, at the same instant, on the same 52 versions, the number that matters is the difference.

7.2 Why real databases pick the cruder rule

The measured cost, from §6.6: one comparison per version, always, versus up to one visible() call per live snapshot per version. But the counting understates it, because a real collector runs concurrently with the workload. The horizon is one integer, snapshotted once; the live snapshot set is a shared, contended structure that changes while you sweep, so using it precisely means either holding a lock across the sweep or reasoning about a set that mutates underneath you.

Wu et al. describe exactly this rule and exactly this cost in their survey of in-memory MVCC engines: "the DBMS checks whether a version's end-ts is less than the T_id of all active transactions. The DBMS maintains a centralized data structure to track this information, but this is a scalability bottleneck in a multi-core system." And the consequence, in their words: "The DBMS's performance drops in the presence of long-running transactions. This is because all the versions generated during the lifetime of such a transaction cannot be removed until it completes."

7.3 Why writes buffer until commit

write() puts the value in txn.writes; nothing enters a chain until commit. This makes abort free — txn.writes.clear() and the transaction is gone, with no published version to hunt down — and it makes the uncommitted-visibility demo trivially correct, because an uncommitted value is physically not in the store.

It is also, loudly, not how PostgreSQL works. See §8; this is the biggest lie in the toy.

7.4 Why newest-first chains

Reads mostly want the current version, and prepending puts it at hop 1. It is a legitimate choice — Wu et al. name it as one of the two append-only variants (N2O vs. O2N) — but it is the opposite of PostgreSQL's HOT chains, and §5.1 and §5.4 both showed it masking real bugs in other lines. If you want the version of this toy that best matches Postgres, change chain.insert(0, ...) to chain.append(...) and flip chain[0] to chain[-1] in commit; the GC numbers are unchanged and the hop counts swap.

7.5 What's deliberately absent

• Locking and write-write conflict detection. Two transactions updating the same key here both succeed and the last commit wins, silently. Real snapshot-isolation systems detect this (PostgreSQL's first-updater-wins rule blocks the second writer, then either errors or re-evaluates). Adding it would double the file and change the subject from visibility to conflicts.
• Durability. Everything is in a dict; a crash loses all of it. That is a different mechanism with its own toy — see wal-kv.
• READ COMMITTED. The snapshot is taken once, at begin(). Postgres's default level re-takes it per statement, which changes what "a long transaction" even means for the horizon.
• Index-only scans and visibility maps. The optimisation that lets Postgres skip the heap when a page is known all-visible is downstream of everything here and needs a page layout to be interesting.

8. What's simplified vs. the real thing

Three consequences the toy therefore cannot show you:

1. Visibility is a two-part question — is this xid committed, and is it visible to me? — which is why Postgres needs the commit log (clog) that this toy has no analogue for.
2. A rolled-back transaction leaves real dead tuples on real pages that VACUUM must reclaim, so abort is not free the way abort() here is.
3. An uncommitted transaction's writes consume storage and lengthen version chains for everybody, before it has decided anything.

This toy's abort is a dict.clear(). Postgres's is a promise to a collector.

The rest of the corners cut:

• One commit id per transaction, no statement granularity. Real tuples also carry cmin/cmax command identifiers so a transaction can avoid seeing rows its own later statements created. Every write in a Txn here lands at one instant.
• Single-threaded, one process, no latching. Store has no locks at all. A real implementation needs the version chain and the "who is running" structure to be safe under concurrent mutation, and — per §7.2 — that structure is a known multicore bottleneck.
• vacuum is synchronous, total and instantaneous. It sweeps every chain in one pass with the workload stopped. Real vacuuming is a background process working page by page, interleaved with live traffic, which is why it can fall behind and why a table can bloat faster than it is swept.
• Nothing is ever reclaimed by the read path. Some engines prune opportunistically while scanning, so a read cleans up as it goes. Wu et al. call this cooperative cleaning, and note the failure mode it creates: "if transactions do not traverse a version chain for a particular tuple, then the system will never remove its expired versions. This problem is called 'dusty corners'."
• Commit ids never wrap. self.clock is a Python int and grows forever. PostgreSQL's transaction ids are 32-bit and wrap around, which turns "vacuum eventually" into "vacuum before two billion transactions elapse or the database shuts down to protect itself" — an entire operational discipline that exists only because the counter is finite.
• No keys are ever deleted. A delete would be a version with a tombstone value and an xmax, and the last version of a key could then be reclaimed entirely — which needs the chain-empty case that vacuum here never hits.

9. Check yourself

Answer before expanding. Every answer is derivable from the source, and every one below was verified by running it.

10. Further reading

Every link below was fetched and confirmed live when this was written.

• PostgreSQL: Introduction to MVCC — two paragraphs, and the source of the slogan this toy is arguing with: "reading never blocks writing and writing never blocks reading." Start here, then notice what it does not promise about the collector.
• PostgreSQL: idle_in_transaction_session_timeout — the manual admitting the failure mode in one sentence, and the setting that exists solely to stop it. The most operationally useful link on this page.
• PostgreSQL: System Columns — xmin, xmax, cmin, cmax as things you can actually SELECT. The note that xmax may be nonzero on a visible row is the whole of §8's first callout in one line.
• Wu, Arulraj, Lin, Xian & Pavlo: An Empirical Evaluation of In-Memory Multi-Version Concurrency Control (PVLDB 10(7), 2017) — the survey that treats garbage collection as one of MVCC's four load-bearing design decisions rather than an afterthought. §4 names the N2O/O2N chain-ordering split from §7.4; §5 has the horizon rule and its scalability bottleneck, "dusty corners", and the long-running-transaction result. If you read one thing after this page, read §5.
• PostgreSQL source: README.HOT — heap-only tuples, forward t_ctid chains, redirecting line pointers, and page-level pruning. This is the real answer to §6.4's hop count and it is more interesting than the toy's.
• PostgreSQL source: procarray.c (doxygen) — ComputeXidHorizons(), GlobalVisTestIsRemovableXid() and the four GlobalVisHorizonKind values. Where §7.2's fact-check landed; read the function list first, it is a good map.
• PostgreSQL: Transaction Isolation — what this toy implements is REPEATABLE READ. The section on READ COMMITTED re-taking a snapshot per statement explains why "a long transaction" means something different at each level.
• The Internals of PostgreSQL, Ch. 5: Concurrency Control — Hironobu Suzuki's book-length walk through tuple headers, the commit log, and visibility checking, with page diagrams. §5.3 shows a tuple being placed into a page with t_xmin set to an in-progress txid, which is the fact §8 is built on.
• Jepsen: Snapshot Isolation — the formal model, and where it sits relative to serializability. Useful for seeing what snapshot isolation still permits (write skew) that this toy makes no attempt to prevent.