Read Consistency

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

// Snapshot Structure
 
class Snapshot {
    // The transaction ID when this snapshot was created
    snapshot_xid: TransactionID
    
    // Transaction IDs that were active (uncommitted) when snapshot was taken
    // Versions from these transactions are NOT visible
    active_txns: Set<TransactionID>
    
    // Minimum active transaction ID at snapshot time
    // Any transaction ID less than this has definitely completed
    xmin: TransactionID
    
    // Maximum transaction ID at snapshot time
    // Any transaction ID greater than this started after the snapshot
    xmax: TransactionID
}
 
// Snapshot Creation (at transaction begin or first read)
function create_snapshot() -> Snapshot:
    snapshot = new Snapshot()
    
    // Get current transaction state atomically
    with global_transaction_lock:
        snapshot.snapshot_xid = get_current_transaction_id()
        snapshot.xmax = next_transaction_id()
        snapshot.active_txns = get_all_active_transaction_ids()
        snapshot.xmin = min(snapshot.active_txns) if not empty else snapshot.xmax
    
    return snapshot
 
// Example snapshot state at a point in time:
// 
// Committed transactions: 100, 101, 102, 104, 105
// Active transactions: 103, 107, 108
// Next transaction ID: 110
//
// Snapshot taken by transaction 109:
// {
//     snapshot_xid: 109,
//     xmin: 103,
//     xmax: 110,
//     active_txns: {103, 107, 108}
// }
//
// Visibility:
// - Txn 100, 101, 102, 104, 105: visible (committed before snapshot)
// - Txn 103: NOT visible (active at snapshot time)
// - Txn 106: visible (committed, not in active set)
// - Txn 107, 108: NOT visible (active at snapshot time)
// - Txn 110+: NOT visible (started after snapshot)

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

// MVCC Visibility Algorithm (PostgreSQL-style)
// Determines if a tuple version is visible to a snapshot
 
function HeapTupleSatisfiesMVCC(tuple: HeapTuple, snapshot: Snapshot) -> Boolean:
    xmin = tuple.xmin  // Transaction that created this tuple
    xmax = tuple.xmax  // Transaction that deleted/updated this tuple (0 if current)
    
    // ========================================
    // STEP 1: Check creator transaction (xmin)
    // ========================================
    
    // Case 1A: Created by our own transaction
    if xmin == current_transaction_id():
        if tuple.cmin >= current_command_id():
            return false  // Created by later command in same transaction
        
        // We created it in an earlier command
        if xmax == 0:
            return true   // We created it, not yet deleted
        
        // Check if we also deleted it
        if xmax == current_transaction_id():
            if tuple.cmax >= current_command_id():
                return true   // Deleted by later command - still visible
            else:
                return false  // Deleted by earlier command
        
        // Deleted by another transaction (which must have aborted)
        // since concurrent transactions can't delete our uncommitted rows
        return true
    
    // Case 1B: Created by another transaction
    if not is_xmin_committed(xmin, snapshot):
        // Creator was active or aborted at snapshot time
        return false
    
    // Creator committed before our snapshot
    
    // ========================================
    // STEP 2: Check deleter transaction (xmax)
    // ========================================
    
    if xmax == 0 or xmax == INVALID_TRANSACTION_ID:
        return true  // Not deleted - definitely visible
    
    // Case 2A: Deleted by our own transaction
    if xmax == current_transaction_id():
        if tuple.cmax >= current_command_id():
            return true   // Deleted by later command - still visible to us
        else:
            return false  // Deleted by earlier command - not visible
    
    // Case 2B: Deleted by another transaction
    if not is_xmax_committed(xmax, snapshot):
        // Deleter was active or aborted at snapshot time
        return true   // Deletion not visible - tuple is visible
    
    // Deleter committed - tuple is not visible
    return false
 
// Helper: Check if xmin transaction is "committed" from snapshot's perspective
function is_xmin_committed(xmin: TransactionID, snapshot: Snapshot) -> Boolean:
    // Quick check: if xmin < snapshot.xmin, it's definitely committed
    if xmin < snapshot.xmin:
        return true
    
    // If xmin >= snapshot.xmax, it started after snapshot
    if xmin >= snapshot.xmax:
        return false
    
    // xmin is in the range [xmin, xmax) - check active list
    if xmin in snapshot.active_txns:
        return false  // Was active at snapshot time - not visible
    
    // Check actual commit status in transaction log
    status = get_transaction_status(xmin)
    return status == COMMITTED
 
// Similar logic for is_xmax_committed...

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

// InnoDB Read View Visibility Check (Simplified)
 
struct ReadView {
    trx_id_t m_low_limit_id;   // Transactions >= this started after read view
    trx_id_t m_up_limit_id;    // Transactions < this completed before read view
    std::vector<trx_id_t> m_ids;  // Active transactions at read view creation
    trx_id_t m_creator_trx_id;    // Transaction that owns this read view
};
 
// Check if a transaction's changes are visible to this read view
bool changes_visible(const ReadView* view, trx_id_t id) {
    // 1. Our own transaction's changes are always visible
    if (id == view->m_creator_trx_id) {
        return true;
    }
    
    // 2. Transaction IDs < m_up_limit_id completed before our read view
    if (id < view->m_up_limit_id) {
        return true;
    }
    
    // 3. Transaction IDs >= m_low_limit_id started after our read view
    if (id >= view->m_low_limit_id) {
        return false;
    }
    
    // 4. Transaction ID is in the ambiguous range - check active list
    // Binary search since m_ids is sorted
    return !std::binary_search(view->m_ids.begin(), view->m_ids.end(), id);
}
 
// Reading a row: may need to traverse undo log
Record read_row_mvcc(const ReadView* view, const Record* latest) {
    Record* current = latest;
    
    while (current != nullptr) {
        trx_id_t creator = current->get_trx_id();
        
        if (changes_visible(view, creator)) {
            // This version was created by a visible transaction
            
            // Check if it's a delete marker
            if (current->is_delete_marked()) {
                return NOT_FOUND;  // Row was deleted
            }
            
            return *current;  // This is the visible version
        }
        
        // This version is not visible - go back in history
        current = current->get_older_version_from_undo_log();
    }
    
    // No visible version found - row didn't exist for this read view
    return NOT_FOUND;
}
 
/*
Example Read View:
  m_low_limit_id: 110
  m_up_limit_id: 103
  m_ids: [103, 107, 108]  // Active at read view creation
  m_creator_trx_id: 109
 
Visibility decisions:
  trx_id = 100: visible (100 < 103, completed before read view)
  trx_id = 103: NOT visible (in m_ids, was active)  
  trx_id = 105: visible (103 <= 105 < 110, not in m_ids)
  trx_id = 107: NOT visible (in m_ids, was active)
  trx_id = 109: visible (it's our own transaction)
  trx_id = 110: NOT visible (>= m_low_limit_id, started after)
*/

Scenario: Dirty Read Prevention with MVCC
 
Time    T1 (Txn 100)                T2 (Txn 101)
────────────────────────────────────────────────────────────────
 1      BEGIN
 2      UPDATE accounts SET         
        balance = 500 
        WHERE id = 1
        (Creates version with xmin=100)
 
 3                                  BEGIN
                                    Snapshot: {active: [100], xmax: 102}
 
 4                                  SELECT balance FROM accounts WHERE id = 1
                                    
                                    Version xmin=100:
                                    - Is 100 in active set? YES
                                    - Therefore: NOT VISIBLE
                                    
                                    Previous version xmin=99 (committed):
                                    - Is 99 < snapshot.xmin? YES
                                    - Therefore: VISIBLE
                                    
                                    Result: Returns OLD balance (e.g., 1000)
                                    ✅ Dirty read prevented!
 
 5      ROLLBACK                    
        (T1 aborts - change discarded)
        
 6                                  SELECT balance FROM accounts WHERE id = 1
                                    Result: Still 1000 (correct - T1 rolled back)
                                    
Without MVCC (if T2 saw uncommitted value):
  Step 4 would return 500 (WRONG!)
  Step 6 would see 1000 back - inconsistent!

Scenario: Non-Repeatable Read Prevention at REPEATABLE READ
 
Time    T1 (Txn 100)                T2 (Txn 101)
────────────────────────────────────────────────────────────────
 1      BEGIN ISOLATION LEVEL
        REPEATABLE READ
        Snapshot taken: {active: [], xmax: 101}
        
 2      SELECT balance FROM accounts WHERE id = 1
        Visible version: balance = 1000 (xmin=99, committed)
        Result: 1000
 
 3                                  BEGIN
 
 4                                  UPDATE accounts SET balance = 500 WHERE id = 1
                                    (Creates new version xmin=101)
                                    
 5                                  COMMIT
                                    (Version xmin=101 now committed)
 
 6      SELECT balance FROM accounts WHERE id = 1
        
        New version xmin=101:
        - Is 101 >= snapshot.xmax (101)? YES
        - Therefore: NOT VISIBLE (started after our snapshot)
        
        Old version xmin=99:
        - Is 99 < snapshot.xmax? YES
        - Is 99 in active set? NO
        - Therefore: VISIBLE
        
        Result: 1000 (same as before!)
        ✅ Repeatable read achieved!
 
 7      COMMIT
 
Without MVCC snapshot:
  Step 6 would return 500 (different from step 2!)
  = Non-repeatable read

Scenario: Phantom Prevention with Snapshot Isolation
 
Time    T1 (Txn 100)                T2 (Txn 101)
────────────────────────────────────────────────────────────────
 1      BEGIN ISOLATION LEVEL 
        REPEATABLE READ
        Snapshot: {active: [], xmax: 101}
        
 2      SELECT COUNT(*) FROM accounts WHERE balance > 1000
        Finds: Account #1 (balance 1500), Account #2 (balance 2000)
        Result: 2 rows
 
 3                                  BEGIN
 
 4                                  INSERT INTO accounts (id, balance) 
                                    VALUES (3, 3000)
                                    (New row with xmin=101)
                                    
 5                                  COMMIT
 
 6      SELECT COUNT(*) FROM accounts WHERE balance > 1000
        
        Scanning all rows:
        - Account #1: xmin=99 < 101 → VISIBLE, balance 1500 ✓
        - Account #2: xmin=98 < 101 → VISIBLE, balance 2000 ✓
        - Account #3: xmin=101 >= snapshot.xmax → NOT VISIBLE ✗
        
        Result: 2 rows (same as before!)
        ✅ Phantom read prevented!

Write Skew Anomaly (NOT Prevented by Standard Snapshot Isolation)
 
Constraint: At least one doctor must be on-call
Initial: doctor_1.on_call = true, doctor_2.on_call = true
 
Time    T1 (Doctor 1)                    T2 (Doctor 2)
────────────────────────────────────────────────────────────────────
 1      BEGIN REPEATABLE READ            BEGIN REPEATABLE READ
        Snapshot: xmax=100                Snapshot: xmax=100
 
 2      SELECT COUNT(*) FROM doctors 
        WHERE on_call = true
        Result: 2 (safe to leave)
        
 3                                       SELECT COUNT(*) FROM doctors 
                                         WHERE on_call = true
                                         Result: 2 (safe to leave)
        
 4      UPDATE doctors SET on_call = false WHERE id = 1
        (doctor_1 thinks doctor_2 will cover)
        
 5                                       UPDATE doctors SET on_call = false 
                                         WHERE id = 2
                                         (doctor_2 thinks doctor_1 will cover)
                                         
 6      COMMIT ✓                         COMMIT ✓
 
Result: Both doctors removed from on-call!
        Constraint violated! 😱
        
No write-write conflict (different rows)
No phantom read (no new rows appeared)
But the combined effect violates application invariant
 
Solution: Use SERIALIZABLE isolation level, which would detect this
          conflict and abort one transaction.

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

-- Pattern: Consistent Reporting with MVCC
 
-- Start a reporting transaction
BEGIN ISOLATION LEVEL REPEATABLE READ;
 
-- First report query
SELECT 
    department_id,
    SUM(salary) as total_salary,
    COUNT(*) as employee_count
FROM employees
GROUP BY department_id;
 
-- This could take minutes for large tables...
 
-- Meanwhile, other transactions are updating salaries,
-- hiring employees, etc. - all proceeding without waiting!
 
-- Second report query - sees SAME data as first
SELECT 
    department_id,
    AVG(salary) as avg_salary
FROM employees
GROUP BY department_id;
 
-- The totals from first query will be consistent with
-- averages from second query - no phantom employees appeared
 
COMMIT;
 
-- Anti-pattern: Using Read Committed for reports
BEGIN;  -- Default is READ COMMITTED in PostgreSQL
 
SELECT department_id, SUM(salary) FROM employees GROUP BY department_id;
-- ... time passes, other transactions commit ...
SELECT department_id, SUM(salary) FROM employees GROUP BY department_id;
-- Could return different totals! Not suitable for consistent reports.
 
COMMIT;

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

-- Pattern: Read-Modify-Write requiring row-level atomicity
 
-- Option 1: Atomic UPDATE (best for simple cases)
UPDATE accounts 
SET balance = balance - 100 
WHERE id = 1 AND balance >= 100;
-- Single statement is always atomic, no read-then-write gap
 
-- Option 2: SELECT FOR UPDATE (explicit row locking)
BEGIN ISOLATION LEVEL REPEATABLE READ;
 
SELECT balance FROM accounts WHERE id = 1 FOR UPDATE;
-- Returns 500; row is now locked against concurrent updates
 
-- Application logic: check balance, calculate, etc.
 
UPDATE accounts SET balance = 400 WHERE id = 1;
COMMIT;
-- Other transactions waited for our lock
 
-- Option 3: Optimistic concurrency with MVCC
BEGIN ISOLATION LEVEL REPEATABLE READ;
 
SELECT balance, version FROM accounts WHERE id = 1;
-- Returns: balance=500, version=5
 
-- Application logic...
 
UPDATE accounts 
SET balance = 400, version = 6 
WHERE id = 1 AND version = 5;
 
-- Check: was the update applied?
-- If version changed, another transaction modified the row
-- - 1 row updated = success
-- - 0 rows updated = conflict, retry transaction
 
COMMIT;