Take locks in one written order

How to do it

Two transfers between the same two accounts in opposite directions each take one lock and wait forever for the other. Taking locks in one global order makes that impossible. The same holds for database rows, so lock rows with SELECT ... FOR UPDATE sorted by ID. Prefer one lock, or none, as Guard state that concurrent code shares says. Prefer a conditional write when conflicts are rare, as Make conditional writes says. Locks across servers follow Keep locks and counters in a shared store. Put the lock map in a comment above the lock fields, since the code cannot show it.

Examples

Go example

func (b *Bank) Transfer(from, to *Account, amount Cents) error {
	first, second := from, to
	if to.ID < from.ID {
		first, second = to, from
	}
	first.mu.Lock()
	defer first.mu.Unlock()
	second.mu.Lock()
	defer second.mu.Unlock()
	return moveFunds(from, to, amount)
}

Python example

def transfer(conn, from_id: int, to_id: int, amount: int) -> None:
    with conn.transaction():
        conn.execute(
            "SELECT id FROM accounts WHERE id = ANY(%s) ORDER BY id FOR UPDATE",
            ([from_id, to_id],),
        )
        conn.execute("UPDATE accounts SET balance = balance - %s WHERE id = %s", (amount, from_id))
        conn.execute("UPDATE accounts SET balance = balance + %s WHERE id = %s", (amount, to_id))

How to check

A stress test runs 1,000 transfers in both directions between two accounts at once. It finishes within 10 seconds and the total balance is unchanged. The database reports 0 deadlocks during the test.

Sources

• CWE-833 Deadlock

Related rules

• ARC-40 Guard state that concurrent code shares in Clean code and architecture
• DAT-16 Make conditional writes in Data and databases
• SCL-8 Keep locks and counters in a shared store in Scaling