Two-phase locking (2PL)

How does 2PL guarantee serializability without seeing the future, and why does it thrash?

The constraint

We must guarantee that the serialization graph has no cycle without knowing the future. We do not know which items later transactions will touch.

The insight

You do not need to see the graph if you can force every transaction to have one well-defined instant at which it holds all the locks it will ever hold. The rule has two phases:

• Growing phase: acquire locks, never release.
• Shrinking phase: release locks, never acquire again.

The instant between them is the lock point.

The proof (two sentences)

If there is an edge Tᵢ → Tⱼ, then Tᵢ must have released a lock that Tⱼ then acquired, so Tᵢ's lock point is before Tⱼ's. Every edge therefore follows lock-point order, which is a total order, so no cycle can exist. 2PL yields conflict serializability, and the serialization order is the order of lock points.

Why "strict"?

Basic 2PL is serializable but not recoverable. Here is a failure:

1. Tᵢ writes X and, in its shrinking phase, releases the lock.
2. Tⱼ reads X and commits.
3. Tᵢ aborts.

Now a committed transaction (Tⱼ) has read a value that never existed, and you cannot roll Tⱼ back because it is already committed. The fix: hold exclusive (write) locks until commit. This gives strictness and removes cascading aborts (where aborting one transaction forces others to abort because they read its data). Holding all locks until commit gives rigorous 2PL, in which the serialization order equals the commit order.

A naming correction. Strict 2PL holds only the write locks until commit; rigorous 2PL holds all locks. Essentially every real implementation is rigorous and calls itself strict. The difference matters because only rigorous 2PL gives you commit order = serialization order, which is what you need when you later want external consistency (the order must match real time).

What it costs: the feedback loop

Under rigorous 2PL, lock hold time equals the transaction duration W, so the conflict window is as large as it can be for every item touched. Now feed this back into the arithmetic of Why concurrency is different:

1. Blocked transactions stay longer, so W grows.
2. A larger W at the same arrival rate means a larger L = λW.
3. A larger L means quadratically more conflict.
4. More conflict means more blocking. Back to step 1.

Throughput rises, peaks, and then falls. This is the classic 2PL thrashing curve. The modelled knee is at roughly a third of the transactions being blocked. (This is an analytic or simulation result from the queueing literature, not a theorem, so treat it as an order of magnitude, not a threshold to tune against.)

This shape is a positive feedback loop: the response to overload increases the load. It is the same structure as a garbage-collector death spiral, and it is a metastable failure (a system that stays broken even after the original trigger is gone). Restarting does not help if the backlog re-creates the loop.

2PL makes the lock point the serialization point; strictness makes the commit point the lock point; the price is that hold time equals transaction duration.