Waiting forever
To change a row safely, a transaction first locks it. While it holds the lock, any other transaction that wants to change the same row has to wait. When the first one commits, the lock is released and the next in line goes ahead.
Usually the wait is a few milliseconds. But there is one arrangement in which the wait never ends.
Two transfers, opposite directions
Two money transfers start at almost the same moment:
- Transfer 1 moves money from account A to account B.
- Transfer 2 moves money from account B to account A.
Each one locks the account it takes money from, then the account it pays into.
Two transfers run at the same time between the same two accounts.
Transfer 1 locks A. Transfer 2 locks B
Both succeed. Nothing is wrong yet.
Transfer 1 asks for B and waits
B is held by Transfer 2.
Transfer 2 asks for A and waits
A is held by Transfer 1.
Neither can ever continue
Each will release its lock only after getting the other's. That is a deadlock.
Notice what is not happening. Nothing is slow. Nothing has crashed. Every line of both transfers is correct. The problem exists only in how the two overlap in time, which is why deadlocks appear under load and almost never in testing.
What the database does about it
Databases watch for this. When they find a circle of transactions each waiting for the next, they pick one, cancel it, and return an error to that application. Its locks are released and the others carry on.
So in practice a deadlock is not a permanent freeze. It is an error on one transaction, a short stall for the others, and work that must be done again.
for attempt in range(3):
try:
with transaction():
transfer(source, target, amount)
break
except DeadlockError:
continue # the database cancelled us: try againPreventing it: one order for everyone
A deadlock needs a circle: 1 waits for 2 while 2 waits for 1. A circle is only possible if two transactions take the same locks in different orders.
So agree on an order and make everyone follow it. For example: always lock the account with the smaller id first.
Two transfers run at the same time between the same two accounts.
Transfer 2 moves money from B to A, but it still locks A first. It has to wait for Transfer 1, and that is fine: while it waits, it holds nothing, so it cannot be blocking anybody. The circle cannot form.
def transfer(source, target, amount):
first, second = sorted([source, target]) # same order, whoever calls
lock(first)
lock(second)
move_money(source, target, amount)Two transfers run at the same time between the same two accounts.
Other ways to reduce them
- Keep transactions short. The less time locks are held, the smaller the window for a collision. Never wait for a user or a slow network call while holding locks.
- Lock everything you need at the start, in one statement, instead of gradually.
- Touch fewer rows. A statement that updates a million rows holds a million locks.
- Set a lock timeout, so a stuck transaction gives up instead of piling up behind others.
Key takeaways
- A deadlock is two or more transactions each waiting for a lock that another one holds.
- No single transaction is wrong. The problem is how they overlap.
- Databases detect deadlocks and cancel one transaction, which must then be retried.
- Taking locks in the same order everywhere makes a circle impossible.
- Short transactions and fewer locks make deadlocks rarer.