Дедлоки в PostgreSQL и InnoDB: граф ожидания и жертва

Три транзакции держат по строке и ждут друг друга по кругу: ни одна не завершится сама, и через секунду одна из них получает deadlock detected. Зачем PostgreSQL ждёт целую секунду, кого он выбирает и чем это отличается от InnoDB и SQLite — разбор ниже. Обычное ожидание блокировки и диагностику очереди описывает статья про блокировки, здесь механизм цикла; очередь и режимы блокировок разобраны в статье про устройство блокировок.

DBA / 01

Граф ожидания из трёх транзакций и жертва

Каждая транзакция ждёт xid следующей: T2 → T3 → T1 → T2. Первой после замыкания цикла проснулась проверка у T2, поэтому отменили её, хотя цикл замкнула T3. Откатилась одна транзакция, остальные две завершились.

Опыт 1: цикл из трёх транзакций в PostgreSQL

Нужен bash (не zsh): функция s запускает сессию psql, подставляя паузы между командами, и печатает \timing.

docker run -d --name dba-deadlock-detection-pg -e POSTGRES_PASSWORD=pg postgres:18
P() { docker exec -i dba-deadlock-detection-pg psql -U postgres -Atq; }
s() { n=$1; shift; { echo '\timing on'; echo "SELECT '$n pid '||pg_backend_pid();"
  while [ $# -gt 0 ]; do sleep $1; echo "$2"; shift 2; done; } | P 2>&1 | sed "s/^/$n: /"; }
P <<'X'
CREATE TABLE t (id int PRIMARY KEY, v int);
INSERT INTO t SELECT g, 0 FROM generate_series(1,3) g;
SHOW deadlock_timeout;
SELECT version();
X

1s
PostgreSQL 18.6 (Debian 18.6-1.pgdg13+2) on x86_64-pc-linux-gnu, compiled by gcc (Debian 14.2.0-19) 14.2.0, 64-bit

Каждая сессия берёт свою строку, потом просит следующую. Паузы суммируются: T2 просит строку 3 на 0,9 с, T1 строку 2 на 1,3 с, T3 строку 1 на 1,5 с — цикл замыкает T3.

s T1 0 "BEGIN;" 0 "UPDATE t SET v=1 WHERE id=1;" 1.3 "UPDATE t SET v=1 WHERE id=2;" 2.5 "COMMIT;" &
s T2 0.3 "BEGIN;" 0 "UPDATE t SET v=2 WHERE id=2;" 0.6 "UPDATE t SET v=2 WHERE id=3;" 2.5 "COMMIT;" &
s T3 0.6 "BEGIN;" 0 "UPDATE t SET v=3 WHERE id=3;" 0.9 "UPDATE t SET v=3 WHERE id=1;" 2.5 "COMMIT;" &
wait

Идентификаторы сессий: T1 pid 110, T2 pid 111, T3 pid 112. Ошибку получила только T2:

T2: ERROR:  deadlock detected
T2: DETAIL:  Process 111 waits for ShareLock on transaction 768; blocked by process 112.
T2: Process 112 waits for ShareLock on transaction 766; blocked by process 110.
T2: Process 110 waits for ShareLock on transaction 767; blocked by process 111.
T2: HINT:  See server log for query details.
T2: CONTEXT:  while updating tuple (0,3) in relation "t"
T2: Time: 1000.330 ms (00:01.000)

Оставшиеся две UPDATE ждали: у T1 — 600,640 мс (до отмены T2), у T3 — 2310,639 мс (до коммита T1). Текст DETAIL — это и есть граф ожидания, записанный по рёбрам: «процесс ждёт xid, который держит процесс». В журнале сервера к нему добавлены запросы каждого участника (docker logs dba-deadlock-detection-pg):

Process 111: UPDATE t SET v=2 WHERE id=3;
Process 112: UPDATE t SET v=3 WHERE id=1;
Process 110: UPDATE t SET v=1 WHERE id=2;

Ожидание до момента отмены равнялось deadlock_timeout: 1000,330 мс — секунда таймера плюс доли миллисекунды на проверку.

Опыт 2: жертва определяется таймером

В опыте 1 отменили T2, которая начала ждать первой, а не T3, замкнувшую цикл. Проверка: два участника, у позже ждущей транзакции A таймер короче. Сессия B берёт строку 2 и на 0,3 с просит строку 1, сессия A берёт строку 1 и на 0,6 с просит строку 2 — цикл замыкает A.

run() { s A 0 "$1" 0 "BEGIN;" 0 "UPDATE t SET v=1 WHERE id=1;" 0.6 "UPDATE t SET v=1 WHERE id=2;" 1.5 "COMMIT;" &
        s B 0.1 "BEGIN;" 0 "UPDATE t SET v=2 WHERE id=2;" 0.2 "UPDATE t SET v=2 WHERE id=1;" 1.5 "COMMIT;" &
        wait; }
run "SHOW deadlock_timeout;"                 # оба 1 с
run "SET deadlock_timeout = '100ms';"        # короткий таймер только у A

Первый запуск (A — pid 127, B — pid 126): ошибка у B, которая ждёт дольше, а A после этого дождалась строки за 700,049 мс.

B: ERROR:  deadlock detected
B: Time: 1000.371 ms (00:01.000)
A: Time: 700.049 ms

Второй запуск (A — pid 140, B — pid 141): ошибка у A, хотя она ждала меньше всех и замкнула цикл сама. B получила строку через 401,127 мс после начала ожидания.

A: ERROR:  deadlock detected
A: Time: 100.375 ms
B: Time: 401.127 ms

Жертву никто не оценивает по возрасту, объёму работы или приоритету: отменяют процесс, чей таймер первым сработал после замыкания цикла. Укороченный deadlock_timeout ускорил обнаружение (100,375 мс против 1000,371 мс), но выбрал другого участника.

Что говорит код PostgreSQL

Ожидающий процесс взводит таймер на DeadlockTimeout (proc.c, ProcSleep, L1400). Когда таймер срабатывает, CheckDeadLock берёт все партиции таблицы блокировок и вызывает DeadLockCheck(MyProc): MyProc — процесс, который проверяет сам себя. Описание в deadlock.c, DeadLockCheck (L207-L210):

 * This code looks for deadlocks involving the given process.  If any
 * are found, it tries to rearrange lock wait queues to resolve the
 * deadlock.  If resolution is impossible, return DS_HARD_DEADLOCK ---
 * the caller is then expected to abort the given proc's transaction.

Поиск цикла идёт в FindLockCycle по рёбрам «ждёт — держит»; если цикл можно разорвать перестановкой очереди ожидания, сервер переставляет очередь и ошибки нет. Иначе возвращается DS_HARD_DEADLOCK, и в CheckDeadLock происходит то, что видно в опыте (L1864-L1874):

		 * Get this process out of wait state. (Note: we could do this more
		 * efficiently by relying on lockAwaited, but use this coding to
		 * preserve the flexibility to kill some other transaction than the
		 * one detecting the deadlock.)
		 *
		 * RemoveFromWaitQueue sets MyProc->waitStatus to
		 * PROC_WAIT_STATUS_ERROR, so ProcSleep will report an error after we
		 * return from the signal handler.
		 */
		Assert(MyProc->waitLock != NULL);
		RemoveFromWaitQueue(MyProc, LockTagHashCode(&(MyProc->waitLock->tag)));

Автор кода оставил возможность убить другую транзакцию, но не воспользовался ей: жертвой всегда становится проверявший.

Опыт 3: InnoDB откатывает более лёгкую транзакцию

Строки и записи блокирует InnoDB по-своему, подробности в статье про undo и блокировки InnoDB; здесь важно только, что undo_no и число структур блокировок определяют вес.

docker run -d --name dba-deadlock-detection-my -e MYSQL_ROOT_PASSWORD=pg mysql:8.4
M() { docker exec -i dba-deadlock-detection-my mysql -uroot -ppg -t 2>/dev/null; }
m() { n=$1; shift; { echo "SELECT '$n' AS who, CONNECTION_ID() AS conn;"
  while [ $# -gt 0 ]; do sleep $1; echo "$2"; shift 2; done; } \
  | docker exec -i dba-deadlock-detection-my mysql -uroot -ppg -vvv --force 2>&1 | sed "s/^/$n: /"; }
M <<'X'
CREATE DATABASE d; CREATE TABLE d.t (id int PRIMARY KEY, v int) ENGINE=InnoDB;
INSERT INTO d.t VALUES (1,0),(2,0),(3,0),(4,0);
SELECT @@version, @@innodb_deadlock_detect, @@innodb_lock_wait_timeout;
X

+-----------+--------------------------+----------------------------+
| @@version | @@innodb_deadlock_detect | @@innodb_lock_wait_timeout |
+-----------+--------------------------+----------------------------+
| 8.4.13    |                        1 |                         50 |
+-----------+--------------------------+----------------------------+

Сценарий сложнее: A меняет три строки и позже замыкает цикл, а B меняет одну строку и ждёт A. Если бы жертвой становился замкнувший цикл, откатилась бы A.

m B 0 "USE d;" 0 "BEGIN;" 0 "UPDATE t SET v=v+1 WHERE id=4;" 1 "SELECT NOW(3) AS b_wait_start;" \
      0 "UPDATE t SET v=v+1 WHERE id=1;" 0 "SELECT NOW(3) AS b_after;" 2 "COMMIT;" &
m A 0.2 "USE d;" 0 "BEGIN;" 0 "UPDATE t SET v=v+1 WHERE id<=3;" 1.5 "SELECT NOW(3) AS a_request;" \
      0 "UPDATE t SET v=v+1 WHERE id=4;" 1 "COMMIT;" &
wait

B: | b_wait_start            | 2026-10-27 20:35:01.362 |
A: | a_request               | 2026-10-27 20:35:02.061 |
B: ERROR 1213 (40001) at line 6: Deadlock found when trying to get lock; try restarting transaction
B: | b_after                 | 2026-10-27 20:35:02.064 |

B ждала 0,699 с и получила ошибку через 3 мс после запроса A, не через секунду. Таблица после опыта: v = 1 во всех четырёх строках — применились три обновления A и четвёртое, которое A получила после отката B. Что InnoDB посчитал, показывает SHOW ENGINE INNODB STATUS\G, раздел LATEST DETECTED DEADLOCK:

*** (1) TRANSACTION:
TRANSACTION 1848, ACTIVE 2 sec starting index read
LOCK WAIT 3 lock struct(s), heap size 1128, 2 row lock(s), undo log entries 1
MySQL thread id 17 ... UPDATE t SET v=v+1 WHERE id=1
*** (2) TRANSACTION:
TRANSACTION 1849, ACTIVE 2 sec starting index read
LOCK WAIT 3 lock struct(s), heap size 1128, 4 row lock(s), undo log entries 3
MySQL thread id 16 ... UPDATE t SET v=v+1 WHERE id=4
*** WE ROLL BACK TRANSACTION (1)

Транзакция (1) — B (поток 17): одна undo-запись и три структуры блокировок. Транзакция (2) — A (поток 16): три undo-записи и те же три структуры. Вес TRX_WEIGHT равен числу undo-записей плюс число структур блокировок: 1 + 3 = 4 у B, 3 + 3 = 6 у A. Откатилась лёгкая B.

Что говорит код InnoDB

В 8.4 нет вызова проверки из самого ожидающего потока. Фоновый lock_wait_timeout_thread просыпается по запросу lock_wait_request_check_for_cycles и раз в секунду (lock0wait.cc L1432-L1456), строит граф ожидания и, если включён innodb_deadlock_detect, ищет циклы. Победителя выбирает lock_wait_choose_victim (L949-L953):

    if (trx_weight_ge(chosen_victim, trx)) {
      /* The joining transaction is 'smaller',
      choose it as the victim and roll it back. */
      chosen_victim = trx;
    }

Цикл перебирается так, что последним идёт замкнувший его участник, а при равных весах выбирается он же. Вес определяется TRX_WEIGHT в trx0trx.h:

static inline uint64_t TRX_WEIGHT(const trx_t *t) {
  return t->undo_no + UT_LIST_GET_LEN(t->lock.trx_locks);
}

Это совпадает с цифрами из INNODB STATUS. Кроме того, транзакция, менявшая нетранзакционные таблицы, считается тяжелее любой другой (trx_weight_ge в trx0trx.cc).

Опыт 4: SQLite не ждёт там, где есть цикл

В SQLite один писатель, и отдельного детектора нет. Дедлок «обе читают, обе хотят писать» он предотвращает отказом на месте:

import sqlite3, time
a = sqlite3.connect('s.db', timeout=5, isolation_level=None)
b = sqlite3.connect('s.db', timeout=5, isolation_level=None)
a.execute('CREATE TABLE t(id INTEGER PRIMARY KEY, v INT)'); a.execute('INSERT INTO t VALUES (1,0),(2,0)')
for c in (a, b): c.execute('BEGIN'); c.execute('SELECT * FROM t').fetchall()
a.execute('UPDATE t SET v=1 WHERE id=1')
t = time.time()
try: b.execute('UPDATE t SET v=2 WHERE id=2')
except sqlite3.OperationalError as e: print(e, 'after %.3f s' % (time.time() - t))
t = time.time()
try: a.execute('COMMIT')
except sqlite3.OperationalError as e: print('A commit:', e, 'after %.3f s' % (time.time() - t))

database is locked after 0.000 s
A commit: database is locked after 5.004 s

У обоих соединений timeout=5 секунд. B прочитала таблицу и хочет писать, а писатель A уже есть: B получает SQLITE_BUSY мгновенно, не дожидаясь таймаута. A ждёт чтения B на COMMIT целых 5 с и тоже получает отказ, потому что B не завершила транзакцию. Причина — в комментарии ядра (btree.c L3576-L3587): если соединение уже держит чтение, обработчик ожидания не вызывается, чтобы один из двоих «уступил». Уступить должно приложение: откатить транзакцию и повторить.

Профилактика: один порядок строк

Тот же сценарий из двух сессий в PostgreSQL, но обе берут строки в порядке 1, затем 2:

s A 0 "BEGIN;" 0 "UPDATE t SET v=v+10 WHERE id=1;" 0.6 "UPDATE t SET v=v+10 WHERE id=2;" 0.2 "COMMIT;" &
s B 0.1 "BEGIN;" 0 "UPDATE t SET v=v+20 WHERE id=1;" 0.2 "UPDATE t SET v=v+20 WHERE id=2;" 0 "COMMIT;" &
wait

B: Time: 703.767 ms

Ошибок в выводе нет: B ждёт строку 1 703,767 мс, пока A не зафиксируется, и проходит. Цикл невозможен, если все пути приложения берут строки в одном порядке, например по возрастанию первичного ключа.

Что из этого следует

Ошибка 40P01 в PostgreSQL (\set VERBOSITY verbose в psql печатает ERROR: 40P01: deadlock detected) и 1213 в MySQL — штатная. Транзакция откатилась целиком, её надо повторить с начала. Остальные участники цикла продолжили работу (опыт 1: T1 и T3 завершились).
Секунда ожидания — цена проверки. Детектор берёт все партиции таблицы блокировок, поэтому PostgreSQL запускает его только по таймеру. В InnoDB проверка шла фоновым потоком, и ошибка пришла за 3 мс (опыт 3).
Жертву не выбрать. В PostgreSQL ею станет процесс с первым сработавшим таймером (опыт 2), в InnoDB — более лёгкая транзакция (опыт 3). Расчёт на конкретного пострадавшего ломается на следующей версии.
Порядок обновления строк убирает класс ошибок. В опыте с одним порядком цикла не было, только ожидание.
В SQLite таймаут не спасает апгрейд чтения до записи (опыт 4). Транзакцию, которая собирается писать, начинай с BEGIN IMMEDIATE: при занятом писателе (второе соединение тоже начало с BEGIN IMMEDIATE и держит запись) она честно ждёт таймаут (при timeout=1 — database is locked after 1.002 s), а не падает мгновенно.

Чек-лист

Найди путь, который меняет несколько строк, и сделай порядок захвата строк одинаковым (по ключу).
Оберни транзакцию в повтор по SQLSTATE 40P01 (PostgreSQL) и 40001 (MySQL, код 1213); число попыток ограничь, в SQLite повторяй на SQLITE_BUSY.
Не ставь deadlock_timeout короче 1 с без причины: проверку запускает каждая сессия, прождавшая дольше таймера, и каждая проверка берёт все партиции таблицы блокировок; а разный таймер у разных сессий меняет жертву (опыт 2).
В MySQL смотри LATEST DETECTED DEADLOCK, в PostgreSQL — DETAIL в журнале ошибок: это готовый граф ожидания.
Убери контейнеры: docker rm -f dba-deadlock-detection-pg dba-deadlock-detection-my.

Дедлоки: граф ожидания, deadlock_timeout и выбор жертвы в PostgreSQL и InnoDB