Two-Phase Locking
Imagine two bank transfers running at the same instant on the same account. One deposits 50. If the database lets both transactions read and write the balance in an arbitrary interleaving, the final balance can end up wrong. This depends purely on timing. This is the core problem of concurrency control. It means guaranteeing that concurrent transactions behave as if they ran one after another. This holds true even though the system interleaves their operations for performance. Conflict Serializability tells us precisely which interleavings ("schedules") are safe. Safe schedules are those equivalent to some serial order. But conflict serializability is a property we can check only after the fact. We check it by examining a completed schedule. What a database actually needs is a protocol. This is a set of rules a scheduler enforces in real time. It must work before the scheduler knows how transactions will unfold. It must also be guaranteed to only ever produce conflict-serializable schedules. Two-Phase Locking (2PL) is the classical answer to this problem. It remains the conceptual backbone of concurrency control in most commercial and open-source database systems. The rule is almost embarrassingly simple to state. Every transaction acquires all the locks it will ever need before it releases any lock. Yet this one discipline is provably sufficient to guarantee conflict serializability. This holds for every schedule the scheduler can produce. It holds regardless of how transactions are interleaved by the operating system or query engine. This article builds 2PL from the ground up. We cover the lock types (shared and exclusive). We cover the compatibility matrix that governs when locks can coexist. We explain the growing and shrinking phases that give the protocol its name. We also cover the theorem that connects the protocol to conflict serializability. We also cover the practical variants — Strict 2PL and Rigorous 2PL — that real systems actually deploy. This matters because plain 2PL alone does not guarantee recoverability from crashes. By the end, you will be able to trace lock acquisition and release through a concrete schedule. You will be able to explain exactly why the two-phase rule forces a conflict-equivalent serial order to exist. You will also see how this protocol sets up the next problems in the pipeline. These include deadlock (Two-Phase Locking can make transactions wait forever on each other). They also include the practical isolation levels that trade some strictness for performance.
- 2PL requires every transaction to finish acquiring all locks (growing phase) before releasing any lock (shrinking phase).
- Shared (S) locks permit concurrent reads; exclusive (X) locks are required for writes and are held alone.
- The two-phase rule guarantees every legal schedule is conflict-serializable — this is the 2PL Correctness Theorem.
- Plain 2PL can still allow cascading rollbacks; Strict 2PL (hold X locks until commit/abort) fixes this and is what real systems use.
- 2PL does not prevent deadlock — it trades that risk for the serializability guarantee, motivating deadlock detection/prevention.
- The lock point (moment of maximum locks held) determines each transaction's position in the equivalent serial order.
If every transaction acquires all its locks before releasing any of them, the resulting schedule is guaranteed to be conflict-serializable.
The idea
A lock is a system-managed flag associated with a data item that a transaction must hold before performing certain operations on that item. The two basic lock modes are shared (S), which a transaction must hold to read an item, and exclusive (X), which a transaction must hold to write an item. Multiple transactions may simultaneously hold S-locks on the same item (concurrent reads are safe), but an X-lock is incompatible with every other lock on that item, including other X-locks and S-locks — a write must be isolated from all other access. This compatibility rule is summarized in a small matrix and is the only fact about lock modes the scheduler needs to enforce mechanically.
Two-Phase Locking is a protocol layered on top of these lock modes: it constrains when a transaction is allowed to request or release locks, without needing to know in advance what data the transaction will touch. Formally, a transaction is two-phase if it can be split into a growing phase, during which it may only acquire locks (and never release any), followed by a shrinking phase, during which it may only release locks (and never acquire any new one). The moment a transaction releases its first lock marks the irreversible transition from growing to shrinking — after that point, it is committed to never asking for another lock. A schedule is said to obey 2PL if every transaction participating in it is two-phase in this sense. The remarkable fact — and the reason this protocol is taught as foundational — is that obeying 2PL is a sufficient (though not necessary) condition for conflict serializability. A scheduler that enforces 2PL never needs to inspect the whole schedule, reason about cycles, or know the future: it only needs to check, locally, that no transaction acquires a lock after it has released one. This turns a global, retrospective correctness property (Conflict Serializability) into a simple, local, real-time rule — exactly the kind of property a database engine can enforce cheaply on every lock request.
How it works
The scheduler intercepts every read and write operation and requires the issuing transaction to hold the appropriate lock first. Concretely:
- Before reading item `X`, a transaction must hold an S-lock or X-lock on `X`.
- Before writing item `X`, a transaction must hold an X-lock on `X`.
- A transaction may upgrade an S-lock to an X-lock (this still counts as "acquiring," so it must happen in the growing phase).
- Once a transaction releases any lock, it may never request a new lock again for the rest of its life.
The lock manager maintains, for each data item, a lock table entry recording which transactions hold which mode of lock on it. Requests that are incompatible with the current holders are queued (this is where deadlock becomes possible — foreshadowed but handled by a separate mechanism). ``` // Lock manager state: for each item X, a set of (transaction, mode) pairs currently held, // plus a wait queue of pending requests. procedure LOCK(T, X, mode): // mode in {S, X} if T has entered its shrinking phase: abort T with error "2PL violation: lock requested after release" while not COMPATIBLE(mode, currentLocksOn(X), except T): block T on wait-queue(X) // may lead to deadlock; handled elsewhere grant (T, mode) on X record X in T.lockSet T.phase = GROWING procedure UNLOCK(T, X): remove (T, mode) from X's lock table entry remove X from T.lockSet T.phase = SHRINKING // irreversible: from now on T may only unlock wake up compatible waiters on X procedure COMPATIBLE(mode, holders, except T): for each (T2, m2) in holders where T2 != except T: if mode == X or m2 == X: return false // X is incompatible with everything return true // S is compatible with other S locks // Transaction execution under 2PL: procedure EXECUTE_TRANSACTION(T, operations): for op in operations: if op is Read(X): LOCK(T, X, S) perform read else if op is Write(X): LOCK(T, X, X) // upgrade if S already held perform write else if op is UnlockRequest(X): UNLOCK(T, X) // At transaction end, release any remaining locks (all at once, in shrinking phase) for X in T.lockSet: UNLOCK(T, X) ``` The pseudocode enforces the two-phase discipline directly: `LOCK` refuses any request once `T.phase` has become `SHRINKING`, and `UNLOCK` is the sole operation that flips the phase. Note that a transaction can call `UNLOCK` many times consecutively once shrinking begins — that is legal — but it can never call `LOCK` again afterward.
Strict and Rigorous variants. Plain 2PL guarantees serializability but not recoverability — a transaction can release an X-lock, letting another transaction read its uncommitted write, and then abort, forcing a cascading rollback. Strict 2PL fixes this by holding all exclusive locks until the transaction commits or aborts (shared locks may still be released early). Rigorous 2PL goes further and holds all locks, shared and exclusive, until commit/abort. Rigorous 2PL has the pleasant extra property that the transactions' commit order matches a valid serialization order, and it is what most production lock managers implement.
Complexity & correctness
Time overhead. Each read or write operation now costs one lock-table lookup and possibly a compatibility check against the item's holder list. If a lock is held in a compatible mode, granting is `O(1)` (hash lookup into the lock table plus a scan of the small holder set, typically bounded by a small constant since exclusive locks admit at most one holder). If the lock is unavailable, the requesting transaction blocks, and the cost becomes wait time rather than CPU time — this is where 2PL's honest tradeoff shows up: throughput can degrade under contention, and in the worst case a cycle of waits produces deadlock, requiring a separate detection or prevention mechanism (a topic 2PL foreshadows but does not solve). Lock acquisition itself, ignoring waiting, is `O(1)` amortized per operation with a hash-based lock table; releasing all locks at transaction end is `O(k)` for `k` locks held.
Space overhead. The lock table needs one entry per currently-locked item, each entry storing the set of holding transactions and mode — `O(L)` where `L` is the number of distinct items locked system-wide at any instant, bounded by the number of active transactions times the items each touches.
Correctness — the 2PL Theorem. The central claim is: > If every transaction in a schedule `S` follows the two-phase locking protocol, then `S` is conflict-serializable. Proof sketch. Define, for each transaction `T_i`, its lock point as the moment `T_i` holds the maximum number of locks it will ever simultaneously hold — equivalently, the instant it transitions from growing to shrinking (the last lock acquisition before the first release). Order the transactions by their lock points: `T_1, T_2, …, T_n` where `T_i`'s lock point precedes `T_j`'s lock point whenever `i < j`. We claim the serial schedule `T_1 T_2 … T_n` (executed in full, one after another) is conflict-equivalent to `S`. Consider any two transactions `T_i`, `T_j` with `i < j` that have a conflicting pair of operations (both access the same item, and at least one is a write). Conflicting operations require conflicting lock modes on the same item, and conflicting locks cannot be held simultaneously — so one transaction's lock request on that item must be granted only after the other releases its lock on it. Suppose, for contradiction, `T_j`'s conflicting operation on item `X` happened before `T_i`'s in `S`. Then `T_j` acquired its lock on `X`, and `T_i` could only acquire its conflicting lock on `X` after `T_j` released its lock on `X`. Since `T_j` only releases locks in its shrinking phase, `T_j`'s release of `X` occurs at or after `T_j`'s lock point. Since `T_i` only acquires locks in its growing phase, `T_i`'s acquisition of `X` occurs at or before `T_i`'s lock point. Chaining these: `T_i`'s lock point ≥ (time `T_i` acquires `X`) ≥ (time `T_j` releases `X`) ≥ `T_j`'s lock point. That contradicts `i < j`, which was defined precisely so that `T_i`'s lock point precedes `T_j`'s. So no such contradiction can arise: every conflicting pair of operations between `T_i` and `T_j` must actually occur in the order `T_i` before `T_j` in `S`, matching their order in the serial schedule. Since all conflicting operation pairs agree in relative order between `S` and the serial schedule `T_1…T_n`, the two schedules are conflict-equivalent, and `S` is conflict-serializable. ∎
Honesty about limits. The converse is false: there exist conflict-serializable schedules that no 2PL scheduler could ever produce, because 2PL is a sufficient, not necessary, condition. 2PL also says nothing about recoverability on its own (motivating Strict/Rigorous variants) and nothing about deadlock avoidance (motivating a dedicated deadlock-handling layer). It guarantees a correctness property, not liveness or throughput.
Worked example
Consider two transactions on accounts `A` and `B`, `T1` transferring $50 from `A` to `B`, and `T2` computing the sum `A + B` for a report. Under Strict 2PL, the scheduler produces the following interleaved schedule (locks acquired just-in-time, all exclusive locks held to commit):
| Step | Action | Lock event | Legal under 2PL? |
|---|---|---|---|
| 1 | T1: `Lock-X(A)` | grant X(A) to T1 | ✓ growing |
| 2 | T1: `Read(A)` | — | ✓ |
| 3 | T1: `A := A - 50` | — | ✓ |
| 4 | T1: `Write(A)` | — | ✓ |
| 5 | T2: `Lock-S(A)` | blocked — X(A) held by T1 | request queued |
| 6 | T1: `Lock-X(B)` | grant X(B) to T1 | ✓ still growing |
| 7 | T1: `Read(B)` | — | ✓ |
| 8 | T1: `B := B + 50` | — | ✓ |
| 9 | T1: `Write(B)` | — | ✓ |
| 10 | T1: `Commit` | release X(A), X(B) | shrinking begins & ends atomically |
| 11 | T2: `Lock-S(A)` | now granted (T1 released) | ✓ growing |
| 12 | T2: `Read(A)` | — | ✓ |
| 13 | T2: `Lock-S(B)` | granted (uncontended) | ✓ growing |
| 14 | T2: `Read(B)` | — | ✓ |
| 15 | T2: `Sum := A + B` | — | ✓ |
| 16 | T2: `Commit` | release S(A), S(B) | shrinking |
Both `T1` and `T2` are individually two-phase: `T1` grows through steps 1–9 and shrinks entirely at step 10 (Strict 2PL releases all X-locks together at commit); `T2` grows through steps 11–14 and shrinks at step 16. The schedule is conflict-equivalent to the serial order `T1, T2` — exactly matching intuition, since `T2` was forced to wait until `T1`'s transfer fully completed before it could read either balance, so it reports a consistent post-transfer total.
Contrast — a violation. Suppose instead the scheduler allowed this (non-2PL) interleaving: `T1` locks and reads `A`, writes `A`, releases X(A) early, then later tries to lock `B`. That last request happens after `T1` has already entered its shrinking phase (it released a lock), so line `LOCK(T, X, mode)` in the pseudocode would immediately abort `T1` with a 2PL violation — the protocol itself refuses to let this schedule occur. This is precisely how the protocol prevents the classic lost-update and inconsistent-read anomalies: it structurally forbids the transaction shapes that could produce them, rather than detecting the anomaly after the fact.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Treating 2PL as "lock everything at the start, unlock at the end" | Confusing 2PL with a specific locking schedule rather than a phase discipline | 2PL only forbids acquire-after-release; locks may still be acquired incrementally as data is touched |
| Believing 2PL prevents deadlock | 2PL only guarantees serializability, a completely separate property from liveness | Pair 2PL with deadlock detection (wait-for graphs) or prevention (timestamp ordering) |
| Releasing an X-lock before commit under plain 2PL | Allows another transaction to read uncommitted data, causing cascading rollback on abort | Use Strict or Rigorous 2PL in practice — never release write locks early |
| Forgetting lock upgrades count as "acquiring" | Upgrading S→X after some other lock was released breaks the growing phase silently | Upgrades must occur strictly within the growing phase, same as any new lock |
| Assuming every conflict-serializable schedule is reachable under 2PL | 2PL is sufficient, not necessary, for serializability | Accept the tradeoff: 2PL trades some concurrency for a simple, checkable guarantee |
Pioneers & history
The two-phase locking protocol was formalized in the context of early relational and network database systems, where multiple programs needed to safely share a single data store without corrupting each other's updates. It grew out of foundational work connecting concurrency control to serializability theory, turning an abstract correctness criterion into an enforceable, real-time system mechanism.
Origins · 1 minKapali P. Eswaran and how this was discovered
Eswaran, together with Jim Gray, Raymond Lorie, and Irving Traiger at IBM's System R project, formalized the notion of consistency for concurrent transaction execution and proved the correctness of two-phase locking. Their 1976 paper, "The Notions of Consistency and Predicate Locks in a Database System," established the mathematical foundation — the lock-point argument used above — that let engineers reason rigorously about a mechanism they were already building into System R, one of the first practical relational database prototypes.
Where this matters
Two-Phase Locking is not a historical curiosity — it is the default concurrency-control discipline inside most production relational database engines. IBM Db2, Microsoft SQL Server, and Oracle's lock-based isolation modes all implement variants of Strict or Rigorous 2PL under the hood for row-level and table-level locking, even when higher isolation levels are exposed to the user through friendlier names. Distributed databases and distributed transaction coordinators (two-phase commit protocols, distributed lock managers in systems like Google's Spanner or older distributed DB2 deployments) extend the same growing/shrinking discipline across machines, adding network round-trips to the lock-acquisition cost analyzed above. The protocol is also the conceptual entry point into two major follow-on topics. First, because 2PL permits transactions to block each other while waiting for locks, real systems must detect or prevent <a class="wiki-link" href="/wiki/cs-db-deadlocks-in-databases" data-track="wiki_article.body.wiki_link">Deadlocks in Databases</a> — cyclic waiting that plain 2PL neither causes to be checked nor prevents from occurring. Second, because full Strict/Rigorous 2PL can be expensive under heavy read contention, most systems expose configurable <a class="wiki-link" href="/wiki/cs-db-isolation-levels" data-track="wiki_article.body.wiki_link">Isolation Levels</a> (Read Committed, Repeatable Read, Serializable) that relax exactly which locks are held and for how long, trading some serializability guarantees for throughput — a tradeoff that only makes sense once you understand what the strict protocol was guaranteeing in the first place.
Ask the tutor: How does Two-Phase Locking interact with deadlock detection algorithms like wait-for graphs, and what happens when a cycle is found?
Does 2PL guarantee that transactions never deadlock?
No — 2PL and deadlock are separate concerns entirely. 2PL guarantees that if a schedule completes, it is conflict-serializable. But because transactions under 2PL can block waiting for locks held by other transactions, it is entirely possible for two or more transactions to wait on each other in a cycle, none able to proceed. This is a deadlock, and 2PL neither causes nor prevents it structurally — it simply doesn't address liveness. Real systems pair 2PL with a separate deadlock-handling layer: either detection (building a wait-for graph and aborting a transaction to break cycles) or prevention (using transaction timestamps to decide which transaction should wait and which should abort, as in the wound-wait or wait-die schemes).
Is Two-Phase Locking necessary for conflict serializability, or only sufficient?
Only sufficient. There exist schedules that are conflict-serializable — equivalent to some serial order — yet could never have been produced by a scheduler enforcing 2PL, because they involve a transaction releasing a lock and later acquiring another in a pattern the two-phase rule forbids. 2PL trades away some of these "accidentally correct" schedules in exchange for a rule the scheduler can check locally and in real time, without ever needing to see the whole schedule or detect cycles after the fact. This is a deliberate, honest tradeoff: simplicity and enforceability over maximal concurrency.
What is the difference between Strict 2PL and Rigorous 2PL?
Strict 2PL requires that all exclusive (write) locks be held until the transaction commits or aborts, while shared (read) locks may be released earlier, during normal execution. Rigorous 2PL is more conservative still: it requires all locks, both shared and exclusive, to be held until commit or abort. Rigorous 2PL guarantees that the order in which transactions commit matches a valid serialization order of the schedule, which simplifies recovery and logging logic. Most production database lock managers implement Rigorous 2PL (or something functionally equivalent) rather than plain or even Strict 2PL, because the extra locking cost is usually worth the simpler recovery guarantees.
Why does releasing a lock early cause cascading rollback?
If a transaction `T1` releases an exclusive lock on item `X` right after writing it — but before committing — another transaction `T2` can acquire a lock on `X` and read `T1`'s uncommitted write. If `T1` later aborts (say, due to a constraint violation or crash), its write to `X` must be undone. But `T2` has already read that now-invalid value, possibly written it elsewhere, or even committed based on it. To maintain correctness, `T2` (and anything that depended on `T2`) must also be rolled back — a cascading rollback. Strict and Rigorous 2PL prevent this entirely by never letting anyone see an uncommitted write in the first place.
How does the lock-point argument actually prove serializability, intuitively?
Every transaction has a moment — its lock point — where it holds the maximum number of locks it will ever hold simultaneously, marking its transition from acquiring to releasing. If you order transactions by these lock points, you get a candidate serial order. The proof shows that for any two transactions with a genuine data conflict (same item, one is a write), the two-phase rule forces their conflicting operations to occur in an order consistent with their lock points: the earlier-lock-point transaction's operation must come first, because the later transaction cannot acquire a conflicting lock until the earlier one releases it, and releases only happen after the lock point. Since every conflicting pair agrees with the lock-point order, the whole schedule is conflict-equivalent to that serial order.
Can 2PL be used with more than two lock modes, like intent locks for hierarchical data?
Yes. Real systems extend the basic S/X model with intent locks (Intent-Shared, Intent-Exclusive, Shared-Intent-Exclusive) to support multiple granularity locking — locking a whole table versus individual rows efficiently. The two-phase discipline applies identically: a transaction still must finish acquiring all locks, at whatever granularity, before releasing any. The compatibility matrix simply grows larger to describe how intent locks interact with each other and with S/X locks up and down the hierarchy, but the growing/shrinking phase rule and its correctness proof are unchanged.
Does 2PL apply to distributed databases, or only single-machine ones?
The same growing/shrinking discipline applies in distributed settings, but lock requests now involve network communication with remote lock managers or a distributed lock service, adding latency and new failure modes (a node crashing while holding locks, for instance). Distributed systems often layer 2PL together with two-phase commit for atomic cross-node commit, and with deadlock detection that must reason about a global wait-for graph spanning multiple machines. The core theorem is unchanged — two-phase acquisition and release still guarantees conflict serializability — but the engineering cost of enforcing it rises substantially compared to a single-machine lock manager.