1. The Concurrency Challenge: Read-Write Conflicts

1.1 Locks and Latency

In standard locking databases, executing an UPDATE statement on a row locks that record. A concurrent SELECT query targeting the same row must block until the updating transaction commits. Under heavy load, these lock queues cascade, leading to transaction timeouts and thread starvation. The core challenge of concurrent databases is keeping isolation boundaries intact without sacrificing latency.

The ultimate goal is to allow readers to query data snapshots without waiting for writers, and writers to update records without blocking readers. MVCC achieves this by decoupling the logical version of a record from its physical representation on disk.

1.2 Lock-Based 2PL vs Multi-Version Storage

A lock-based system maintains a single physical copy of a row and blocks parallel threads. A multi-version system maintains multiple logical copies in memory, routing queries to visible snapshots.

Common Misconception — MVCC completely eliminates database locks: A common developer misconception is that MVCC databases do not use locks at all. In reality, MVCC only eliminates read-write locks. Write-write conflicts still require row-level exclusive locks to prevent two transactions from updating the exact same record simultaneously, which would cause data corruption.

2. What is Multi-Version Concurrency Control (MVCC)?

2.1 Decoupling Physical Rows

Instead of overwriting an existing record when a write occurs, an MVCC engine writes a new physical version of that row (called a tuple) to the database page. This means that at any point in time, a single logical row can have multiple physical versions stored on disk, each representing the row state at a specific transaction checkpoint.

When a query is executed, the transaction receives a virtual snapshot of active transaction IDs. The database engine uses this snapshot to evaluate which physical version of the row is visible to the caller, filtering out modifications from uncommitted or newer transactions.

Mermaid Diagram: The physical separation of row tuples under MVCC, allowing Tx 101 to read old version while Tx 102 updates.

3. Row Metadata Headers: xmin, xmax, and t_cid

3.1 System Headers in Tuple Blocks

To track transaction bounds, the PostgreSQL engine prepends a 23-byte header to every database tuple. The three critical system fields are: (1) **xmin**: the transaction ID (txid) of the transaction that created (inserted) this tuple version. (2) **xmax**: the txid of the transaction that deleted or updated this tuple. For active, non-deleted rows, xmax is set to 0. (3) **t_cid** (Command ID): tracks the sequence number of SQL commands executed within a single transaction block, preventing a transaction from reading its own updates before they are committed.

4. The Snapshot Visibility Rules

4.1 Defining Snapshot Parameters

A database snapshot is defined by three variables: $x_{\text{min}}$ (the lowest transaction ID that is still active), $x_{\text{max}}$ (the next unassigned transaction ID), and a list of active transaction IDs. The engine evaluates whether a physical tuple with header values $(t_{\text{xmin}}, t_{\text{xmax}})$ is visible to transaction $T_c$ by running a series of boundary checks.

These visibility rules verify if the inserting transaction committed before the snapshot was taken, and if the deleting transaction is uncommitted or started after the snapshot boundary. These checks prevent dirty reads and non-repeatable reads during transaction executions.

4.2 The Snapshot Visibility Formulas

When a transaction $T_c$ requests a snapshot, the database engine returns a snapshot object containing the bounds $[x_{\text{min}}, x_{\text{max}}]$ and a set of active transaction IDs $S_{\text{active}}$. The visibility function $V(t)$ evaluates the status of a tuple created by transaction $t_{\text{xmin}}$ and deleted by transaction $t_{\text{xmax}}$. First, we evaluate the visibility of the tuple's creation:

If the tuple's creation is visible, we next evaluate the visibility of the tuple's deletion. If the tuple has not been deleted or updated ($t_{\text{xmax}} = 0$), the tuple remains visible. Otherwise, the engine checks if the deletion has committed:

The final visibility state $V$ of the tuple is a logical combination of these two sub-evaluations. A tuple is visible to transaction $T_c$ if and only if its creation is visible and its deletion is not committed:

This math guarantees that readers do not block writers. When a writer updates a row, it creates a new tuple version. The reader's snapshot filters out this new version because its $t_{\text{xmin}}$ is in $S_{\text{active}}$ (active/uncommitted). The reader continues to read the old tuple version ($t_{\text{xmax}}$ is active/uncommitted, so deletion is not committed), maintaining snapshot isolation. Below is a comparison table of visibility cases:

Pitfall — Sub-transactions visibility leaks: If a transaction uses savepoints (sub-transactions) that abort, their transaction IDs must be marked as aborted in the CLOG. If the engine fails to check sub-transaction status recursively, aborted data could leak into parent queries. Postgres tracks sub-transaction trees to prevent this.

5. Modifying Rows: Insert, Update, and Delete in MVCC

5.1 Tuple Lifecycle

When modifying data, the MVCC engine processes operations as follows:

• **Insert**: Creates a new physical tuple. The xmin field is populated with the current transaction ID, and xmax is set to 0.
• **Delete**: Does not remove the tuple from disk. Instead, the engine updates the xmax field of the existing tuple with the deleting transaction's ID.
• **Update**: Combines a delete and an insert. The engine sets the xmax of the old tuple to the current transaction ID, and writes a new tuple with xmin set to the current transaction ID.

Pitfall — Running out of transaction IDs (wrap-around): Since transaction IDs are represented as 32-bit unsigned integers, the maximum number of transactions is $2^{32} \approx 4.2$ billion. If a database runs continuously, the ID counter can wrap around back to 3. If this occurs without maintenance, old transactions suddenly appear in the future, causing data visibility loss. PostgreSQL prevents this by running autovacuum to freeze ancient transactions.

6. The Dead Tuple Problem and VACUUM

6.1 Database Bloat

Because updates and deletes write new tuples instead of overwriting, disk pages accumulate obsolete row versions that are no longer visible to any active transaction. These are called **Dead Tuples**. If left uncleaned, these dead tuples consume disk space and degrade read performance (since index scans must traverse dead pointers).

To reclaim space, PostgreSQL runs the VACUUM command. The vacuum daemon scans table pages, identifies dead tuples, updates the Free Space Map (FSM) to mark those byte ranges as reusable, and removes index pointers. This allows future inserts to overwrite the dead tuple space without increasing file sizes.

6.2 Autovacuum Threshold Formula and the Visibility Map

To prevent manual administrator intervention, the PostgreSQL engine runs an automatic background service called **autovacuum**. This service monitors table modification history and automatically schedules a vacuum pass when the number of dead tuples exceeds a dynamically calculated threshold. Let $D_{\text{threshold}}$ be the trigger threshold of dead tuples, let $N_{\text{tuples}}$ be the total number of live tuples in the table, let $S_{\text{scale}}$ be the autovacuum scale factor (a percentage default of 0.20), and let $T_{\text{threshold}}$ be the base threshold (default of 50 tuples):

When the number of dead tuples tracked by the stats collector exceeds $D_{\text{threshold}}$, autovacuum launches a worker process. In addition to updating the Free Space Map (FSM), the vacuum worker updates the **Visibility Map (VM)**. The VM is a flat bitmap storing two bits for each database page:

• **All-Visible**: Indicates that all tuples in the page are visible to all active and future transactions. This allows index-only scans to bypass fetching the raw heap page entirely, speeding up query execution times.
• **All-Frozen**: Indicates that all tuples in the page have been frozen. The engine can skip scanning this page entirely during transaction wrap-around checks.

Below is a comparison table of vacuum performance factors:

Pitfall — Disabling Autovacuum entirely: Disabling autovacuum to save CPU cycles leads to database corruption. Over time, the commit counter will wrap around, forcing the entire database server to enter read-only safety mode to prevent data loss. Never turn off autovacuum; tune its parameters instead.

7. Advanced: Serializable Snapshot Isolation (SSI) and Write Skew

7.1 Concurrency Anomalies

While MVCC prevents standard anomalies like dirty reads, it is susceptible to **Write Skew** under standard Snapshot Isolation. Write skew occurs when two concurrent transactions read overlapping data sets, make decisions based on those reads, and write disjoint updates that violate business rules (e.g. two doctors on call attempting to leave simultaneously when at least one must remain).

PostgreSQL resolves this in its Serializable isolation level by tracking dependencies dynamically (Serializable Snapshot Isolation). The engine monitors active queries and raises a serialization failure (error 40001) if a dependency cycle is detected, forcing the client to retry the transaction.

7.2 Dependency Graphs and rw-Antidependencies

To enforce true serializability without blocking readers, PostgreSQL implements Serializable Snapshot Isolation (SSI). SSI operates by constructing a dynamic **Dependency Graph** of active transactions in memory. The vertices in this graph represent transactions, and the directed edges represent dependency relationships. SSI tracks three types of dependencies: write-after-read, read-after-write, and write-after-write.

The critical edge type that leads to write skew anomalies is the **read-write antidependency** (denoted as $T_1 \xrightarrow{rw} T_2$). A read-write antidependency exists if transaction $T_1$ reads a physical version of tuple $V$, and concurrent transaction $T_2$ creates a newer version of $V$ (via update or delete), effectively making $T_1$'s read obsolete. Mathematically, the SSI engine monitors the graph for cycles containing two consecutive $rw$-antidependency edges:

If such a path forms a cycle, a serialization anomaly is possible. The transaction designated as $T_{\text{pivot}}$ (the middle node) is flagged. When $T_{\text{pivot}}$ or one of its dependencies attempts to commit, the engine aborts the transaction, rolling back its changes and throwing a 40001 SQL error code.

To track these dependencies, Postgres allocates virtual lock flags called **SIREAD locks** in a shared memory pool. Unlike standard heavyweight locks, SIREAD locks are completely non-blocking. They act as markers indicating that a transaction has read a specific tuple, page, or relation. If a concurrent write occurs on that marker, the $rw$-edge is registered in the graph:

Below is a comparison table of isolation anomalies:

Pitfall — Exceeding SIREAD Lock Memory: Because SIREAD locks are tracked in a fixed-size shared memory pool, executing a single transaction that reads millions of individual rows can exhaust the lock table. To prevent crashes, Postgres automatically escalates multiple tuple locks on a page into a single page lock, and page locks into a relation lock. However, this escalation increases the likelihood of false serialization failures, causing harmless parallel transactions to abort. Keep serializable transactions small and bounded.

8. Advanced: Comparison of Concurrency Architectures

8.1 Concurrency Models Comparison

The table below compares the performance, locking overhead, and concurrency bounds of different isolation models:

Pitfall — Over-relying on autovacuum default frequencies: Under heavy write-update loads, the default autovacuum triggers may run too infrequently. The table will grow rapidly, accumulating gigabytes of dead tuples, before autovacuum launches. Configure custom autovacuum scale factors for high-velocity update tables to prevent disk exhaustion.

9. Complete MVCC Row Visibility Engine Implementation

9.1 The JavaScript Code

The following JavaScript engine implements snapshot visibility checks, verifying if a row version can be read by a transaction:

10. Interactive: MVCC Visibility Simulator

Click "Step Visibility" to trace the MVCC visibility checker. Watch how active transaction maps block uncommitted changes from view:

Concurrency Throughput comparison

The chart below compares the throughput of transactions per second (TPS) between locking-based (2PL) and multi-version (MVCC) databases under different read/write ratios:

12. Frequently Asked Questions