Database Deadlocks

Deadlocks are a classic concurrency problem that can cripple the performance of a database system. When two or more transactions hold locks on resources that the others need, they end up waiting forever. This article walks through the fundamentals of deadlocks, illustrates a common scenario, explains how modern databases detect and resolve them, and offers practical strategies to reduce their occurrence.

What Is a Deadlock?

In a relational database, a transaction is a unit of work that must be executed atomically. To preserve data consistency, the database acquires locks on rows, pages, or tables. A deadlock occurs when:

1. Transaction A holds a lock on Resource 1 and requests a lock on Resource 2.
2. Transaction B holds a lock on Resource 2 and requests a lock on Resource 1.

Neither transaction can proceed until the other releases its lock, creating a cycle of waiting that can never resolve on its own.

The Coffman Conditions

A deadlock can only arise if all four of the following conditions hold simultaneously:

These are known as the Coffman conditions and form the theoretical basis for deadlock analysis.

A Concrete Example

Consider a simple account table:

Two concurrent transactions perform money transfers:

• T1: Add 100 to account 1, then subtract 100 from account 2.
• T2: Add 50 to account 2, then subtract 50 from account 1.

-- Transaction T1
BEGIN;
UPDATE account SET balance = balance + 100 WHERE id = 1;   -- X lock on row 1
UPDATE account SET balance = balance - 100 WHERE id = 2;   -- waits for X lock on row 2
COMMIT;

-- Transaction T2
BEGIN;
UPDATE account SET balance = balance + 50 WHERE id = 2;    -- X lock on row 2
UPDATE account SET balance = balance - 50 WHERE id = 1;    -- waits for X lock on row 1
COMMIT;

If T1 acquires the lock on row 1 before T2 locks row 2, the two updates will block each other, forming a classic deadlock.

How Databases Detect Deadlocks

Most relational engines implement a wait‑for graph:

• Nodes represent active transactions.
• Directed edges point from a waiting transaction to the one holding the required lock.

A background thread periodically scans this graph for cycles. When a cycle is found, the system knows a deadlock exists.

How Deadlocks Are Resolved

Once a deadlock is detected, the database chooses one transaction as the victim and rolls it back:

• The victim releases all its locks.
• The remaining transactions can continue.
• The client receives an error such as Deadlock found when trying to get lock; try restarting transaction.

Choosing the victim usually involves heuristics that minimize wasted work, such as selecting the transaction that has performed the fewest operations or has the lowest cost to roll back.

Prevention and Mitigation Strategies

While deadlocks cannot be eliminated entirely, careful design and coding practices can dramatically reduce their frequency.

1. Consistent Lock Ordering

If all transactions acquire locks in the same deterministic order (e.g., always lock rows with smaller id first), circular wait is prevented. Even simple operations like updating multiple rows should follow a global ordering rule.

2. Reduce Transaction Scope

• Keep transactions short and focused.
• Avoid long‑running external calls (RPC, file I/O) inside a transaction.
• Break large updates into smaller batches.

3. Index Design

Missing indexes can cause full‑table scans that lock many rows unnecessarily. Ensure that queries use appropriate indexes so that only the required rows are locked.

4. Lower Isolation Levels When Safe

Using a weaker isolation level such as READ COMMITTED reduces the use of gap locks and next‑key locks, which are common sources of deadlocks in InnoDB. Only elevate to REPEATABLE READ or SERIALIZABLE when the business logic demands it.

5. Retry Logic

Deadlocks are often transient. Applications should catch the deadlock error (e.g., MySQL error 1213) and automatically retry the transaction after a short back‑off. A simple exponential‑backoff strategy can be implemented in most languages.

6. Use Explicit Locking When Needed

Sometimes acquiring a lock explicitly with SELECT … FOR UPDATE before performing related updates can give you more control over lock ordering and reduce the chance of deadlocks.

7. Monitor and Tune

Regularly inspect the database’s deadlock logs. Many engines expose deadlock traces that include the SQL statements and the lock graph. Use this information to identify problematic patterns and refactor code accordingly.

Summary

Deadlocks arise when concurrent transactions hold locks that each other needs, forming a cycle of waiting. They satisfy the Coffman conditions and can stall database operations entirely. Modern databases detect deadlocks via wait‑for graphs and resolve them by rolling back a victim transaction. By adopting consistent lock ordering, keeping transactions short, indexing properly, choosing appropriate isolation levels, implementing retry logic, and monitoring deadlock incidents, developers and DBAs can keep deadlocks at bay and maintain high throughput in their systems.