The labs on this site need JavaScript to run. The same content is written out below.

Learn › Database › Transactions and locking

Deadlocks in the database

When two transactions wait for each other, how does the database end it?

Transaction A moves 100 from account 1 to account 2, and transaction B moves 50 from account 2 to account 1. If the two lock the rows in opposite orders, they end up waiting for each other. Java threads in this situation would simply stop forever, but MySQL InnoDB detects the situation by itself, rolls one side back, and returns an error.

Checked against real execution · Ran 10 combinations on MySQL 8.4.11 with two sessions and checked the results against them

Concepts in this lab

Deadlock

This is a state in which two or more threads (or transactions) can never make progress, because each is waiting for a resource that the other holds. The typical case is that A holds resource 1 and waits for 2 while B holds resource 2 and waits for 1. It can be prevented by always acquiring resources in the same order.

Deadlock detection and the victim

A database feature that finds, by itself, a cycle of transactions waiting for each other's locks and forcibly rolls one of them back. When a transaction has to wait for a lock, MySQL InnoDB follows who is waiting for whom and checks whether there is a cycle. If there is one, it chooses a transaction, rolls it back as a whole, and returns error 1213 (Deadlock found). The transaction that is rolled back is called the victim, and InnoDB tries to choose a small transaction that has changed fewer rows. The side that survives proceeds without an error. Everything the victim did has been canceled, so the application must run that transaction again from the start.

Lock wait timeout

A failure of a statement that waited for a lock held by another transaction to be released, up to a set time, and still could not get it. In MySQL InnoDB, when innodb_lock_wait_timeout (default 50 seconds) passes, error 1205 (Lock wait timeout exceeded) is returned. Unlike a deadlock, it can occur even when there is no cycle of mutual waiting, and a common cause is another transaction being kept open for a long time. Under the default settings, only the statement that was waiting is canceled and the transaction stays alive, so the earlier changes and locks remain. That is why, when you get this error, you must roll back yourself and then decide whether to try again.

Shared locks and exclusive locks

A shared lock (S) is a lock for reading, and several transactions can hold it at the same time. An exclusive lock (X) is a lock for writing, and only one transaction can hold it. While data has an exclusive lock, no other transaction can take a shared lock or an exclusive lock on it.

Transaction

A way to group several data changes into a single unit so that either all of them are applied (commit) or all of them are canceled (rollback). In a bank transfer, it prevents an intermediate state where only one of the withdrawal and the deposit is applied. It is the most basic means a database has for keeping data consistent.

Try these

• Default settings — Opposite orders. The database detects the deadlock and rolls one side back, and that transfer is lost.
• If the rolled-back side tries again — It runs again from the start, and both transfers are applied.
• If the rows are locked in the same order — One side just waits for a moment, and both finish without an error.
• If B had done more work — This time A is rolled back. The side with less to undo is chosen.
• A long wait that is not a deadlock — With no cycle, nothing is detected. After waiting until the time limit, the side that waits gets error 1205.
• If the timeout is ignored and committed — Only the earlier statement is applied, and 50 disappears.

Running with the default settings

1. A: UPDATE … - 100 WHERE id = 1: Transaction A subtracts 100 from account 1. To change a row, it must take an exclusive lock on that row, and this lock is not released until A commits or rolls back.
2. B: UPDATE … - 50 WHERE id = 2: Transaction B subtracts 50 from account 2. It takes an exclusive lock on the row of account 2. The two are different rows so far, so nobody is waiting yet.
3. A: UPDATE … + 100 WHERE id = 2: A tries to add 100 to account 2. B holds the lock on that row, so A waits. A waits while holding the lock on account 1.
4. B: UPDATE … + 50 WHERE id = 1: B tries to add 50 to account 1. A holds the lock on that row, but A is waiting for B to finish. A waits for B and B waits for A, so a cycle has formed. If nothing is done, neither can ever proceed.
5. Deadlock detection in InnoDB: When a transaction has to wait for a lock, InnoDB follows who is waiting for whom and checks whether there is a cycle. It found a cycle, so it chooses one of the two and rolls it back. The documentation does not say which side is chosen when the two transactions have done the same amount of work. This screen shows the case where B is chosen. In the MySQL used for the check, it was B, which started waiting later, all 30 times.
6. B: Gets error 1213 (Deadlock found when trying to get lock; try restarting transaction). Not only the statement that was waiting but the whole transaction of B is rolled back. The change made earlier to the balance of account 2 is canceled too, and all the locks it held are released. This happens right away, without waiting for the lock wait timeout (default 50 seconds).
7. A: The statement that was waiting (UPDATE … + 100 WHERE id = 2) runs. The locks were released when B was rolled back. A did not get an error and does not even know that there was a deadlock.
8. A: COMMIT: The transfer of A (100 from account 1 to account 2) is applied. The balance is 900 for account 1 and 1100 for account 2.
9. B: Sends ROLLBACK and stops. InnoDB has already rolled it back, so there is nothing more to cancel. The transfer of B (50 from account 2 to account 1) was not applied anywhere. One request from a user has simply disappeared.

Result of this run

• InnoDB detects the deadlock by itself, rolls one transaction back as a whole, and returns error 1213. The side that survives proceeds as if nothing had happened. The database ends the deadlock, but doing the rolled-back work again is up to the application.
• If it does not try again, that request disappears without being applied.
• Your code cannot decide which side is rolled back. So prepare for the possibility that both transactions can get error 1213.

Code

-- account table: accounts 1 and 2 each have a balance of 1000

-- Transaction A: moves 100 from account 1 to account 2
START TRANSACTION;
UPDATE account SET balance = balance - 100 WHERE id = 1;
UPDATE account SET balance = balance + 100 WHERE id = 2;
COMMIT;

-- Transaction B: moves 50 from account 2 to account 1 (runs at the same time as A)
START TRANSACTION;
UPDATE account SET balance = balance - 50 WHERE id = 2;
UPDATE account SET balance = balance + 50 WHERE id = 1;
COMMIT;

-- What the side that got the error does
ROLLBACK;                          -- and stops

Assumptions of this model

Ten combinations (the settings that make sense for each of the three orders) were run in the same order as shown on the screen, with two sessions, on MySQL 8.4.11 on the PC used to write this lab (InnoDB, isolation level REPEATABLE READ, innodb_deadlock_detect on, innodb_rollback_on_timeout off). The lab was checked against these runs: which side gets which error code, whether the changes and locks remain in that transaction right after the error, and the final balances all match the screen. In the deadlock, error 1213 arrived within a few milliseconds (with the lock wait timeout set to 20 seconds), and when the session that got the error read again the row it had changed, it saw the original value 1000 and held 0 record locks. For the lock wait timeout, instead of waiting for the default 50 seconds, innodb_lock_wait_timeout of that session was reduced to 2 seconds, and even after error 1205 arrived 2 seconds later, the value 950 that the session had changed and 1 record lock were still there. Which side is rolled back in a deadlock with equal amounts of work is not set by the documentation, so the lab does not state it as a fact. Over 30 repetitions, B, which started waiting later, was rolled back all 30 times, and when B first changed 50 other rows, A was rolled back all 30 times. The statements that InnoDB tries to choose a small transaction, and that a deadlock rolls back the whole transaction while a lock wait timeout rolls back only that statement, also agree with the explanations in 17.7.5.2 Deadlock Detection and 17.20.5 InnoDB Error Handling of the MySQL 8.4 Reference Manual. What changes when the server settings are changed (when deadlock detection is turned off, or innodb_rollback_on_timeout is turned on) is not covered. The lab assumes that the two transactions interleave in exactly this order; in practice, depending on the timing, they more often pass without a deadlock.

Previous lab: Stock decrement and locks · Next lab: Undo and redo logs