Deadlock Detection

Before a request parks, look for a cycle in the wait-for graph that it would close; if there is one, roll back the youngest transaction on it with 01804 and let the others go on. Print the graph with lock graph.

Not run yet · 5 tests

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.

Drawing the diagram…

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:

droid session

>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.

droid session

>@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.

The algorithm in words

Is there a cycle?

Depth-first search over who waits for whom.

1.Draw an edge from a waiting session to every session it waits for: holders of a conflicting mode, and waiters ahead of it with one.
2.Before parking a new request, add its edges as if it waited.
3.Search from each session the requester would wait for, following edges, marking sessions seen. Reaching the requester again means a cycle.
4.Collect every session on a cycle through the requester, the requester included.

Choosing and ending the victim

The youngest gives way.

1.The victim is the collected session whose transaction has the largest id.
2.Print 01804 under the victim's tag: the requester's line, or the line the victim is parked with.
3.Roll back the victim's whole transaction as ROLLBACK does, release all its locks, and drop its parked statement.
4.If the victim was not the requester, the requester asks again: granted, or waiting, checked again.
5.Then resume parked statements as any release does.

Output contract for this stage

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

Input	Output
a request that would close a cycle	`[ERROR:01804] ...` under the victim's tag, then the lines of statements that could now run
`lock graph`	`[LOCKS] <n> -> <m>` per edge, sorted by `n`, then `m`, ascending; `[LOCKS] no waits` with none
`lock graph x`	`[ERROR:00104] ...`

What you should see when done

shell

$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.

Loading starter code…

No run yet

5 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.