Deadlock detection

Deep dive

How it works

In: a lock request that must wait (transaction, resource) · Out: keep waiting, or abort one victim in a cycle · State: per resource holder and FIFO waiters; per blocked transaction the resource it waits for · Cost: O(V + E) per check; about 60-80 ns per waiting transaction in the code below (measured on this Mac, Apple M4 Pro).

1. A transaction asks for a resource. Free: grant it. Held by another: queue behind it; the edge is me → holder.
2. Search outward from the new waiter only: a new cycle must contain the new edge (PostgreSQL's lock manager README makes the same argument).
3. Depth-first search along the edges with a visited set. A path returning to the start is a cycle; a path ending at a running transaction is not.
4. Pick one victim in the cycle; one abort breaks it.
5. Roll the victim back: release its locks, hand each to its first waiter.
6. Return a deadlock error to the victim's caller, which retries the whole transaction.
7. Variant: skip the graph; bound waits with a timeout (innodb_lock_wait_timeout). It aborts healthy slow transactions and delays real deadlocks.

Victim policies. InnoDB "tries to pick small transactions" (size = rows inserted, updated or deleted). PostgreSQL's manual calls the victim "difficult to predict"; its README says usually the detecting transaction, after first trying to reorder the wait queue to avoid any abort. The sketch aborts the youngest: least work lost, and a retry that keeps its timestamp eventually becomes the oldest.

Prevention.

• Global lock order: lock keys ascending; every wait edge points to a higher key, so no cycle. PostgreSQL's manual calls this the best defense.
• Everything up front (conservative two-phase locking): needs the lock set in advance.
• Wait-die / wound-wait (Rosenkrantz, Stearns, Lewis 1978): an older requester waits and a younger dies (wait-die), or an older requester aborts the younger holder and a younger waits (wound-wait). A restart keeps its timestamp, so it cannot starve. Linux offers this as ww_mutex.

Distributed. No node sees the whole graph. Edge-chasing (Chandy, Misra, Haas 1983): a blocked transaction sends a probe along its wait edges across nodes; a probe returning to its initiator proves a cycle. Timeouts and wound-wait need no global state.

Code

use std::collections::{HashMap, HashSet, VecDeque};
pub type Tx = u64; // transaction id = start timestamp: smaller = older
pub type Res = u64;
#[derive(Debug, PartialEq)]
pub enum Outcome { Granted, Blocked, Deadlock { victim: Tx } }
#[derive(Default)]
pub struct LockTable {
    holder: HashMap<Res, Tx>,
    queue: HashMap<Res, VecDeque<Tx>>, // FIFO waiters per resource
    waits: HashMap<Tx, Res>,           // the one resource a blocked tx waits for
    held: HashMap<Tx, Vec<Res>>,
}
impl LockTable {
    /// Exclusive lock. On a wait, search for a cycle through `tx`; if found, abort the youngest member.
    pub fn acquire(&mut self, tx: Tx, res: Res) -> Outcome {
        match self.holder.get(&res) {
            None => { self.grant(tx, res); return Outcome::Granted }
            Some(&h) if h == tx => return Outcome::Granted,
            _ => {}
        }
        self.queue.entry(res).or_default().push_back(tx);
        self.waits.insert(tx, res);
        match self.find_cycle(tx) {
            None => Outcome::Blocked,
            Some(cycle) => {
                let victim = *cycle.iter().max().unwrap();
                self.abort(victim);
                Outcome::Deadlock { victim }
            }
        }
    }
    pub fn holder(&self, res: Res) -> Option<Tx> { self.holder.get(&res).copied() }
    pub fn is_blocked(&self, tx: Tx) -> bool { self.waits.contains_key(&tx) }
    // Wait-for edge: tx -> holder of the resource tx waits for (exclusive locks: out-degree <= 1).
    fn edges(&self, tx: Tx) -> Vec<Tx> {
        self.waits.get(&tx).and_then(|r| self.holder.get(r)).copied().into_iter().collect()
    }
    /// Iterative DFS from `start` (PostgreSQL also only looks for cycles through the waiter).
    fn find_cycle(&self, start: Tx) -> Option<Vec<Tx>> {
        let mut path = vec![start];
        let mut seen = HashSet::from([start]);
        let mut stack = vec![self.edges(start)];
        while let Some(top) = stack.last_mut() {
            match top.pop() {
                Some(n) if n == start => return Some(path),
                Some(n) if seen.insert(n) => { path.push(n); stack.push(self.edges(n)); }
                Some(_) => {}
                None => { stack.pop(); path.pop(); }
            }
        }
        None
    }
    fn grant(&mut self, tx: Tx, res: Res) {
        self.holder.insert(res, tx);
        self.held.entry(tx).or_default().push(res);
    }
    /// Abort or commit: drop the wait, release all locks, hand each to its first waiter.
    pub fn abort(&mut self, tx: Tx) {
        if let Some(r) = self.waits.remove(&tx) { self.queue.get_mut(&r).unwrap().retain(|&w| w != tx); }
        for res in self.held.remove(&tx).unwrap_or_default() {
            self.holder.remove(&res);
            if let Some(next) = self.queue.get_mut(&res).and_then(|q| q.pop_front()) {
                self.waits.remove(&next);
                self.grant(next, res);
            }
        }
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn transfer_deadlock_picks_youngest() {
        let mut t = LockTable::default(); // A = tx 1 locks x then y; B = tx 2 locks y then x
        assert_eq!(t.acquire(1, 10), Outcome::Granted);
        assert_eq!(t.acquire(2, 20), Outcome::Granted);
        assert_eq!(t.acquire(1, 20), Outcome::Blocked);
        assert_eq!(t.acquire(2, 10), Outcome::Deadlock { victim: 2 });
        assert_eq!(t.holder(20), Some(1)); // A inherited y when B rolled back
    }
    #[test]
    fn three_cycle() {
        let mut t = LockTable::default();
        for i in 1..=3 { t.acquire(i, i); }
        assert_eq!((t.acquire(1, 2), t.acquire(2, 3)), (Outcome::Blocked, Outcome::Blocked));
        assert_eq!(t.acquire(3, 1), Outcome::Deadlock { victim: 3 });
    }
    /// 200 two-lock transfers over 8 accounts, 4 in flight, random interleaving. Returns deadlock count.
    fn simulate(ordered: bool) -> u32 {
        let (mut seed, mut next, mut done, mut deadlocks) = (7u64, 0, 0, 0);
        let mut rnd = |m: u64| { seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407); (seed >> 33) % m };
        let mut t = LockTable::default();
        let mut live: Vec<(Tx, Vec<Res>, usize)> = vec![]; // (tx, locks to take in order, progress)
        while done < 200 {
            while live.len() < 4 && next < 200 {
                let (a, b) = (rnd(8), rnd(7)); // b != a after the shift
                let mut locks = vec![a, (a + 1 + b) % 8];
                if ordered { locks.sort() } // ascending key order: no cycle can form
                live.push((next, locks, 0)); next += 1;
            }
            let i = rnd(live.len() as u64) as usize;
            let (tx, locks, step) = live[i].clone();
            if t.is_blocked(tx) { continue }
            if step == locks.len() { t.abort(tx); live.remove(i); done += 1; continue }
            if let Outcome::Deadlock { victim } = t.acquire(tx, locks[step]) {
                deadlocks += 1; done += 1; live.retain(|p| p.0 != victim); // a real caller retries it
            } else if t.holder(locks[step]) == Some(tx) { live[i].2 += 1 }
        }
        deadlocks
    }
    #[test]
    fn ascending_order_never_deadlocks() { assert_eq!(simulate(true), 0); assert!(simulate(false) > 0); }
}

Complexity and constants

• One check: O(V + E) over transactions reachable from the waiter. Measured on this Mac (Apple M4 Pro, release build, best of 5): closing a chain of n waiters into a cycle, search plus victim abort:

• Order of 60-140 ns per edge here (hash lookups, a small Vec per node).
• Cost drivers: cycle length, check frequency, the latch held during the check. InnoDB treats a wait-for list over 200 transactions, or over 1,000,000 locks examined, as a deadlock and rolls back the checker.

Efficiency

• Cost: about 1.4 µs for a 10-waiter chain, 7.6 ms for 100,000 (measured on this Mac, Apple M4 Pro). The real price is the aborted transaction: work lost and redone, plus backoff. Bound: latch contention and wasted work.
• Levers:
  • ascending lock order in application code — no cycles, aborts or retries (PostgreSQL manual) — the lock set is known per request
  • delay the check (deadlock_timeout) — no graph work for short waits (PostgreSQL README) — short transactions
  • detection off plus a short lock wait timeout — no graph work on a hot row (MySQL manual on innodb_deadlock_detect) — many threads wait on one row
  • short transactions, indexes on filtered columns — fewer waits (MySQL manual) — always
  • retry with exponential backoff and jitter — the same pair does not collide again — deadlocks that cannot be designed out
• Naive → standard → state of the art:
  • wait forever · stalls until a restart
  • timeout only · bounded stall, healthy waits aborted too
  • global lock order in code, graph check as safety net · no aborts on the common path

Implementation notes

• Two rows at once (ratings, balances). Lock both in one statement in key order: SELECT id FROM players WHERE id IN ($1, $2) ORDER BY id FOR UPDATE. PostgreSQL sorts first, then locks (its SELECT page: rows can look out of order only if sort keys change while blocked). Or take pg_advisory_xact_lock on the smaller id first. In a stored procedure, sort the ids at the top, then update.
• The order must hold on every code path; one path in the wrong order is enough.
• Catch the error, roll back, rerun the whole transaction, not just the failing statement. Side effects outside the database need idempotency keys.
• Log them (innodb_print_all_deadlocks, SHOW ENGINE INNODB STATUS; in PostgreSQL the server log): the report shows the reversed order.
• Isolation level does not prevent them (InnoDB manual: deadlocks come from writes). Serializable failures use 40001 and also need a retry (SSI).

Pitfalls

• Upgrade deadlocks: two transactions read-lock a row, then both write it. Take the write lock first.
• InnoDB can miss deadlocks that involve LOCK TABLES (unless innodb_table_locks = 1 and autocommit = 0) or another storage engine's locks; set innodb_lock_wait_timeout.
• A database lock held across an application mutex or RPC makes a cycle the database cannot see; only a timeout resolves it.
• Retrying at once re-creates the collision: add jitter and a retry cap.
• Go prints "all goroutines are asleep - deadlock!" only when no goroutine can run and no timer is pending; two goroutines stuck while others run go unreported.

Variants and alternatives

In production

• Databases: PostgreSQL and MySQL InnoDB, both returning a retryable error.
• Kernels: Linux lockdep validates lock-class order at runtime.
• Runtimes: Go exits on total deadlock; Rust's parking_lot has an opt-in detector.
• Application code: bank transfers and rating updates sort the two ids first.

Implementations

Sources

• PostgreSQL docs, Explicit Locking (Deadlocks). docs
• PostgreSQL docs, Lock Management (deadlock_timeout). docs
• PostgreSQL source, lmgr/README, The Deadlock Detection Algorithm. text
• PostgreSQL docs, Error Codes (40P01). docs
• MySQL 8.4 manual, Deadlocks in InnoDB, Deadlock Detection, error 1213 (ER_LOCK_DEADLOCK). archived copy
• D. Rosenkrantz, R. Stearns, P. Lewis, System Level Concurrency Control for Distributed Database Systems, ACM TODS, 1978. paper
• K. M. Chandy, J. Misra, L. M. Haas, Distributed Deadlock Detection, ACM TOCS, 1983. paper
• Linux kernel documentation, Runtime locking correctness validator (lockdep). docs
• Go runtime, checkdead in src/runtime/proc.go. source