Multi-Version Concurrency Control (MVCC)

Snapshot Isolation is the core guarantee of MVCC. Each transaction operates on a consistent snapshot of the database as it existed at the transaction's start time. This means:

• Readers never block writers, and writers never block readers.
• Transactions see a static view of committed data, unaffected by concurrent modifications.
• This is crucial for long-running analytical queries that require a stable point-in-time view while the underlying data is being updated.

MVCC requires a mechanism to store and manage multiple data item versions. Common implementations include:

• Append-Only Storage: New versions are written to new storage locations (e.g., new table rows or disk pages). The previous version remains intact for ongoing readers.
• Version Chains: Each row has a header pointing to a linked list of its historical versions, often stored in a rollback segment or undo log.
• Garbage Collection (Vacuuming): A critical background process that identifies and removes dead versions—those no longer needed by any active transaction snapshot—to reclaim storage.

Every transaction is assigned a unique, monotonically increasing Transaction ID (XID). Each data version is tagged with:

• xmin: The XID of the transaction that created this version.
• xmax: The XID of the transaction that deleted or superseded this version (if any). A version is visible to a transaction if:
• The creating transaction (xmin) was committed before the snapshot was taken.
• The deleting transaction (xmax) is either uncommitted or committed after the snapshot was taken. This metadata enables the system to reconstruct the correct snapshot for any transaction.

While MVCC eliminates read-write conflicts, write-write conflicts must still be detected and resolved. This occurs when two concurrent transactions attempt to modify the same data item. Common resolution strategies include:

• First-Committer-Wins: The system detects a conflict if a transaction tries to commit a change to a row that has been updated by another already-committed transaction since its snapshot began. The later committer is typically aborted and must retry.
• This mechanism is a form of Optimistic Concurrency Control (OCC), where conflicts are resolved at commit time rather than prevented upfront with locks.

MVCC is the standard implementation for high Isolation Levels in modern databases like PostgreSQL and Oracle:

• Read Committed (Default): Each statement in a transaction sees a snapshot of data committed before the statement began. This can lead to non-repeatable reads.
• Repeatable Read / Snapshot Isolation: The entire transaction sees a snapshot from its start. This prevents non-repeatable reads and phantom reads in many cases.
• Serializable: Uses additional predicate locking or serializable snapshot isolation (SSI) algorithms on top of MVCC to detect and abort transactions that would violate serializable execution, providing the strongest guarantee.

MVCC provides significant performance and scalability benefits compared to pessimistic locking schemes:

• High Read Scalability: Analytical and reporting workloads can run concurrently with heavy write loads.
• Eliminates Deadlocks: Since readers don't take locks, many common deadlock scenarios are avoided.
• Reduced Lock Overhead: The database manages version visibility instead of a centralized lock manager for reads. The trade-off is increased storage overhead for version history and CPU cost for visibility checks and garbage collection.

A concurrency control strategy where transactions proceed without acquiring locks, assuming conflicts are rare. Conflicts are detected at commit time via validation. If a conflict is detected (e.g., a read item was modified by another transaction), the transaction is rolled back and must be retried.

• Key Mechanism: Uses read and write sets for validation.
• Contrast with MVCC: OCC typically has a single "current" version and aborts on conflict; MVCC maintains multiple versions to allow readers to proceed without aborting writers.
• Use Case: High-contention scenarios where rollback costs are acceptable.

A conflict prevention strategy that uses locks (e.g., read/write locks) to guarantee exclusive access to resources. It assumes conflicts are likely and prevents them by blocking conflicting transactions.

• Key Mechanism: Two-Phase Locking (2PL) is a common protocol.
• Contrast with MVCC: Eliminates the overhead of maintaining multiple versions but can lead to reader-writer blocking and reduced throughput.
• Use Case: Systems where data consistency is paramount and contention patterns are predictable.

A data structure designed for distributed systems that can be replicated across many agents. Concurrent updates can be applied independently and merged later without coordination, guaranteeing eventual consistency. Operations are commutative, associative, and idempotent.

• Key Mechanism: State-based (convergent) or operation-based (commutative).
• Relation to MVCC: Both aim for high availability. CRDTs resolve conflicts at the data type level for eventual consistency; MVCC provides stronger snapshot isolation for immediate consistency within a node.
• Use Case: Collaborative applications, distributed counters, sets.

A logical timestamp mechanism used in distributed systems to capture causal relationships between events. Each agent maintains a vector of counters, one for each node in the system.

• Key Mechanism: On an event, an agent increments its own counter. Vectors are attached to messages and merged on receipt.
• Relation to MVCC: While MVCC uses timestamps or transaction IDs for version ordering, vector clocks can determine if versions are concurrent (causally unrelated), which is crucial for conflict detection in eventually consistent systems.
• Use Case: Detecting concurrent updates, version staleness, and causal consistency.

A transaction isolation level that provides each transaction with a consistent snapshot of the database as of the start of the transaction. It guarantees that all reads see the same snapshot, and the transaction commits only if its writes do not conflict with any concurrent updates made since that snapshot.

• Key Mechanism: MVCC is the primary implementation technique for Snapshot Isolation.
• Write Skew: A known anomaly under Snapshot Isolation where two concurrent transactions read overlapping data, make disjoint updates, and both commit, leading to an inconsistent state.
• Use Case: The standard isolation level for many MVCC-based databases (e.g., PostgreSQL's REPEATABLE READ, Oracle, SQL Server).

ACID (Atomicity, Consistency, Isolation, Durability) defines the guarantees of a database transaction. Isolation is specifically managed by concurrency control methods like MVCC.

• Isolation Levels: Define the visibility of concurrent transactions' effects. MVCC enables higher levels like Read Committed and Snapshot Isolation without pervasive locking.
• Levels: Read Uncommitted, Read Committed (common MVCC default), Repeatable Read (often Snapshot Isolation), Serializable.
• Relation: MVCC is an implementation strategy to achieve specific isolation levels while balancing performance and consistency.