MVCC — Multi-Version Concurrency Control

MVCC — Multi-Version Concurrency Control

You've built snapshot isolation with whole-table copies and lock-based mutual exclusion. Real production databases (Postgres, MySQL/InnoDB, Oracle) implement snapshot isolation far more cheaply using MVCC: instead of copying data or blocking readers against writers, every row keeps a chain of versions, each tagged with when it was created (and, implicitly, when it was superseded). This lesson has you build that version-chain store directly.

The version chain

Instead of one value per key, you keep a list of versions:

key "x": [ {value: 1, txid: T1, committed: True,  commit_ts: 1},
           {value: 2, txid: T3, committed: True,  commit_ts: 4},
           {value: 3, txid: T7, committed: False, commit_ts: None} ]

Reads never overwrite in place — a WRITE just appends a new uncommitted version tagged with the writer's transaction id. A version only becomes visible to other transactions once its owner commits and it receives a commit_ts from the global commit clock.

Snapshot timestamps

The key insight that makes this whole scheme work: each transaction, at BEGIN, captures a snapshot_ts equal to the current commit clock (0 if nothing has committed yet). That single number is its snapshot — no copying required. From then on, a READ for that transaction asks: "of all versions of this key, which is the newest one that was either (a) written by me, uncommitted, or (b) committed with commit_ts <= my snapshot_ts?"

Walk the chain newest to oldest and return the first entry that satisfies visible. This naturally implements "your own writes shadow everyone else's, and everyone else only sees a fixed point-in-time snapshot" — exactly what you simulated with table copies earlier, but now at row granularity and without ever blocking a reader.

COMMIT and the commit clock

COMMIT is where a transaction's writes become real to others:

1. Bump the global commit clock by 1.
2. Stamp every uncommitted version this transaction created with committed=True, commit_ts=<new clock value>.
3. Output the new commit_ts.

Because the clock only advances on commit, and each transaction's snapshot was fixed at BEGIN time, a transaction can never see writes from another transaction that committed after it began — even if that other transaction commits while the first is still running. That's the whole point of snapshot isolation: no read ever blocks, and no read ever sees a half-finished or "too new" write.

ABORT

An aborted transaction's uncommitted versions must simply disappear from the chains — filter them out of every key's version list. Nothing needs a commit_ts because they never existed as far as anyone else is concerned.

DUMP for debugging

DUMP <key> prints the chain oldest→newest so you (and the tests) can see exactly what's stored: committed entries as commit_ts:value, uncommitted ones as T<txid>:value. This is a diagnostic window into the raw version chain, similar in spirit to the .count debug command from the snapshot-isolation lesson — it shows ground truth, not any one transaction's filtered view.

Edge cases to watch

• A key with no writes at all → DUMP reports EMPTY, READ returns NULL.
• Multiple writes to the same key within one uncommitted transaction — only the most recent one should be visible to that transaction's own reads.
• READ/WRITE/COMMIT/ABORT against an unknown or already-finished transaction id — treat as invalid input rather than crashing.
• Garbage collection of old versions is a real MVCC concern (Postgres calls this "vacuum") but is out of scope here — chains only grow, which is fine for this exercise.

This is the real algorithm behind "readers never block writers, writers never block readers" — the property that makes MVCC databases so much more concurrent than pure lock-based ones.