Two-phase locking

Deep dive

How it works

In: a transaction's read and write requests on named resources · Out: granted locks in an order that is serializable, or a deadlock abort · State: lock table resource → granted (txn, mode) list plus FIFO waiters; per transaction its held locks · Cost: lock and unlock O(1) expected; deadlock detection O(V + E) on the waits-for graph.

        S   X
   S    ✓   ✗        lock table: resource → {granted: [(txn, mode)], waiters: FIFO}
   X    ✗   ✗

1. Before a read, take S. Before a write, take X (or upgrade S → X).
2. The lock manager grants the request if it is compatible with all granted locks and no earlier waiter conflicts with it (FIFO, prevents starvation). Otherwise the transaction waits.
3. Deadlocks: either build the waits-for graph and abort a victim on a cycle (youngest, or the one with least work), or prevent cycles with timestamps:
   • wait-die: an older requester waits; a younger one aborts ("dies").
   • wound-wait: an older requester aborts ("wounds") the younger holder; a younger requester waits. A restarted transaction keeps its original timestamp, so it eventually becomes the oldest and cannot starve.
4. At commit or abort, release everything and wake compatible waiters.

Code

use std::collections::HashMap;
use std::sync::{Condvar, Mutex};

#[derive(Clone, Copy, PartialEq, Debug)]
pub enum Mode { S, X }

#[derive(Debug)]
pub struct Abort; // roll back, then retry with the SAME timestamp (no starvation)

pub struct LockManager { table: Mutex<HashMap<u64, Vec<(u64, Mode)>>>, cv: Condvar } // res -> holders

impl LockManager {
    pub fn new() -> Self { LockManager { table: Mutex::new(HashMap::new()), cv: Condvar::new() } }

    /// Wait-die: smaller ts = older. Older waits for younger holders; younger dies. No cycles possible.
    pub fn lock(&self, txn: u64, res: u64, mode: Mode) -> Result<(), Abort> {
        let mut t = self.table.lock().unwrap();
        loop {
            let holders = t.entry(res).or_default();
            let mut conflict = false;
            for &(h, m) in holders.iter() {
                if h != txn && (mode == Mode::X || m == Mode::X) {
                    if h < txn { return Err(Abort); } // a holder is older than us: die
                    conflict = true;
                }
            }
            if !conflict {
                match holders.iter_mut().find(|(h, _)| *h == txn) {
                    Some(held) => if mode == Mode::X { held.1 = Mode::X }, // upgrade S → X
                    None => holders.push((txn, mode)),
                }
                return Ok(());
            }
            t = self.cv.wait(t).unwrap();
        }
    }

    fn release_all(&self, txn: u64, held: &[u64]) {
        let mut t = self.table.lock().unwrap();
        for r in held {
            if let Some(h) = t.get_mut(r) {
                h.retain(|&(x, _)| x != txn);
                if h.is_empty() { t.remove(r); }
            }
        }
        self.cv.notify_all(); // real lock managers wake only that resource's queue
    }
}

pub struct Txn<'a> { lm: &'a LockManager, ts: u64, held: Vec<u64> }

impl<'a> Txn<'a> {
    pub fn new(lm: &'a LockManager, ts: u64) -> Self { Txn { lm, ts, held: Vec::new() } }
    pub fn lock(&mut self, res: u64, mode: Mode) -> Result<(), Abort> {
        self.lm.lock(self.ts, res, mode)?;
        self.held.push(res);
        Ok(())
    }
}

// Strict 2PL: nothing is released before the transaction ends, which is when Txn drops.
impl Drop for Txn<'_> {
    fn drop(&mut self) { self.lm.release_all(self.ts, &self.held); }
}

This sketch has no FIFO queue: a waiting X request can be overtaken by a stream of new S requests. Production lock managers keep a per-resource wait queue and grant in order.

Complexity and constants

• Lock acquire/release on an uncontended hash-table entry: order of 100 ns to 1 µs, including the lock manager latch. At millions of transactions/s the central lock table becomes the bottleneck (Yu et al. measured 2PL variants collapsing at high core counts).
• Hot row: if a transaction holds X for 1 ms (including a commit fsync), that row allows at most 1000 updates/s, whatever the hardware.
• Memory: InnoDB stores row locks as per-page bitmaps (a few bits per row) rather than one object per row.
• Wait-die and wound-wait abort more than detection does (some aborts are false positives) but need no graph search.

Efficiency

• Cost: an uncontended lock acquire and release is order of 100 ns to 1 µs including the lock-manager latch. A hot row held X for 1 ms (including the commit fsync) allows at most 1000 updates/s. Bound: waiting, not CPU; at high core counts the central lock table limits throughput (Yu et al. measured 2PL variants collapsing).
• Levers:
  • hold locks briefly, no user think time or RPCs, contended lock last — shorter hold — always
  • lock in a canonical key order — no deadlocks, so no detection cost — code that controls its access order
  • hash resources into latch-protected buckets, or keep the lock word in the record (VLL, Silo-style TID words); InnoDB uses per-page bitmaps — cheaper lock manager — high transaction rates
  • intent locks plus row locks, escalate to a table lock past a threshold — bounded memory — large scans
  • wait-die/wound-wait, or innodb_deadlock_detect = OFF with timeouts — no graph search — heavy contention
• Naive → standard → state of the art:
  • one global lock · serial execution
  • strict 2PL with a hashed lock table and deadlock detection · order of 100 ns-1 µs per lock
  • MVCC snapshots for readers, locks only for writers · readers take no locks

Implementation notes

• Lock ordering: when the code can, acquire locks in a canonical order (by key) to avoid deadlocks entirely.
• Update (U) locks (SQL Server): read with an intent to write. U is compatible with S but not with U, so two readers that both want to upgrade cannot deadlock.
• Granularity: take IX on the table, then X on rows. Escalate to a table lock past some row count (SQL Server escalates at about 5000 locks per statement) to bound memory.
• Partitioned lock table: hash resources into N latch-protected buckets to remove the single-latch bottleneck.
• Lightweight locks: store the lock word inside the record (VLL, Silo-style TID words), with no central table.
• Spanner uses wound-wait for read-write transactions. A wound-wait abort needs a cross-node message, but no global deadlock detector.

Pitfalls

• Upgrade deadlocks: two transactions with S both request X. Use U locks or take X up front.
• Phantoms: row locks alone do not stop inserts into a scanned range. Lock the range (next-key) or the predicate.
• Holding locks during user think time or RPCs. Keep the transaction short, or move to optimistic schemes.
• Lock convoys: a wake-all after each release thrashes a hot resource. Wake only the grantable waiters.
• Deadlock detection that runs on every wait is costly under heavy contention. InnoDB allows disabling it (innodb_deadlock_detect = OFF) and relying on lock wait timeouts.

Variants and alternatives

In production

• Relational databases: SQL Server (locking by default), DB2, MySQL InnoDB (row and next-key locks for writes), PostgreSQL row locks (FOR UPDATE, FOR SHARE).
• Distributed databases: Spanner (wound-wait), most distributed databases for write intents.
• No verified use outside transactional data stores was found.

Implementations

Sources

• K. Eswaran, J. Gray, R. Lorie, I. Traiger, The Notions of Consistency and Predicate Locks in a Database System, CACM, 1976. paper
• J. Gray, R. Lorie, G. Putzolu, I. Traiger, Granularity of Locks and Degrees of Consistency in a Shared Data Base, 1976.
• D. Rosenkrantz, R. Stearns, P. Lewis, System Level Concurrency Control for Distributed Database Systems, ACM TODS, 1978. paper
• X. Yu et al., Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores, VLDB, 2014. paper
• J. Corbett et al., Spanner: Google's Globally-Distributed Database, OSDI, 2012. paper
• A. Thomson et al., Calvin: Fast Distributed Transactions for Partitioned Database Systems, SIGMOD, 2012. paper