MVCC: Version Chains

Locks make transactions wait for each other. Multi-version concurrency control avoids most of that waiting with one idea: never overwrite anything. When a transaction changes a row, it adds a new version next to the old one. Readers keep reading the version that was current for them; writers pile up new ones. This is how PostgreSQL, Oracle and InnoDB let readers and writers run side by side.

A key is a chain of versions

Instead of one value per key, the store keeps a chain, oldest first. Each version records who wrote it, its value (or a delete marker, since a delete is also just a new version), and a commit timestamp:

x:  1:A  ->  2:B  ->  pending(t3):C

1:A was committed with timestamp 1, 2:B with timestamp 2, and pending(t3):C is a version written by transaction t3 which has not committed, so it has no timestamp yet.

Snapshots are just a number

A global commit clock counts commits that changed something. When a transaction begins it records the clock value as its snapshot. That single number is its whole view of the database; nothing is copied.

A version is visible to transaction T when:

• it is committed and its timestamp is at most T's snapshot; or
• it is uncommitted and T itself wrote it (you see your own writes).

A read walks the chain newest to oldest and returns the first visible version. Other transactions' uncommitted versions are skipped, and so are versions committed after T began. A delete marker that turns out to be the visible version means "the key does not exist".

x:  1:A -> 2:B -> 3:C              clock = 3
reader snapshot = 1  sees A        reader snapshot = 2  sees B        a new transaction sees C

All three read the same chain at the same time, and none waits for anyone.

Writing and conflicts

A write appends a new uncommitted version (a second write by the same transaction just replaces its own pending version, so each transaction has at most one pending version per key). Two rules stop transactions from clobbering each other:

1. Write-write conflict. If the newest version of the key is pending and belongs to another transaction, the write is refused: ERR write conflict on <key>: held by <txid>. (A real database would make the second writer wait; here it fails so you can see the rule.)
2. First-updater-wins. If the newest committed version has a timestamp greater than the writer's snapshot, somebody committed a change the writer cannot see, and overwriting it blindly would lose that update: ERR could not serialize access: <key>.

A refused write leaves the transaction open; it can still read, write other keys, or abort.

Commit and abort

COMMIT is cheap: if the transaction wrote anything, the clock advances by one and every pending version it created is stamped with the new value, all in one step, so its writes appear to others together. A transaction that wrote nothing needs no timestamp and leaves the clock alone (COMMIT <txid> read-only). ABORT just deletes the transaction's pending versions.

Garbage: why VACUUM exists

Chains only grow, and old versions pile up. A version is garbage when no current or future transaction can ever need it. The horizon is the oldest snapshot among the active transactions (or the clock if none are active). For each key, take the newest committed version at or below the horizon: that is the version the oldest reader sees, and everything older than it is dead. If that version is itself a delete marker, it is dead too (nothing older remains for it to hide), which can empty the chain and remove the key completely. Pending versions are never touched. One long-running transaction therefore holds back cleanup for everyone, which is a real operational problem in PostgreSQL.

Commands

BEGIN, READ, WRITE, DELETE, COMMIT, ABORT take a transaction id; DUMP <key> shows the raw chain (EMPTY if none) and VACUUM prints VACUUM removed=<n>.

Common mistakes

• Comparing against the current clock instead of the transaction's snapshot.
• Walking oldest to newest, and returning a stale version.
• Forgetting that a delete marker hides older versions from the reader that sees it.
• Vacuuming the version the oldest reader still sees.

Your exercise

The starter parses and prints. You implement read_version, write_version, commit, abort and vacuum. The mistake to avoid: treating another transaction's pending version as visible.