How Do Databases Detect Deadlocks?
Learn how databases detect deadlocks using wait-for graphs and cycle detection, and how the victim transaction is chosen.
Expected Interview Answer
Databases detect deadlocks by building a wait-for graph, where each transaction is a node and an edge points from a waiting transaction to the transaction holding the lock it needs, and periodically checking that graph for a cycle, which proves a deadlock exists.
When transaction A waits on a lock held by transaction B, and B is simultaneously waiting on a lock held by A, neither can proceed and no timeout alone can distinguish this from ordinary slow progress. The database's lock manager tracks these wait relationships and runs a cycle-detection algorithm (essentially depth-first search) either periodically or whenever a new wait edge is added. Once a cycle is found, the engine picks a victim transaction, usually the one with the least work done or lowest priority, aborts it and releases its locks, and lets the remaining transactions continue.
- Guarantees forward progress instead of indefinite blocking
- Distinguishes true circular waits from ordinary slow queries
- Automatically selects a victim to minimize wasted work
- Frees held locks quickly once a cycle is confirmed
AI Mentor Explanation
Imagine two batters stuck mid-pitch, each waiting for the other to make the first move toward a run, both refusing to commit — the umpire watches for exactly this frozen standoff pattern rather than just any slow running between wickets. Once the umpire recognizes the circular standoff, they call it and send one batter back to restart play. A deadlock detector works the same way: it looks specifically for a closed waiting cycle, not just generic slowness, then aborts one party to break it.
Step-by-Step Explanation
Step 1
Track lock ownership
The lock manager records which transaction holds each lock and which transactions are waiting on it.
Step 2
Build the wait-for graph
An edge is added from a waiting transaction to the transaction currently holding the requested lock.
Step 3
Search for a cycle
A background thread or on-demand check runs cycle detection (e.g. depth-first search) over the wait-for graph.
Step 4
Abort a victim transaction
When a cycle is confirmed, the engine rolls back a chosen victim, releasing its locks so the remaining transactions can proceed.
What Interviewer Expects
- Clear explanation of the wait-for graph and cycle detection
- Distinction between deadlock detection and simple timeout-based blocking
- Understanding of victim selection criteria
- Awareness that the aborted transaction must retry from the application side
Common Mistakes
- Confusing deadlock detection with plain query timeouts
- Assuming any two blocked transactions are automatically a deadlock
- Forgetting that the victim transaction must be retried by the application
- Not mentioning that detection has a cost, so it runs periodically rather than continuously in some engines
Best Answer (HR Friendly)
“A database detects a deadlock by tracking which transaction is waiting on which lock and building a graph of those wait relationships. If it finds a closed loop, like transaction A waiting for B while B waits for A, that is a deadlock, so the database automatically kills one of the transactions to break the cycle and lets the other one proceed.”
Code Example
-- Session 1
BEGIN;
UPDATE Accounts SET balance = balance - 100 WHERE account_id = 1;
-- ... pauses here, holding the lock on account_id = 1
-- Session 2 (runs concurrently)
BEGIN;
UPDATE Accounts SET balance = balance - 50 WHERE account_id = 2;
-- ... pauses here, holding the lock on account_id = 2
-- Session 1 now requests account_id = 2 (held by Session 2)
UPDATE Accounts SET balance = balance + 100 WHERE account_id = 2;
-- Session 2 now requests account_id = 1 (held by Session 1)
UPDATE Accounts SET balance = balance + 50 WHERE account_id = 1;
-- The engine detects the wait-for cycle and aborts one session
-- with an error such as: "deadlock detected"Follow-up Questions
- How does a database choose which transaction to abort as the deadlock victim?
- How can consistent lock ordering prevent deadlocks from occurring at all?
- What is the difference between deadlock detection and deadlock prevention?
- How should application code handle a deadlock error returned by the database?
MCQ Practice
1. What data structure do databases use to detect deadlocks?
The wait-for graph tracks which transactions are waiting on which others; a cycle in it indicates a deadlock.
2. What proves that a deadlock exists in a wait-for graph?
A cycle means each transaction in the loop is waiting on the next, so none can ever proceed without intervention.
3. What does the database typically do once a deadlock cycle is confirmed?
The engine rolls back a chosen victim transaction, releasing its locks so the remaining transaction(s) can complete.
Flash Cards
What is a wait-for graph? — A graph where an edge points from a waiting transaction to the transaction holding the lock it needs.
What confirms a deadlock? — A cycle detected in the wait-for graph.
How is a deadlock resolved? — The engine aborts a chosen victim transaction, releasing its locks so others can proceed.
Detection vs prevention? — Detection finds and breaks cycles after they form; prevention avoids them via ordering or timeouts before they occur.