Loading learning content...
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.
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.
Before we define Two-Phase Locking, we must first understand why naive locking strategies fail. Consider a simple scenario:
Imagine two transactions:
If T₁ uses locks but releases each lock immediately after reading, something dangerous can happen:
123456789101112131415161718192021222324252627282930
-- 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 AT₁: READ(A) → $500 -- T₁ reads A = $500T₁: UNLOCK(A) -- T₁ releases lock immediately ❌ PREMATURE! T₂: LOCK(A) -- T₂ acquires lock on AT₂: READ(A) → $500 -- T₂ reads AT₂: A = A - 100 -- T₂ computes new valueT₂: WRITE(A) → $400 -- T₂ writes A = $400T₂: UNLOCK(A) -- T₂ releases A T₂: LOCK(B) -- T₂ acquires lock on BT₂: READ(B) → $500 -- T₂ reads BT₂: B = B + 100 -- T₂ computes new valueT₂: WRITE(B) → $600 -- T₂ writes B = $600T₂: UNLOCK(B) -- T₂ releases BT₂: COMMIT -- T₂ commits T₁: LOCK(B) -- T₁ acquires lock on BT₁: 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)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?
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:
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.
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:
| 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:
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.
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.
Let's revisit our earlier example and see how Two-Phase Locking prevents the inconsistent read problem:
123456789101112131415161718192021222324252627282930313233
-- 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 phaseT₁: UNLOCK(B) -- T₁ continues shrinkingT₁: COMMIT -- T₁ commits -- Now T₂ can proceedT₂: LOCK(A) -- T₂ acquires AT₂: READ(A) → $500T₂: WRITE(A) → $400 -- A = A - 100T₂: LOCK(B) -- T₂ acquires BT₂: READ(B) → $500T₂: WRITE(B) → $600 -- B = B + 100T₂: UNLOCK(A)T₂: UNLOCK(B)T₂: COMMIT -- Final state: A = $400, B = $600, Total = $1000 ✓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:
But never a mixture of the two. This is the essence of serializability—the result is equivalent to some serial execution.
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:
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.
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.
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.
A critical skill for database engineers is the ability to quickly determine whether a given transaction schedule follows 2PL. Here's a systematic approach:
123456789101112131415161718192021222324
ALGORITHM: Check 2PL Compliance for Transaction Tᵢ 1. Extract all lock operations for Tᵢ from the schedule2. Let first_unlock = position of first UNLOCK operation3. Let last_lock = position of last LOCK operation IF last_lock > first_unlock: RETURN "NOT 2PL compliant" // Transaction acquires a lock after releasing anotherELSE: 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| 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 |
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).
We've established the theoretical foundation of Two-Phase Locking. Let's consolidate the key concepts:
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.
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.