Build a lock manager and deadlock detector

The queues of transactions waiting on each other, drawn next to the engine’s split-second latches. This lesson builds the first half: the table that says who holds what, who is waiting, and who has to give up.

Before you start. Locks, Latches & Transactions taught strict two-phase locking, the wait-for graph and a forced deadlock on a real Postgres. The Database That Won't Answer showed a lock queue freezing an app. Transactions (MVCC) built snapshots, which avoid locks for readers, and said row locks were not built. This lesson builds them. A graph with a cycle is the only idea from Graphs (BFS, DFS, Dijkstra, topological sort) you need. The code is in teaching/code/database-internals/04-locks.

The idea in 30 seconds

A lock manager keeps, per lockable thing, the holders and a first-in first-out queue of waiters; two requests are compatible only if both are shared.
A transaction waits for the holders it conflicts with and for the earlier requests it conflicts with; those waits form a graph, and a deadlock is a cycle in it.
The detector only has to check for a cycle through the transaction that just began waiting, because that is the only edge that is new.
Breaking a deadlock means aborting one transaction in the cycle and releasing its locks; which one is a policy, and the program chooses the youngest.
A first-in first-out queue stops a stream of readers from starving a waiting writer, and makes a late reader wait behind it.
Two transactions that each hold a shared lock and ask to upgrade deadlock on a single row; asking for the exclusive lock first avoids it.

Read the story · Skip to the numbers