Notestransactions🌱 seedling
Deadlock
Also: Deadlocks · Waits-For Graph · Deadlock Detection · Wound-Wait · Wait-Die · Lock Ordering
Two or more transactions each hold a lock the other needs, so all of them wait forever. Databases find the cycle in a waits-for graph (or prevent it with timestamp priorities) and abort a victim, which the application must retry.
Why it exists
Any system where transactions acquire locks incrementally and hold them, like Two-Phase Locking or SELECT … FOR UPDATE, can form a cycle: T1 holds A and wants B, T2 holds B and wants A.
How it works
- Detection: the lock manager tracks who waits for whom and searches for cycles. Postgres checks after
deadlock_timeout(1 s by default) and aborts a victim with SQLSTATE 40P01; InnoDB checks as soon as a transaction would wait (MySQL error 1213). - Timeouts: with
innodb_deadlock_detectoff (sometimes done under extreme concurrency, where detection itself is costly), InnoDB relies oninnodb_lock_wait_timeout, 50 s by default. - Prevention by priority: each transaction gets a timestamp. Wait-die: a younger requester aborts itself instead of waiting. Wound-wait: an older requester aborts the younger holder. Either way waits only run one direction, so no cycle forms.
- Prevention by ordering: acquire locks in a global order (e.g. ascending primary key).
Trade-offs
| Approach | Cost |
|---|---|
| detection | CPU for graph search; victims lose their work |
| timeouts | slow to resolve; can abort transactions that weren't deadlocked |
| wait-die / wound-wait | aborts some transactions that would never have deadlocked |
| lock ordering | discipline across every code path |
In practice
- Spanner uses wound-wait for read-write transactions, so it never needs global deadlock detection.
- A frequent real-world source: two code paths updating the same pair of rows in opposite orders, or gap-lock conflicts between concurrent inserts in InnoDB.
Pitfalls
- Treating a deadlock error as fatal instead of retrying the whole transaction.
- Long transactions widen the window in which cycles form.
Connections
- Part of
- Two-Phase Locking
- Related
- Retry with Backoff
- In real systems
- PostgreSQLMySQL
Recall
These cards are also in your review deck, scheduled with spaced repetition.