Deadlock

A deadlock occurs when two or more transactions are each waiting for a lock held by the other, forming a cycle of dependencies where no transaction can proceed.

graph LR
    T1[Transaction 1] -->|holds lock on A, waits for B| T2[Transaction 2]
    T2 -->|holds lock on B, waits for A| T1

Example

T1: BEGIN; UPDATE accounts SET balance = 100 WHERE id = 1;  -- locks row 1
T2: BEGIN; UPDATE accounts SET balance = 200 WHERE id = 2;  -- locks row 2
T1: UPDATE accounts SET balance = 300 WHERE id = 2;         -- waits for T2's lock
T2: UPDATE accounts SET balance = 400 WHERE id = 1;         -- waits for T1's lock → DEADLOCK

Detection

The DBMS maintains a wait-for graph — a directed graph where an edge from T1 to T2 means T1 is waiting for a lock held by T2. A cycle in this graph = deadlock.

When detected, the DBMS selects a victim transaction to abort (typically the youngest, cheapest, or least-progressed), breaking the cycle. The victim is rolled back and can retry.

Prevention

Timestamp-based strategies that avoid cycles entirely:

Strategy	Rule	Behavior
Wait-Die	Older waits, younger dies	If T1 is older than T2, T1 waits; otherwise T1 aborts and retries
Wound-Wait	Older wounds, younger waits	If T1 is older than T2, T2 is forced to abort; otherwise T1 waits

Both guarantee no cycles form. Wound-Wait is generally preferred (fewer total aborts).

Avoidance

• Lock ordering — All transactions acquire locks in the same global order (e.g., by table name, then by Primary Key). If every transaction locks resources in the same sequence, cycles cannot form.
• Lock timeouts — Abort transactions that wait longer than a threshold. Simple but may abort non-deadlocked transactions.
• Conservative 2PL — Acquire all locks before starting. No deadlocks, but impractical for most workloads.

Deadlocks in Distributed Databases

In distributed systems, deadlocks span multiple nodes, making detection harder since the full wait-for graph is split across sites:

Technique	How It Works	Trade-off
Centralized	One site collects all wait-for data	Simple but single point of failure
Distributed (Edge-Chasing)	Probe messages traverse the transaction cycle across nodes	No single point of failure but more network traffic
Hierarchical	Nodes in a tree; each level checks its group, escalates up	Balanced load but depends on hierarchy structure
Path-Pushing	Nodes push local wait-for graphs to neighbors for incremental detection	Distributed processing but can produce redundant messages

Resolution: The site that detects the cycle selects a victim (typically the youngest or cheapest transaction), aborts it, and releases its locks.

Deadlocks in Practice

• PostgreSQL — Detects deadlocks automatically; aborts one transaction with error ERROR: deadlock detected
• MySQL (InnoDB) — Uses wait-for graph; the transaction with fewest row-level locks is the victim
• Application mitigation — Keep transactions short, access resources in consistent order, use SELECT ... FOR UPDATE only when necessary