2PL Definition

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.

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:

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:

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:

The shape of the lock graph is always a mountain:

1. The graph starts at zero (no locks held)
2. During the growing phase, the graph only increases or stays flat (never decreases)
3. At the lock point, the graph reaches its maximum
4. During the shrinking phase, the graph only decreases or stays flat (never increases)
5. 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.

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

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.

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:

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:

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.

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