2pl Variants - Learning Module

Loading content...

0/241

Strict Two-Phase Locking (Strict 2PL)

The Real-World Standard for Transaction Isolation

When you execute a transaction in PostgreSQL, MySQL InnoDB, SQL Server, or Oracle, you're almost certainly using Strict Two-Phase Locking. Not basic 2PL—but its more rigorous cousin that holds exclusive locks until the transaction commits or aborts.

Why does every major database system implement this stricter protocol? The answer lies in a fundamental problem that basic 2PL cannot solve: recoverability. Basic 2PL guarantees serializability—but it can produce schedules where a crash requires cascading rollbacks across transactions that have already committed. This is catastrophic.

Strict 2PL adds a simple but profound constraint: no exclusive lock is released until the transaction ends. This single rule eliminates cascading failures and makes crash recovery predictable and efficient. It's the protocol that makes databases truly reliable.

What You Will Learn

By the end of this page, you will understand why Strict 2PL is the de facto standard in production databases. You'll learn how holding exclusive locks until commit prevents dirty reads and cascading aborts, why this is essential for crash recovery, and how Strict 2PL bridges the gap between serializability and recoverability. This knowledge is fundamental to understanding how real database systems operate.

The Problem with Basic 2PL

Before we understand Strict 2PL, we must appreciate the critical flaw in the basic Two-Phase Locking protocol that necessitates this stricter variant.

Basic 2PL Recap:

Basic 2PL divides a transaction's execution into two phases:

Growing Phase: Acquire locks; no locks released
Shrinking Phase: Release locks; no new locks acquired

Once a transaction releases its first lock, it enters the shrinking phase and cannot acquire new locks. This guarantees conflict serializability—the resulting schedule is equivalent to some serial execution of the transactions.

But there's a devastating catch.

The Dirty Read Vulnerability

Basic 2PL allows a transaction to release an exclusive (write) lock before committing—while still in the shrinking phase. Another transaction can then read this uncommitted value. If the first transaction aborts, the second transaction has read data that never officially existed. This is a dirty read, and it breaks recoverability.

A Concrete Disaster Scenario:

Consider two transactions, T₁ and T₂, operating on account balance A (initially $1000):

Basic 2PL Failure: Dirty Read Leading to Unrecoverable Schedule
Time	T₁ (Transfer)	T₂ (Report)	Lock State on A	Value of A
t₁	lock-X(A)		X: T₁	$1000
t₂	read(A) → $1000		X: T₁	$1000
t₃	A = A - 500		X: T₁	$500 (uncommitted)
t₄	write(A)		X: T₁	$500 (uncommitted)
t₅	unlock(A) ← Enters shrinking phase		None	$500 (uncommitted)
t₆		lock-S(A) ← Granted!	S: T₂	$500 (uncommitted)
t₇		read(A) → $500 ← Dirty read!	S: T₂	$500 (uncommitted)
t₈		unlock(A)	None	$500 (uncommitted)
t₉		COMMIT ← T₂ commits with dirty data	None	$500 (uncommitted)
t₁₀	ABORT ← T₁ fails!		None	$1000 (rolled back)

The Catastrophe:

T₂ has committed a report showing a balance of $500. But T₁ aborted, so the $500 value never officially existed—A should still be $1000. This creates three critical problems:

Data Inconsistency: The committed report contains phantom data
Cascading Abort Required: To fix this, T₂ would need to be rolled back—but it already committed
Impossible Recovery: We cannot abort a committed transaction; durability guarantees prevent it

This is an unrecoverable schedule. The database has permanently recorded data derived from a transaction that was rolled back. Basic 2PL, despite guaranteeing serializability, allows these disasters.

The Core Issue

Basic 2PL's fatal flaw is allowing exclusive locks to be released before commit. This creates a window where uncommitted data becomes visible to other transactions. When this happens, database recovery becomes impossible without violating durability.

Strict 2PL: The Essential Constraint

Strict Two-Phase Locking adds a single, powerful constraint to basic 2PL that eliminates the dirty read vulnerability completely:

A transaction must hold all its exclusive (write) locks until it commits or aborts.

This means exclusive locks are only released as part of the transaction's termination—never before. The lock release and transaction end become a single, atomic event.

Formal Definition

Strict 2PL = Basic 2PL + 'All exclusive locks held by a transaction are released only after the transaction commits or aborts.' Shared (read) locks may still be released early during the shrinking phase, but write locks persist until termination.

Why This Single Rule Fixes Everything:

Holding exclusive locks until transaction end means:

No Dirty Reads: Other transactions cannot access written data until the writing transaction commits or aborts
No Cascading Aborts: Since uncommitted data is never visible, no transaction can become dependent on uncommitted changes
Simple Recovery: After a crash, we can abort incomplete transactions without affecting committed ones
Strict Schedules: The resulting schedules are guaranteed to be both serializable AND recoverable

Converting Mermaid diagram...

The Subtle Distinction:

In Strict 2PL, the transaction still has two phases (growing and shrinking), but the shrinking phase only applies to shared locks. Exclusive locks have a one-phase behavior: they're acquired during the growing phase and held until the absolute end.

This is why some texts describe Strict 2PL as having a modified shrinking phase—because exclusive locks don't participate in it. They're held until the commit/abort action releases them all at once.

How Strict 2PL Eliminates Dirty Reads

Let's revisit our disaster scenario, but now with Strict 2PL enforced. Observe how the simple rule of holding exclusive locks transforms the outcome:

Strict 2PL: Dirty Read Prevented
Time	T₁ (Transfer)	T₂ (Report)	Lock State on A	Value of A
t₁	lock-X(A)		X: T₁	$1000
t₂	read(A) → $1000		X: T₁	$1000
t₃	A = A - 500		X: T₁	$500 (uncommitted)
t₄	write(A)		X: T₁	$500 (uncommitted)
t₅	(continues holding X lock)	lock-S(A) BLOCKED!	X: T₁	$500 (uncommitted)
t₆	(more operations...)	WAITING...	X: T₁	$500 (uncommitted)
t₇	ABORT ← T₁ fails	STILL WAITING	X: T₁	$500 (uncommitted)
t₈	unlock(A) ← Released on abort		None	$1000 (rolled back)
t₉		lock-S(A) ← Now granted!	S: T₂	$1000
t₁₀		read(A) → $1000 ← Clean data!	S: T₂	$1000
t₁₁		unlock(A), COMMIT	None	$1000

The Critical Difference:

T₂'s request for a shared lock on A at time t₅ is blocked because T₁ still holds an exclusive lock. T₂ must wait until T₁ either commits or aborts. When T₁ aborts, A is restored to $1000, and only then does T₂ gain access.

T₂ never sees the uncommitted $500 value. Its report correctly shows $1000. The schedule is recoverable because no committed transaction ever read uncommitted data.

Problem Solved

By blocking access to exclusively-locked data until transaction end, Strict 2PL ensures that transactions only ever read committed data. This single mechanism prevents dirty reads, eliminates cascading aborts, and makes crash recovery straightforward.

Formal Guarantee:

In Strict 2PL, if transaction Tⱼ reads a value written by transaction Tᵢ, then Tᵢ must have already committed or aborted before Tⱼ reads. Since abort restores original values and commit makes changes permanent, Tⱼ always reads a committed, consistent value.

This is precisely the definition of a cascadeless schedule: no transaction reads uncommitted data, so no cascading aborts can ever be necessary.

Strict 2PL and Recoverability

The relationship between Strict 2PL and schedule recoverability is fundamental to understanding why every production database uses this protocol. Let's establish the formal connection.

Schedule Classification Hierarchy

•Serial Schedules — Transactions execute one after another, no interleaving. Trivially correct but terrible performance.
•Serializable Schedules — Equivalent to some serial schedule. Produced by basic 2PL. May not be recoverable!
•Recoverable Schedules — If Tⱼ reads from Tᵢ, then Tᵢ must commit before Tⱼ commits. Allows cascading aborts.
•Cascadeless Schedules — No transaction reads uncommitted data. Subset of recoverable. No cascading aborts possible.
•Strict Schedules — No transaction reads OR writes uncommitted data. Strongest guarantee. Produced by Strict 2PL.

Converting Mermaid diagram...

Key Insight:

Strict 2PL produces schedules that belong to the intersection of Serializable and Strict schedules. This is not just a theoretical nicety—it's the practical sweet spot:

Serializable ensures logical correctness (isolation)
Strict ensures recoverability (durability after failures)

Basic 2PL only guarantees the first. Strict 2PL guarantees both.

Why 'Strict' Matters for Recovery

Strict schedules have a crucial property: after a crash, recovery can restore the database to a consistent state by simply undoing all uncommitted transactions and redoing all committed ones. There's no need to track dependencies between transactions or worry about cascading rollbacks. This dramatically simplifies recovery algorithms like ARIES.

Proof that Strict 2PL Produces Strict Schedules:

In Strict 2PL, exclusive locks are held until commit or abort
Before any transaction Tⱼ can write to a data item X, it must acquire an exclusive lock on X
If Tᵢ wrote to X (holding X-lock) and Tⱼ wants to read or write X, Tⱼ must wait for Tᵢ's lock
Tᵢ's lock is only released when Tᵢ commits or aborts
Therefore, Tⱼ can only access X after Tᵢ terminates
This is precisely the definition of a strict schedule ∎

The elegance is in the simplicity: the lock-holding rule mechanically enforces exactly the schedule property we need for safe recovery.

Implementation Mechanics

Understanding how databases implement Strict 2PL reveals the engineering behind the theory. The implementation must efficiently manage lock acquisition, blocking, and release while maintaining the strict guarantee.

strict_2pl_implementation.pseudo
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
// Strict 2PL Lock Manager - Pseudocode
 
class Strict2PLLockManager {
    locks: Map<DataItem, LockEntry>
    transactionLocks: Map<TransactionId, Set<DataItem>>
    
    // Acquire lock (blocks if incompatible lock held)
    func acquireLock(txn: Transaction, item: DataItem, mode: LockMode): void {
        if mode == EXCLUSIVE:
            // Wait until no other transaction holds any lock
            while locks[item].heldBy != null && locks[item].heldBy != txn.id:
                wait(locks[item].waitQueue)
            
            locks[item] = { mode: EXCLUSIVE, heldBy: txn.id }
            transactionLocks[txn.id].add(item)
            
        else if mode == SHARED:
            // Wait until no exclusive lock held by another transaction
            while locks[item].mode == EXCLUSIVE && locks[item].heldBy != txn.id:
                wait(locks[item].waitQueue)
            
            locks[item].sharedHolders.add(txn.id)
            transactionLocks[txn.id].add(item)
    }
    
    // Release shared lock (can be done before commit in Strict 2PL)
    func releaseSharedLock(txn: Transaction, item: DataItem): void {
        if locks[item].mode == SHARED:
            locks[item].sharedHolders.remove(txn.id)
            transactionLocks[txn.id].remove(item)
            notifyWaiters(item)
    }
    
    // Release ALL exclusive locks - ONLY called on commit/abort
    func releaseAllExclusiveLocks(txn: Transaction): void {
        for item in transactionLocks[txn.id]:
            if locks[item].mode == EXCLUSIVE && locks[item].heldBy == txn.id:
                locks[item] = { mode: NONE, heldBy: null }
                notifyWaiters(item)
        
        transactionLocks.remove(txn.id)
    }
    
    // Transaction commit - releases X-locks after commit record is durable
    func commit(txn: Transaction): void {
        writeCommitRecord(txn)      // Write to log
        forceLogToDisk()            // Ensure durability
        releaseAllExclusiveLocks(txn)  // NOW release X-locks
    }
    
    // Transaction abort - releases X-locks after undo is complete
    func abort(txn: Transaction): void {
        undoAllWrites(txn)          // Restore original values
        writeAbortRecord(txn)       // Log the abort
        releaseAllExclusiveLocks(txn)  // NOW release X-locks
    }
}

Critical Implementation Points:

•Lock Table Structure — A hash table mapping data items to lock entries. Each entry tracks the lock mode, holder(s), and a wait queue for blocked transactions.
•Transaction Lock Registry — A mapping from each transaction to all locks it holds. Essential for releasing all locks on commit/abort.
•Wait Queues — FIFO queues for transactions waiting on each locked item. Prevents starvation and ensures fairness.
•Commit/Abort Ordering — Exclusive locks are released AFTER commit/abort records are durably written to the log. This ensures recovery correctness.
•Lock Upgrade — When a transaction holds a shared lock and needs exclusive access, it must upgrade (if no other shared holders) or wait.

The Critical Ordering

On commit: (1) Write commit record, (2) Force log to disk, (3) Release exclusive locks. On abort: (1) Undo all writes, (2) Write abort record, (3) Release exclusive locks. The lock release MUST be the final step to maintain strictness guarantees.

Performance Implications

Strict 2PL's safety comes with performance trade-offs that every database administrator must understand. The stricter lock holding increases contention compared to basic 2PL, but this cost is almost always acceptable given the safety guarantees.

Advantages

•Simple Recovery — No cascading abort logic needed; just undo uncommitted, redo committed
•Predictable Behavior — Transactions never see uncommitted data; debugging is straightforward
•No Phantom Dependencies — Committed transactions are never affected by future aborts
•Well-Understood — Extensive research and decades of production experience
•ACID Compliance — Directly supports isolation and durability requirements

Performance Costs

•Longer Lock Holding — X-locks held for entire transaction duration increases contention
•Reduced Concurrency — More blocking when transactions write shared data
•Deadlock Risk — Longer lock durations increase probability of deadlocks
•Write-Heavy Penalty — Workloads with many writes suffer more than read-heavy
•Long Transaction Impact — One long write transaction can block many short ones

Strict 2PL Performance Impact by Workload
Workload Type	Concurrency Impact	Mitigation Strategies
Read-Heavy (90%+ reads)	Minimal impact — shared locks can still release early; X-locks rare	Default Strict 2PL works well
Write-Heavy (40%+ writes)	Significant contention — X-locks block all access to written items	Shorter transactions, partitioning, MVCC overlay
Mix with Hot Spots	Severe bottleneck — popular items constantly locked	Denormalization, caching, optimistic concurrency for hot data
Long Transactions	Cascading delays — one long T blocks many short ones	Transaction splitting, asynchronous patterns, queue-based designs
High Throughput OLTP	Lock manager becomes bottleneck	Lock-free structures for metadata, coarse-grained partitioning

The Practical Reality

Despite these costs, Strict 2PL remains the foundation of transaction processing because the alternative—unrecoverable schedules—is unacceptable. Modern databases mitigate contention through MVCC (Multi-Version Concurrency Control), which allows readers to access old versions without blocking on X-locks. We'll explore this in the Timestamp & MVCC chapter.

Strict 2PL in Production Databases

Every major relational database implements Strict 2PL, though often combined with other techniques for performance. Understanding these implementations helps when tuning and troubleshooting production systems.

Strict 2PL Implementation Across Database Systems
Database	Lock Implementation	Strict 2PL + MVCC?	Notable Features
PostgreSQL	Row-level X-locks held until commit	Yes — writers block writers, readers see snapshots	MVCC via tuple versioning; no read locks needed for snapshots
MySQL InnoDB	Row-level X-locks with gap locks	Yes — MVCC for consistent reads	Next-key locking prevents phantoms; configurable isolation
SQL Server	Row/page/table X-locks until commit	Yes (optional RCSI)	Lock escalation; snapshot isolation available
Oracle	Row-level X-locks until commit	Yes — always MVCC	Readers never blocked; undo segments store versions
SQLite	Database-level X-lock until commit	WAL mode adds concurrency	Simpler model; one writer at a time

The MVCC Complement:

Modern databases typically combine Strict 2PL for write-write conflicts with MVCC for read-write scenarios:

Writes still acquire X-locks (Strict 2PL)
Reads don't acquire locks but see a consistent snapshot (MVCC)
Result: Readers don't block writers, writers don't block readers

This hybrid approach preserves Strict 2PL's recoverability guarantees while dramatically improving read concurrency. The X-locks still prevent write-write conflicts, and the MVCC layer provides consistent reads without blocking.

Investigating Lock Behavior

In PostgreSQL, use pg_locks to see current locks. In MySQL, use INFORMATION_SCHEMA.INNODB_LOCKS. In SQL Server, use sys.dm_tran_locks. Understanding your database's lock behavior helps diagnose contention and design efficient transactions.

investigate_locks.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
31
-- PostgreSQL: View current locks
SELECT 
    locktype,
    relation::regclass,
    mode,
    granted,
    pid,
    pg_blocking_pids(pid) as blocked_by
FROM pg_locks
WHERE NOT granted OR locktype = 'relation'
ORDER BY relation;
 
-- MySQL InnoDB: View lock waits
SELECT 
    r.trx_id AS waiting_trx_id,
    r.trx_mysql_thread_id AS waiting_thread,
    b.trx_id AS blocking_trx_id,
    b.trx_mysql_thread_id AS blocking_thread
FROM information_schema.innodb_lock_waits w
JOIN information_schema.innodb_trx b ON b.trx_id = w.blocking_trx_id
JOIN information_schema.innodb_trx r ON r.trx_id = w.requesting_trx_id;
 
-- SQL Server: View lock waits
SELECT 
    request_session_id,
    resource_type,
    resource_database_id,
    request_mode,
    request_status
FROM sys.dm_tran_locks
WHERE request_status = 'WAIT';

Summary: Strict 2PL Fundamentals

Strict 2PL is the cornerstone of transaction processing in production databases. Let's consolidate the key concepts:

Key Takeaways

•Basic 2PL is insufficient — It guarantees serializability but allows dirty reads that create unrecoverable schedules. Transactions can commit based on data that later rolls back.
•Strict 2PL adds one rule — Hold all exclusive locks until commit or abort. This single constraint eliminates the dirty read vulnerability completely.
•No dirty reads, no cascading aborts — Because uncommitted data is never visible, committed transactions are never affected by later aborts.
•Strict schedules simplify recovery — After a crash, recovery is straightforward: undo uncommitted, redo committed. No need to track inter-transaction dependencies.
•Performance trade-off exists — Longer lock holding increases contention, especially for write-heavy workloads. Modern databases mitigate this with MVCC.
•Universal adoption — Every major production database implements Strict 2PL because the alternative—unrecoverable schedules—is unacceptable for reliable data management.

What's Next:

Strict 2PL holds exclusive locks until commit. But what about shared locks? The next page explores Rigorous 2PL—an even stricter variant that holds ALL locks (both shared and exclusive) until transaction end. We'll examine when this additional strictness is necessary and what guarantees it provides beyond Strict 2PL.

Page Complete

You now understand Strict Two-Phase Locking—the protocol that makes database transactions reliable by ensuring exclusive locks are never released before commit. This knowledge is essential for understanding how production databases balance concurrency with correctness.

Strict Two-Phase Locking (Strict 2PL)

The Real-World Standard for Transaction Isolation

What You Will Learn

The Problem with Basic 2PL

Before we understand Strict 2PL, we must appreciate the critical flaw in the basic Two-Phase Locking protocol that necessitates this stricter variant.

Basic 2PL Recap:

Basic 2PL divides a transaction's execution into two phases:

Growing Phase: Acquire locks; no locks released
Shrinking Phase: Release locks; no new locks acquired

But there's a devastating catch.

The Dirty Read Vulnerability

A Concrete Disaster Scenario:

Consider two transactions, T₁ and T₂, operating on account balance A (initially $1000):

Basic 2PL Failure: Dirty Read Leading to Unrecoverable Schedule
Time	T₁ (Transfer)	T₂ (Report)	Lock State on A	Value of A
t₁	lock-X(A)		X: T₁	$1000
t₂	read(A) → $1000		X: T₁	$1000
t₃	A = A - 500		X: T₁	$500 (uncommitted)
t₄	write(A)		X: T₁	$500 (uncommitted)
t₅	unlock(A) ← Enters shrinking phase		None	$500 (uncommitted)
t₆		lock-S(A) ← Granted!	S: T₂	$500 (uncommitted)
t₇		read(A) → $500 ← Dirty read!	S: T₂	$500 (uncommitted)
t₈		unlock(A)	None	$500 (uncommitted)
t₉		COMMIT ← T₂ commits with dirty data	None	$500 (uncommitted)
t₁₀	ABORT ← T₁ fails!		None	$1000 (rolled back)

The Catastrophe:

T₂ has committed a report showing a balance of $500. But T₁ aborted, so the $500 value never officially existed—A should still be $1000. This creates three critical problems:

Data Inconsistency: The committed report contains phantom data
Cascading Abort Required: To fix this, T₂ would need to be rolled back—but it already committed
Impossible Recovery: We cannot abort a committed transaction; durability guarantees prevent it

The Core Issue

Strict 2PL: The Essential Constraint

Strict Two-Phase Locking adds a single, powerful constraint to basic 2PL that eliminates the dirty read vulnerability completely:

A transaction must hold all its exclusive (write) locks until it commits or aborts.

This means exclusive locks are only released as part of the transaction's termination—never before. The lock release and transaction end become a single, atomic event.

Formal Definition

Why This Single Rule Fixes Everything:

Holding exclusive locks until transaction end means:

No Dirty Reads: Other transactions cannot access written data until the writing transaction commits or aborts
No Cascading Aborts: Since uncommitted data is never visible, no transaction can become dependent on uncommitted changes
Simple Recovery: After a crash, we can abort incomplete transactions without affecting committed ones
Strict Schedules: The resulting schedules are guaranteed to be both serializable AND recoverable

Converting Mermaid diagram...

The Subtle Distinction:

How Strict 2PL Eliminates Dirty Reads

Let's revisit our disaster scenario, but now with Strict 2PL enforced. Observe how the simple rule of holding exclusive locks transforms the outcome:

Strict 2PL: Dirty Read Prevented
Time	T₁ (Transfer)	T₂ (Report)	Lock State on A	Value of A
t₁	lock-X(A)		X: T₁	$1000
t₂	read(A) → $1000		X: T₁	$1000
t₃	A = A - 500		X: T₁	$500 (uncommitted)
t₄	write(A)		X: T₁	$500 (uncommitted)
t₅	(continues holding X lock)	lock-S(A) BLOCKED!	X: T₁	$500 (uncommitted)
t₆	(more operations...)	WAITING...	X: T₁	$500 (uncommitted)
t₇	ABORT ← T₁ fails	STILL WAITING	X: T₁	$500 (uncommitted)
t₈	unlock(A) ← Released on abort		None	$1000 (rolled back)
t₉		lock-S(A) ← Now granted!	S: T₂	$1000
t₁₀		read(A) → $1000 ← Clean data!	S: T₂	$1000
t₁₁		unlock(A), COMMIT	None	$1000

The Critical Difference:

T₂ never sees the uncommitted $500 value. Its report correctly shows $1000. The schedule is recoverable because no committed transaction ever read uncommitted data.

Problem Solved

Formal Guarantee:

This is precisely the definition of a cascadeless schedule: no transaction reads uncommitted data, so no cascading aborts can ever be necessary.

Strict 2PL and Recoverability

The relationship between Strict 2PL and schedule recoverability is fundamental to understanding why every production database uses this protocol. Let's establish the formal connection.

Schedule Classification Hierarchy

•Serial Schedules — Transactions execute one after another, no interleaving. Trivially correct but terrible performance.
•Serializable Schedules — Equivalent to some serial schedule. Produced by basic 2PL. May not be recoverable!
•Recoverable Schedules — If Tⱼ reads from Tᵢ, then Tᵢ must commit before Tⱼ commits. Allows cascading aborts.
•Cascadeless Schedules — No transaction reads uncommitted data. Subset of recoverable. No cascading aborts possible.
•Strict Schedules — No transaction reads OR writes uncommitted data. Strongest guarantee. Produced by Strict 2PL.

Converting Mermaid diagram...

Key Insight:

Strict 2PL produces schedules that belong to the intersection of Serializable and Strict schedules. This is not just a theoretical nicety—it's the practical sweet spot:

Serializable ensures logical correctness (isolation)
Strict ensures recoverability (durability after failures)

Basic 2PL only guarantees the first. Strict 2PL guarantees both.

Why 'Strict' Matters for Recovery

Proof that Strict 2PL Produces Strict Schedules:

In Strict 2PL, exclusive locks are held until commit or abort
Before any transaction Tⱼ can write to a data item X, it must acquire an exclusive lock on X
If Tᵢ wrote to X (holding X-lock) and Tⱼ wants to read or write X, Tⱼ must wait for Tᵢ's lock
Tᵢ's lock is only released when Tᵢ commits or aborts
Therefore, Tⱼ can only access X after Tᵢ terminates
This is precisely the definition of a strict schedule ∎

The elegance is in the simplicity: the lock-holding rule mechanically enforces exactly the schedule property we need for safe recovery.

Implementation Mechanics

strict_2pl_implementation.pseudo
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
// Strict 2PL Lock Manager - Pseudocode
 
class Strict2PLLockManager {
    locks: Map<DataItem, LockEntry>
    transactionLocks: Map<TransactionId, Set<DataItem>>
    
    // Acquire lock (blocks if incompatible lock held)
    func acquireLock(txn: Transaction, item: DataItem, mode: LockMode): void {
        if mode == EXCLUSIVE:
            // Wait until no other transaction holds any lock
            while locks[item].heldBy != null && locks[item].heldBy != txn.id:
                wait(locks[item].waitQueue)
            
            locks[item] = { mode: EXCLUSIVE, heldBy: txn.id }
            transactionLocks[txn.id].add(item)
            
        else if mode == SHARED:
            // Wait until no exclusive lock held by another transaction
            while locks[item].mode == EXCLUSIVE && locks[item].heldBy != txn.id:
                wait(locks[item].waitQueue)
            
            locks[item].sharedHolders.add(txn.id)
            transactionLocks[txn.id].add(item)
    }
    
    // Release shared lock (can be done before commit in Strict 2PL)
    func releaseSharedLock(txn: Transaction, item: DataItem): void {
        if locks[item].mode == SHARED:
            locks[item].sharedHolders.remove(txn.id)
            transactionLocks[txn.id].remove(item)
            notifyWaiters(item)
    }
    
    // Release ALL exclusive locks - ONLY called on commit/abort
    func releaseAllExclusiveLocks(txn: Transaction): void {
        for item in transactionLocks[txn.id]:
            if locks[item].mode == EXCLUSIVE && locks[item].heldBy == txn.id:
                locks[item] = { mode: NONE, heldBy: null }
                notifyWaiters(item)
        
        transactionLocks.remove(txn.id)
    }
    
    // Transaction commit - releases X-locks after commit record is durable
    func commit(txn: Transaction): void {
        writeCommitRecord(txn)      // Write to log
        forceLogToDisk()            // Ensure durability
        releaseAllExclusiveLocks(txn)  // NOW release X-locks
    }
    
    // Transaction abort - releases X-locks after undo is complete
    func abort(txn: Transaction): void {
        undoAllWrites(txn)          // Restore original values
        writeAbortRecord(txn)       // Log the abort
        releaseAllExclusiveLocks(txn)  // NOW release X-locks
    }
}

Critical Implementation Points:

•Lock Table Structure — A hash table mapping data items to lock entries. Each entry tracks the lock mode, holder(s), and a wait queue for blocked transactions.
•Transaction Lock Registry — A mapping from each transaction to all locks it holds. Essential for releasing all locks on commit/abort.
•Wait Queues — FIFO queues for transactions waiting on each locked item. Prevents starvation and ensures fairness.
•Commit/Abort Ordering — Exclusive locks are released AFTER commit/abort records are durably written to the log. This ensures recovery correctness.
•Lock Upgrade — When a transaction holds a shared lock and needs exclusive access, it must upgrade (if no other shared holders) or wait.

The Critical Ordering

Performance Implications

Advantages

•Simple Recovery — No cascading abort logic needed; just undo uncommitted, redo committed
•Predictable Behavior — Transactions never see uncommitted data; debugging is straightforward
•No Phantom Dependencies — Committed transactions are never affected by future aborts
•Well-Understood — Extensive research and decades of production experience
•ACID Compliance — Directly supports isolation and durability requirements

Performance Costs

•Longer Lock Holding — X-locks held for entire transaction duration increases contention
•Reduced Concurrency — More blocking when transactions write shared data
•Deadlock Risk — Longer lock durations increase probability of deadlocks
•Write-Heavy Penalty — Workloads with many writes suffer more than read-heavy
•Long Transaction Impact — One long write transaction can block many short ones

Strict 2PL Performance Impact by Workload
Workload Type	Concurrency Impact	Mitigation Strategies
Read-Heavy (90%+ reads)	Minimal impact — shared locks can still release early; X-locks rare	Default Strict 2PL works well
Write-Heavy (40%+ writes)	Significant contention — X-locks block all access to written items	Shorter transactions, partitioning, MVCC overlay
Mix with Hot Spots	Severe bottleneck — popular items constantly locked	Denormalization, caching, optimistic concurrency for hot data
Long Transactions	Cascading delays — one long T blocks many short ones	Transaction splitting, asynchronous patterns, queue-based designs
High Throughput OLTP	Lock manager becomes bottleneck	Lock-free structures for metadata, coarse-grained partitioning

The Practical Reality

Strict 2PL in Production Databases

Strict 2PL Implementation Across Database Systems
Database	Lock Implementation	Strict 2PL + MVCC?	Notable Features
PostgreSQL	Row-level X-locks held until commit	Yes — writers block writers, readers see snapshots	MVCC via tuple versioning; no read locks needed for snapshots
MySQL InnoDB	Row-level X-locks with gap locks	Yes — MVCC for consistent reads	Next-key locking prevents phantoms; configurable isolation
SQL Server	Row/page/table X-locks until commit	Yes (optional RCSI)	Lock escalation; snapshot isolation available
Oracle	Row-level X-locks until commit	Yes — always MVCC	Readers never blocked; undo segments store versions
SQLite	Database-level X-lock until commit	WAL mode adds concurrency	Simpler model; one writer at a time

The MVCC Complement:

Modern databases typically combine Strict 2PL for write-write conflicts with MVCC for read-write scenarios:

Writes still acquire X-locks (Strict 2PL)
Reads don't acquire locks but see a consistent snapshot (MVCC)
Result: Readers don't block writers, writers don't block readers

Investigating Lock Behavior

investigate_locks.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
31
-- PostgreSQL: View current locks
SELECT 
    locktype,
    relation::regclass,
    mode,
    granted,
    pid,
    pg_blocking_pids(pid) as blocked_by
FROM pg_locks
WHERE NOT granted OR locktype = 'relation'
ORDER BY relation;
 
-- MySQL InnoDB: View lock waits
SELECT 
    r.trx_id AS waiting_trx_id,
    r.trx_mysql_thread_id AS waiting_thread,
    b.trx_id AS blocking_trx_id,
    b.trx_mysql_thread_id AS blocking_thread
FROM information_schema.innodb_lock_waits w
JOIN information_schema.innodb_trx b ON b.trx_id = w.blocking_trx_id
JOIN information_schema.innodb_trx r ON r.trx_id = w.requesting_trx_id;
 
-- SQL Server: View lock waits
SELECT 
    request_session_id,
    resource_type,
    resource_database_id,
    request_mode,
    request_status
FROM sys.dm_tran_locks
WHERE request_status = 'WAIT';

Summary: Strict 2PL Fundamentals

Strict 2PL is the cornerstone of transaction processing in production databases. Let's consolidate the key concepts:

Key Takeaways

•Basic 2PL is insufficient — It guarantees serializability but allows dirty reads that create unrecoverable schedules. Transactions can commit based on data that later rolls back.
•Strict 2PL adds one rule — Hold all exclusive locks until commit or abort. This single constraint eliminates the dirty read vulnerability completely.
•No dirty reads, no cascading aborts — Because uncommitted data is never visible, committed transactions are never affected by later aborts.
•Strict schedules simplify recovery — After a crash, recovery is straightforward: undo uncommitted, redo committed. No need to track inter-transaction dependencies.
•Performance trade-off exists — Longer lock holding increases contention, especially for write-heavy workloads. Modern databases mitigate this with MVCC.
•Universal adoption — Every major production database implements Strict 2PL because the alternative—unrecoverable schedules—is unacceptable for reliable data management.

What's Next:

Page Complete