Multi-Version Concurrency Control (MVCC)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

// Determining Version Visibility
// Given: Transaction T with snapshot timestamp S
//        Version V of data item with metadata
 
function is_version_visible(T: Transaction, V: Version) -> Boolean:
    // Step 1: Check if creator transaction has committed
    creator_status = get_transaction_status(V.xmin)
    
    if creator_status == ABORTED:
        return false  // Created by aborted transaction - never visible
    
    if creator_status == IN_PROGRESS:
        if V.xmin == T.id:
            return true   // Transaction sees its own uncommitted writes
        else:
            return false  // Created by another in-progress transaction
    
    // Creator committed - check if commit was before our snapshot
    if creator_status == COMMITTED:
        if V.xmin_commit_time > T.snapshot_time:
            return false  // Committed after our snapshot started
    
    // Step 2: Check if version has been superseded
    if V.xmax == 0 or V.xmax == NULL:
        return true  // Current version - not yet superseded
    
    deleter_status = get_transaction_status(V.xmax)
    
    if deleter_status == ABORTED:
        return true  // Delete was rolled back - version still valid
    
    if deleter_status == IN_PROGRESS:
        if V.xmax == T.id:
            return false  // We deleted it ourselves
        else:
            return true   // Another transaction's uncommitted delete - still visible to us
    
    if deleter_status == COMMITTED:
        if V.xmax_commit_time > T.snapshot_time:
            return true   // Deleted after our snapshot - still visible to us
        else:
            return false  // Deleted before our snapshot - not visible
    
    return false  // Should not reach here
 
// Helper: Get transaction commit status
function get_transaction_status(txn_id: TransactionID) -> Status:
    // Different implementations:
    // PostgreSQL: Check pg_xact (clog)
    // InnoDB: Check undo log headers + active transaction list
    // Oracle: Check rollback segment transaction table
    return lookup_transaction_status(txn_id)

PostgreSQL Heap-Based Version Chain (O2N)
 
Initial State - Row inserted by Txn 100:
┌────────────────────────────────────────────────────┐
│ Heap Page 1                                        │
│  ┌────────────────────────────────────────────┐    │
│  │ Tuple @ (1,1)                              │    │
│  │   xmin: 100  xmax: 0  ctid: (1,1)          │    │
│  │   data: {name: "Alice", balance: 1000}     │    │
│  └────────────────────────────────────────────┘    │
└────────────────────────────────────────────────────┘
 
After UPDATE by Txn 150 (balance = 900):
┌────────────────────────────────────────────────────┐
│ Heap Page 1                                        │
│  ┌────────────────────────────────────────────┐    │
│  │ Tuple @ (1,1)  [OLD VERSION]               │    │
│  │   xmin: 100  xmax: 150  ctid: (1,3) ──────────► to new
│  │   data: {name: "Alice", balance: 1000}     │    │
│  └────────────────────────────────────────────┘    │
│                                                    │
│  ┌────────────────────────────────────────────┐    │
│  │ Tuple @ (1,3)  [NEW VERSION - CURRENT]     │    │
│  │   xmin: 150  xmax: 0  ctid: (1,3)          │    │
│  │   data: {name: "Alice", balance: 900}      │    │
│  └────────────────────────────────────────────┘    │
└────────────────────────────────────────────────────┘
 
After another UPDATE by Txn 200 (balance = 850):
┌─────────────────────────────────────────────────────────────────┐
│ Heap Page 1                               Heap Page 2           │
│  ┌─────────────────────────────────┐       ┌─────────────────── │
│  │ (1,1) xmin:100 xmax:150 ─────────────►  │                    │
│  │       ctid:(1,3)                │    ┌──┘                    │
│  │       balance: 1000             │    │                       │
│  └─────────────────────────────────┘    ▼                       │
│  ┌─────────────────────────────────┐   (2,1) [CURRENT]          │
│  │ (1,3) xmin:150 xmax:200 ────────────► xmin:200 xmax:0        │
│  │       balance: 900              │       balance: 850         │
│  └─────────────────────────────────┘                            │
└─────────────────────────────────────────────────────────────────┘
 
Version Chain: (1,1) → (1,3) → (2,1)
                100     150     200   (Transaction IDs)

InnoDB Undo Log-Based Version Chain (N2O)
 
Initial State - Row inserted by Trx 100:
┌────────────────────────────────────────────────────┐
│ Clustered Index (Primary Key)                      │
│  ┌────────────────────────────────────────────┐    │
│  │ Row PK=1                                   │    │
│  │   DB_TRX_ID: 100                           │    │
│  │   DB_ROLL_PTR: NULL (no previous version)  │    │
│  │   data: {name: "Alice", balance: 1000}     │    │
│  └────────────────────────────────────────────┘    │
└────────────────────────────────────────────────────┘
 
After UPDATE by Trx 150 (balance = 900):
┌────────────────────────────────────────────────────┐
│ Clustered Index                                    │
│  ┌────────────────────────────────────────────┐    │
│  │ Row PK=1  [CURRENT VERSION]                │    │
│  │   DB_TRX_ID: 150                           │    │
│  │   DB_ROLL_PTR: ──────────────────────────────►  │
│  │   data: {name: "Alice", balance: 900}      │    │
│  └────────────────────────────────────────────┘    │
└────────────────────────────────────────────────────┘
                                                  │
┌─────────────────────────────────────────────────┼──┐
│ Undo Log (Rollback Segment)                     ▼  │
│  ┌────────────────────────────────────────────┐    │
│  │ Undo Record                                │    │
│  │   TRX_ID: 100                              │    │
│  │   Previous Undo: NULL                      │    │
│  │   Old values: {balance: 1000}              │    │
│  └────────────────────────────────────────────┘    │
└────────────────────────────────────────────────────┘
 
After another UPDATE by Trx 200 (balance = 850):
┌────────────────────────────────────────────────────┐
│ Clustered Index                                    │
│  ┌────────────────────────────────────────────┐    │
│  │ Row PK=1  [CURRENT VERSION]                │    │
│  │   DB_TRX_ID: 200  DB_ROLL_PTR: ─────────────────► Undo #2
│  │   data: {balance: 850}                     │    │
│  └────────────────────────────────────────────┘    │
└────────────────────────────────────────────────────┘
 
┌────────────────────────────────────────────────────┐
│ Undo Log                                           │
│  ┌────────────────────────────────────────────┐    │
│  │ Undo Record #2 (Trx 200's changes)         │    │
│  │   TRX_ID: 150                              │    │
│  │   Previous Undo: ────────────► Undo #1     │    │
│  │   Old values: {balance: 900}               │    │
│  └────────────────────────────────────────────┘    │
│  ┌────────────────────────────────────────────┐    │
│  │ Undo Record #1 (Trx 150's changes)         │    │
│  │   TRX_ID: 100                              │    │
│  │   Previous Undo: NULL                      │    │
│  │   Old values: {balance: 1000}              │    │
│  └────────────────────────────────────────────┘    │
└────────────────────────────────────────────────────┘
 
Version Chain: Current → Undo#2 → Undo#1 → (original insert)
               200       150       100

PostgreSQL HOT (Heap-Only Tuple) Update
 
Scenario: Table users (id PK, name indexed, balance NOT indexed)
UPDATE users SET balance = 900 WHERE id = 1;
 
Without HOT (indexed column change or no room in page):
┌────────────────────────────────────────┐
│ Index on 'name'                        │
│   "Alice" → (page 1, item 1) [OLD]     │
│   "Alice" → (page 2, item 5) [NEW]  ←─── New index entry needed!
└────────────────────────────────────────┘
 
With HOT (non-indexed column change, room in same page):
┌────────────────────────────────────────┐
│ Index on 'name'                        │
│   "Alice" → (page 1, item 1)           │  ← Index unchanged!
└────────────────────────────────────────┘
                    │
                    ▼
┌────────────────────────────────────────┐
│ Heap Page 1                            │
│  ┌──────────────────────────────┐      │
│  │ Item 1 (OLD - HEAP ONLY)     │      │
│  │   xmax: 150                  │      │
│  │   t_ctid: (1, 3) ──────────────────►│
│  └──────────────────────────────┘      │
│  ┌──────────────────────────────┐      │
│  │ Item 3 (NEW - CURRENT)       │      │
│  │   xmax: 0                    │      │
│  │   HEAP_ONLY flag set         │  ← Not directly indexed
│  └──────────────────────────────┘      │
└────────────────────────────────────────┘
 
HOT chain pruning: When page is accessed, old HOT versions
can be immediately reclaimed without full VACUUM.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

// Version Lifecycle State Machine
 
enum VersionState {
    IN_PROGRESS,    // Created by active transaction
    COMMITTED,      // Creating transaction committed - visible to new transactions
    OBSOLETE,       // Superseded and no longer needed by any transaction
    RECLAIMED       // Space has been reclaimed by GC
}
 
class Version {
    state: VersionState = IN_PROGRESS
    created_by: Transaction
    superseded_by: Transaction = null
    
    // Transition: IN_PROGRESS → COMMITTED
    on_creator_commit():
        this.state = COMMITTED
        // Version now visible to new transactions starting after commit
    
    // Transition: COMMITTED → OBSOLETE
    on_obsolescence_detected():
        // Happens when:
        // 1. superseded_by has committed, AND
        // 2. oldest_active_snapshot > max(created_by.commit_time, superseded_by.commit_time)
        this.state = OBSOLETE
        // Version can now be garbage collected
    
    // Transition: OBSOLETE → RECLAIMED
    on_garbage_collection():
        // PostgreSQL: VACUUM removes tuple, updates visibility map, FSM
        // InnoDB: Purge thread frees undo log record
        this.state = RECLAIMED
        free_storage(this)
}
 
// Determining if version is obsolete
function is_version_obsolete(v: Version) -> Boolean:
    if v.state != COMMITTED:
        return false
    
    if v.superseded_by == null:
        return false  // Still the current version
    
    if not v.superseded_by.is_committed():
        return false  // Newer version not yet permanent
    
    oldest_snapshot = get_oldest_active_snapshot_timestamp()
    
    // If oldest active snapshot started after the superseder committed,
    // no one can ever need this version again
    return oldest_snapshot > v.superseded_by.commit_time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

-- PostgreSQL VACUUM Operations
 
-- Standard VACUUM: reclaims dead tuple space within table
VACUUM my_table;
-- Table size may not shrink - space is marked reusable
-- Fast, doesn't lock the table for writes
 
-- VACUUM ANALYZE: reclaims space AND updates statistics
VACUUM ANALYZE my_table;
-- Critical for query planner to make good decisions
 
-- VACUUM FULL: rewrites entire table, returns space to OS
VACUUM FULL my_table;
-- Requires exclusive lock - blocks reads and writes!
-- Use only when significant space reclamation needed
 
-- Check vacuum stats for a table
SELECT 
    schemaname,
    relname,
    n_live_tup,
    n_dead_tup,
    n_dead_tup::float / NULLIF(n_live_tup + n_dead_tup, 0) as dead_ratio,
    last_vacuum,
    last_autovacuum,
    last_analyze,
    vacuum_count,
    autovacuum_count
FROM pg_stat_user_tables 
WHERE relname = 'my_table';
 
-- Autovacuum configuration parameters
-- autovacuum_vacuum_threshold = 50 (minimum dead tuples before vacuum)
-- autovacuum_vacuum_scale_factor = 0.2 (fraction of table that must be dead)
-- autovacuum_naptime = 1min (sleep time between runs)
 
-- A table with 100,000 rows triggers autovacuum when:
-- dead_tuples > 50 + (0.2 * 100,000) = 20,050 dead tuples
 
-- Monitoring for bloat
SELECT 
    current_setting('autovacuum_vacuum_scale_factor') as scale_factor,
    current_setting('autovacuum_vacuum_threshold') as threshold;
 
-- Check for tables needing vacuum
SELECT 
    schemaname || '.' || relname as table_name,
    n_dead_tup as dead_tuples,
    n_live_tup as live_tuples,
    n_dead_tup::float / NULLIF(n_live_tup, 0) * 100 as dead_percentage,
    last_autovacuum
FROM pg_stat_user_tables
WHERE n_dead_tup > 1000
ORDER BY n_dead_tup DESC;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

-- PostgreSQL: Analyzing version storage overhead
 
-- Calculate table bloat estimate
SELECT
    schemaname,
    relname,
    pg_size_pretty(pg_total_relation_size(relid)) as total_size,
    pg_size_pretty(pg_relation_size(relid)) as table_size,
    pg_size_pretty(pg_indexes_size(relid)) as indexes_size,
    n_live_tup,
    n_dead_tup,
    ROUND(
        n_dead_tup::numeric / NULLIF(n_live_tup + n_dead_tup, 0) * 100, 2
    ) as dead_pct,
    -- Estimate actual data size vs allocated
    ROUND(
        (n_live_tup * 100)::numeric / 
        (pg_relation_size(relid) / 8192.0 * 200), 2  -- Assume 200 rows/page at fill factor
    ) as fill_efficiency_pct
FROM pg_stat_user_tables
WHERE schemaname = 'public'
ORDER BY pg_total_relation_size(relid) DESC;
 
-- More accurate bloat calculation using pgstattuple
CREATE EXTENSION IF NOT EXISTS pgstattuple;
 
SELECT 
    table_len,
    tuple_count,
    tuple_len,
    dead_tuple_count,
    dead_tuple_len,
    free_space,
    free_percent
FROM pgstattuple('my_table');
 
-- InnoDB: Check undo tablespace usage
-- (Run in MySQL/MariaDB)
-- SHOW ENGINE INNODB STATUS;  -- Look for "History list length"
-- 
-- SELECT
--     TOTAL_EXTENTS * 1048576 / 1024 / 1024 as undo_mb
-- FROM INFORMATION_SCHEMA.FILES
-- WHERE FILE_TYPE = 'UNDO LOG';