Lock Concepts - Learning Module

Loading content...

0/241

Lock Compatibility Matrix

The Rules of Coexistence

Every society functions by rules—traffic flows because red light means stop and green means go. Databases have their own traffic rules for concurrent transactions, codified in the Lock Compatibility Matrix.

This matrix is the authoritative reference that the Lock Manager consults on every single lock request: Can this lock be granted given what locks already exist? Should this transaction wait, or can it proceed immediately? The matrix encodes, in a simple tabular form, the entire logic of lock coexistence.

Understanding the compatibility matrix is essential for:

Predicting transaction blocking behavior
Diagnosing concurrency bottlenecks
Designing efficient concurrent applications
Understanding how isolation levels are implemented

In this page, we explore the compatibility matrix in depth: its structure, the reasoning behind each entry, extended matrices for additional lock modes, and how the matrix drives the Lock Manager's decisions.

What You Will Learn

By the end of this page, you will understand the structure of the basic S/X compatibility matrix, the logical reasoning behind each compatibility rule, extended matrices with intention locks and update locks, how the Lock Manager uses the matrix algorithmically, and performance implications of compatibility decisions.

The Basic S/X Compatibility Matrix

The fundamental lock compatibility matrix for shared (S) and exclusive (X) locks is elegantly simple:

Lock Compatibility Matrix: Basic S/X Model
Lock Request ↓ / Lock Held →	No Lock	Shared (S)	Exclusive (X)
Shared (S)	✓ Grant	✓ Grant	✗ Wait
Exclusive (X)	✓ Grant	✗ Wait	✗ Wait

Reading the Matrix:

Rows represent the lock being requested
Columns represent locks currently held on the data item
Cell values indicate whether the request is granted (✓) or blocked (✗)

Let's analyze each cell:

Cell-by-Cell Analysis

•S + No Lock → Grant: A data item with no lock can accept a shared lock. This is the uncontended case—first reader arrives.
•S + S → Grant: Multiple shared locks coexist. This is the key insight: readers don't conflict with readers.
•S + X → Wait: Cannot read while someone is writing. The reader must wait for the writer to finish.
•X + No Lock → Grant: A data item with no lock can accept an exclusive lock. The writer has free access.
•X + S → Wait: Cannot write while readers are reading. The writer must wait for all readers to finish.
•X + X → Wait: Cannot write while another writer is writing. Writers are strictly serialized.

The Fundamental Insight:

The matrix captures a single, profound insight: read operations are inherently compatible with each other, but write operations conflict with everything. This reflects the reality that:

Reading data doesn't modify it, so multiple readers see the same consistent value
Writing data modifies it, which would cause readers to see inconsistent states
Concurrent writes would overwrite each other, losing data

Converting Mermaid diagram...

Symmetry and Asymmetry

Notice that the matrix is symmetric: S+X and X+S both result in waiting. This makes intuitive sense—if readers block writers, writers should block readers. The only asymmetric behavior is around the No Lock column, and even that's symmetric in a sense: both S and X can be granted on unlocked items.

Mathematical Foundation

The compatibility matrix can be formalized mathematically, which enables rigorous proofs about locking protocols and helps in designing new lock modes.

Formal Definition:

Let L be the set of lock modes. The compatibility relation ≈ is a binary relation on L:

For lock modes m₁, m₂ ∈ L, we say m₁ ≈ m₂ (m₁ is compatible with m₂) if and only if transactions holding m₁ and m₂ simultaneously on the same data item can execute correctly without conflict.

For the basic S/X model:

L = {S, X}
S ≈ S (compatible)
S ≉ X (not compatible)
X ≉ S (not compatible)
X ≉ X (not compatible)

compatibility_math.ts
TypeScript
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
// Formal Representation of Lock Compatibility
 
enum LockMode {
    NONE = 0,
    SHARED = 1,
    EXCLUSIVE = 2
}
 
// Compatibility matrix as a 2D array
// compatible[held][requested] = true if compatible
const compatibilityMatrix: boolean[][] = [
    //           NONE    SHARED   EXCLUSIVE
    /* NONE */   [true,   true,    true],
    /* SHARED */ [true,   true,    false],
    /* EXCL */   [true,   false,   false]
];
 
/**
 * Determines if a requested lock is compatible with currently held lock
 */
function isCompatible(held: LockMode, requested: LockMode): boolean {
    return compatibilityMatrix[held][requested];
}
 
// Mathematical properties of the compatibility relation
 
/**
 * Reflexivity: Is every lock mode compatible with itself?
 * S ≈ S: true (multiple readers OK)
 * X ≈ X: false (only one writer)
 * Therefore, the relation is NOT reflexive
 */
function isReflexive(): boolean {
    return Object.values(LockMode)
        .filter(m => typeof m === 'number')
        .every(m => isCompatible(m as LockMode, m as LockMode));
    // Returns false because X ≉ X
}
 
/**
 * Symmetry: If m₁ ≈ m₂, does m₂ ≈ m₁?
 * For S/X: Yes, the matrix is symmetric
 * S ≈ S implies S ≈ S ✓
 * S ≉ X implies X ≉ S ✓
 */
function isSymmetric(): boolean {
    for (let m1 = 0; m1 <= 2; m1++) {
        for (let m2 = 0; m2 <= 2; m2++) {
            if (compatibilityMatrix[m1][m2] !== compatibilityMatrix[m2][m1]) {
                return false;
            }
        }
    }
    return true; // Returns true for S/X matrix
}
 
/**
 * Lock mode strength ordering: X > S > None
 * A stronger lock is compatible with fewer other locks
 */
function lockStrength(mode: LockMode): number {
    // Count how many modes this is incompatible with
    let conflicts = 0;
    for (let other = 0; other <= 2; other++) {
        if (!isCompatible(mode, other as LockMode)) conflicts++;
    }
    return conflicts;
}
// lockStrength(S) = 1 (conflicts with X only)
// lockStrength(X) = 2 (conflicts with S and X)

Key Mathematical Properties

•Symmetry: The S/X compatibility matrix is symmetric: if m₁ ≈ m₂, then m₂ ≈ m₁. This simplifies reasoning.
•Not Reflexive: X ≉ X, so the relation is not reflexive. A transaction cannot hold two X-locks on the same item (it would just be one lock).
•Lock Strength Ordering: Locks can be ordered by strength: X > S. Stronger locks conflict with more modes.
•Lattice Structure: Lock modes form a lattice where NONE < S < X, useful for lock escalation decisions.

Why Math Matters Here

The mathematical formalization enables proofs of correctness for locking protocols. For example, we can prove that if all transactions follow Two-Phase Locking with this compatibility matrix, the resulting schedule is serializable. These proofs underpin database correctness guarantees.

Lock Manager Decision Algorithm

The Lock Manager uses the compatibility matrix at the heart of its decision-making process. Here's how it processes each lock request:

Converting Mermaid diagram...

lock_manager_algorithm.ts
TypeScript
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// Lock Manager Core Algorithm Using Compatibility Matrix
 
interface LockRequest {
    transactionId: string;
    dataItem: string;
    mode: 'S' | 'X';
}
 
interface LockTableEntry {
    mode: 'NONE' | 'S' | 'X';
    holders: Set<string>;      // Transaction IDs
    waitQueue: LockRequest[];
}
 
class LockManager {
    private lockTable: Map<string, LockTableEntry> = new Map();
    
    // Core compatibility check
    private compatibilityMatrix = {
        'NONE': { 'S': true, 'X': true },
        'S':    { 'S': true, 'X': false },
        'X':    { 'S': false, 'X': false }
    };
    
    /**
     * Main entry point for lock requests
     */
    requestLock(request: LockRequest): 'GRANTED' | 'WAITING' {
        const entry = this.getOrCreateEntry(request.dataItem);
        
        // Step 1: Check if item is unlocked
        if (entry.mode === 'NONE') {
            return this.grantLock(request, entry);
        }
        
        // Step 2: Check wait queue (fairness)
        if (entry.waitQueue.length > 0) {
            // Someone already waiting - must queue to maintain fairness
            return this.enqueueLock(request, entry);
        }
        
        // Step 3: Consult compatibility matrix
        const isCompatible = this.compatibilityMatrix[entry.mode][request.mode];
        
        if (isCompatible) {
            return this.grantLock(request, entry);
        } else {
            return this.enqueueLock(request, entry);
        }
    }
    
    private grantLock(request: LockRequest, entry: LockTableEntry): 'GRANTED' {
        // Update lock mode (S stays S if adding S, becomes S if was NONE)
        if (request.mode === 'X') {
            entry.mode = 'X';
        } else if (entry.mode === 'NONE') {
            entry.mode = 'S';
        }
        // If entry.mode was already 'S' and request is 'S', stays 'S'
        
        entry.holders.add(request.transactionId);
        console.log(`Lock GRANTED: ${request.transactionId} gets ${request.mode} on ${request.dataItem}`);
        return 'GRANTED';
    }
    
    private enqueueLock(request: LockRequest, entry: LockTableEntry): 'WAITING' {
        entry.waitQueue.push(request);
        console.log(`Lock WAITING: ${request.transactionId} queued for ${request.mode} on ${request.dataItem}`);
        return 'WAITING';
    }
    
    /**
     * Release lock and process wait queue
     */
    releaseLock(transactionId: string, dataItem: string): void {
        const entry = this.lockTable.get(dataItem);
        if (!entry) return;
        
        entry.holders.delete(transactionId);
        
        // Update mode if no holders left
        if (entry.holders.size === 0) {
            entry.mode = 'NONE';
        }
        
        // Process waiting transactions
        this.processWaitQueue(entry, dataItem);
    }
    
    private processWaitQueue(entry: LockTableEntry, dataItem: string): void {
        if (entry.waitQueue.length === 0) return;
        
        // Try to grant as many compatible requests as possible
        const toGrant: LockRequest[] = [];
        const remaining: LockRequest[] = [];
        
        for (const request of entry.waitQueue) {
            // Would this request be compatible with what we'd have after granting toGrant?
            const futureMode = this.getFutureMode(entry.mode, toGrant);
            
            if (this.compatibilityMatrix[futureMode][request.mode]) {
                toGrant.push(request);
            } else {
                // Once we hit an incompatible request, stop (FIFO fairness)
                remaining.push(...entry.waitQueue.slice(entry.waitQueue.indexOf(request)));
                break;
            }
        }
        
        entry.waitQueue = remaining;
        
        // Grant all compatible requests
        for (const request of toGrant) {
            this.grantLock(request, entry);
            // Wake up transaction (implementation-dependent)
        }
    }
    
    private getFutureMode(current: string, toGrant: LockRequest[]): 'NONE' | 'S' | 'X' {
        if (toGrant.some(r => r.mode === 'X')) return 'X';
        if (toGrant.length > 0 || current === 'S') return 'S';
        return 'NONE';
    }
}

Batch Granting

When an X-lock is released, the Lock Manager can grant multiple waiting S-locks at once (since S is compatible with S). This is more efficient than processing them one at a time and is a key optimization in real systems.

Extended Lock Modes

The basic S/X model, while foundational, is often extended with additional lock modes to handle special cases more efficiently. The most common extensions are Update Locks (U) and Intention Locks (IS, IX, SIX).

Update Locks (U) solve the upgrade deadlock problem we saw earlier. A U-lock allows reading with the intention to write later.

The Problem:

T1: S-lock(X) → T2: S-lock(X) → T1: wants X-lock (blocked by T2)
                                → T2: wants X-lock (blocked by T1)
= DEADLOCK

The Solution:

T1: U-lock(X) → T2: S-lock(X) blocked! → T1: upgrade to X-lock (succeeds)

Compatibility Matrix with Update Locks
Request \ Held	S	U	X
S	✓	✓	✗
U	✓	✗	✗
X	✗	✗	✗

•U is compatible with S (readers can continue)
•U is NOT compatible with U (only one upgrader allowed)
•U can convert to X when all S-locks release
•Prevents upgrade deadlock by serializing upgrade attempts

Matrix Size Explosion

Each new lock mode adds a row AND column to the matrix. With 6 modes (IS, IX, S, SIX, U, X), the matrix has 36 cells. This is why most systems use only the modes they truly need—complexity grows quadratically.

Multiple-Granularity Locking Protocol

Intention locks enable multiple-granularity locking (MGL), where transactions can lock at different levels of the database hierarchy (database → table → page → row).

The Hierarchy:

Database
  └── Table A
        ├── Page 1
        │     ├── Row 1
        │     ├── Row 2
        │     └── Row 3
        └── Page 2
              ├── Row 4
              └── Row 5

MGL Rules:

Multiple-Granularity Locking Rules

•Root First: The lock hierarchy must be traversed from the root (database or table) to the desired node.
•Intention Before Actual: Before acquiring S or X on a node, the transaction must hold the appropriate intention lock (IS or IX) on ALL ancestors.
•IS Required for S: To get S on a node, hold IS (or stronger) on all ancestors.
•IX Required for X: To get X on a node, hold IX (or stronger) on all ancestors.
•Release Bottom-Up: Locks are released from leaves up to the root, never skipping levels.

Converting Mermaid diagram...

mgl_example.sql
SQL
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
-- Multiple-Granularity Locking in Practice
 
-- Transaction T1: Update a single row
-- Internally acquires: IX(Table) → IX(Page) → X(Row)
BEGIN TRANSACTION;
UPDATE employees SET salary = 50000 WHERE id = 123;
-- Only Row 123 is X-locked; other rows on same page are accessible
COMMIT;
 
 
-- Transaction T2: Scan entire table
-- Internally acquires: S(Table)
BEGIN TRANSACTION;
SELECT * FROM employees;
-- If T1 is running, T2 blocks (IX not compatible with S)
COMMIT;
 
 
-- Transaction T3: Update different row (same table, different page)
-- Internally acquires: IX(Table) → IX(Page 2) → X(Row)
BEGIN TRANSACTION;
UPDATE employees SET salary = 60000 WHERE id = 456;
-- T1 and T3 can RUN CONCURRENTLY if rows are on different pages
-- (IX is compatible with IX at table level)
COMMIT;
 
 
-- SQL Server: Explicit table lock (bypasses row locking)
SELECT * FROM employees WITH (TABLOCK, HOLDLOCK);
-- Acquires S directly on table - blocks all writers

Why MGL Matters

Without intention locks, checking if a table can be X-locked would require examining every row's lock. With intention locks, we check one table-level lock. This changes O(n) checks to O(1)—essential for scalability.

Performance Implications of Compatibility Decisions

The compatibility matrix directly impacts system throughput. Understanding these implications helps in designing efficient concurrent applications.

Performance Benefits

•Read concurrency: S+S compatibility allows massive read parallelism
•Fine-grained locks: Intention locks enable row-level locking without scanning
•Batch readers: When X releases, all waiting S-locks can be granted at once
•Lock mode selection: Choosing the weakest sufficient mode maximizes concurrency

Performance Costs

•Writer blocking: X incompatibility serializes all writers on an item
•Reader starvation: Continuous S-locks can indefinitely block X requests
•Lock convoy: Many transactions waiting for one X-lock release simultaneously
•Compatibility checking: Each lock request requires matrix lookup

Workload Patterns and Compatibility Impact
Workload Type	Lock Pattern	Compatibility Behavior	Performance
Read-Heavy	Many S, few X	S-locks rarely block each other	Excellent concurrency
Write-Heavy	Many X, few S	X-locks serialize writes	Poor concurrency on hot rows
Mixed Read-Write	S and X interleaved	Writers wait for readers and vice versa	Moderate concurrency
Hot Spot	Many X on one row	All writers queue on single item	Serial execution effectively

Mitigation Strategies:

•Minimize lock duration: Acquire late, release early (within protocol constraints).
•Use appropriate isolation: Don't use Serializable when Read Committed suffices.
•Avoid hot spots: Distribute writes across multiple rows (e.g., hash partitioning).
•Batch writes: Combine multiple updates into single transactions to reduce lock overhead.
•Consider MVCC: For read-heavy workloads, MVCC avoids reader-writer blocking entirely.

Monitoring Lock Contention

Production databases expose lock wait statistics. High lock wait times on specific tables/rows indicate contention. Use this data to identify hot spots and optimize access patterns.

The Compatibility Matrix in Real Database Systems

Different database systems implement variations of the compatibility matrix. Understanding these variations helps when working with specific systems.

PostgreSQL uses eight table-level lock modes:

•ACCESS SHARE: Acquired by SELECT. Compatible with everything except ACCESS EXCLUSIVE.
•ROW SHARE: FOR UPDATE. Conflicts with EXCLUSIVE and ACCESS EXCLUSIVE.
•ROW EXCLUSIVE: UPDATE, DELETE, INSERT. Allows other row modifications.
•SHARE UPDATE EXCLUSIVE: VACUUM, CREATE INDEX CONCURRENTLY.
•SHARE: CREATE INDEX (non-concurrent). Blocks writes.
•SHARE ROW EXCLUSIVE: Blocks most operations.
•EXCLUSIVE: Blocks most operations except pure reads.
•ACCESS EXCLUSIVE: ALTER TABLE, DROP. Blocks everything.

PostgreSQL primarily uses MVCC for reads, so the row-level locking is mainly for explicit FOR UPDATE/SHARE and for handling UPDATE/DELETE conflicts. Most SELECT statements don't acquire any row locks.

System-Specific Knowledge

While the fundamental S/X compatibility principles are universal, the details vary significantly between systems. Always consult your specific database's documentation for lock modes and their exact compatibility rules.

Summary: The Heart of Concurrency Control

The lock compatibility matrix is the authoritative rulebook that governs all lock decisions. Let's consolidate the key insights:

Key Takeaways

•The matrix encodes compatibility rules — Row = requested lock, Column = held lock, Cell = grant or wait.
•S+S is compatible, all X combinations wait — This reflects read-read safety and write-everything conflict.
•The matrix is symmetric — If A conflicts with B, then B conflicts with A.
•Extended modes solve special problems — Update locks prevent upgrade deadlocks, intention locks enable multi-granularity.
•The Lock Manager consults the matrix for every request — It's the core of the granting algorithm.
•Compatibility affects performance directly — More compatible modes = more concurrency = higher throughput.
•Different systems have different matrices — PostgreSQL, MySQL, SQL Server each have variations.

What's Next:

With a solid understanding of lock concepts, types, and compatibility, we'll examine Lock Granularity—the art of choosing what to lock. Should we lock an entire table, a page, or a single row? The answer profoundly affects both correctness and performance.

Page Complete

You now understand the lock compatibility matrix: its structure, mathematical properties, extended lock modes, and how the Lock Manager uses it algorithmically. In the next page, we'll explore lock granularity and the tradeoffs involved in choosing what to lock.

Lock Compatibility Matrix

The Rules of Coexistence

Understanding the compatibility matrix is essential for:

Predicting transaction blocking behavior
Diagnosing concurrency bottlenecks
Designing efficient concurrent applications
Understanding how isolation levels are implemented

What You Will Learn

The Basic S/X Compatibility Matrix

The fundamental lock compatibility matrix for shared (S) and exclusive (X) locks is elegantly simple:

Lock Compatibility Matrix: Basic S/X Model
Lock Request ↓ / Lock Held →	No Lock	Shared (S)	Exclusive (X)
Shared (S)	✓ Grant	✓ Grant	✗ Wait
Exclusive (X)	✓ Grant	✗ Wait	✗ Wait

Reading the Matrix:

Rows represent the lock being requested
Columns represent locks currently held on the data item
Cell values indicate whether the request is granted (✓) or blocked (✗)

Let's analyze each cell:

Cell-by-Cell Analysis

•S + No Lock → Grant: A data item with no lock can accept a shared lock. This is the uncontended case—first reader arrives.
•S + S → Grant: Multiple shared locks coexist. This is the key insight: readers don't conflict with readers.
•S + X → Wait: Cannot read while someone is writing. The reader must wait for the writer to finish.
•X + No Lock → Grant: A data item with no lock can accept an exclusive lock. The writer has free access.
•X + S → Wait: Cannot write while readers are reading. The writer must wait for all readers to finish.
•X + X → Wait: Cannot write while another writer is writing. Writers are strictly serialized.

The Fundamental Insight:

The matrix captures a single, profound insight: read operations are inherently compatible with each other, but write operations conflict with everything. This reflects the reality that:

Reading data doesn't modify it, so multiple readers see the same consistent value
Writing data modifies it, which would cause readers to see inconsistent states
Concurrent writes would overwrite each other, losing data

Converting Mermaid diagram...

Symmetry and Asymmetry

Mathematical Foundation

The compatibility matrix can be formalized mathematically, which enables rigorous proofs about locking protocols and helps in designing new lock modes.

Formal Definition:

Let L be the set of lock modes. The compatibility relation ≈ is a binary relation on L:

For lock modes m₁, m₂ ∈ L, we say m₁ ≈ m₂ (m₁ is compatible with m₂) if and only if transactions holding m₁ and m₂ simultaneously on the same data item can execute correctly without conflict.

For the basic S/X model:

L = {S, X}
S ≈ S (compatible)
S ≉ X (not compatible)
X ≉ S (not compatible)
X ≉ X (not compatible)

compatibility_math.ts
TypeScript
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
// Formal Representation of Lock Compatibility
 
enum LockMode {
    NONE = 0,
    SHARED = 1,
    EXCLUSIVE = 2
}
 
// Compatibility matrix as a 2D array
// compatible[held][requested] = true if compatible
const compatibilityMatrix: boolean[][] = [
    //           NONE    SHARED   EXCLUSIVE
    /* NONE */   [true,   true,    true],
    /* SHARED */ [true,   true,    false],
    /* EXCL */   [true,   false,   false]
];
 
/**
 * Determines if a requested lock is compatible with currently held lock
 */
function isCompatible(held: LockMode, requested: LockMode): boolean {
    return compatibilityMatrix[held][requested];
}
 
// Mathematical properties of the compatibility relation
 
/**
 * Reflexivity: Is every lock mode compatible with itself?
 * S ≈ S: true (multiple readers OK)
 * X ≈ X: false (only one writer)
 * Therefore, the relation is NOT reflexive
 */
function isReflexive(): boolean {
    return Object.values(LockMode)
        .filter(m => typeof m === 'number')
        .every(m => isCompatible(m as LockMode, m as LockMode));
    // Returns false because X ≉ X
}
 
/**
 * Symmetry: If m₁ ≈ m₂, does m₂ ≈ m₁?
 * For S/X: Yes, the matrix is symmetric
 * S ≈ S implies S ≈ S ✓
 * S ≉ X implies X ≉ S ✓
 */
function isSymmetric(): boolean {
    for (let m1 = 0; m1 <= 2; m1++) {
        for (let m2 = 0; m2 <= 2; m2++) {
            if (compatibilityMatrix[m1][m2] !== compatibilityMatrix[m2][m1]) {
                return false;
            }
        }
    }
    return true; // Returns true for S/X matrix
}
 
/**
 * Lock mode strength ordering: X > S > None
 * A stronger lock is compatible with fewer other locks
 */
function lockStrength(mode: LockMode): number {
    // Count how many modes this is incompatible with
    let conflicts = 0;
    for (let other = 0; other <= 2; other++) {
        if (!isCompatible(mode, other as LockMode)) conflicts++;
    }
    return conflicts;
}
// lockStrength(S) = 1 (conflicts with X only)
// lockStrength(X) = 2 (conflicts with S and X)

Key Mathematical Properties

•Symmetry: The S/X compatibility matrix is symmetric: if m₁ ≈ m₂, then m₂ ≈ m₁. This simplifies reasoning.
•Not Reflexive: X ≉ X, so the relation is not reflexive. A transaction cannot hold two X-locks on the same item (it would just be one lock).
•Lock Strength Ordering: Locks can be ordered by strength: X > S. Stronger locks conflict with more modes.
•Lattice Structure: Lock modes form a lattice where NONE < S < X, useful for lock escalation decisions.

Why Math Matters Here

Lock Manager Decision Algorithm

The Lock Manager uses the compatibility matrix at the heart of its decision-making process. Here's how it processes each lock request:

Converting Mermaid diagram...

lock_manager_algorithm.ts
TypeScript
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// Lock Manager Core Algorithm Using Compatibility Matrix
 
interface LockRequest {
    transactionId: string;
    dataItem: string;
    mode: 'S' | 'X';
}
 
interface LockTableEntry {
    mode: 'NONE' | 'S' | 'X';
    holders: Set<string>;      // Transaction IDs
    waitQueue: LockRequest[];
}
 
class LockManager {
    private lockTable: Map<string, LockTableEntry> = new Map();
    
    // Core compatibility check
    private compatibilityMatrix = {
        'NONE': { 'S': true, 'X': true },
        'S':    { 'S': true, 'X': false },
        'X':    { 'S': false, 'X': false }
    };
    
    /**
     * Main entry point for lock requests
     */
    requestLock(request: LockRequest): 'GRANTED' | 'WAITING' {
        const entry = this.getOrCreateEntry(request.dataItem);
        
        // Step 1: Check if item is unlocked
        if (entry.mode === 'NONE') {
            return this.grantLock(request, entry);
        }
        
        // Step 2: Check wait queue (fairness)
        if (entry.waitQueue.length > 0) {
            // Someone already waiting - must queue to maintain fairness
            return this.enqueueLock(request, entry);
        }
        
        // Step 3: Consult compatibility matrix
        const isCompatible = this.compatibilityMatrix[entry.mode][request.mode];
        
        if (isCompatible) {
            return this.grantLock(request, entry);
        } else {
            return this.enqueueLock(request, entry);
        }
    }
    
    private grantLock(request: LockRequest, entry: LockTableEntry): 'GRANTED' {
        // Update lock mode (S stays S if adding S, becomes S if was NONE)
        if (request.mode === 'X') {
            entry.mode = 'X';
        } else if (entry.mode === 'NONE') {
            entry.mode = 'S';
        }
        // If entry.mode was already 'S' and request is 'S', stays 'S'
        
        entry.holders.add(request.transactionId);
        console.log(`Lock GRANTED: ${request.transactionId} gets ${request.mode} on ${request.dataItem}`);
        return 'GRANTED';
    }
    
    private enqueueLock(request: LockRequest, entry: LockTableEntry): 'WAITING' {
        entry.waitQueue.push(request);
        console.log(`Lock WAITING: ${request.transactionId} queued for ${request.mode} on ${request.dataItem}`);
        return 'WAITING';
    }
    
    /**
     * Release lock and process wait queue
     */
    releaseLock(transactionId: string, dataItem: string): void {
        const entry = this.lockTable.get(dataItem);
        if (!entry) return;
        
        entry.holders.delete(transactionId);
        
        // Update mode if no holders left
        if (entry.holders.size === 0) {
            entry.mode = 'NONE';
        }
        
        // Process waiting transactions
        this.processWaitQueue(entry, dataItem);
    }
    
    private processWaitQueue(entry: LockTableEntry, dataItem: string): void {
        if (entry.waitQueue.length === 0) return;
        
        // Try to grant as many compatible requests as possible
        const toGrant: LockRequest[] = [];
        const remaining: LockRequest[] = [];
        
        for (const request of entry.waitQueue) {
            // Would this request be compatible with what we'd have after granting toGrant?
            const futureMode = this.getFutureMode(entry.mode, toGrant);
            
            if (this.compatibilityMatrix[futureMode][request.mode]) {
                toGrant.push(request);
            } else {
                // Once we hit an incompatible request, stop (FIFO fairness)
                remaining.push(...entry.waitQueue.slice(entry.waitQueue.indexOf(request)));
                break;
            }
        }
        
        entry.waitQueue = remaining;
        
        // Grant all compatible requests
        for (const request of toGrant) {
            this.grantLock(request, entry);
            // Wake up transaction (implementation-dependent)
        }
    }
    
    private getFutureMode(current: string, toGrant: LockRequest[]): 'NONE' | 'S' | 'X' {
        if (toGrant.some(r => r.mode === 'X')) return 'X';
        if (toGrant.length > 0 || current === 'S') return 'S';
        return 'NONE';
    }
}

Batch Granting

Extended Lock Modes

Update Locks (U) solve the upgrade deadlock problem we saw earlier. A U-lock allows reading with the intention to write later.

The Problem:

T1: S-lock(X) → T2: S-lock(X) → T1: wants X-lock (blocked by T2)
                                → T2: wants X-lock (blocked by T1)
= DEADLOCK

The Solution:

T1: U-lock(X) → T2: S-lock(X) blocked! → T1: upgrade to X-lock (succeeds)

Compatibility Matrix with Update Locks
Request \ Held	S	U	X
S	✓	✓	✗
U	✓	✗	✗
X	✗	✗	✗

•U is compatible with S (readers can continue)
•U is NOT compatible with U (only one upgrader allowed)
•U can convert to X when all S-locks release
•Prevents upgrade deadlock by serializing upgrade attempts

Matrix Size Explosion

Multiple-Granularity Locking Protocol

Intention locks enable multiple-granularity locking (MGL), where transactions can lock at different levels of the database hierarchy (database → table → page → row).

The Hierarchy:

Database
  └── Table A
        ├── Page 1
        │     ├── Row 1
        │     ├── Row 2
        │     └── Row 3
        └── Page 2
              ├── Row 4
              └── Row 5

MGL Rules:

Multiple-Granularity Locking Rules

•Root First: The lock hierarchy must be traversed from the root (database or table) to the desired node.
•Intention Before Actual: Before acquiring S or X on a node, the transaction must hold the appropriate intention lock (IS or IX) on ALL ancestors.
•IS Required for S: To get S on a node, hold IS (or stronger) on all ancestors.
•IX Required for X: To get X on a node, hold IX (or stronger) on all ancestors.
•Release Bottom-Up: Locks are released from leaves up to the root, never skipping levels.

Converting Mermaid diagram...

mgl_example.sql
SQL
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
-- Multiple-Granularity Locking in Practice
 
-- Transaction T1: Update a single row
-- Internally acquires: IX(Table) → IX(Page) → X(Row)
BEGIN TRANSACTION;
UPDATE employees SET salary = 50000 WHERE id = 123;
-- Only Row 123 is X-locked; other rows on same page are accessible
COMMIT;
 
 
-- Transaction T2: Scan entire table
-- Internally acquires: S(Table)
BEGIN TRANSACTION;
SELECT * FROM employees;
-- If T1 is running, T2 blocks (IX not compatible with S)
COMMIT;
 
 
-- Transaction T3: Update different row (same table, different page)
-- Internally acquires: IX(Table) → IX(Page 2) → X(Row)
BEGIN TRANSACTION;
UPDATE employees SET salary = 60000 WHERE id = 456;
-- T1 and T3 can RUN CONCURRENTLY if rows are on different pages
-- (IX is compatible with IX at table level)
COMMIT;
 
 
-- SQL Server: Explicit table lock (bypasses row locking)
SELECT * FROM employees WITH (TABLOCK, HOLDLOCK);
-- Acquires S directly on table - blocks all writers

Why MGL Matters

Performance Implications of Compatibility Decisions

The compatibility matrix directly impacts system throughput. Understanding these implications helps in designing efficient concurrent applications.

Performance Benefits

•Read concurrency: S+S compatibility allows massive read parallelism
•Fine-grained locks: Intention locks enable row-level locking without scanning
•Batch readers: When X releases, all waiting S-locks can be granted at once
•Lock mode selection: Choosing the weakest sufficient mode maximizes concurrency

Performance Costs

•Writer blocking: X incompatibility serializes all writers on an item
•Reader starvation: Continuous S-locks can indefinitely block X requests
•Lock convoy: Many transactions waiting for one X-lock release simultaneously
•Compatibility checking: Each lock request requires matrix lookup

Workload Patterns and Compatibility Impact
Workload Type	Lock Pattern	Compatibility Behavior	Performance
Read-Heavy	Many S, few X	S-locks rarely block each other	Excellent concurrency
Write-Heavy	Many X, few S	X-locks serialize writes	Poor concurrency on hot rows
Mixed Read-Write	S and X interleaved	Writers wait for readers and vice versa	Moderate concurrency
Hot Spot	Many X on one row	All writers queue on single item	Serial execution effectively

Mitigation Strategies:

•Minimize lock duration: Acquire late, release early (within protocol constraints).
•Use appropriate isolation: Don't use Serializable when Read Committed suffices.
•Avoid hot spots: Distribute writes across multiple rows (e.g., hash partitioning).
•Batch writes: Combine multiple updates into single transactions to reduce lock overhead.
•Consider MVCC: For read-heavy workloads, MVCC avoids reader-writer blocking entirely.

Monitoring Lock Contention

Production databases expose lock wait statistics. High lock wait times on specific tables/rows indicate contention. Use this data to identify hot spots and optimize access patterns.

The Compatibility Matrix in Real Database Systems

Different database systems implement variations of the compatibility matrix. Understanding these variations helps when working with specific systems.

PostgreSQL uses eight table-level lock modes:

•ACCESS SHARE: Acquired by SELECT. Compatible with everything except ACCESS EXCLUSIVE.
•ROW SHARE: FOR UPDATE. Conflicts with EXCLUSIVE and ACCESS EXCLUSIVE.
•ROW EXCLUSIVE: UPDATE, DELETE, INSERT. Allows other row modifications.
•SHARE UPDATE EXCLUSIVE: VACUUM, CREATE INDEX CONCURRENTLY.
•SHARE: CREATE INDEX (non-concurrent). Blocks writes.
•SHARE ROW EXCLUSIVE: Blocks most operations.
•EXCLUSIVE: Blocks most operations except pure reads.
•ACCESS EXCLUSIVE: ALTER TABLE, DROP. Blocks everything.

System-Specific Knowledge

Summary: The Heart of Concurrency Control

The lock compatibility matrix is the authoritative rulebook that governs all lock decisions. Let's consolidate the key insights:

Key Takeaways

•The matrix encodes compatibility rules — Row = requested lock, Column = held lock, Cell = grant or wait.
•S+S is compatible, all X combinations wait — This reflects read-read safety and write-everything conflict.
•The matrix is symmetric — If A conflicts with B, then B conflicts with A.
•Extended modes solve special problems — Update locks prevent upgrade deadlocks, intention locks enable multi-granularity.
•The Lock Manager consults the matrix for every request — It's the core of the granting algorithm.
•Compatibility affects performance directly — More compatible modes = more concurrency = higher throughput.
•Different systems have different matrices — PostgreSQL, MySQL, SQL Server each have variations.

What's Next:

Page Complete