Two Philosophies
A deadlock is a cycle of transactions each waiting for a lock another holds. Engines handle it in one of two ways: stop cycles from ever forming, or let them form and break them.
Detection
- The engine maintains a wait for graph where an edge means one transaction waits on another.
- Periodically or on each wait it checks for a cycle.
- If a cycle exists, it picks a victim, usually the cheapest to roll back, aborts it, and the others proceed.
- This adds no overhead when there are no deadlocks, which is the common case.
Prevention
Prevention assigns each transaction a timestamp and uses it to decide who waits.
- Wait die: an older transaction may wait for a younger one, but a younger one requesting an older one's lock is aborted, or dies.
- Wound wait: an older transaction wounds a younger holder by aborting it, while a younger one waits.
Both schemes guarantee no cycle forms because waits only go in one direction by age.
Choosing
Detection suits low conflict workloads. Prevention suits systems that cannot afford to scan a wait for graph or want predictable behavior.
Key idea
Deadlock detection finds cycles in a wait for graph and aborts a victim, while prevention uses transaction age to ensure waits never form a cycle.