Part 4 of 6 · 3 min read
Two-phase locking
Shared and exclusive locks held until the end of the transaction.
Think of a library reference book. Many people may read it together at one desk. If someone wants to write notes in it, they must have it alone, and readers must wait until they finish.
For about 30 years, the book says, this was the only widely used serializable algorithm. The rules are stronger than the locks of module 2. Many transactions may read an object together, but a write needs exclusive access:
- If A has read an object, B must wait before writing it until A ends.
- If A has written an object, B must wait before reading it until A ends. Reading an old version is not allowed.
So writers block readers and readers block writers. This is the opposite of snapshot isolation's rule. In return, 2PL stops every race of module 2, including lost updates and write skew.
Two-phase locking (2PL)
Two-phase locking makes a transaction take a shared lock to read and an exclusive lock to write, and hold every lock until it commits or aborts.
Example: a transaction reads account A under a shared lock, then writes account B under an exclusive lock. It releases both only at commit.
The name: phase one, while running, acquires locks. Phase two, at the end, releases them all. A transaction that first reads and then writes may upgrade its shared lock to an exclusive one. MySQL InnoDB and SQL Server use it for their serializable level, and DB2 for repeatable read. It must not be confused with two-phase commit (module 9), which is something else.
Deadlock
A deadlock is two or more transactions each waiting for a lock the other holds, so none can go on.
Example: T1 holds the lock on A and wants B. T2 holds B and wants A. The database notices, aborts one, and the application must retry it.
Performance. The book names this as the big drawback. Locks cost time, but worse is lost concurrency: whenever two transactions could possibly race, one waits. Waits have no upper limit in classic databases, so a queue can form and latency at high percentiles becomes unstable. One slow transaction can hold up many others. Deadlocks are more frequent under 2PL, and each retry repeats all the work.
Predicate locks. A phantom has no row to lock. A predicate lock belongs to all rows that match a search condition, including rows not yet in the table. A reader of "bookings of room 123 between 12:00 and 13:00" takes a shared predicate lock on that condition. A writer who inserts or changes a row must check whether its old or new value matches a held predicate lock, and wait if it does. This stops all phantoms and write skew.
Index-range locks. Checking many predicate locks is slow. Most databases use a coarser version, index-range locking (next-key locking). The lock covers a larger set than needed, which is safe because any write matching the original also matches the larger set. For example lock all bookings of room 123 on the room index, or the noon to 1 p.m. range on a time index. If no suitable index exists, the fallback is a shared lock on the whole table: safe but slow.
A worked example. Balances A = 500, B = 500. T1 moves 100 from A to B. T2 sums A + B.
| Step | T1 | T2 |
|---|---|---|
| 1 | Exclusive lock A, A = 400 | |
| 2 | Wants shared lock on A, waits | |
| 3 | Exclusive lock B, B = 600, commit, release | |
| 4 | Gets locks, reads 400 + 600 = 1,000 |
T2 never sees 900. It waited for T1. The price is the wait.
Check yourself:
- Why does 2PL stop write skew while snapshot isolation does not?
- What does a database do when it finds a deadlock?