MVCC in Storage Engines

The common idea, three implementations

Multi-version concurrency control keeps several versions of each record so that readers see a consistent snapshot without blocking writers, and writers don't wait for readers. MVCC in PostgreSQL covers PostgreSQL's user-visible behavior. This page compares how different storage engines physically store versions, because that choice determines where old versions live, what a read costs, what cleans up garbage, and how long-running transactions hurt.

Every MVCC design must answer four questions:

Question Options
Where do old versions live? In the table itself (append), in a separate undo area (delta), or in sorted runs (LSM)
How is a version tagged? Transaction IDs + commit status lookup, or commit timestamps / sequence numbers
How does a reader find its version? Walk newest→oldest, or oldest→newest, comparing against its snapshot
Who removes dead versions, and when? VACUUM, purge threads, compaction — all limited by the oldest active snapshot

Design 1: append-only versions in the heap (PostgreSQL)

graph LR subgraph heap["Heap page"] v1["tuple v1<br/>xmin=100 xmax=200<br/>balance=50"] -->|"t_ctid"| v2["tuple v2<br/>xmin=200 xmax=0<br/>balance=80"] end idx["Index entry: id=7"] --> v1 idx2["Index entry: id=7 (new, unless HOT)"] --> v2

An UPDATE never modifies a tuple in place. It writes a complete new tuple and stamps the old one's xmax with the updating transaction's ID. Each tuple carries xmin (creator) and xmax (deleter); a reader decides visibility by checking those IDs against its snapshot (the set of transactions in progress when it started) and the commit log (pg_xact) for each ID's commit status.

  • Read cost: an index may point at several versions; each must be visibility-checked. Hint bits cache "this xmin is committed" in the tuple to avoid repeated commit-log lookups.
  • Write cost: a full new tuple per update, and — unless the update qualifies as HOT (heap-only tuple: no indexed column changed and there is room on the same page) — a new entry in every index. This is the main source of PostgreSQL's write amplification on update-heavy tables.
  • Garbage collection: VACUUM scans for tuples whose xmax is committed and older than every snapshot, and frees them. Dead tuples in the meantime bloat both table and indexes.
  • Rollback is free: an aborted transaction's tuples simply never become visible.

Design 2: in-place update with undo logs (InnoDB, Oracle)

graph LR rec["Clustered index record (latest)<br/>balance=80<br/>DB_TRX_ID=200<br/>DB_ROLL_PTR"] -->|"roll pointer"| u1["Undo record<br/>'before trx 200: balance=50'<br/>trx_id=100, roll_ptr"] u1 -->|"roll pointer"| u2["Undo record<br/>'before trx 100: balance=20'"]

InnoDB updates the record in place in the clustered index, after writing the old values to the undo log (itself WAL-protected). The record holds the ID of the last transaction that modified it and a roll pointer to the undo record with the previous version; undo records chain further back.

A reader with a read view (its snapshot: which transaction IDs are visible) looks at the latest record; if the modifying transaction is not visible to it, it follows the roll pointer and reconstructs the older version by applying undo records, until it reaches a visible one.

  • Read cost: cheap for recent snapshots (the latest version is usually visible); expensive for old snapshots that must walk long undo chains.
  • Write cost: the record is updated in place; secondary indexes change only if an indexed column changed (secondary indexes keep delete-marked entries and rely on the clustered record for visibility).
  • Garbage collection: purge threads discard undo records no read view can need, and physically remove delete-marked records.
  • Rollback costs work: an aborted transaction must apply its undo records to restore the old values.

The famous failure mode: one long-running transaction (or an idle session with an open read view) prevents purge, the undo log grows by gigabytes (history list length in SHOW ENGINE INNODB STATUS), and every reader of a hot row walks an ever-longer undo chain.

Design 3: versions as sorted entries (LSM engines)

In an LSM engine, MVCC falls out of the data structure itself. Every write gets a sequence number, and the engine stores internal keys (user_key, sequence, type) sorted by user key ascending and sequence descending (see LSM Tree):

balance@300 PUT 80     ← newest
balance@200 PUT 50
balance@100 PUT 20

A snapshot is just a sequence number. A read at snapshot 250 seeks to (balance, 250) and finds the first entry with sequence ≤ 250: balance@200 = 50. No commit-status lookups, no chains to follow — the sort order puts the right version first.

  • Read cost: one seek per source (memtable, each relevant SSTable); old versions sit right after the newest in sort order and are usually in the same block.
  • Write cost: an update is an ordinary append.
  • Garbage collection: compaction drops versions that are shadowed by a newer version visible to every live snapshot (the exact rule is in Compaction and Recovery).
  • Transactions on top (RocksDB TransactionDB, TiKV, CockroachDB): sequence numbers or timestamps provide the snapshot; conflict detection compares the latest sequence of written keys to the snapshot — see Iterators, Snapshots, and Transactions. Distributed systems often put an explicit timestamp into the key (key@ts), so versions are addressable across nodes (TiKV's Percolator columns, CockroachDB's MVCC keys).

Side by side

PostgreSQL (append in heap) InnoDB (in place + undo) LSM (sorted versions)
Where old versions live Heap pages, next to live data Undo log (separate) Same sorted files, adjacent to newer versions
Update writes New full tuple (+ index entries unless HOT) Undo record + in-place change One new entry
Read of latest Possibly skip dead versions Direct Direct (first entry)
Read of old snapshot Visibility checks per version Reconstruct via undo chain Seek; versions adjacent
Garbage collection VACUUM Purge threads Compaction
Abort cost Free Apply undo Free (batch never applied)
Long-running snapshot causes Table and index bloat Undo growth, slow old reads Space amplification; versions kept through compaction

Version ordering: newest-to-oldest vs. oldest-to-newest

Academic comparisons (e.g. Wu, Pavlo et al., "An Empirical Evaluation of In-Memory Multi-Version Concurrency Control," VLDB 2017) classify version storage as append-only (oldest-to-newest or newest-to-oldest chains), time-travel (old versions copied to a separate table), and delta (undo records). Their finding mirrors the table above: delta storage is efficient for updates touching few columns and for reads of the latest version; append-only is simpler and cheaper to abort; and garbage collection is the dominant cost in every design under long transactions.

The universal constraint: the oldest snapshot

In every design, a version can be removed only when no active snapshot can see it. The oldest open snapshot — a forgotten transaction, a long analytics query, a stuck replication slot in PostgreSQL, an un-released RocksDB snapshot or iterator — pins all versions created since. Symptoms differ by design (bloat, undo growth, space amplification) but the cause and the fix are the same: find and end the old snapshot, and monitor its age (pg_stat_activity.xact_start, backend_xmin; InnoDB history list length; RocksDB rocksdb.oldest-snapshot-time).

Common pitfall

Assuming that MVCC makes long read-only transactions free because they "don't block anyone." They do not block writers, but they block garbage collection for the entire database, not just the tables they read: a PostgreSQL transaction open for hours on one small table prevents VACUUM from removing dead tuples in every table of the database, and an InnoDB read view does the same for purge across all tables. The cost appears elsewhere and later — bloated, slower tables that remain bloated after the transaction ends, until VACUUM or purge catches up. Long reads belong on a replica, or in a snapshot-based export, rather than in a transaction on the primary.