Database Series : MVCC

DB Series Core Concept Part 4: Let Readers Read, Writers Write — At the Same Time

Multi-Version Concurrency Control is a database technique that maintains multiple versions of data to enable concurrent access without traditional locking. It’s the foundation of modern database performance, allowing readers and writers to operate simultaneously without blocking each other.

Why MVVC Matters

Modern applications require:

• High throughput (millions of transactions/second)
• Low latency (millisecond response times)
• Strong consistency (ACID guarantees)
• Concurrent read-write workloads

MVVC enables all four simultaneously. Without it, traditional locking would create severe bottlenecks in concurrent systems.

Core Concepts

Version Chains

Every row of data maintains a chain of versions:

Current Version (Latest)
    ↓ (pointer)
Previous Version
    ↓ (pointer)
Earlier Version
    ↓ (pointer)
Original Version

Each version stores:

• User data (the actual column values)
• Version metadata (who created/deleted it, when)
• Pointers (links to other versions in the chain)

Snapshot Isolation

When a transaction starts, it receives a snapshot — a consistent view of the database at that moment. The snapshot determines which versions are visible to that transaction.

Key principle: A transaction’s snapshot never changes during its lifetime. All queries within that transaction see the same data, preventing non-repeatable reads and phantom reads.

Transaction Visibility

Each transaction sees versions based on its snapshot:

• Visible: Versions committed before the transaction’s snapshot
• Invisible: Versions created after the transaction’s snapshot
• To access older versions: Follow pointers to previous versions in the chain

Database Implementations

Let me show how three major databases implement MVVC differently:

MySQL InnoDB: Detailed Architecture

How MySQL Stores Versions

MySQL embeds version metadata directly in every row:

[User Data] [DB_TRX_ID] [DB_ROLL_PTR]
   ↓           ↓              ↓
 Columns   Transaction    Pointer to
           that modified  undo log entry
           this version   (previous version)

The Read View Snapshot

When a MySQL transaction starts, it creates a Read View:

Read View {
  low_limit_id = 100,           # Lowest active TX
  up_limit_id = 110,            # Next TX to assign
  active_trx_list = [105, 108]  # Currently active TXs
}

Visibility Algorithm

A row is visible if ALL three conditions are true:

1. DB_TRX_ID < up_limit_id (110)
   The row was modified before the snapshot cutoff

2. DB_TRX_ID is committed
   The modifying transaction completed successfully

3. DB_TRX_ID NOT in active_trx_list [105, 108]
   The modifying transaction is not currently open

If not visible: Follow DB_ROLL_PTR pointer to the undo log, check the older version.

Example: MySQL Version Chain

Initial row: id=1, balance=1000
Metadata: DB_TRX_ID=105

TX107 updates balance → 900:
  Create undo log entry
  Link: 105 → 107 (pointer)

TX110 updates balance → 800:
  Create another undo log entry
  Link: 107 → 110 (pointer)
Version chain: 110 (current) → 107 → 105 (oldest)
Reader with snapshot up_limit_id=109:
  Check 110: 110 >= 109 → skip
  Check 107: 107 < 109 ✓, committed ✓, NOT in active ✓ → VISIBLE!
  Return: balance=900

MySQL Garbage Collection

Key advantage: Automatic and continuous

Process:
1. Background purge thread monitors active transactions
2. Finds minimum active TX ID
3. Removes undo entries older than this TX
4. Space reclaimed immediately to tablespace

Drawback: Long transactions block purge
→ Undo tablespace grows unbounded
→ Can exhaust server memory

PostgreSQL: Detailed Architecture

How PostgreSQL Stores Versions

PostgreSQL doesn’t use undo logs. Instead, versions are actual heap tuples on disk:

Heap Tuple Format:
[User Data] [xmin] [xmax] [Pointer to newer]
   ↓         ↓      ↓           ↓
 Columns  Creator Deleter    Next version
          TX ID   TX ID      in chain

Snapshot Structure

Snapshot {
  xmin = 100,
  xmax = 110,
  active_txs = [105, 108, 109]
}

The Four-Part Visibility Rule

A tuple is visible ONLY IF ALL four are true:

1. xmin is committed
   The creating transaction finished

2. xmin < snapshot.xmax (110)
   Row created before snapshot cutoff

3. xmin NOT in snapshot.active_txs [105, 108, 109]
   Creator is not currently open

4. AND (xmax is null OR xmax not committed)
   Row not deleted, OR deletion not committed

Example Of Visibility

Initial tuple: id=1, balance=1000
Metadata: xmin=105, xmax=null
(Created by TX105, not deleted)

TX107 updates balance → 900:
  Old tuple marked: xmin=105, xmax=107
  New tuple created: xmin=107, xmax=null

TX110 updates balance → 800:
  Previous tuple marked: xmin=107, xmax=110
  New tuple created: xmin=110, xmax=null

Heap contains three tuples:
  Tuple 1: xmin=105, xmax=107, balance=1000 (dead)
  Tuple 2: xmin=107, xmax=110, balance=900 (dead)
  Tuple 3: xmin=110, xmax=null, balance=800 (current)

Reader with snapshot (xmin=100, xmax=109, active_txs=[105,108,109]):

Check Tuple 3 (xmin=110, xmax=null):
  1. xmin (110) committed? YES ✓
  2. xmin (110) < snapshot_xmax (109)? NO ✗ → SKIP

Check Tuple 2 (xmin=107, xmax=110):
  1. xmin (107) committed? YES ✓
  2. xmin (107) < snapshot_xmax (109)? YES ✓
  3. xmin (107) in active_txs [105,108,109]? NO ✓
  4. (xmax (110) is null OR not committed)? 110 committed ✗ → SKIP

Check Tuple 1 (xmin=105, xmax=107):
  1. xmin (105) committed? YES ✓
  2. xmin (105) < snapshot_xmax (109)? YES ✓
  3. xmin (105) in active_txs [105,108,109]? YES ✗ → SKIP

No visible tuple found!
Reader must reconstruct from older tuples or sees no row.

Note: If active_txs=[108,109] (105 NOT active):
  Tuple 1 passes all 4 checks:
  1. xmin (105) committed? YES ✓
  2. xmin (105) < snapshot_xmax (109)? YES ✓
  3. xmin (105) NOT in active_txs [108,109]? YES ✓
  4. xmax (107) committed? YES, but xmax not null ✗
  → Still SKIP (row was deleted by TX107)

If snapshot is (xmin=100, xmax=108, active_txs=[]):
  Tuple 1 is VISIBLE:
  1. xmin (105) committed? YES ✓
  2. xmin (105) < snapshot_xmax (108)? YES ✓
  3. xmin (105) NOT in active_txs []? YES ✓
  4. xmax (107) is committed? YES, but checking: xmax < snapshot_xmax (108)? YES ✓
  → VISIBLE! Return: balance=1000

HOT (Heap-Only Tuple) Optimization

PostgreSQL’s unique performance feature:

Update name (indexed):
  → Must update index
  → Overhead

Update salary (non-indexed):
  → HOT update (new tuple on same page)
  → No index update needed
  → 5-10x faster!

This is why PostgreSQL performs well for update-heavy workloads with non-key column modifications.

PostgreSQL Garbage Collection

Manual with automatic option:

Process:
1. VACUUM daemon scans table periodically
2. Marks dead tuples (xmax set) for reuse
3. VACUUM FULL compacts (rewrites entire table)

Problem: Dead tuples remain on disk
→ Table bloat (can grow 10x)
→ Need regular monitoring
→ Requires tuning autovacuum parameters

ScyllaDB: Unique Architecture

Per-Cell Versioning (NOT Row-Level)

This is fundamentally different from MySQL/PostgreSQL:

Row: user_id=1
name:  {timestamp: 1000, value: 'Alice'}
       {timestamp: 950, value: 'Al'}
email: {timestamp: 1050, value: 'alice@ex.com'}
       {timestamp: 1020, value: 'alice@email.com'}
age:   {timestamp: 900, value: 25}
Key difference: Different columns have different timestamps!
(NOT a transactional snapshot)

Last-Write-Wins (LWW) Principle

When reading:
  - Latest timestamp wins automatically
  - No snapshot concept
  - Different cells may have different ages

Example read:
  name: latest = 1000 → returns 'Alice'
  email: latest = 1050 → returns 'alice@ex.com'
  age: only = 900 → returns 25

Result row mixes different timestamp versions!
(Acceptable for eventual consistency systems)

Critical Difference: No Transactions

MySQL/PostgreSQL:
  ✓ ACID transactions
  ✓ Snapshot isolation
  ✓ Consistent row views

ScyllaDB:
  ✗ NO ACID transactions
  ✗ NO snapshot isolation
  ✗ Per-cell Last-Write-Wins
  → Eventual consistency model

ScyllaDB Garbage Collection

Automatic and distributed:

Process:
1. Set TTL (time-to-live) on data
2. Compaction process runs independently on each node
3. Expired cells removed automatically
4. No central coordinator needed

Advantage: Scales linearly with cluster size
Drawback: Eventual consistency by default

Version Visibility Rules

Let me show the corrected visibility rules for all three databases:

Conflict Detection & Resolution

When two transactions modify the same row, what happens?

Optimistic Locking (PostgreSQL, MySQL)

Strategy: Assume conflicts are rare, detect at commit time

TX1: READ account (balance=1000)
TX2: READ account (balance=1000)

TX1: UPDATE balance=900, COMMIT ✓
TX2: UPDATE balance=800, COMMIT ?

At TX2 commit:
  Validation: Did anyone else modify account since my snapshot?
  Result: YES (TX1 did)
  Action: ROLLBACK TX2

Application must retry TX2

Pros: Low overhead for read-heavy workloads Cons: High-contention workloads = many rollbacks

Pessimistic Locking (InnoDB)

Strategy: Acquire locks upfront, prevent conflicts

TX1: Lock account
TX2: Attempts account → BLOCKS

TX1: UPDATE balance=900, COMMIT, release lock
TX2: Acquires lock, continues
TX2: UPDATE balance=800, COMMIT ✓

Result: Both succeed, serialized order guaranteed

Pros: No rollbacks, guaranteed success Cons: Lock contention reduces concurrency

Garbage Collection Deep Dive

Let me show how each database cleans up old versions:

Phantom Reads & Snapshot Isolation

The Phantom Read Problem

TX1: SELECT COUNT(*) FROM users WHERE age > 30
     Returns: 5 users (Alice, Bob, Charlie, Diana, Eve)

TX2: INSERT users (name='Frank', age=35)
TX1: SELECT COUNT(*) FROM users WHERE age > 30
     Returns: 6 users (Frank appeared!)

Frank is a “phantom” — appeared mid-transaction.

How MVVC Prevents Phantoms

Snapshot isolation prevents phantoms automatically:

TX1 starts: Snapshot captured
  Visible TXs: {1, 2, 3, 4, 5}
TX1 queries:  SELECT * WHERE age > 30
  Returns rows from visible TXs
TX2 inserts:  (created by TX6, outside snapshot)
  Frank inserted by TX6
TX1 re-queries: Same condition, same snapshot
  TX6 row INVISIBLE (6 > snapshot cutoff)
  Returns identical results

Key insight: Snapshot remains fixed. New inserts after snapshot are invisible.

Index Management with MVVC

MySQL: Indexes Point to Primary Key

PRIMARY KEY (id):
  id=1 → Row versions in undo chain

SECONDARY INDEX (name):
  'Alice' → points to id=1
  'Alicia' → points to id=1 (new entry for new version)
Update name:
  Both index entries exist
  Lookup finds correct version

Cost: Every column update may require index updates

PostgreSQL: HOT Optimization

Update indexed column (name):
  → Normal update, index must change

Update non-indexed column (salary):
  → HOT eligible
  → New version on same heap page
  → NO index update needed
  → 5-10x faster!

Isolation Levels & Trade-offs

Let me create a comprehensive comparison:

Performance Implications

Issue 1: Version Chain Traversal

Row updated 1000 times = 1000 versions in chain
Old reader (snapshot=100) searches chain:
  v1000 → v999 → ... → v200 (finally visible!)

Cost: O(n) lookups, CPU overhead
  1000 chain traversals per read!

Issue 2: Table Bloat (PostgreSQL)

Timeline:
  Day 1: 100 MB table
  Week 1: 1 million updates (no VACUUM): 1000 MB

Why: Dead tuples remain on disk
     Sequential scans = 10x slower

Issue 3: Long Transactions Block GC

TX runs 10 hours:
  All undo/versions created during must be retained
  Undo log grows unbounded
  System runs out of memory

Issue 4: Read-Write Scaling (MVVC’s Superpower)

Without MVVC: Readers block writers, writers block readers → 1000 ops/sec With MVVC: Readers and writers run in parallel → 100,000+ ops/sec

10–100x throughput improvement!

Complete Feature Comparison

Conclusion: Why MVVC Matters

The Revolution MVVC Enabled

Without MVVC, modern databases couldn’t exist. Traditional locking would create severe bottlenecks:

Without MVVC (Traditional Locking):
  100 concurrent readers + 10 writers
  → Readers lock rows
  → Writers wait
  → Writers lock rows
  → Readers wait
  → Throughput: ~1000 ops/sec (limited by locks)
  → CPU: 10% utilized (mostly waiting)

With MVVC:
  Same workload
  → Readers see snapshots (no locks)
  → Writers create versions (non-blocking)
  → Both run in parallel
  → Throughput: 100,000+ ops/sec (linear scaling)
  → CPU: 95% utilized (doing real work)

Result: 100x throughput improvement

Choosing Your Database

MySQL InnoDB:

• When: OLTP applications requiring strong consistency
• Why: Automatic GC, REPEATABLE READ default, mature
• Trade-off: More complex internals (Read View, undo logs)

PostgreSQL:

• When: Complex queries, complex schemas, flexibility
• Why: HOT optimization, advanced features, powerful SQL
• Trade-off: Manual VACUUM management, table bloat risk

ScyllaDB:

• When: Time-series data, massive scale, eventual consistency acceptable
• Why: Horizontal scaling, automatic TTL-based GC, distributed
• Trade-off: No ACID transactions, eventual consistency, different model

Complete MVVC Overview

Summary

Multi-Version Concurrency Control (MVCC) is a database technique that maintains multiple versions of data to enable concurrent access without traditional locking mechanisms. At its core, MVCC allows readers to access historical snapshots of data while writers simultaneously create new versions, eliminating blocking and dramatically improving throughput. When a transaction starts, it receives a snapshot — a consistent view of the database at that moment — which determines which row versions it can see based on visibility rules that compare transaction IDs or timestamps against the snapshot information. MySQL InnoDB implements MVCC using a Read View structure with DB_TRX_ID and an active transaction list, storing older versions in undo logs that are continuously purged by a background thread. PostgreSQL stores versions as heap tuples directly on disk with xmin/xmax fields and enforces a four-part visibility rule; it optimizes non-key column updates through Heap-Only Tuples (HOT) to avoid index maintenance. ScyllaDB takes a fundamentally different approach with per-cell timestamps and Last-Write-Wins semantics, enabling automatic, distributed TTL-based garbage collection without transactional overhead. Each database handles conflicts differently — some use optimistic locking (detect conflicts at commit) while others use pessimistic locking (prevent conflicts upfront) — and all prevent anomalies like phantom reads through snapshot isolation, where new inserts after a transaction’s snapshot remain invisible. Garbage collection is critical: MySQL’s continuous purge reclaims space immediately but is blocked by long transactions, PostgreSQL requires manual VACUUM which risks table bloat, and ScyllaDB automatically expires data based on TTL. The choice of isolation level (READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, or SERIALIZABLE) trades consistency for concurrency — higher levels prevent more anomalies but reduce parallelism. MVCC’s fundamental advantage is lock-free concurrency: 100 concurrent readers and 10 writers achieve 100,000+ operations per second with MVCC versus only ~1,000 ops/sec with traditional locking, delivering 10–100x throughput improvements. Understanding MVCC’s mechanics across databases is essential for designing systems that balance strong consistency with high performance and scalability.

Thank you for reading until the end. Before you go:

• Please consider clapping and following the writer! 👏
• Connect me on **LinkedIn**