Multi-Version Concurrency Control (MVCC)

Topic Overview

Multiple Versions Per Key

Multi-version concurrency control stores several values for one key tagged with sequence or timestamp. Readers observe a snapshot without blocking writers; writers append new versions. PostgreSQL heap tuples and RocksDB with column families use variants of this idea.

Version Chain Sketch

Map key to sorted list of (seq, value) pairs. Read picks latest version with seq <= read_snapshot.

cCopy
Loading…

• Garbage-collect versions older than oldest active snapshot
• MVCC pairs naturally with LSM append-only writes
• Conflicts detected at commit if snapshot rules violated
• Track min_active_snapshot for retention policy

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement simplified MVCC get/put with snapshot reads. This exercise requires a reader at snapshot S not to see writes committed after S.

Your Task

Multi-version concurrency control keeps every committed version of a value, so a reader sees a consistent snapshot without blocking writers. Build an MVCC key-value store.

• Each key has a chain of versions, newest first. A version is a value and its commit_ts.
• Write adds a version at the head. Its commit_ts must be later than the head's; otherwise the write is rejected.
• Read at ts returns the newest version with commit_ts <= ts. A reader never sees a write that committed after its snapshot. That is what prevents dirty and non-repeatable reads: a transaction that started at ts 3 keeps seeing the same value even after someone commits at ts 4.
• Garbage collection with the oldest active snapshot ts removes, for each key, every version older than the newest version with commit_ts <= ts. That version itself stays: the reader at ts still needs it. A key with no version at or before ts is left alone.

At most 16 keys.

Input

Commands until the end of input:

• write K V TS
• read K TS
• chain K
• gc TS

Output

• write: write key=10 value=100 commit_ts=2, or write key=10 rejected: commit_ts 3 not after 4.
• read: read key=10 at ts=3 -> 100 (commit_ts=2), or read key=10 at ts=1 -> none.
• chain: key=10 chain: 200@4 -> 100@2, newest first as value@commit_ts, or key=10 chain: empty.
• gc: gc oldest_active_ts=3 removed=1.