Two-phase locking

Why it matters

When a database blocks your UPDATE until another transaction finishes, or kills a transaction with "deadlock detected", two-phase locking is at work. It is the textbook protocol for serializability, still used by SQL Server, MySQL's InnoDB (for writes and locking reads) and many others, and it underlies the SELECT ... FOR UPDATE that applications use to make read-then-write logic safe. It is also one of the most asked DBMS interview topics, usually together with deadlocks.

The idea

Before reading an item a transaction takes a shared lock (S); before writing it takes an exclusive lock (X). Locks are compatible only if both are shared.

Locks alone are not enough: a transaction that locks A, writes, unlocks, then locks B can still interleave badly with another. Two-phase locking (2PL) adds one rule: a transaction may not acquire any lock after it has released one. Its life therefore has a growing phase (acquiring locks, never releasing) and a shrinking phase (releasing, never acquiring). The point where it holds all its locks is the lock point.

Why it works. In any 2PL schedule, ordering transactions by their lock points gives an equivalent serial order: if Ti and Tj conflict, one must have released a lock the other later acquired, so the first reached its lock point first. Every 2PL schedule is conflict serializable.

Variants

Real databases use strict or rigorous 2PL, because releasing write locks early would let others read uncommitted data.

Granularity and intention locks

Locking every row of a million-row update is expensive; locking the whole table blocks everyone. Databases support multiple granularity: database, table, page and row locks, with intention locks on the ancestors. To lock a row in X, a transaction first takes IX (intention exclusive) on the table; to lock a row in S, it takes IS. A transaction wanting the whole table in X checks the table lock alone and sees that someone holds IX, without inspecting every row. SIX (shared plus intention exclusive) suits "read the whole table, update a few rows". Many engines also perform lock escalation, converting many row locks into one table lock when a threshold is passed.

Deadlocks

Locking can create cycles of waiting: T1 holds A and waits for B, T2 holds B and waits for A. Neither can proceed.

1. 1

   Detection

   The DBMS maintains a wait-for graph (an edge Ti → Tj when Ti waits for a lock Tj holds) and periodically looks for cycles. It aborts a victim (often the youngest or the one with the least work) and the application retries. Most databases do this.
2. 2

   Timeouts

   Abort any transaction that waits longer than a threshold. Simple, but slow to react and can abort transactions that were not deadlocked.
3. 3

   Prevention with timestamps

   Give each transaction a start timestamp. Wait-die: an older transaction may wait for a younger one; a younger requester dies (aborts and restarts with its original timestamp). Wound-wait: an older requester wounds (aborts) the younger holder; a younger one waits. Both prevent cycles and avoid starvation.
4. 4

   Application practice

   Access rows in a consistent order (for example by primary key), keep transactions short, and retry on deadlock errors.

Phantoms

Locking existing rows does not stop another transaction from inserting a new row that matches your query. Preventing phantoms needs locks on ranges, not rows: predicate locks in theory, and next-key or gap locks on index ranges in practice (InnoDB uses them at its repeatable read level).

Trade-offs

2PL gives serializability with a simple rule, at the cost of blocking (readers wait for writers and writers for readers), deadlocks that need detection and retries, and reduced throughput under contention on hot rows. Fine-grained locks increase concurrency and lock-manager overhead; coarse locks are cheap and block more. Multiversion schemes, covered two lessons on, let readers avoid locks entirely, which is why most modern databases combine MVCC for reads with locks for writes.

In an interview

Connect the theory to application code: "Two checkouts updating the same stock row: with strict 2PL the second UPDATE waits for the first to commit, so no lost update. If I read then write in application code, I take the lock up front with SELECT FOR UPDATE. To avoid deadlocks I lock rows in primary-key order and retry on deadlock errors."