2PL Definition - Two-Phase Locking Protocol | OneNoughtOne

0/278

Database Management SystemsTwo-Phase Locking (2PL)

Two-Phase Locking Protocol

LevelIntermediate

Duration60 mins

TopicTwo-Phase Locking (2PL)

1 / 5

2PL Definition

The Protocol That Powers Modern Databases

In the previous module, we explored the fundamental building blocks of concurrency control: locks. We learned about shared and exclusive locks, lock compatibility, and lock granularity. But knowing what locks are is only half the battle. The critical question remains: How should transactions acquire and release locks to guarantee correct concurrent execution?

This question might seem trivial at first glance. After all, can't transactions simply grab locks when they need data and release them when they're done? The answer, as we'll discover, is a resounding no. The timing and sequence of lock operations profoundly impacts whether concurrent transactions produce correct results.

Two-Phase Locking (2PL) is the elegant solution to this problem—a protocol so fundamental that it forms the backbone of concurrency control in virtually every major relational database system, from PostgreSQL to Oracle, MySQL to SQL Server.

What You Will Learn

By the end of this page, you will understand the formal definition of Two-Phase Locking, why the two-phase structure is essential for correctness, how 2PL differs from naive locking approaches, and the historical context that led to its development. This foundation is critical before we explore the mechanics of each phase.

The Problem 2PL Solves

Before we define Two-Phase Locking, we must first understand why naive locking strategies fail. Consider a simple scenario:

Imagine two transactions:

T₁ reads account A, then reads account B
T₂ transfers $100 from A to B

If T₁ uses locks but releases each lock immediately after reading, something dangerous can happen:

naive_locking_problem.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
-- Transaction T₁: Read both accounts to compute total balance
-- Transaction T₂: Transfer $100 from A to B
 
-- Initial state: A = $500, B = $500, Total = $1000
 
-- Naive locking interleaving (PROBLEMATIC):
 
T₁: LOCK(A)           -- T₁ acquires lock on A
T₁: READ(A) → $500    -- T₁ reads A = $500
T₁: UNLOCK(A)         -- T₁ releases lock immediately ❌ PREMATURE!
 
T₂: LOCK(A)           -- T₂ acquires lock on A
T₂: READ(A) → $500    -- T₂ reads A
T₂: A = A - 100       -- T₂ computes new value
T₂: WRITE(A) → $400   -- T₂ writes A = $400
T₂: UNLOCK(A)         -- T₂ releases A
 
T₂: LOCK(B)           -- T₂ acquires lock on B
T₂: READ(B) → $500    -- T₂ reads B
T₂: B = B + 100       -- T₂ computes new value
T₂: WRITE(B) → $600   -- T₂ writes B = $600
T₂: UNLOCK(B)         -- T₂ releases B
T₂: COMMIT            -- T₂ commits
 
T₁: LOCK(B)           -- T₁ acquires lock on B
T₁: READ(B) → $600    -- T₁ reads B = $600 (updated by T₂)
T₁: UNLOCK(B)         -- T₁ releases B
 
-- T₁ computes total: $500 + $600 = $1100 ❌ WRONG!
-- Correct total should be $1000 (money was just transferred, not created)

The Inconsistent Read Problem

T₁ observed an inconsistent database state: it saw A before the transfer and B after the transfer. This violation occurred despite both transactions using locks correctly in isolation. The problem is that T₁ released its lock on A too early, allowing T₂ to modify A and B before T₁ finished reading both values.

The root cause: T₁ released a lock before it was truly done with its work. By releasing the lock on A, T₁ "opened a window" that allowed T₂ to slip in and modify data that T₁ would later need to read.

This is not a contrived example—it's a fundamental problem that occurs in any system allowing concurrent access to shared data. The question becomes: What rules should govern when locks are acquired and released?

Formal Definition of Two-Phase Locking

Two-Phase Locking (2PL) is a concurrency control protocol that divides each transaction's execution into exactly two phases based on lock acquisition and release behavior:

The Two-Phase Locking Protocol

Phase 1 - Growing Phase: A transaction may acquire (obtain) locks but may NOT release any lock.

Phase 2 - Shrinking Phase: A transaction may release locks but may NOT acquire any new lock.

Once a transaction releases its first lock, it enters the shrinking phase and can never acquire another lock.

Let's express this more formally using mathematical notation:

Let L⁺(X) denote a lock acquisition on data item X, and L⁻(X) denote a lock release on X.

2PL Rule: For any transaction Tᵢ, if Tᵢ performs L⁻(X) before L⁺(Y) for any data items X and Y (where possibly X = Y), then the schedule is NOT 2PL-compliant.

Equivalently: All lock acquisitions must precede all lock releases.

The Lock Point: The moment when a transaction has acquired all the locks it will ever need (the transition point from growing to shrinking phase) is called the lock point. This concept will become crucial when we prove that 2PL guarantees serializability.

Converting Mermaid diagram...

Visualizing the Two Phases

The "two phases" become strikingly clear when we graph the number of locks held by a transaction over time. This visualization reveals the protocol's essential constraint:

Lock Count Over Time in 2PL Transaction
Time	Operation	Locks Held	Phase
t₁	Lock(A)	1	Growing ↑
t₂	Read(A)	1	Growing ↑
t₃	Lock(B)	2	Growing ↑
t₄	Read(B)	2	Growing ↑
t₅	Lock(C)	3	Growing ↑
t₆	Write(C)	3	Growing ↑
t₇	Lock Point	3 (MAX)	Transition
t₈	Unlock(A)	2	Shrinking ↓
t₉	Unlock(B)	1	Shrinking ↓
t₁₀	Unlock(C)	0	Shrinking ↓
t₁₁	Commit	0	Complete

The shape of the lock graph is always a mountain:

The graph starts at zero (no locks held)
During the growing phase, the graph only increases or stays flat (never decreases)
At the lock point, the graph reaches its maximum
During the shrinking phase, the graph only decreases or stays flat (never increases)
The graph ends at zero (all locks released)

Critical insight: The graph can NEVER have a "valley" followed by another "peak". If a transaction releases a lock and then tries to acquire another, it violates 2PL. This single constraint—no valleys followed by peaks—is the entire protocol.

Common Misconception

2PL does NOT require that all locks be acquired before any data operations. A transaction can acquire locks, perform reads/writes, acquire more locks, perform more operations—as long as it hasn't released any locks yet. The constraint is only on the RELEASE of locks, not on the timing of data operations within the growing phase.

How 2PL Fixes the Naive Locking Problem

Let's revisit our earlier example and see how Two-Phase Locking prevents the inconsistent read problem:

2pl_solution.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
32
33
-- Transaction T₁: Read both accounts (following 2PL)
-- Transaction T₂: Transfer $100 from A to B (following 2PL)
 
-- Initial state: A = $500, B = $500, Total = $1000
 
-- 2PL-compliant execution:
 
T₁: LOCK(A)           -- T₁ acquires lock on A (growing phase)
T₁: READ(A) → $500    -- T₁ reads A = $500
-- T₁ CANNOT release A yet (would enter shrinking phase too early)
 
T₁: LOCK(B)           -- T₁ acquires lock on B (still growing phase)
T₁: READ(B) → $500    -- T₁ reads B = $500
 
-- T₁ has now acquired ALL locks it needs (LOCK POINT reached)
-- T₁ can now calculate: Total = $500 + $500 = $1000 ✓ CORRECT!
 
T₁: UNLOCK(A)         -- T₁ enters shrinking phase
T₁: UNLOCK(B)         -- T₁ continues shrinking
T₁: COMMIT            -- T₁ commits
 
-- Now T₂ can proceed
T₂: LOCK(A)           -- T₂ acquires A
T₂: READ(A) → $500
T₂: WRITE(A) → $400   -- A = A - 100
T₂: LOCK(B)           -- T₂ acquires B
T₂: READ(B) → $500
T₂: WRITE(B) → $600   -- B = B + 100
T₂: UNLOCK(A)
T₂: UNLOCK(B)
T₂: COMMIT
 
-- Final state: A = $400, B = $600, Total = $1000 ✓

Naive Locking (INCORRECT)

•Locks released immediately after use
•Creates "windows" for interference
•Can observe inconsistent states
•No guarantee of serializability
•T₁ saw: A=$500, B=$600 (impossible state)

Two-Phase Locking (CORRECT)

•All locks held until shrinking phase
•No windows for interference
•Always observes consistent state
•Guarantees conflict serializability
•T₁ saw: A=$500, B=$500 (valid state)

Why does 2PL work?

By requiring T₁ to hold the lock on A until after it acquires the lock on B, 2PL ensures that T₁ observes a consistent snapshot of both values. T₂ cannot modify A while T₁ holds its lock, so T₁ is guaranteed to see either:

The state before T₂'s transfer (A=$500, B=$500), or
The state after T₂'s transfer (A=$400, B=$600)

But never a mixture of the two. This is the essence of serializability—the result is equivalent to some serial execution.

Historical Context and Theoretical Foundation

Two-Phase Locking wasn't just discovered—it was proven mathematically. Understanding this history helps appreciate why 2PL became the dominant concurrency control mechanism.

The Genesis of 2PL:

In 1976, K.P. Eswaran, J.N. Gray, R.A. Lorie, and I.L. Traiger published the seminal paper "The Notions of Consistency and Predicate Locks in a Database System" at IBM Research. This paper introduced Two-Phase Locking and proved its correctness.

The key theorem they proved:

The 2PL Theorem (1976)

Theorem: If all transactions in a schedule follow the Two-Phase Locking protocol, then the schedule is conflict-serializable.

Corollary: The equivalent serial order is determined by the order of the transactions' lock points. If transaction Tᵢ's lock point occurs before Tⱼ's lock point, then in the equivalent serial schedule, Tᵢ precedes Tⱼ.

Why this matters:

This theorem transformed database concurrency control from an ad-hoc engineering practice into a mathematically rigorous discipline. Before 2PL, system designers had to reason about every possible interleaving of operations—an exponentially complex task. With 2PL, designers could simply ensure all transactions followed the protocol, and correctness would be guaranteed automatically.

The influence of 2PL:

System	Year	2PL Implementation
IBM System R	1977	First commercial implementation
Oracle	1979	Adapted 2PL with variations
DB2	1983	Strict 2PL
SQL Server	1989	Strict 2PL with lock escalation
PostgreSQL	1996	2PL with MVCC hybrid
MySQL InnoDB	2001	Strict 2PL

Every major relational database system implements some variant of 2PL. It's not an exaggeration to say that 2PL is one of the most successful theoretical results in computer science, with direct practical impact on billions of daily database transactions.

The 2PL Contract: What It Guarantees

Two-Phase Locking establishes a contract between the database system and its users. Understanding this contract is essential for correct database design and debugging concurrency issues.

What 2PL Guarantees

•Conflict Serializability — Every 2PL schedule is equivalent to some serial schedule. The concurrent execution produces results identical to running transactions one after another.
•Consistent Database States — If each transaction individually preserves database consistency, and all transactions follow 2PL, then the database remains consistent after any sequence of committed transactions.
•Isolation Enforcement — Transactions appear to execute in isolation from each other's intermediate states. No transaction can observe another's partial results (during the transaction's own execution).
•Deterministic Ordering — The equivalent serial order is determined by lock points. This provides a well-defined serialization order that can be reasoned about.

What 2PL Does NOT Guarantee

•Freedom from Deadlock — 2PL can lead to deadlocks where transactions wait for each other indefinitely. Deadlock detection/prevention is handled separately.
•Recoverability — Basic 2PL doesn't guarantee that schedules are recoverable. Strict 2PL (covered later) addresses this.
•Fair Scheduling — 2PL doesn't prevent starvation. A transaction might wait indefinitely while others continuously acquire conflicting locks.
•Performance — Holding locks longer (as 2PL requires) reduces concurrency. There's an inherent tension between correctness and performance.

The Trade-off Principle

2PL trades concurrency for correctness. By forcing transactions to hold locks longer, it reduces the overlap between transactions. This guarantees correct results but may increase wait times and reduce throughput. Understanding this trade-off is essential for performance tuning in production systems.

Recognizing 2PL Compliance

A critical skill for database engineers is the ability to quickly determine whether a given transaction schedule follows 2PL. Here's a systematic approach:

2pl_compliance_check.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ALGORITHM: Check 2PL Compliance for Transaction Tᵢ
 
1. Extract all lock operations for Tᵢ from the schedule
2. Let first_unlock = position of first UNLOCK operation
3. Let last_lock = position of last LOCK operation
 
IF last_lock > first_unlock:
    RETURN "NOT 2PL compliant"
    // Transaction acquires a lock after releasing another
ELSE:
    RETURN "2PL compliant"
    // All locks acquired before any release
 
EXAMPLE 1 (2PL Compliant):
T₁: Lock(A) → Lock(B) → Lock(C) → Unlock(A) → Unlock(B) → Unlock(C)
last_lock = 3 (Lock C)
first_unlock = 4 (Unlock A)
3 < 4 → ✓ 2PL Compliant
 
EXAMPLE 2 (NOT 2PL Compliant):
T₂: Lock(A) → Unlock(A) → Lock(B) → Unlock(B)
last_lock = 3 (Lock B)
first_unlock = 2 (Unlock A)
3 > 2 → ✗ NOT 2PL Compliant

Quick 2PL Compliance Examples
Schedule	2PL Compliant?	Reason
L(A), L(B), U(A), U(B)	✓ Yes	All locks before all unlocks
L(A), U(A), L(B), U(B)	✗ No	L(B) after U(A)
L(A), L(B), L(C), U(C), U(B), U(A)	✓ Yes	Last lock before first unlock
L(A), R(A), U(A)	✓ Yes	Single lock, trivially 2PL
L(A), L(B), U(A), L(C), U(B), U(C)	✗ No	L(C) after U(A)
L(A), L(B), L(C), U(A), U(C), U(B)	✓ Yes	Unlock order doesn't matter, only that all locks precede

Key Insight

The order in which locks are released doesn't matter for 2PL compliance. The protocol only requires that ALL lock acquisitions complete before ANY release begins. Whether you unlock A before B or B before A during the shrinking phase is irrelevant to correctness (though it may affect deadlock behavior).

Summary: Understanding 2PL Definition

We've established the theoretical foundation of Two-Phase Locking. Let's consolidate the key concepts:

Key Takeaways

•Naive locking fails — Releasing locks early creates windows for inconsistent reads and lost updates.
•2PL divides transactions into two phases — Growing (acquire only) and Shrinking (release only).
•The lock point marks the transition — The moment when maximum locks are held, separating the two phases.
•2PL guarantees conflict serializability — Proven mathematically by Eswaran et al. in 1976.
•The equivalent serial order follows lock point order — Transactions serialize in the order their lock points occur.
•2PL trades concurrency for correctness — Longer lock holding reduces parallelism but ensures valid results.

What's next:

Now that we understand what Two-Phase Locking is and why it exists, we'll dive deep into each phase. The next page examines the Growing Phase in detail—exploring exactly what happens during lock acquisition, how conflicts are handled, and the strategies transactions use to acquire the locks they need.

Page Complete

You now understand the formal definition of Two-Phase Locking, its historical origins, and why the two-phase structure is essential for database correctness. This theoretical foundation prepares you to explore the mechanics of each phase and ultimately understand how production database systems implement this critical protocol.