Two-Phase Locking

How two-phase locking works

Run two bank transfers at the same time and you can lose money. Transaction A reads a balance of $100, transaction B also reads $100, A writes $80, B writes $120 — and a deposit silently vanishes. This is a lost update, and it is the kind of anomaly a concurrency-control protocol exists to forbid. The gold standard for correctness is serializability: the concurrent execution must produce the same result as some serial order of the transactions, as if they had run one at a time.

Two-phase locking, introduced by Eswaran, Gray, Lorie, and Traiger at IBM in 1976, achieves serializability with a single discipline on how locks are taken and released. Every transaction obeys two phases:

• Growing phase. The transaction may acquire locks but may not release any.
• Shrinking phase. Once the transaction releases its first lock, it may release more but may never acquire another.

The moment between the two phases — when the transaction holds the maximum number of locks it will ever hold — is the lock point. That single instant is the key to the whole proof. Because no transaction can grab a new lock after letting one go, you can serialize the entire schedule by sorting transactions on their lock points. Any two conflicting operations (a write versus a read or write of the same item) are forced into the same relative order they would have had in that serial schedule. There is no way to interleave them backwards.

Locks come in modes. A shared (S) lock permits concurrent readers; an exclusive (X) lock is required to write and conflicts with every other lock. The lock manager enforces a compatibility matrix: S is compatible with S, everything else conflicts. A transaction that requests a conflicting lock simply waits until the holder releases it.

The lock point and the serialization proof

Here is the argument in one paragraph. Suppose the schedule were not conflict-serializable. Then its precedence graph — a node per transaction, an edge T_i → T_j whenever an operation of T_i conflicts with and precedes one of T_j — contains a cycle T₁ → T₂ → … → T₁. An edge T_i → T_j means T_i released a lock that T_j then acquired, so T_i's lock point precedes T_j's. Follow the cycle and you conclude T₁'s lock point strictly precedes itself — a contradiction. So no cycle exists, the precedence graph is acyclic, a topological order exists, and that order is a serial schedule equivalent to the real one. That is conflict serializability, and 2PL delivers it for free.

The catch the proof hides: nothing in it rules out two transactions waiting on each other forever. Serializability and deadlock-freedom are separate properties, and 2PL gives you only the first.

Variants worth knowing

Basic 2PL. The textbook protocol: release locks as soon as you no longer need them, as long as you never reacquire. Maximizes concurrency but allows a transaction to read another's uncommitted writes, so a later abort can cascade — every transaction that read the dirty data must also abort.

Strict 2PL (S2PL). Hold all exclusive locks until the transaction commits or aborts; shared locks may be released earlier. This makes the schedule recoverable and cascadeless: no transaction ever reads uncommitted data, so an abort never propagates.

Strong strict 2PL (SS2PL), a.k.a. rigorous 2PL. Hold all locks — shared and exclusive — until commit. The shrinking phase collapses to a single instant at commit time. This is the variant essentially every real database implements, because it is the easiest to reason about and recover from. "2PL in production" almost always means SS2PL.

Conservative (static) 2PL. Acquire every lock the transaction will need before it does any work, and abort the attempt if even one is unavailable. This is the only variant that is deadlock-free — there is no partial-hold state to cycle on — but it requires knowing the full lock set up front, which is rarely practical.

When to use 2PL — and when not to

• Write-heavy OLTP where transactions are short and you need true serializability without a versioning engine. SS2PL is simple and battle-tested.
• Workloads that genuinely conflict — if two transactions almost always touch the same hot rows, MVCC just defers the conflict to commit-time validation, so locking up front may be cheaper.
• Systems that must avoid write skew without snapshot-isolation surprises. Serializable 2PL has no write-skew anomaly; plain snapshot isolation does.

Avoid pure 2PL when reads dominate. Under 2PL a long analytic SELECT takes shared locks that block every writer touching those rows, and one slow reporting query can freeze an entire table. That single pain point is why multi-version concurrency control took over: readers get a consistent snapshot without locking, and only writers contend.

2PL versus other concurrency-control schemes

	Strict 2PL	MVCC (snapshot)	Serializable Snapshot Isolation	Optimistic (OCC)	Timestamp ordering
Guarantee	Serializable	Snapshot isolation	Serializable	Serializable	Serializable
Readers block writers?	Yes	No	No	No	Sometimes
Failure mode	Deadlock → abort	Write-write conflict → abort	Dangerous-structure → abort	Validation fail → abort	Late timestamp → abort
Best for	Short write-heavy txns	Read-heavy mixed	Read-heavy needing serializability	Low-contention	Real-time / distributed
Cost per item	Lock entry + wait queue	Version chain + GC	Version chain + rw-tracking	Read/write set buffer	2 timestamps per item
Real-world use	SQL Server SERIALIZABLE, DB2	PostgreSQL, Oracle, InnoDB reads	PostgreSQL SERIALIZABLE	FoundationDB, some in-memory DBs	Spanner-style with TrueTime

The headline trade-off: 2PL is pessimistic — it assumes conflict and pays for it up front with locking and waiting. MVCC and OCC are optimistic — they assume conflict is rare and only pay at commit time, but pay more (a full abort and retry) when they are wrong. PostgreSQL's SERIALIZABLE level is Serializable Snapshot Isolation (SSI), which keeps MVCC's non-blocking reads while detecting the specific "dangerous structures" that break serializability.

What the numbers actually say

• Deadlock probability scales as length⁴ × transactions². Jim Gray's analysis shows that, for a transaction taking k locks among R resources with n concurrent transactions, the deadlock rate grows roughly with n·k⁴ / R². Double the locks per transaction and deadlocks become ~16× more frequent.
• Most deadlocks are 2-cycles. In practice the overwhelming majority of detected deadlocks involve exactly two transactions; cycles of length 3+ are rare, which is why simple victim selection works well.
• Lock-table memory is real. A lock entry plus its wait-queue node is on the order of 100+ bytes; a transaction touching a million rows under strict row-level 2PL can consume tens of megabytes of lock-manager state, which is why engines escalate to page- or table-level locks past a threshold (SQL Server escalates near ~5,000 locks on one object).
• Lock-point ordering costs nothing extra. The serialization order is a byproduct of the lock acquisitions you already make — there is no separate timestamp to maintain, unlike timestamp-ordering schemes that store a read-TS and write-TS per item.

JavaScript implementation

A minimal lock manager with shared/exclusive modes and a per-transaction phase guard. The acquire call returns a promise that resolves when the lock is granted, so a transaction simply awaits a conflicting lock.

class LockManager {
  constructor() {
    this.locks = new Map();   // item -> { mode, holders:Set, queue:[] }
    this.phase = new Map();   // txId -> 'growing' | 'shrinking'
  }

  // compatible if both shared and no exclusive holder
  _compatible(entry, mode) {
    if (entry.holders.size === 0) return true;
    return mode === 'S' && entry.mode === 'S';
  }

  acquire(txId, item, mode) {              // mode: 'S' or 'X'
    if (this.phase.get(txId) === 'shrinking')
      throw new Error(`2PL violation: tx ${txId} acquired ${item} after releasing a lock`);
    this.phase.set(txId, 'growing');

    let entry = this.locks.get(item);
    if (!entry) { entry = { mode, holders: new Set(), queue: [] }; this.locks.set(item, entry); }

    return new Promise(resolve => {
      const grant = () => {
        entry.holders.add(txId);
        entry.mode = entry.holders.size > 1 ? 'S' : mode;
        resolve();
      };
      if (this._compatible(entry, mode) && entry.queue.length === 0) grant();
      else entry.queue.push({ txId, mode, grant });   // wait
    });
  }

  release(txId, item) {                    // entering / staying in shrinking phase
    this.phase.set(txId, 'shrinking');
    const entry = this.locks.get(item);
    if (!entry) return;
    entry.holders.delete(txId);
    // wake the next compatible waiter(s)
    while (entry.queue.length && this._compatible(entry, entry.queue[0].mode)) {
      const w = entry.queue.shift();
      w.grant();
      if (w.mode === 'X') break;            // exclusive grant is exclusive
    }
  }

  // SS2PL: release everything at commit/abort in one shot
  releaseAll(txId, items) { for (const i of items) this.release(txId, i); }
}

Two details to flag. First, the phase map is the entire enforcement of the 2PL rule — once a transaction calls release, any later acquire throws. Second, this manager has no deadlock detection: two transactions that await each other's locks will hang. That is correct 2PL behavior — deadlock handling is a separate layer.

Python implementation

The same protocol with an explicit waits-for graph and cycle detection bolted on, so deadlocks become aborts instead of hangs. This is closer to what a real engine does.

from collections import defaultdict

class Deadlock(Exception): pass

class LockManager:
    def __init__(self):
        self.holders   = defaultdict(set)   # item -> {tx, ...}
        self.mode      = {}                  # item -> 'S' | 'X'
        self.waiting   = {}                  # tx -> item it waits on
        self.phase     = {}                  # tx -> 'growing' | 'shrinking'
        self.held      = defaultdict(set)    # tx -> {items}

    def _compatible(self, item, mode):
        h = self.holders[item]
        if not h: return True
        return mode == 'S' and self.mode.get(item) == 'S'

    def _detect_cycle(self, start_tx):
        # follow waits-for edges; an edge tx -> holder means tx waits on holder
        seen, stack = set(), [start_tx]
        while stack:
            tx = stack.pop()
            if tx in seen: continue
            seen.add(tx)
            item = self.waiting.get(tx)
            if item is None: continue
            for holder in self.holders[item]:
                if holder == start_tx:        # cycle back to us
                    return True
                stack.append(holder)
        return False

    def acquire(self, tx, item, mode):
        if self.phase.get(tx) == 'shrinking':
            raise ValueError(f"2PL violation: tx {tx} acquires after releasing")
        self.phase[tx] = 'growing'
        if not self._compatible(item, mode):
            self.waiting[tx] = item
            if self._detect_cycle(tx):
                self.waiting.pop(tx, None)
                raise Deadlock(f"tx {tx} would deadlock on {item}")
            # in a real engine the caller would block here and retry on wake
            return False
        self.waiting.pop(tx, None)
        self.holders[item].add(tx)
        self.mode[item] = 'S' if len(self.holders[item]) > 1 else mode
        self.held[tx].add(item)
        return True

    def release(self, tx, item):
        self.phase[tx] = 'shrinking'
        self.holders[item].discard(tx)
        self.held[tx].discard(item)

    def commit(self, tx):                     # SS2PL: release all locks at once
        for item in list(self.held[tx]):
            self.release(tx, item)
        self.phase.pop(tx, None)

The interesting asymmetry versus the JavaScript version: detecting deadlock requires global state — the waits-for graph spanning every transaction — whereas enforcing 2PL itself is purely local to one transaction's phase flag. That separation is exactly why textbooks present them as two distinct concerns.

Deadlock: detection versus prevention

Since 2PL invites deadlock, every real implementation pairs it with one of two strategies:

• Detection. Maintain a waits-for graph and periodically (or on every blocked acquire) search for a cycle. When one is found, pick a victim — usually the youngest transaction or the one holding the fewest locks — abort it, release its locks, and let the rest proceed. This is what PostgreSQL and MySQL/InnoDB do, with a configurable timeout (InnoDB's innodb_lock_wait_timeout defaults to 50 seconds).
• Prevention via timestamps. Assign each transaction a timestamp and use wait-die (an older transaction waits for a younger one, a younger one requesting an older's lock dies and restarts) or wound-wait (an older transaction preempts a younger holder). Both guarantee no cycle can form because every wait edge points consistently from older to younger or vice versa. Aborted transactions keep their original timestamp on restart so they eventually become the oldest and cannot starve.

Common bugs and edge cases

• Reacquiring after release. The single most common 2PL bug: a transaction releases a lock, then loops back and grabs another. This silently breaks serializability with no error unless you enforce the phase guard. Always assert the phase.
• Lock upgrades cause deadlock. Two transactions both take a shared lock, then both try to upgrade to exclusive — each waits for the other to drop its S lock. Use update (U) locks, which are exclusive on the upgrade intent, or take the X lock up front.
• The phantom problem. Row locks protect rows that exist; they cannot protect rows that don't yet. A range query that returns nothing, then sees a new matching row inserted by a concurrent transaction, has hit a phantom. Predicate locks or next-key / gap locks (InnoDB) are needed for true serializability — plain row-level 2PL is not enough.
• Forgetting strictness invites cascading aborts. Releasing exclusive locks before commit lets others read uncommitted data; if you then abort, every reader must abort too. Hold write locks to commit (S2PL) to make aborts non-cascading.
• Lock escalation surprises. Engines silently convert thousands of row locks into one table lock to save memory, which can suddenly serialize transactions that were happily concurrent at row granularity. Watch for it under bulk operations.
• Using 2PL when MVCC would do. If your workload is read-dominated, pessimistic locking forces readers and writers to block each other for no benefit; snapshot reads eliminate the contention entirely.