The idea: let age decide, so no cycle can form

Under locking, a deadlock is a cycle of transactions that each wait for the next one. Two-phase locking lets such a cycle form and then finds it. Deadlock prevention stops the cycle from forming at all. Each transaction gets a timestamp when it starts, and on every lock conflict the database compares the ages of the two transactions. Only one of them is allowed to wait. The other one is rolled back.

A two by two grid. Rows: the requester is older, the requester is younger than the holder. Columns: wait-die and wound-wait. Wait-die: older waits, younger dies. Wound-wait: older wounds the holder, younger waits.
The same conflict, two rules: wait-die rolls back the younger requester, wound-wait rolls back the younger holder.

The canvas runs one small workload at a time. Each transaction runs a fixed program of UPDATE statements and a COMMIT. Each UPDATE takes an exclusive (X) lock on its row and keeps it until COMMIT (strict 2PL). A clock ticks, and in each tick T1, T2 and T3 run their next statement in that order. The table under the panels runs the same workload under all three schemes, so you can compare them.

Timestamps: smaller is older

A transaction's timestamp ts is the time it started. The page numbers them 1, 2, 3 in start order. A smaller ts means an older transaction. The schemes compare the ts of the requester (the transaction asking for the lock) with the ts of the holder (the transaction that has it). When the row is free, nothing special happens: the lock is granted.

Wait-die

In wait-die, an older requester may wait for a younger holder. A younger requester may never wait for an older holder: it dies. It is rolled back, frees its locks and starts again later. Only the requester is ever rolled back, so wait-die never touches the work of the holder.

Demo: older asks, younger holds (wait-die waits): T1 (ts 1) asks for A, which T2 (ts 2) holds. T1 is older, so it waits. T2 commits at t = 3, and T1 gets A. That is 1 wait, 0 rollbacks, and everyone has committed at t = 4. Demo: younger asks, older holds (wait-die dies): T2 asks for A, which T1 holds. T2 is younger, so it dies at t = 2, restarts at t = 4 and commits at t = 6.

Wound-wait

In wound-wait, an older requester does not wait: it wounds the younger holder. The holder is rolled back and the older transaction takes the lock. A younger requester waits for an older holder. So an older transaction never waits for a younger one.

requester vs holderwait-diewound-wait
requester olderrequester waitsholder is rolled back ✗
requester youngerrequester is rolled back ✗requester waits

Run demos 1 and 2 (or 3 and 4) one after the other: the same conflict gives the opposite answer. In the "older asks, younger holds" workload, wound-wait rolls back T2 at t = 2 although there is no deadlock. T2 restarts and the workload ends at t = 6 instead of t = 4. In the "younger asks, older holds" workload it is wait-die that rolls back for nothing. Both schemes are pessimistic: they roll back whenever a cycle could form, not only when one does.

Why no cycle can form

Look at the wait-for graph. Under wait-die, every edge goes from an older waiter to a younger holder. Under wound-wait, every edge goes from a younger waiter to an older holder. Either way, edges only go one way by age. A cycle would have to come back to where it started, so at some point it would have to go the other way. That can't happen, so there is never a deadlock.

Demo: three-way cycle under wound-wait runs T1 (A then B), T2 (B then C) and T3 (C then A). With plain waiting, that is the cycle T1 → T2 → T3 → T1. Under wound-wait, T1 wounds T2 at t = 2 and T3 waits for T1, which is allowed. The cycle never closes: 1 wait, 1 rollback, done at t = 6.

No starvation: a restart keeps its timestamp

A transaction that is rolled back starts again from its first statement. The page restarts it 2 ticks later. The key rule: it keeps its old timestamp. Every transaction that starts later is younger than it. So each time it restarts, fewer transactions are older, and in the end it is the oldest one. The oldest transaction is never rolled back by either scheme, so it finishes. If a restart took a new timestamp, a transaction could die again and again forever (starvation).

Time runs down from t = 1 to t = 6. T1 with ts 1 holds A until it commits at t = 4. T2 with ts 2 asks for A at t = 1 and dies, asks again at t = 3 and dies, and at t = 5 finds A held by T3 with ts 3, so it waits and gets A when T3 commits in the same tick. T2 commits at t = 6.
T2 keeps ts 2 through two restarts, so when the newer T3 (ts 3) holds the row, T2 is the older one and waits instead of dying.

Demo: restart keeps its timestamp (wait-die): T1 holds A from t = 1 to t = 4. T2 (ts 2) asks for A at t = 1 and at t = 3 and dies both times. At t = 4, T1 commits and the new T3 (ts 3) takes A. At t = 5, T2 asks again. Now the holder is T3, and T2 is older, so T2 waits. T3 commits in the same tick, and T2 gets A. Result: 1 wait, 2 rollbacks, all committed at t = 6.

Prevention vs detection, and what MariaDB does

MariaDB's InnoDB uses neither scheme. Every requester waits, whatever its age. Each time a transaction starts to wait, the deadlock detector follows the wait-for graph (innodb_deadlock_detect = ON, the default). When it finds a cycle, it rolls back a victim and sends it:

ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

InnoDB picks the "smaller" victim, the one that has changed or locked fewer rows, so less work is lost. The page uses the number of locks held, and a tie goes to the transaction that just asked. The application must run the transaction again, and the retry is a new transaction with a new trx id: nothing like "keep your timestamp" exists. With innodb_deadlock_detect = OFF, a waiter gives up after innodb_lock_wait_timeout seconds (50 by default) with ERROR 1205 (HY000): Lock wait timeout exceeded. SHOW ENGINE INNODB STATUS prints the last deadlock.

Demo: crossed locks under InnoDB detection: T1 locks A then B, T2 locks B then A. Both wait at t = 2, the detector finds T2 → T1 → T2, and T2 (trx 102) is the victim. Its retry is trx 103. That is 2 waits and 1 rollback. Wait-die and wound-wait also roll back T2 once on this workload, but without waiting for the cycle to close.

wait-die / wound-waitdetection (InnoDB)
when it rolls backwhen a cycle could formonly when a cycle exists
cost per lock waitcompare two timestampssearch the wait-for graph
victimalways the younger onethe "smaller" one
starvationno: restart keeps its tspossible in theory; apps retry

Detection wins when deadlocks are rare, which is the usual case: it only rolls back when it must. Prevention needs no graph search, which helps in a distributed database where the graph is spread over many machines. Google Spanner uses wound-wait for this reason.

Other ways to handle the same problem: timestamp ordering uses timestamps without locks at all, checking every read and write against read_TS and write_TS. An operating system finds deadlocks in a resource-allocation graph: see deadlock detection. With threads, the usual fix is a global lock order: see lock order deadlock. Why a 2PL schedule is safe at all is on conflict serializability.

See also Multiple Granularity Locking for locks at table, page and row level and the intention locks that connect them.

What the page leaves out

The page has only exclusive locks, one lock per row, and a fixed restart delay of 2 ticks. Real systems also have shared locks, where one requester can conflict with several holders and the rule is checked against each of them. A wounded transaction that is already committing is usually allowed to finish. MariaDB has no setting for wait-die or wound-wait; they are shown as textbook schemes next to what InnoDB really does.

On the mind map

Open the Databases & Storage mind mapDatabases& StorageSchema and storage: how rows land on diskSchema and storageIndexes: find rows without a full scanIndexesRunning a query: parse, plan, executeRunning a queryCost-based optimizer: estimate rows, pick cheapest planCost-based optimizerQuery rewrites: same answer, simpler queryQuery rewritesTransactions: ACID: isolation and recoveryTransactionsApps and connections: the client side of the databaseApps and connectionsMongoDB: documents, replica sets, shardsMongoDBMVCC and isolationMVCC and isolationreaders see a snapshot of row versionsTwo-phase lockingTwo-phase lockinggrow locks, then release; detect cyclesConflict serializabilityConflict serializabilityCycle in precedence graph = not serializableRecoverable schedulesRecoverable schedulesCommit only after those you read fromWait-Die and Wound-WaitAge decides who waits and who rolls backMultiple Granularity LockingMultiple Granularity LockingIntention locks on every ancestorOptimistic vs pessimisticOptimistic vs pessimisticversion check vs SELECT FOR UPDATEValidation-based OCCValidation-based OCCCheck read/write sets at commit, else abortWAL and ARIESWAL and ARIESlog first; redo all, then undo losersTimestamp orderingTimestamp orderingolder timestamp wins; late writes abortOpen the Databases & Storage mind mapDatabases & StorageACID: isolation and recoveryTransactionsMVCC and isolationMVCC and isolationreaders see a snapshot of row versionsTwo-phase lockingTwo-phase lockinggrow locks, then release; detect cyclesConflict serializabilityConflict serializabilityCycle in precedence graph = not serializableRecoverable schedulesRecoverable schedulesCommit only after those you read fromWait-Die and Wound-WaitAge decides who waits and who rolls backMultiple Granularity LockingMultiple Granularity LockingIntention locks on every ancestorOptimistic vs pessimisticOptimistic vs pessimisticversion check vs SELECT FOR UPDATEValidation-based OCCValidation-based OCCCheck read/write sets at commit, else abortWAL and ARIESWAL and ARIESlog first; redo all, then undo losersTimestamp orderingTimestamp orderingolder timestamp wins; late writes abort
This page on the Databases & Storage mind map · 55 pages in 8 branches · open it to see the whole map and test yourself in recall mode.