What a Deadlock Is
A deadlock happens when transactions form a cycle of waiting. Transaction A holds a lock B wants, and B holds a lock A wants. Neither can proceed, so they wait forever unless the system intervenes.
Detection
The database tracks a wait for graph where an edge points from a waiting transaction to the one holding its desired lock. A cycle in this graph means a deadlock. The system periodically searches for cycles and, when it finds one, aborts a victim transaction to break it. The victim is usually the one that did the least work, so it is cheap to roll back and retry.
Prevention
Instead of detecting cycles, prevention stops them from forming. Common schemes use transaction timestamps.
- Wait die: an older transaction may wait for a younger one, but a younger one requesting an older one's lock is aborted.
- Wound wait: an older transaction forces a younger holder to abort, while a younger one waits.
Timeouts
A simpler approximation aborts any transaction that waits longer than a threshold. It is easy but can kill transactions that were not truly deadlocked.
Key idea
Deadlocks are cycles of waiting, resolved either by detecting cycles in a wait for graph and aborting a victim, or by preventing cycles with timestamp ordering.