Deadlock Detection

Why this stage exists

Two transfers run in opposite directions. Session 1 takes 10 from account 1, then asks for account 2. Session 2 has already taken 20 from account 2, and now asks for account 1. Each waits for a lock the other holds, and neither will ever release it, because releasing happens at the end of a transaction and neither can reach its end.

Waiting is now built, so this can happen, and nothing in the program would ever end it. A deadlock is a cycle of waits, and the only way out is to end one of the transactions on it.

Finding the cycle

Draw an arrow from each waiting session to each session it waits for: the wait-for graph. A deadlock is exactly a cycle in it. Arrows only appear when a request starts to wait, so that is the only moment a new cycle can form, and the only moment to look. Before parking a request, add its arrows and search, depth first, from each session it would wait for: if a path leads back to the requester, waiting would close a cycle.

lock graph prints the arrows:

>lock graph
[LOCKS] 2 -> 1
[LOCKS] 3 -> 1
[LOCKS] 3 -> 2

Here session 3 waits for session 1, which holds the row, and also for session 2, which waits ahead of it. No arrow leads back to anyone, so there is no deadlock: just a queue.

Choosing the victim

Ending any transaction on the cycle breaks it. Which one is a policy, and it must be deterministic, or no test could say what should happen. This engine picks the youngest transaction on the cycle, the one with the largest id, whichever session's request closed it. The young one has usually done the least work, and an old transaction is never starved by being chosen again and again.

The victim's session prints 01804, and its whole transaction is rolled back, as ROLLBACK does: every change undone, every lock released, its waiting statement dropped. Its session is then IDLE and may begin again. The others carry on: the statement that was waiting for the victim's locks gets them.

>@1 update acct set bal = bal + 10 where id = 2;
@1| [LOCK] session 1 waits for session 2 on acct:2
>@2 update acct set bal = bal + 20 where id = 1;
@2| [ERROR:01804] deadlock: transaction 6 was rolled back
@1| Update statement executed successfully (1 rows)
@1| [EXEC] rows_examined=1

There are no timeouts. A timeout guesses that a long wait is a deadlock, and its outcome depends on how fast the machine is: it cannot be tested, and the graph already knows for sure.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 86.

What you should see when done

$droid --db d.db
Welcome to droid!
>create table acct (id int primary key, bal int);
Create table statement executed successfully
>insert into acct (id, bal) values (1, 100);
Insert statement executed successfully (1 rows)
>insert into acct (id, bal) values (2, 100);
Insert statement executed successfully (1 rows)
>@1 begin;
@1| Begin statement executed successfully
>@1 update acct set bal = bal - 10 where id = 1;
@1| Update statement executed successfully (1 rows)
@1| [EXEC] rows_examined=1
>@2 begin;
@2| Begin statement executed successfully
>@2 update acct set bal = bal - 20 where id = 2;
@2| Update statement executed successfully (1 rows)
@2| [EXEC] rows_examined=1
>@1 update acct set bal = bal + 10 where id = 2;
@1| [LOCK] session 1 waits for session 2 on acct:2
>@2 update acct set bal = bal + 20 where id = 1;
@2| [ERROR:01804] deadlock: transaction 5 was rolled back
@1| Update statement executed successfully (1 rows)
@1| [EXEC] rows_examined=1
>@1 commit;
@1| Commit statement executed successfully
>.exit
exiting.. good bye!

Common bugs in this stage

• Choosing the requester as the victim. The rule is the youngest on the cycle, whoever closed it.
• Rolling back only the last statement. The victim's locks stay held, and the cycle stays.
• Forgetting edges to waiters ahead. A request queued behind another can be part of a cycle too.
• Printing the [LOCK] line for a request that is a deadlock. It never waits.
• Resuming before the requester asks again, when the victim was someone else.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: sessions are at most 1000, so the graph is an adjacency list in a fixed array; a recursive search with a seen array is enough.
• C++: std::map<int, std::set<int>> for edges gives lock graph its order for free.
• Rust: a BTreeMap<u32, BTreeSet<u32>> for edges, and an explicit stack for the search.
• Zig: build the edges into an AutoArrayHashMap(u32, ArrayList(u32)) on demand; the graph is small and rebuilt at each check.