Imagine two cars meeting on a narrow one-lane bridge from opposite sides. Neither can move forward until the other backs up, and neither wants to back up. Both are stuck forever.
Databases face the same situation. In the Lock-Based Concurrency Control (2PL) chapter we saw that a transaction may hold some locks while waiting for another lock. If two (or more) transactions end up waiting for each other, none of them can ever continue.
A deadlock is a situation in which every transaction in a set is waiting for a lock held by another transaction in the same set, so none of them can proceed.
In this chapter we will see how deadlocks happen, how a DBMS prevents them, how it detects them using a wait-for graph, how it recovers, and we will create a real deadlock in MySQL.
A Simple Deadlock
T1 transfers money from account A to B. T2 transfers money from B to A. Both use 2PL with exclusive locks.
T1 T2
lock-X(A) ✔ granted
lock-X(B) ✔ granted
write(A)
write(B)
lock-X(B) ⏳ waits for T2
lock-X(A) ⏳ waits for T1
T1 ──waits for──▶ T2
▲ │
└────waits for─────┘
T1 cannot release A until it gets B (it is still in its growing phase), and T2 cannot release B until it gets A. Without help from the DBMS, they will wait forever.
Four Necessary Conditions
A deadlock can occur only if all four of these conditions (the Coffman conditions) hold at the same time:
Condition | Meaning in a DBMS |
|---|---|
Mutual exclusion | An X lock can be held by only one transaction at a time |
Hold and wait | A transaction holds some locks while waiting for more |
No preemption | A lock cannot be forcibly taken away from a transaction |
Circular wait | T1 waits for T2, T2 waits for T3, …, Tn waits for T1 |
Every deadlock-handling technique works by breaking one of these conditions, either in advance (prevention) or after the fact (detection and recovery, which "preempts" a victim by rolling it back).
Broadly there are two strategies:
Deadlock prevention: design the protocol so that a deadlock can never form. Useful when deadlocks would be frequent.
Deadlock detection and recovery: let deadlocks happen occasionally, find them, and break them. Usually cheaper when deadlocks are rare — which is why most real databases use it.
Deadlock Prevention
1. Lock Everything at Once (Conservative 2PL)
A transaction must lock all the items it needs before it begins. It never holds some locks while waiting for others, so hold and wait is broken. As discussed in the 2PL chapter, the problem is that a transaction rarely knows its full data set in advance, and items stay locked for longer than needed.
2. Lock Ordering
Put a fixed order on all data items (for example by primary key) and require every transaction to lock items only in that order. In our bank example, both T1 and T2 would have to lock A before B. T2 would then wait on A while holding nothing, so no cycle can form. This breaks circular wait.
This is also the most practical advice for application developers: always update rows in a consistent order.
3. Timestamp-Based Schemes: Wait-Die and Wound-Wait
These two schemes use the transaction timestamps from the Timestamp Ordering Protocol chapter. Smaller timestamp = older transaction. Suppose Ti requests a lock currently held by Tj.
Wait-Die (non-preemptive)
If Ti is older than Tj → Ti waits.
If Ti is younger than Tj → Ti dies (is rolled back).
Only older transactions wait for younger ones, so every waiting edge goes old → young and a cycle is impossible.
Wound-Wait (preemptive)
If Ti is older than Tj → Ti wounds Tj (Tj is rolled back and Ti gets the lock).
If Ti is younger than Tj → Ti waits.
Here only younger transactions wait for older ones, so again a cycle is impossible.
Worked Example
Let TS(T1) = 5, TS(T2) = 10, TS(T3) = 15 (T1 is the oldest).
Requester | Holder | Wait-Die | Wound-Wait |
|---|---|---|---|
T1 (5) | T2 (10) | T1 waits | T2 is rolled back (wounded) |
T3 (15) | T2 (10) | T3 is rolled back (dies) | T3 waits |
T2 (10) | T1 (5) | T2 is rolled back (dies) | T2 waits |
T1 (5) | T3 (15) | T1 waits | T3 is rolled back (wounded) |
A handy memory trick: in both schemes, the younger transaction is always the one that gets rolled back. The scheme name tells you what happens when the older transaction (first word) requests and when the younger requests (second word):
Older requests Younger requests
Wait-Die WAIT DIE (younger rolls back)
Wound-Wait WOUND (younger) WAIT
Why Keep the Original Timestamp?
When a transaction is rolled back by wait-die or wound-wait, it restarts with its original timestamp. (This is the opposite of the Timestamp Ordering protocol, where a restarted transaction gets a new one.) As time passes, the restarted transaction becomes relatively older and older, until it is the oldest in the system and can no longer be rolled back. This prevents starvation.
Wait-Die vs Wound-Wait
Feature | Wait-Die | Wound-Wait |
|---|---|---|
Type | Non-preemptive | Preemptive |
Who waits? | Older waits for younger | Younger waits for older |
Who is rolled back? | Younger requester | Younger holder |
Repeated rollbacks | A young transaction may die many times on the same item | Usually fewer rollbacks |
Starvation | No (original timestamp kept) | No (original timestamp kept) |
Both schemes may roll back transactions that would never actually have deadlocked. That unnecessary work is the price of prevention.
4. No-Wait and Timeouts
No-wait: if a lock cannot be granted immediately, roll back the requester at once. Simple, deadlock-free, but causes many needless rollbacks.
Timeout: a transaction waits for a lock for at most a fixed time; after that it is rolled back. It is simple and handles deadlocks automatically, but choosing the time is hard: too short causes needless rollbacks, too long wastes time when a real deadlock exists. Strictly speaking, timeouts sit between prevention and detection.
Deadlock Detection: The Wait-For Graph
Instead of preventing deadlocks, the DBMS can periodically check whether one exists. It maintains a wait-for graph:
Each node is an active transaction.
An edge Ti → Tj means Ti is waiting for a lock held by Tj.
A deadlock exists if and only if the wait-for graph contains a cycle.
Example
Suppose the lock table says:
T1 holds A, waits for B (held by T2)
T2 holds B, waits for C (held by T3)
T3 holds C, waits for A (held by T1)
T4 waits for A (held by T1)
T4
│
▼
┌────▶ T1 ────▶ T2
│ │
│ ▼
└─────────────── T3
Cycle: T1 → T2 → T3 → T1 → DEADLOCK
T1, T2 and T3 are deadlocked. T4 is not part of the cycle; it is just waiting behind T1. Once the deadlock is broken and T1 eventually finishes, T4 will continue.
Don't confuse the wait-for graph with the precedence graph from the serializability chapters. A precedence graph describes conflicts in a finished schedule; a wait-for graph describes who is currently waiting for whom.
How Often to Run Detection?
Cycle detection (for example using DFS) costs time, so a system can run it on every lock wait, or periodically. If deadlocks are frequent, check often; otherwise deadlocked transactions sit idle and their locks block others too.
Recovery from Deadlock
When a cycle is found, the DBMS must break it by rolling back one or more transactions. This involves three decisions.
1. Victim Selection
Choose the transaction whose rollback costs the least. Factors include:
How long it has run and how much longer it needs
How many data items it has used or modified
How many transactions would have to be rolled back in total
2. Rollback
Total rollback: abort the victim completely and restart it. Simple and common.
Partial rollback: roll back only as far as needed to release the lock that breaks the cycle. Cheaper, but the system must record more information (for example, savepoints).
3. Avoiding Starvation
If the same transaction is always chosen as the cheapest victim, it may never finish. A common fix is to include the number of times it has already been rolled back in the cost, so it eventually stops being chosen.
A Real Deadlock in MySQL
MySQL's InnoDB engine uses detection. When a lock wait would create a cycle, it immediately rolls back one transaction (by default it prefers the "smaller" one, based on how many rows it has inserted, updated or deleted) and returns error 1213 to it.
We created a copy of the tutorial's company_db sample database and ran two sessions at the same time, with a short SLEEP so that they interleave. Both employees 2 and 3 start with a salary of 95000.00.
Session A:
START TRANSACTION;
UPDATE employees SET salary = salary + 1000 WHERE emp_id = 2; -- X lock on row 2
SELECT 'A: locked emp 2' AS step;
DO SLEEP(2);
SELECT 'A: now asking for emp 3' AS step;
UPDATE employees SET salary = salary + 1000 WHERE emp_id = 3; -- needs row 3
SELECT 'A: got emp 3' AS step;
COMMIT;
Session B (starts one second later):
START TRANSACTION;
UPDATE employees SET salary = salary - 500 WHERE emp_id = 3; -- X lock on row 3
SELECT 'B: locked emp 3' AS step;
DO SLEEP(2);
SELECT 'B: now asking for emp 2' AS step;
UPDATE employees SET salary = salary - 500 WHERE emp_id = 2; -- needs row 2
SELECT 'B: got emp 2' AS step;
COMMIT;
Output of Session B:
+-----------------+
| step |
+-----------------+
| B: locked emp 3 |
+-----------------+
+-------------------------+
| step |
+-------------------------+
| B: now asking for emp 2 |
+-------------------------+
ERROR 1213 (40001) at line 6: Deadlock found when trying to get lock; try restarting transaction
Output of Session A:
+-----------------+
| step |
+-----------------+
| A: locked emp 2 |
+-----------------+
+-------------------------+
| step |
+-------------------------+
| A: now asking for emp 3 |
+-------------------------+
+--------------+
| step |
+--------------+
| A: got emp 3 |
+--------------+
Here is what happened:
time Session A Session B
0s X(row 2) granted
1s X(row 3) granted
2s wants row 3 → waits for B
3s wants row 2 → waits for A
→ cycle A → B → A detected
→ B chosen as victim, rolled back
gets row 3, COMMIT
Final data:
+--------+-------------+----------+
| emp_id | name | salary |
+--------+-------------+----------+
| 2 | Priya Iyer | 96000.00 |
| 3 | Rohan Mehta | 96000.00 |
+--------+-------------+----------+
Only Session A's +1000 updates survived. Session B's −500 on employee 3 was rolled back completely, which released its lock and let A finish. Note that the whole transaction B was rolled back, not just the failing statement — the application must catch error 1213 and retry the transaction. Which session becomes the victim depends on InnoDB's choice and on timing; in this run it was B.
Some useful InnoDB facts (MySQL 8.x):
innodb_deadlock_detect(defaultON) enables immediate detection. On very high-concurrency systems it can be turned off, in which case InnoDB relies on the timeout below.innodb_lock_wait_timeout(default 50 seconds) gives up on an ordinary lock wait with error 1205.SHOW ENGINE INNODB STATUSprints aLATEST DETECTED DEADLOCKsection showing both transactions and the locks involved.
Deadlock vs Starvation
Deadlock | Starvation |
|---|---|
A set of transactions wait for each other in a cycle | One transaction waits (or is rolled back) indefinitely while others progress |
No transaction in the cycle makes progress | The system as a whole makes progress |
Fixed by prevention or detection + rollback | Fixed by fair lock queues, keeping original timestamps, counting rollbacks |
Common Mistakes
Swapping wait-die and wound-wait. Remember: in both, the younger transaction is the one rolled back; the older one never is.
Giving a new timestamp after wait-die/wound-wait rollback. They keep the original timestamp to avoid starvation.
Thinking every waiting transaction is deadlocked. Only transactions on a cycle are deadlocked (T4 in our example was not).
Assuming strict 2PL prevents deadlocks. It prevents cascading rollbacks, not deadlocks.
Retrying only the failed statement in an application. After error 1213 the whole transaction has been rolled back; retry it from the start.
Interview Questions
What are the four necessary conditions for deadlock?
Mutual exclusion, hold and wait, no preemption, and circular wait. All four must hold at the same time.
Explain wait-die and wound-wait in one line each.
Wait-die: an older requester waits, a younger requester dies. Wound-wait: an older requester wounds (rolls back) the younger holder, a younger requester waits.
How does a DBMS detect deadlock?
It builds a wait-for graph with an edge Ti → Tj when Ti waits for a lock held by Tj, and checks it for a cycle. A cycle means deadlock.
Is the timestamp ordering protocol subject to deadlock?
No. Basic timestamp ordering never makes a transaction wait; it rolls back instead.
How would you reduce deadlocks in an application?
Access rows in a consistent order, keep transactions short, add suitable indexes so fewer rows are locked, and retry transactions that fail with a deadlock error.
Summary
A deadlock is a cycle of transactions each waiting for a lock held by the next.
It needs mutual exclusion, hold and wait, no preemption and circular wait.
Prevention: conservative 2PL, lock ordering, wait-die, wound-wait, no-wait, timeouts.
Detection: find a cycle in the wait-for graph; then recover by choosing a victim, rolling it back (totally or partially) and avoiding starvation.
MySQL InnoDB detects deadlocks immediately, rolls back a victim with ERROR 1213, and the application should retry.
Rolling a transaction back requires knowing what it changed. In the next chapter, Recovery & Logging, we will see how the log makes rollbacks and crash recovery possible.