MVCC

In 1978, David Reed at MIT published his PhD thesis: "Naming and Synchronization in a Decentralized Computer System." Buried in it was an idea that would revolutionize database design: Multi-Version Concurrency Control — MVCC. The insight: readers should never block writers, and writers should never block readers. Achieve this by keeping multiple versions of every row. Every read sees a consistent snapshot from a specific point in time. Every write creates a new version without touching the version older readers are looking at.

Traditional locking databases blocked liberally. If you were reading a row, no one could write to it. If you were writing, no one could read. On big tables with hot rows, this crushed concurrency — 5 concurrent users could grind a database to a halt because they all wanted the same page. MVCC dissolved this. Postgres (1986), Oracle (1988 via undo tablespaces), and later MySQL InnoDB (2001 via undo logs) all adopted variants of MVCC. Every serious modern database now has MVCC — CockroachDB, Spanner, YugabyteDB, TiDB, MongoDB, SQL Server (since 2005), MariaDB.

The trade-off is bloat. Every UPDATE creates a new tuple version; the old one becomes dead and must eventually be garbage collected. Postgres's VACUUM, Oracle's undo tablespace cleanup, InnoDB's purge thread — all fight the same battle: reclaim space from dead versions without blocking live readers. Get this wrong and your database bloats. Get it right and you have unlimited concurrent readers with zero contention.

The core idea — every row has a version chain

In an MVCC database, a row is not one thing — it's a chain of versions, each tagged with the transaction that created it and the transaction that deleted it. When you read, the database walks the chain and finds the version that was "alive" at your transaction's start time.

In Postgres each row has two hidden columns: xmin (the transaction ID that inserted this version) and xmax (the transaction ID that deleted or updated it — 0 if still current). Every transaction has a transaction ID (XID) incremented monotonically. Every read query captures a snapshot — the set of XIDs it should consider "visible." The visibility rule is:

• Version is visible iff xmin is committed and in the snapshot, AND xmax is either 0 or not yet committed / not in the snapshot.

Interactive: readers and writers don't block

Watch the reader and writer proceed in parallel — they never wait on each other. The reader sees the snapshot at transaction start. The writer creates a new version. Both commit. This is impossible in a strict locking database.

Snapshot isolation — the isolation level MVCC unlocks

MVCC naturally implements snapshot isolation — every transaction sees a consistent view of the database as of its start time. This is the isolation level Postgres, Oracle, and MySQL InnoDB call "REPEATABLE READ" (though the SQL-92 standard defines it slightly differently). Snapshot isolation prevents:

• Dirty reads — you never see uncommitted data. Every version has an xmin that must be committed to be visible.
• Non-repeatable reads — read the same row twice, get the same answer. Because your snapshot doesn't change during your transaction.
• Phantom reads — a query with a range condition returns the same rows the second time. New inserts happen at higher XIDs not in your snapshot.

But snapshot isolation is not fully serializable. It admits one specific anomaly called write skew — two transactions read overlapping data and each updates a different piece based on what the other read. Both commit successfully but their combined effect violates an invariant that neither individually would violate.

Postgres 9.1 (2011) shipped Serializable Snapshot Isolation (SSI) — detects potential write-skew via predicate locks and aborts one of the conflicting transactions. Full serializability with MVCC's reader-writer concurrency. This is what most modern databases mean by "SERIALIZABLE."

The bloat problem — VACUUM and its friends

Every UPDATE creates a new tuple. The old one is dead — no live transaction can see it — but it still occupies disk space until reclaimed. If you don't clean up, your table bloats. Fast writes make it worse: at 10k updates/sec, an unchecked table can double in size in minutes.

Postgres has autovacuum — a background daemon that periodically scans tables looking for dead tuples. It reclaims space, updates visibility maps, and prevents XID wraparound. Oracle uses undo tablespaces that automatically age out old versions after a retention period. InnoDB has a purge thread. Every MVCC engine has some form of this — it's the price of the reader-writer non-blocking property.

MVCC vs locking — the fundamental choice

Applied in real systems

Key takeaways

• MVCC keeps multiple versions of every row. Readers never block writers, writers never block readers.
• Every version has metadata: xmin (creator), xmax (deleter). Reads use a snapshot to decide which versions are visible.
• MVCC naturally implements snapshot isolation. Prevents dirty reads, non-repeatable reads, phantoms — but not write skew.
• Serializable Snapshot Isolation (SSI) — MVCC + predicate locks. Postgres 9.1+, others. Full serializability without giving up MVCC.
• Bloat is the cost. Dead tuples accumulate; VACUUM (PG), undo tablespace (Oracle), purge thread (InnoDB) all fight this.
• Every serious modern database uses MVCC: Postgres, Oracle, MySQL InnoDB, SQL Server, CockroachDB, Spanner, TiDB, YugabyteDB, MongoDB. Locking-only databases are rare historical artifacts.
• MVCC + HLC/TrueTime timestamps enables distributed MVCC — the foundation of NewSQL systems that offer ACID at planetary scale.

References

• Reed (1978) — Naming and Synchronization in a Decentralized Computer System.
• Bernstein & Goodman (1983) — Multiversion Concurrency Control.
• Ports & Grittner (2012) — Serializable Snapshot Isolation in PostgreSQL. VLDB.
• Kleppmann (2017) — Designing Data-Intensive Applications, Chapter 7.
• Bailis et al. (2013) — "Highly Available Transactions" — how MVCC relates to CAP.
• Postgres official docs on MVCC + VACUUM + XID wraparound.