A Cycle Of Waiting
A deadlock occurs when two or more transactions each hold a lock the other needs, forming a cycle in the wait for graph. No transaction can proceed because each waits on another. Left alone they would wait forever.
Detecting The Cycle
The engine maintains a wait for graph whose nodes are transactions and whose edges mean one transaction waits for a lock held by another. A background detector periodically searches this graph for a cycle. Finding a cycle means a deadlock exists.
Choosing The Victim
To break the cycle the engine aborts one transaction, the victim, releasing its locks so the others continue. Victim selection tries to minimize cost.
- The transaction that has done the least work is often chosen, since rolling it back is cheap.
- Some engines prefer the transaction holding fewer locks or the newest one.
- The victim receives a deadlock error and must retry.
Avoiding Deadlocks
Acquiring locks in a consistent order across transactions prevents cycles from forming, which is more reliable than depending on detection.
Key idea
A deadlock is a cycle in the wait for graph; the engine detects it and aborts the lowest cost victim to release locks, while consistent lock ordering prevents cycles in the first place.