vault

Deadlock Detection and Prevention

13 min read

Deadlock Detection and Prevention

A deadlock is the failure mode intrinsic to any lock-based (2PL) database: two or more transactions each hold a lock the other needs, so none can proceed. InnoDB defines it exactly: “A deadlock is a situation in which multiple transactions are unable to proceed because each transaction holds a lock that is needed by another one. Because all transactions involved are waiting for the same resource to become available, none of them ever releases the lock it holds” (InnoDB deadlocks docs). Because 2PL’s serializability guarantee requires holding locks to commit, deadlock cannot be eliminated — only managed. There are two philosophies: detection (let deadlocks happen, find the cycle in a wait-for graph, and abort a victim) and prevention (assign transaction timestamps and abort proactively so a cycle can never form — the wait-die and wound-wait schemes). This note covers both, plus the humble but essential third option: avoid deadlocks by acquiring locks in a consistent order.

Mental Model: A Cycle in the Wait-For Graph

The clean abstraction is the wait-for graph: one node per active transaction, and a directed edge T1 → T2 whenever T1 is blocked waiting for a lock held by T2. A deadlock exists if and only if this graph has a cycle. The MySQL engineering blog on InnoDB spells out why, using a bipartite transaction-resource graph: “the only edges going out of transactions are of the ‘waits-for-access’ kind and lead to resources, and the only edges going out of resources are of the ‘is-accessed-by’ kind and lead to transactions, so the cycle must alternate between transactions and resources … and each transaction is blocked waiting for a resource it can not obtain because it is in possession of another transaction which is also waiting” (InnoDB Data Locking, Part 3). Collapse the resources and you get the transaction-only wait-for graph; a cycle there is a deadlock.

flowchart LR
  T1["T1<br/>holds lock on A<br/>wants B"] -->|"waits for"| T2["T2<br/>holds lock on B<br/>wants A"]
  T2 -->|"waits for"| T1

A minimal two-transaction deadlock as a wait-for cycle. What it shows: T1 locked row A then asked for B; T2 locked B then asked for A; each edge points to the transaction holding the wanted lock. The insight: the cycle is the deadlock — no external resource shortage, no bug, just an unlucky interleaving of lock-acquisition orders. Detection means finding this cycle; prevention means guaranteeing it can never close; avoidance means both transactions locking A before B so the second simply waits instead of forming the loop.

Detection is the default in both major engines. The efficient trick, per the InnoDB blog, is that you never need to search the whole graph continuously: “removing an edge or a node can not introduce a deadlock cycle. It is only when a new edge is added that a new cycle can be formed.” A new edge appears exactly when “a transaction T requests an access right to a resource R and has to wait.” So detection runs only at that moment: when T is about to block, check whether granting-it-later would close a cycle — walk the wait-for chain from the holder of R and see “if such a path exists then adding the edge will cause a deadlock.” InnoDB (since 8.0.18) optimizes further with a sparse graph: “we can create a ‘sparse graph’ by selecting just the oldest outgoing edge for each transaction,” and cycle detection becomes “a simple linear algorithm” over the array of currently-waiting transactions — no stop-the-world.

Victim selection: once a cycle is found, one transaction must die so the rest proceed. “InnoDB detects the condition and rolls back one of the transactions (the victim).” The choice is by weight: InnoDB “favours sacrificing ‘lighter’ transactions as defined by INFORMATION_SCHEMA.INNODB_TRX.TRX_WEIGHT,” where weight is roughly the number of rows modified plus locks held — so the transaction that has done the least work is killed, minimizing wasted effort and rollback cost (transactions that changed non-transactional tables are treated as heavier and spared). The victim receives error 1213 ER_LOCK_DEADLOCK and, per the docs, “even if your application logic is correct, you must still handle the case where a transaction must be retried.” PostgreSQL similarly “automatically detects deadlock situations and resolves them by aborting one of the transactions involved,” warning that “exactly which transaction will be aborted is difficult to predict and should not be relied upon” (PostgreSQL explicit locking).

The deadlock_timeout Optimization

Cycle detection isn’t free, so PostgreSQL doesn’t run it the instant a transaction blocks. Instead it waits deadlock_timeout first: “This is the amount of time to wait on a lock before checking to see if there is a deadlock condition … The check for deadlock is relatively expensive, so the server doesn’t run it every time it waits for a lock. We optimistically assume that deadlocks are not common in production applications and just wait on the lock for a while before checking” (PostgreSQL lock config). The default is one second (1s). The trade-off is stated plainly: “Increasing this value reduces the amount of time wasted in needless deadlock checks, but slows down reporting of real deadlock errors.” Most lock waits resolve well under a second (the holder commits), so paying the cycle-search cost only after a full second of waiting means the vast majority of waits never trigger it.

InnoDB’s equivalent knob is the fallback when detection is disabled: innodb_deadlock_detect defaults to ON, but if you set it OFF (advisable only on extremely high-concurrency systems where the detection cost itself becomes a bottleneck), “InnoDB relies on the innodb_lock_wait_timeout setting to roll back transactions in case of a deadlock.” That timeout defaults to 50 seconds — a transaction waiting longer than 50s for a row lock gives up with error 1205 “Lock wait timeout exceeded.” Timeout-based handling is cruder (it can’t tell a genuine deadlock from a merely slow holder, and 50s is a long stall) but cheap and simple. innodb_print_all_deadlocks (default OFF) can be enabled to log every deadlock, not just the last, for diagnosis via SHOW ENGINE INNODB STATUS.

Prevention: Wait-Die and Wound-Wait

Prevention refuses to let a cycle form in the first place, by assigning every transaction a timestamp at start (older = smaller timestamp = higher priority) and consulting it whenever a transaction would wait. The two classic schemes come from Rosenkrantz, Stearns & Lewis, “System Level Concurrency Control for Distributed Database Systems” (ACM Transactions on Database Systems 3(2), June 1978). Both work by ensuring waits only ever go in one direction along the age ordering, which makes cycles impossible.

Uncertain

Verify: the precise wait-die / wound-wait requester-vs-holder rules and the “restarted transactions keep their original timestamp” anti-starvation property, attributed to Rosenkrantz, Stearns & Lewis (1978). Reason: these were confirmed via consistent university course notes (Emory CS554, Colorado State CS551) surfaced through web search rather than a directly fetched copy of the 1978 primary (the Colorado State page returned HTTP 403; the original paper was not retrievable during writing). The rules are textbook-standard and agreed across the secondary sources, but the exact wording is not from a fetched primary. To resolve: consult the TODS 1978 paper text directly. uncertain

  • Wait-Die (non-preemptive). When a transaction requests a lock held by another: if the requester is older (smaller timestamp) it is allowed to wait; if the requester is younger it is aborted (“dies”) and restarted. So an old transaction may wait for a young one, but a young one never waits for an old one — waits only point from old → young, which cannot cycle. Older transactions never die, guaranteeing eventual completion.
  • Wound-Wait (preemptive). The dual: if the requester is older, it “wounds” (aborts) the younger holder and takes the lock; if the requester is younger, it waits. Here waits point from young → old, also acyclic. An older transaction never waits behind a younger holder — it preempts it.

The names encode the behavior: in wait-die, the requesting transaction either waits or dies (only requesters abort); in wound-wait, the requester either wounds the holder or waits (holders can be preempted). The critical anti-starvation property is shared: a restarted transaction keeps its original timestamp. As the standard course-note treatments state it, when transactions are rolled back they are restarted with the same timestamp, and to avoid starvation a process should not be assigned a new timestamp each time it restarts — because over time a repeatedly-aborted transaction becomes the oldest in the system, at which point (wait-die) it can only wait, never die, or (wound-wait) it wins every preemption. Wait-die tends to cause more aborts (younger requesters die even when the holder would finish soon) but never preempts running work; wound-wait causes fewer aborts but throws away partial work when it wounds a holder.

Avoidance: Consistent Lock Ordering

The cheapest deadlock is the one that never happens. Both engines’ docs give the same first-line advice: acquire locks in a consistent global order. PostgreSQL: “The best defense against deadlocks is generally to avoid them by being certain that all applications using a database acquire locks on multiple objects in a consistent order. In the example above, if both transactions had updated the rows in the same order, no deadlock would have occurred.” A second rule: “the first lock acquired on an object in a transaction [should be] the most restrictive mode that will be needed” — take the X lock up front rather than S-then-upgrade, since lock upgrades are a prime deadlock source. Ordering works because a cycle requires two transactions to disagree on lock order (one does A→B, the other B→A); force everyone to A→B and the wait-for graph becomes a DAG by construction. When ordering isn’t feasible (ad-hoc queries, ORM-generated SQL), the fallback is detection plus a retry loop.

Configuration and Code

-- PostgreSQL: tune the detection latency and observe deadlocks
SHOW deadlock_timeout;                 -- default '1s'
SET deadlock_timeout = '500ms';        -- report deadlocks faster (more CPU on busy systems)
-- Deadlocks are logged with the full cycle; count them:
--   grep 'deadlock detected' postgresql.log
-- InnoDB: inspect detection settings and the last deadlock
SELECT @@innodb_deadlock_detect,       -- ON  (detection enabled)
       @@innodb_lock_wait_timeout;     -- 50  (seconds, fallback / general lock wait)
SET GLOBAL innodb_print_all_deadlocks = ON;   -- log every deadlock, not just the last
SHOW ENGINE INNODB STATUS\G            -- LATEST DETECTED DEADLOCK section shows both transactions
# The universal application contract: deadlock/serialization errors are RETRYABLE.
import time
def run_txn(conn, body, retries=5):
    for attempt in range(retries):
        try:
            with conn.begin():
                return body(conn)
        except DeadlockError:            # MySQL 1213 / Postgres 40P01 / SQLSTATE 40001-family
            if attempt == retries - 1:
                raise
            time.sleep(0.01 * 2 ** attempt)   # exponential backoff before retry

The retry loop is not optional: since “you must still handle the case where a transaction must be retried” (InnoDB) and the victim “should not be relied upon” (PostgreSQL), every transaction that can deadlock needs backoff-and-retry. Exponential backoff prevents two transactions from re-colliding in lockstep.

Failure Modes and Misunderstandings

  • Deadlock ≠ lock wait timeout ≠ lock contention. A deadlock is a cycle (resolved instantly by detection). A lock wait timeout (InnoDB 1205) is a single transaction waiting too long on a non-cyclic lock — often just a slow holder, not a deadlock. Conflating them sends you tuning the wrong knob.
  • Disabling detection is rarely right. Turning off innodb_deadlock_detect trades instant cycle-breaking for a 50-second stall per deadlock; only justified on extreme-concurrency systems where detection itself is the bottleneck, and only paired with a short innodb_lock_wait_timeout.
  • Gap locks make InnoDB deadlocks non-obvious. At Repeatable Read, gap locks mean transactions can deadlock on ranges they never explicitly touched. Dropping to Read Committed (no gap locks) reduces this class of deadlock.
  • Lock upgrades deadlock predictably. Two transactions both holding S on a row and both wanting X will always deadlock. Take the restrictive lock first.
  • Retry without backoff = livelock. Two transactions that deadlock, both abort, both immediately retry, and deadlock again can loop forever. Backoff (ideally randomized) is essential.
  • Victim choice affects fairness, not correctness. Killing the lightest transaction (InnoDB) minimizes wasted work but can repeatedly victimize small transactions competing with a large one — watch for a small transaction that never completes.

Alternatives and When to Choose Them

Detection vs. prevention vs. avoidance is a real engineering choice. Detection (InnoDB, PostgreSQL default) maximizes concurrency — transactions run freely and only pay when a real cycle forms — at the cost of some transactions doing work that gets rolled back; it’s the right default for general-purpose databases where deadlocks are occasional. Prevention (wait-die/wound-wait) never builds a wait-for cycle and needs no graph search, which suits distributed systems where a global wait-for graph is expensive to maintain (Google Spanner’s descendants and various distributed OLTP systems use wound-wait-style schemes); its cost is aborting transactions that might have completed fine. Avoidance (consistent lock ordering) is free and eliminates whole deadlock classes but requires disciplined application design and is impossible for fully ad-hoc workloads. The best real systems layer all three: order locks where you can (avoidance), detect and retry where you can’t (detection), and — in distributed settings — fall back to timestamp-based prevention. The one non-negotiable across all of them is the retry loop.

Production Notes

The dominant real-world deadlock in MySQL shops is the InnoDB gap-lock deadlock under Repeatable Read: two transactions inserting or updating within overlapping index ranges deadlock on next-key locks they never named. The standard remediations — consistent statement ordering, smaller transactions, sometimes switching to Read Committed to disable gap locks — are all documented above and are routine DBA work. SHOW ENGINE INNODB STATUS (or innodb_print_all_deadlocks logging) is the diagnostic; the “LATEST DETECTED DEADLOCK” section prints both transactions, their held and waited-for locks, and which was rolled back. On PostgreSQL, the classic deadlock is two transactions updating the same set of rows in different orders; the fix is application-level ordering plus retry on 40P01. As of 2026-07, InnoDB 8.4 LTS defaults are innodb_deadlock_detect=ON, innodb_lock_wait_timeout=50, and current PostgreSQL defaults deadlock_timeout=1s — the load-bearing operational constants. The deepest lesson is architectural: deadlock is the tax 2PL charges for serializability, which is precisely why MVCC and SSI are so attractive — their lock-free reads and non-blocking SIREAD predicate locks cannot deadlock at all, moving the cost from deadlock-and-retry to serialization-failure-and-retry.

See Also

Graph View