Pointer Walk

Deadlocks

Two transfers lock the same two accounts in opposite order and wait forever. Locking in one order fixes it.

DatabasesIntermediate8 min read

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.

Opposite lock orderInteractive
Transfer 1
Account A
free
Account B
free
Transfer 2

Two transfers run at the same time between the same two accounts.

  1. Transfer 1 locks A. Transfer 2 locks B

    Both succeed. Nothing is wrong yet.

  2. Transfer 1 asks for B and waits

    B is held by Transfer 2.

  3. Transfer 2 asks for A and waits

    A is held by Transfer 1.

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

python
for attempt in range(3):
    try:
        with transaction():
            transfer(source, target, amount)
        break
    except DeadlockError:
        continue          # the database cancelled us: try again

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

Same lock orderInteractive
Transfer 1
Account A
free
Account B
free
Transfer 2

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.

python
def transfer(source, target, amount):
    first, second = sorted([source, target])     # same order, whoever calls
    lock(first)
    lock(second)
    move_money(source, target, amount)
Opposite lock orderInteractive
Locking
Transfer 1
Account A
free
Account B
free
Transfer 2

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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress