MVCC (Multi-Version Concurrency Control)

Locks give isolation by making everyone wait. MVCC gives it by never overwriting anything: each commit creates a new version of the key, tagged with a commit timestamp, and each transaction reads a frozen snapshot of the past. Readers never block writers; writers never block readers. Postgres, MySQL InnoDB, etcd, FoundationDB, and Spanner all run on this idea.

Two timestamps per transaction

A single global clock counts commits. Each transaction carries:

• read timestamp (rts) — the clock value at BEGIN. This is the snapshot: the transaction sees, for each key, the newest version with ts <= rts (plus its own buffered writes, which always win).
• write timestamp (wts) — assigned at COMMIT: the clock ticks to the next value and stamps every buffered write.

Version history is append-only:

a: ts=1 1       <- committed first
a: ts=3 99      <- newer version; snapshots with rts >= 3 see this one

A read at rts=1 sees 1; a read at rts=3 sees 99. A version committed at ts=2 is invisible to a snapshot with rts=1: that transaction began before the commit, and its view must not shift mid-flight. That immunity to concurrent commits is snapshot isolation.

First-committer-wins

Two transactions buffer a write to the same key. Whoever commits first, wins; the second must abort, because its writes were based on a snapshot that no longer reflects that key. The check at COMMIT is beautifully small: for each key in the write buffer, if a committed version exists with ts > rts, someone got there first — abort. Note the strict >: a version at exactly ts == rts was already in your snapshot, and overwriting what you could see is fine.

Two consequences this course's grader probes:

• Read-only commits still tick the clock. Every successful COMMIT takes the next timestamp, buffered writes or not.
• Aborts leave nothing behind. No version is written; the aborted transaction simply reports which key doomed it.

Snapshot isolation is not the top of the ladder — it still admits write skew, where two transactions each read what the other writes and both commit — but it eliminates dirty and non-repeatable reads without a single lock. The garbage it accumulates (old versions) is what Postgres VACUUM sweeps; here we keep every version so STATE can print the full history.

Your exercise

Implement BEGIN, the <id> PUT/GET/COMMIT/ROLLBACK commands, and STATE. The grader-caught mistakes, from the real tests: (1) visibility is ts <= rts — tx 3 with rts=1 doing GET a must print 1 (the ts=1 version is inside its snapshot) while GET b prints <nil> (b committed at ts=2, after the snapshot); a strict < hides the first, a missing check leaks the second; (2) conflict is ts > rts, strictly — tx 3 (rts=1) overwriting the a@ts=1 it just read commits fine as OK wts=3, but tx 5 (rts=3) committing after tx 4 took ts=4 prints ABORT key=a; a >= check falsely aborts tx 3; (3) versions append, never replace — after two commits of a, STATE prints both a: ts=1 1 and a: ts=2 2, sorted by key then ts, and a rolled-back transaction leaves STATE printing nothing at all; (4) exact tokens — BEGIN prints TX 3 rts=1, success prints OK wts=3, rollback prints ROLLBACK.