What is a Deadlock?
A deadlock occurs when two or more transactions are each waiting for a lock held by another transaction in the group, forming a circular wait. No transaction can make progress because each is blocked by another member of the cycle. Without intervention, these transactions would wait forever.
The Wait-For Graph
The standard way to model deadlocks is the wait-for graph. Each node represents an active transaction. A directed edge from T1 to T2 means "T1 is waiting for a lock that T2 currently holds." A cycle in this graph means a deadlock exists. For example: T1 waits for T2, T2 waits for T3, T3 waits for T1 — a 3-way deadlock.
Deadlock Detection
The database periodically builds (or incrementally maintains) the wait-for graph and checks for cycles using a depth-first search. When a cycle is found, the system must abort one transaction in the cycle to break it. This is called the victim. Common victim selection policies:
- Youngest transaction (most recent start time) — it has done the least work
- Least work done (fewest locks, fewest writes) — minimizes wasted effort
- Lowest priority — some systems let applications assign priorities
The aborted transaction's locks are released, allowing others to proceed. The aborted transaction can then be retried.
Deadlock Prevention
Instead of detecting deadlocks after they form, prevention strategies ensure they never occur:
- Wait-Die (non-preemptive): if T1 is older than T2 (lower timestamp), T1 waits. If T1 is younger, T1 aborts (dies) immediately. Older transactions never abort for younger ones.
- Wound-Wait (preemptive): if T1 is older than T2, T1 wounds T2 (forces T2 to abort). If T1 is younger, T1 waits. Younger transactions never preempt older ones.
Both schemes guarantee no cycles because the wait-for edges always point in one direction (from older to younger, or vice versa).
Timeout-Based Approach
A simpler but less precise approach: if a transaction has been waiting for a lock for longer than a timeout threshold, assume it is deadlocked and abort it. This avoids the overhead of maintaining a wait-for graph but may abort transactions unnecessarily (false positives) or take too long to react (if the timeout is too generous).
Lock Ordering
Application-level prevention: always acquire locks in a consistent global order (e.g., by table name then by primary key). If every transaction follows the same ordering, circular waits are impossible. This is a best practice in application code but cannot be enforced by the database for ad-hoc queries.
Real-Life: Classic Deadlock Scenario
Two users simultaneously update each other's accounts:
- T1: UPDATE accounts SET balance = balance - 100 WHERE id = 'A'; then UPDATE accounts SET balance = balance + 100 WHERE id = 'B';
- T2: UPDATE accounts SET balance = balance - 50 WHERE id = 'B'; then UPDATE accounts SET balance = balance + 50 WHERE id = 'A';
Timeline:
- T1 acquires X-lock on row A.
- T2 acquires X-lock on row B.
- T1 requests X-lock on row B — blocked (T2 holds it).
- T2 requests X-lock on row A — blocked (T1 holds it).
Deadlock! T1 waits for T2, T2 waits for T1.
How databases handle this:
- MySQL InnoDB: maintains a wait-for graph, detects the cycle immediately, aborts the transaction with fewer locks (returns error 1213: "Deadlock found").
- PostgreSQL: runs deadlock detection after a configurable timeout (default 1 second), then aborts one transaction.
- SQL Server: has a dedicated background deadlock monitor thread that checks every 5 seconds (or more frequently under load).
Prevention with lock ordering: If both transactions always locked rows in alphabetical order (A before B), T2 would request A first, wait for T1, and T1 would finish without a cycle.