MVCC (multi-version concurrency control)

MVCC (multi-version concurrency control) is how most transactional databases let readers and writers share rows. Instead of making readers wait while a row changes, the database keeps older versions and shows each transaction the one that matches its snapshot. PostgreSQL, InnoDB, Oracle and CockroachDB all use it, and it explains why a long report doesn’t freeze checkout, and why one forgotten transaction can bloat a database.

Picture it first: the munim who never erases

A wholesale shop’s munim (accountant) never erases. When Asha’s balance goes from ₹500 to ₹400, he writes a new line, “Asha ₹400, for token 105”, and notes in the old line’s margin “replaced by token 105”.

Everyone who checks a balance takes a token at the door. A customer with token 108 reads the newest line finished before token 108 was issued. Nobody waits for the munim, and he waits for nobody.

Two things still need care. Two clerks can’t change Asha’s line at once, because only one new line can follow the old one. And old pages can be torn out only when nobody holds a token old enough to need them, so one customer in the corner holding token 40 since morning keeps every page after it.

A second shop corrects lines in place, first copying the old value onto a slip in a back drawer for customers with old tokens.

Map it back: lines are row versions, tokens are transaction IDs, “what was finished when my token was issued” is a snapshot, the margin note is PostgreSQL’s xmax, the back drawer is the undo log of InnoDB and Oracle, tearing out pages is VACUUM or purge, and the customer in the corner is a long-running transaction.

The problem MVCC solves

Without versions, a database protects rows with locks: readers take shared locks, writers need exclusive ones, and under strict two-phase locking both are held until commit.

Picture a 20-minute report summing every UPI wallet balance while payments flow. The report’s shared locks block every payment touching a row it has read, and each payment’s exclusive lock blocks the report. The slowest transaction sets everyone’s pace.

MVCC breaks that coupling by keeping more than one version of a row. A writer creates a new version without destroying the one readers might be using, and a reader picks the version matching its snapshot, taking no lock. As the PostgreSQL documentation puts it, reading never blocks writing, and writing never blocks reading.

The limit: two writers to the same row still conflict. Only one new version can follow the current one, so the second writer waits for the first one’s row lock, then carries on against the new version or aborts. Snapshot isolation’s formal rule is first committer wins; PostgreSQL’s REPEATABLE READ enforces it with the row lock, so the second writer gets an error once the first commits, while InnoDB’s REPEATABLE READ lets it write on top of the new version.

How MVCC works, step by step

Every MVCC engine has the same five parts.

1. An ordered ID for every writer: a counter (PostgreSQL’s xid, InnoDB’s trx id) or a timestamp (Oracle’s SCN, CockroachDB’s hybrid logical clock).
2. Stamped versions. Every insert, update or delete produces a version stamped with its creator’s ID; old versions are marked as replaced or copied elsewhere.
3. A snapshot: which transactions’ effects a reader may see, stored as an upper bound plus a list of transactions still in flight.
4. A visibility rule. Return the newest version whose creator is visible to the snapshot and whose deleter, if any, is not. Your own changes are always visible to you.
5. Garbage collection. A replaced version older than every live snapshot can never be read again, so it is removed. The oldest live snapshot is the horizon.

The big design choice is where old versions live. A 2017 VLDB study by Wu et al. names the families: append-only storage keeps every version in the table (PostgreSQL); delta storage updates in place and keeps before-images in a rollback area (InnoDB, Oracle). That choice shapes everything below.

PostgreSQL: a new tuple for every update

What every tuple carries

PostgreSQL stores a table as a heap of 8 kB pages. Each row version, a tuple, starts with a 23-byte header (on most machines) holding three MVCC fields:

• xmin: the transaction that inserted this version.
• xmax: the transaction that deleted or replaced it, or 0. It can be non-zero on a visible tuple if the deleter hasn’t committed, rolled back, or only locked the row.
• t_ctid: where this version, or its replacement, lives.

A location, or ctid, is a page number plus a slot number, written (0,2). You can select xmin, xmax and ctid as hidden system columns on any table; because the ctid changes on every update, never use it as an identifier.

INSERT, UPDATE and DELETE

• INSERT writes a tuple with xmin = your xid and xmax = 0.
• DELETE writes nothing new; it sets xmax on the current tuple.
• UPDATE is a delete plus an insert: it sets xmax on the old tuple, writes a complete new tuple (every column) wherever there is space, and points the old t_ctid at it.

Nothing is overwritten, so updates are “out of place”, and the old tuple stays on disk until clean-up removes it. Rollback is almost free: PostgreSQL marks your xid aborted and everything you wrote becomes invisible.

Snapshots and visibility

pg_current_snapshot() shows a snapshot as xmin:xmax:xip_list:

• xmin: the lowest transaction ID still running; everything below has finished.
• xmax: one past the highest completed ID; everything at or above is invisible.
• xip_list: the IDs in between that were still running.

A tuple is visible when its xmin had committed as of the snapshot (below its xmax, not in its xip list, recorded as committed) and its xmax is 0, aborted, or not committed as far as the snapshot can tell.

“Recorded as committed” is a lookup in pg_xact (formerly the CLOG), two bits per transaction. The first reader to learn a tuple’s outcome caches it as a hint bit in the header, which is why the first SELECT after a bulk load can cause disk writes.

A worked example

One wallet row through two updates in psql, on PostgreSQL 13 or later at the default READ COMMITTED level. Transaction IDs and ctids are illustrative.

CREATE TABLE wallet (id int PRIMARY KEY, owner text, balance int);
INSERT INTO wallet VALUES (7, 'asha', 500);          -- ran as xid 100
UPDATE wallet SET balance = 400 WHERE id = 7;        -- ran as xid 105

SELECT xmin, xmax, ctid, * FROM wallet WHERE id = 7;
--  xmin | xmax | ctid  | id | owner | balance
--   105 |    0 | (0,2) |  7 | asha  |     400

-- Session B
BEGIN;
UPDATE wallet SET balance = 300 WHERE id = 7;        -- xid 110, not committed

-- Session A, at the same time
SELECT xmin, xmax, ctid, * FROM wallet WHERE id = 7;
--   105 |  110 | (0,2) |  7 | asha  |     400        -- old version, xmax already set
SELECT pg_current_snapshot();
--  110:112:110                                       -- 110 running; 111 already done

-- Session B
COMMIT;

-- Session A
SELECT xmin, xmax, ctid, * FROM wallet WHERE id = 7;
--   110 |    0 | (0,3) |  7 | asha  |     300

The xmax of 110 on a version Session A still sees is not a bug: 110 has claimed the row but not committed, so for A the old version is current. And B’s UPDATE didn’t turn ₹400 into ₹300; it added a third tuple. The pageinspect extension shows all of them:

CREATE EXTENSION pageinspect;
SELECT lp, t_xmin, t_xmax, t_ctid
FROM heap_page_items(get_raw_page('wallet', 0));
--  lp | t_xmin | t_xmax | t_ctid
--   1 |    100 |    105 | (0,2)
--   2 |    105 |    110 | (0,3)
--   3 |    110 |      0 | (0,3)

On a busy page, pruning may already have removed the middle tuple. Figure 1 draws the chain and which snapshot sees which tuple.

Indexes, ctid and HOT updates

An index entry stores a key and a ctid, and carries no visibility information, so an index scan finds candidate tuples and checks each one’s xmin and xmax in the heap.

Because an ordinary update puts the new version at a new ctid, every index needs a new entry, even on untouched columns. Uber’s 2016 write-up of its move to MySQL showed one column change in a table with three indexes costing at least four physical writes (a tuple and three index entries), before WAL.

HOT (heap-only tuple) updates avoid that when two conditions hold:

1. The update changes no indexed column (summarising indexes such as BRIN don’t count).
2. The old tuple’s page has room for the new one.

The new tuple stays on the same page, no index gets an entry, and lookups follow the chain from the original slot; intermediate versions can even be pruned during reads. n_tup_hot_upd in pg_stat_all_tables shows how often HOT works.

InnoDB: update in place, history in the undo log

Hidden columns

InnoDB stores each table as a B-tree clustered on the primary key, so leaf pages hold the rows. Its multi-versioning chapter lists three hidden fields:

• DB_TRX_ID (6 bytes): the last transaction that inserted or updated the row (a delete is an update that sets a “deleted” bit).
• DB_ROLL_PTR (7 bytes): points to an undo record holding the row’s previous contents.
• DB_ROW_ID (6 bytes): used only when the table has no suitable key and InnoDB generates the clustered index.

UPDATE writes undo, then changes the row

An UPDATE first writes an undo record with the before-image of the changed columns plus the old DB_TRX_ID and roll pointer, then changes the clustered record in place, stamps its own trx id, and points DB_ROLL_PTR at that undo record. The roll pointers chain back through history.

Undo has two jobs: rollback applies it backwards (so big transactions are slow to roll back), and consistent reads use it to rebuild older versions. Insert undo is discarded at commit; update and delete undo stays until no snapshot could need it.

Read views

InnoDB’s snapshot, the read view, holds the same facts as PostgreSQL’s: a low-water mark (IDs below are visible), a high-water mark (IDs at or above are not), and the read-write transactions active when it was made. A consistent read checks the record’s DB_TRX_ID; if the view can’t see it, it follows DB_ROLL_PTR, rebuilds the previous version, and checks again, until a version is visible or the chain ends (the row didn’t exist for this reader).

Secondary indexes hold no versions

Secondary index records have no hidden columns and are never updated in place: changing an indexed column delete-marks the old entry and inserts a new one. When a reader meets a delete-marked entry, or a secondary page last changed by a transaction newer than its view, it must look the row up in the clustered index, check DB_TRX_ID, and walk undo if needed. So a covering index quietly stops covering on busy pages.

Purge and the history list

A DELETE removes nothing physically. Background purge threads remove delete-marked rows and index entries, and free undo, once no read view needs them. Committed undo awaiting purge is the history list, whose length SHOW ENGINE INNODB STATUS reports; MySQL’s purge documentation says it is usually below a few thousand, and grows under heavy writes or long transactions, read-only ones included. innodb_purge_threads defaults to 1 on machines with 16 or fewer logical processors, otherwise 4; innodb_max_purge_lag (0, off, by default) throttles DML when purge falls behind.

Oracle: undo segments and SCNs

Oracle is a delta store too: changes write undo into undo segments, and the current block holds the newest data. Time is a system change number (SCN), and a query is consistent to one: when the statement opened under READ COMMITTED, or when the transaction began under SERIALIZABLE or READ ONLY. For a block changed after that SCN, Oracle copies it in memory and applies undo until it matches, a consistent read (CR) clone, using the block header’s interested transaction list (ITL) to find which changes had committed.

The difference is what happens when history runs short. Committed undo older than the undo retention period is “expired” and reusable. Oracle tunes that period from tablespace size and load, and when space is tight may overwrite even unexpired undo, unless RETENTION GUARANTEE is set, which makes DML fail instead. A long query whose undo was overwritten fails with ORA-01555: snapshot too old; in Oracle’s words, rollback records a reader needed were overwritten by other writers. The fixes: more undo, a longer UNDO_RETENTION, or a shorter query.

So Oracle sacrifices the old reader to protect everyone else, while PostgreSQL and InnoDB protect the old reader and let storage grow. PostgreSQL’s opt-in equivalent, old_snapshot_threshold, was removed in version 17.

PostgreSQL vs InnoDB vs Oracle

Neither design wins outright: PostgreSQL makes old reads and rollbacks cheap and pays on updates and clean-up; InnoDB and Oracle make updates cheap and charge old readers. See PostgreSQL vs MySQL.

Readers and writers on one timeline

Figure 3 puts the rule and its limit on one row, at PostgreSQL’s REPEATABLE READ.

At t3, v1’s xmax (B’s xid) is still running, so v1 is current for A and the read doesn’t wait. At t4, A must write after v1, but B holds the row lock. When B commits, the row holds ₹400, which A’s snapshot can’t see; had A computed the balance from its own read (₹500 − ₹100), it would erase B’s change. So PostgreSQL aborts A with SQLSTATE 40001, and the application retries.

How isolation levels sit on top of MVCC

MVCC is the machinery; isolation levels are policies built from three choices.

When to take the snapshot. READ COMMITTED takes one per statement. REPEATABLE READ (snapshot isolation) takes one per transaction: in PostgreSQL at the first statement that isn’t transaction control, in InnoDB at the first consistent read, in Oracle at the start of a SERIALIZABLE or READ ONLY transaction. See read committed vs repeatable read.

What a writer does on meeting a newer version. PostgreSQL’s READ COMMITTED waits, re-checks its WHERE clause against the new version, and updates it if it still matches; REPEATABLE READ aborts, as in Figure 3. InnoDB’s REPEATABLE READ runs UPDATE, DELETE and locking reads against the latest committed version even while plain SELECTs see the old one, so read-then-write code can silently lose updates; see the lost update problem.

Whether to track reads. Snapshots catch only write-write conflicts on one row. Two transactions that read the same rows and write different ones never collide, so a rule spanning rows can break: write skew, as when two on-call doctors each see the other on duty and both sign off. MVCC alone gives snapshot isolation, not serializability; PostgreSQL’s SERIALIZABLE adds read tracking (serializable isolation). All the anomalies are in transaction isolation levels.

Cleaning up old versions

Every janitor obeys one rule: remove a version only when no live snapshot could read it.

• PostgreSQL: VACUUM, usually via autovacuum, frees dead tuples and their index entries; HOT chains are also pruned during reads.
• InnoDB: purge threads remove delete-marked records and discard undo.
• Oracle: tables hold no old versions; undo is reused after its retention period.

Tuning and wraparound live in vacuum and bloat. What defeats every janitor is a long-lived snapshot.

Going deeper: costs and failure modes

Long transactions hold back the horizon

The oldest live snapshot sets the horizon for every table in the database (in InnoDB, the whole server), not just the tables it touched. Figure 4 shows a report that began at 09:00, ran one query and then sat “idle in transaction”.

Scale it to a Flipkart-style sale: 5,000 order-row updates per second for a 2-hour report is 5,000 × 7,200 = 36 million versions that can’t be removed. In PostgreSQL they are dead tuples that every scan steps over, and the table stays big afterwards because VACUUM only makes space reusable. In InnoDB they are undo, and old readers walk longer chains.

The culprits are mundane: a forgotten BEGIN in a console, a slow API call inside a transaction, mysqldump --single-transaction, analytics on the primary, or, in PostgreSQL, an abandoned replication slot or a replica feeding back old snapshots (data replication).

Write amplification versus reconstruction cost

PostgreSQL makes the writer pay: a non-HOT update rewrites the whole row and touches every index, all of it also WAL-logged. A table with six indexes and a constantly updated last_seen_at is the classic victim. InnoDB makes the old reader pay: updates are small, but a reader ten updates behind applies ten undo records, and on a hot row with an old read view that walk shows up in latency.

Hot rows still queue

MVCC does nothing for write contention: if every flash-sale order decrements one stock row, every writer queues on its row lock. Fixes are in contention and double booking and design a flash sale.

Transaction IDs run out

PostgreSQL’s xids are 32 bits and compared modulo 2^32, so a tuple more than about 2 billion transactions old would suddenly look as if it came from the future. VACUUM must freeze old tuples before that happens. A long transaction blocks freezing too, and in the extreme pushes a busy database towards a forced shutdown (vacuum and bloat).

MVCC beyond the classic three

CockroachDB and Spanner use timestamps instead of transaction-ID lists. CockroachDB stores each key’s versions in its LSM engine, Pebble, tagged with hybrid-logical-clock timestamps; a read at time T returns the newest version at or below T, and AS OF SYSTEM TIME reads the past on purpose. A version is garbage-collected once a newer one is older than gc.ttlseconds, 14,400 seconds (4 hours) by default; protected timestamps keep versions alive for running backups. Spanner keeps versions for one hour by default, up to seven days if configured; a longer window buys longer reads and point-in-time recovery, and costs storage.

RocksDB and other LSM engines give every write a sequence number, and a snapshot is just a sequence number: a version is visible if its number is at or below the snapshot’s. Compaction drops old versions but keeps any a live snapshot can see; RocksDB’s wiki notes that hundreds of thousands of live snapshots slowed compaction into write stalls. See reads and writes: how databases store and fetch data.

Cheat sheet

How to say it in the interview

“MVCC keeps multiple versions of each row. Every write creates a version stamped with its transaction ID, and every transaction reads from a snapshot of what had committed, so readers take no locks and writers don’t wait for them. Two writers on one row still conflict: the second waits for the row lock, then re-applies or gets a serialization error. PostgreSQL appends a tuple per update and VACUUM removes dead ones; InnoDB updates in place and keeps old values in undo, cleared by purge. So I keep payment transactions short, run reports on a replica, and set an idle-in-transaction timeout so one stuck session can’t pin old versions for everyone.”

Does MVCC mean no locks? No. Plain reads take no row locks, but writers lock the rows they change, SELECT … FOR UPDATE locks on purpose, and DDL takes table locks. MVCC removes reader-writer blocking, not writer-writer blocking; InnoDB even adds gap locks for locking reads at REPEATABLE READ.

Why can a long transaction slow down the whole database? Clean-up may only remove versions no live snapshot can see, and the oldest snapshot sets that horizon for every table in the database. So PostgreSQL bloats and scans step over dead tuples, InnoDB’s history list grows and old reads walk longer undo chains, and Oracle eventually fails the long query with ORA-01555. End it and the horizon jumps forward.

Postgres vs MySQL MVCC: which is better for update-heavy tables? It depends on indexes. InnoDB updates in place with a small undo record and touches a secondary index only when its column changes, so it wins on heavily indexed tables. PostgreSQL rewrites the tuple and, unless the update is HOT, adds an entry to every index; with unindexed hot columns and free page space, HOT makes it competitive. In return, PostgreSQL’s rollbacks and old reads are cheap, while InnoDB pays in undo walks and purge.

How does MVCC give you snapshot isolation but not serializable? Snapshots make reads consistent, and the write-write check stops two transactions replacing the same version. But one that reads rows A and B and writes B never conflicts with one that reads both and writes A, so an invariant across them can break: write skew. Serializability needs read tracking, as in PostgreSQL’s SSI, or locks on what was read.

Where to go next

• Vacuum and bloat: autovacuum tuning, wraparound, and what blocks clean-up.
• Transaction isolation levels: the anomalies, and what each database does.
• Read committed vs repeatable read: snapshot per statement or per transaction.
• Serializable isolation: how SSI adds read tracking to stop write skew.
• Lost update problem: the write-write race and its fixes.
• Optimistic vs pessimistic locking: locking rows yourself on top of MVCC.
• PostgreSQL vs MySQL: the wider differences behind the two designs.
• Write-ahead logging: redo versus undo, and how version changes are logged.
• Concurrency control: MVCC beside two-phase locking and optimistic schemes.

References and further reading

1. PostgreSQL documentation: Concurrency Control — Introductionpostgresql.orgEach statement sees a snapshot; reading never blocks writing and writing never blocks reading, even under SSI.
2. PostgreSQL documentation: System Columnspostgresql.orgDefinitions of xmin, xmax and ctid, why a visible row can have a non-zero xmax, and 32-bit transaction IDs.
3. PostgreSQL documentation: Database Page Layout (Table Row Layout)postgresql.org8 kB pages, item identifiers, ctid as page plus item number, and the 23-byte tuple header with t_xmin, t_xmax and t_ctid.
4. PostgreSQL documentation: Heap-Only Tuples (HOT)postgresql.orgThe two conditions for a HOT update, pruning of intermediate versions during normal reads, and fillfactor.
5. PostgreSQL documentation: System Information Functions (snapshot information)postgresql.orgpg_current_snapshot() and the xmin:xmax:xip_list snapshot format with the meaning of each component.
6. MySQL 8.4 Reference Manual: InnoDB Multi-Versioningdev.mysql.comDB_TRX_ID, DB_ROLL_PTR and DB_ROW_ID, insert versus update undo, purge, and why secondary indexes fall back to the clustered index.
7. MySQL 8.4 Reference Manual: Purge Configurationdev.mysql.comPurge threads and their defaults, innodb_max_purge_lag, and history list length growing under long transactions.
8. Oracle Database Concepts: Data Concurrency and Consistencydocs.oracle.comStatement- and transaction-level read consistency by SCN, undo segments, consistent read clones and interested transaction lists.
9. Oracle Database Administrator’s Guide: Managing Undodocs.oracle.comExpired versus unexpired undo, automatic retention tuning, RETENTION GUARANTEE, and snapshot too old errors.
10. CockroachDB documentation: Storage Layer (MVCC and garbage collection)cockroachlabs.comTimestamped MVCC values in Pebble, time-travel reads, garbage collection by GC TTL, and protected timestamps.