Deadlock in databases
Locking keeps writers from clobbering each other, but it can create a new kind of stuck. Picture two transactions, each already holding a lock, and each now waiting for the lock the OTHER one holds. Neither will give up what it has until it gets what it wants — so neither ever moves. They're frozen forever in a 'deadly embrace.' This is a deadlock, and this lesson shows how it forms, how the database SPOTS it, and how it breaks the standoff.
The deadly embrace, concretely
Let's make it real with two rows, A and B, and two transactions running at once. • Transaction 1 locks row A (it got there first). Now it needs row B too, so it asks for B's lock. • Transaction 2 locks row B (it got there first). Now it needs row A too, so it asks for A's lock. But B is held by T2, so T1 has to wait for T2. And A is held by T1, so T2 has to wait for T1. Each is waiting for the other to let go — and neither will let go, because a transaction never releases a lock it holds until it has finished, and it can't finish until it gets the lock it's waiting for. Round and round, forever. That's a deadlock: a perfect circle of waiting where nobody can ever take the first step.
How the database DETECTS it: the wait-for cycle
The database keeps a little map called the wait-for graph: an arrow from every waiting transaction to the transaction it's waiting on. T1 is waiting on T2, so draw T1 → T2. T2 is waiting on T1, so draw T2 → T1. Follow the arrows and you go T1 → T2 → T1 → T2… — a loop. A loop in the wait-for graph is the unmistakable fingerprint of a deadlock: it means a group of transactions are all waiting on each other in a circle, so none can ever proceed. The database periodically checks this graph for cycles. The instant it finds one, it knows: 'these transactions are deadlocked, they will never sort themselves out — I have to step in.'
How the database RESOLVES it: pick a victim
Once a cycle is found, the fix is blunt but effective: the database picks one transaction in the loop to be the VICTIM, and kills it. It aborts that transaction and rolls back all its changes (remember atomicity — rolling back is clean and safe, as if it never ran). Killing the victim makes it release its locks. Now the OTHER transaction can finally grab what it was waiting for and continue. The cycle is broken; the survivor proceeds. The victim isn't lost forever — its application usually just gets a 'deadlock, please retry' message and runs it again, and the second time around the path is usually clear. Databases tend to pick the cheapest victim to roll back — often the one that's done the least work — so the least effort is wasted.
Avoiding deadlocks in the first place
Detect-and-kill works, but the best deadlock is the one that never forms. The simplest habit: always grab locks in the SAME ORDER everywhere. If every transaction that needs both A and B always locks A first, then B, the cycle from the story can't form — whoever gets A first will get B too, and the other just waits politely in line, no embrace. That's why consistent lock ordering is a classic rule of thumb. You can't always arrange it, which is why databases still detect-and-resolve as a safety net. But ordering your locks removes a whole category of deadlocks before they can happen — cheaper than cleaning them up after.
Questions you might have
▸How is a database deadlock different from the deadlock I read about in operating systems?
It's the exact same idea — a circular wait where everyone holds something everyone else needs — just with database row locks instead of OS resources. The mechanics, the wait-for cycle, and the 'break it by force' fix all carry straight over. If you want to SEE the wait-for cycle animate, there's a deadlock animation over in the OS track that shows the loop forming and breaking.
▸Isn't killing a transaction a bit drastic? Can't they just share?
They can't share — that's the whole problem. Each one is holding an exclusive lock and refuses to release it until it finishes, and it can't finish without the other's lock. There's no compromise that lets both proceed; the circle has no give. Sacrificing one is the only way to free the rest, which is why the database does it.
▸What happens to the victim's work — is it just lost?
Its changes are rolled back, so nothing half-done is left behind (atomicity again). The application typically gets a 'deadlock detected, transaction aborted' error and simply retries the whole transaction. The second attempt usually succeeds, because by then the other transaction has finished and released its locks. So the work isn't lost — it's just redone on a clear path.
▸Does MVCC have deadlocks too, or only locking?
Deadlocks are mainly a LOCKING phenomenon — they need two transactions each holding a lock the other wants. Pure MVCC reads don't block, so they don't deadlock. But real databases still use some locks for write-write conflicts, so deadlocks can still appear there. The cleaner the system avoids holding overlapping locks, the rarer they get.
Best read after: Concurrency control