Database Deadlocks

1. What Is a Deadlock

A deadlock means that two (or more) transactions each hold a lock the other wants. If transaction 1 obtains an exclusive lock on table A while trying to obtain an exclusive lock on table B, and transaction 2 already holds the exclusive lock on table B while requesting an exclusive lock on table A, neither transaction can proceed.

1.1. Example

Two concurrent transactions are modifying one table. The first transaction executes:

UPDATE accounts SET balance = balance + 100.00 WHERE acctnum = 11111;

This obtains a row-level lock on the row where acctnum = 11111. Then the second transaction executes:

UPDATE accounts SET balance = balance + 100.00 WHERE acctnum = 22222;
UPDATE accounts SET balance = balance - 100.00 WHERE acctnum = 11111;

The first UPDATE statement successfully obtains a row-level lock on the specified row where acctnum = 22222, so it successfully updates that row. But the second UPDATE statement finds that the row it is trying to update is already locked, so it waits for the transaction holding that lock to finish. Transaction 1 executes:

UPDATE accounts SET balance = balance - 100.00 WHERE acctnum = 22222;

Transaction 1 tries to obtain a row-level lock on the specified row, but transaction 2 holds this lock. Therefore, transaction 1 is blocked by transaction 2, while transaction 2 is also blocked by transaction 1. This is a deadlock.

2. How to Resolve Deadlocks

2.1. Timeout

2.1.1. What It Is

Wait until timeout. For example, the timeout for MySQL InnoDB is configured by innodb_lock_wait_timeout.

2.1.2. Problem

The duration is difficult to determine.

2.2. Deadlock Detection

2.2.1. What It Is

Perform deadlock detection. After a deadlock is found, proactively roll back one transaction in the deadlock chain so that the other transactions can continue executing. For example, MySQL InnoDB can enable this logic by setting innodb_deadlock_detect to on. After it is enabled, when MySQL acquires a lock and finds a conflict, it performs deadlock detection, checking whether there is a cycle in the wait-for graph (see Entry Node of a Cycle in a Linked List.md). As shown below: treat transactions and the locks they hold as vertices, and requested locks as edges, then construct a graph. If there is a cycle in the graph, there is a deadlock.

Once a deadlock is found, it is recorded, and one transaction is chosen as the victim and rolled back.

2.2.2. Problem

If all transactions update the same row, every newly arriving thread has to determine whether its addition causes a deadlock. The complexity is O(N), which consumes too much CPU.

3. References

• Explicit Locking
• What Causes Database Concurrency Deadlocks and What Are the Solutions? (internal link redacted)