Уровни изоляции: что ваша база разрешает на самом деле

Аномалии, у которых есть имена

В 1999 году Атул Адья в диссертации заменил расплывчатые словесные определения ANSI на явления, определённые через граф зависимостей между транзакциями. Пользоваться его именами удобно по практической причине: они не допускают спора о том, что именно вы наблюдали.

Уровни выстраиваются лестницей: каждый запрещает всё, что запрещает предыдущий, плюс ещё одно.

Вся практическая разница между snapshot isolation и сериализуемостью — одна анти-зависимость. У read skew она одна, и SI его предотвращает. У write skew их две, и SI бессилен.

Write skew: как списать больше, чем есть

Классический случай выглядит невинно. Правило: суммарный остаток по двум счетам клиента не должен уходить в минус. Две транзакции снимают деньги — каждая со своего счёта — и каждая перед списанием проверяет сумму остатков.

-- транзакция A                     -- транзакция B
BEGIN;                              BEGIN;
SELECT sum(balance) FROM accounts   SELECT sum(balance) FROM accounts
 WHERE client = 7;  -- 200           WHERE client = 7;  -- 200
-- 200 - 150 >= 0, можно            -- 200 - 150 >= 0, можно
UPDATE accounts SET balance =       UPDATE accounts SET balance =
  balance - 150 WHERE id = 1;         balance - 150 WHERE id = 2;
COMMIT;                             COMMIT;

Конфликта по записи нет: транзакции трогают разные строки. Каждая читала консистентный снимок и приняла верное решение. Обе фиксируются — и суммарный остаток становится минус сто. Инвариант нарушен, при этом ни одна транзакция по отдельности его не нарушала.

Та же форма встречается вне денег: последний дежурный врач снимает себя со смены одновременно с коллегой; два менеджера резервируют последний слот на складе; две операции присваивают один и тот же номер документу. Везде проверяется одно, а изменяется другое — и SI такую пару пропускает по построению.

Что делает serializable и сколько он стоит

У дыры в snapshot isolation есть форма: любой цикл, который SI пропускает, содержит две подряд идущие анти-зависимости. Значит, достаточно следить за транзакцией, у которой есть и входящая, и исходящая, — она называется опорной, — и не дать ей зафиксироваться.

Это и есть SSI Кэхилла, Рёма и Фекете (SIGMOD 2008) — алгоритм, который реализован в PostgreSQL под именем SERIALIZABLE. Проверка намеренно консервативна: она отклоняет и часть транзакций, которые на самом деле были сериализуемы. Платой оказывается пропускная способность, а не корректность.

Проверить, а не поверить

Чтобы найти аномалию, нужен граф зависимостей: рёбра «запись после записи», «чтение после записи» и «запись после чтения» между транзакциями. Дальше ищутся циклы, и по их составу явление называется по имени.

Одна трудность делает наивный подход бесполезным. Чтобы провести ребро между двумя записями, нужно знать, какая была раньше, — а из истории над обычными значениями это невосстановимо: две записи числа 5 неотличимы. Спросить порядок у самой базы значит поверить подсудимому на слово.

Выход придуман в Elle (Kingsbury, Alvaro, VLDB 2020): значения делают накапливающимися списками, и каждая запись добавляет уникальный элемент. Тогда одно-единственное чтение [a, b, c] само по себе утверждает, что a было раньше b, а b раньше c. Порядок версий восстанавливается из наблюдений, а не берётся из внутренностей базы — и база, которая солгала бы о собственном порядке, оказывается уличена, а не выслушана.

Дальше — техника: компоненты сильной связности по Тарьяну, а внутри каждой поиск в ширину, который находит кратчайший цикл. Это не педантизм: «цикл среди сорока одной транзакции» — не отчёт об ошибке, а две транзакции с выписанными рёбрами — отчёт.

Лестница: проверка в обе стороны

Дальше начинается то, ради чего всё и затевалось. Каждый уровень проверяется двумя утверждениями сразу.

• Соблюдает. На сотнях расписаний из сида уровень ни разу не произвёл аномалию, которую обязан предотвращать.
• Не строже, чем заявлено. Существует расписание, на котором он производит ровно то, что предотвращает следующая ступень.

read-uncommitted     соблюдает на 150 расписаниях   допускает G1b на сиде 0
read-committed       соблюдает на 150 расписаниях   допускает G-single на сиде 1
snapshot-isolation   соблюдает на 150 расписаниях   допускает G2-item на сиде 25
serializable         соблюдает на 150 расписаниях   не допускает ничего, фиксирует 51%

Вторая половина важнее первой. Соблюдение само по себе не доказывает почти ничего: движок, отклоняющий каждую транзакцию, был бы «чист» на всех уровнях, а проверка, которая ничего не находит, с ним бы согласилась. Требование производить запрещённое следующей ступенью закрывает эту дыру — и заодно проверяет саму проверку: чекер, не умеющий найти write skew под snapshot isolation, ничем не подкрепил бы и своё оправдание serializable.

Последняя строка — из той же логики. На конкурентной нагрузке serializable фиксирует 51% транзакций, и это утверждается тестом, а не печатается для справки: оправдание, купленное отказом от всех транзакций, ничего не стоит.

Что с этим делать в приложении

Поднимать всё до SERIALIZABLE — не единственный ответ и часто не лучший. Практических путей три, и они комбинируются.

Отдельно стоит помнить, что повтор транзакции и повтор запроса — разные вещи. Клиентский ретрай без ключа идемпотентности создаёт вторую операцию, и никакой уровень изоляции от этого не спасёт; про это — отдельный разбор про идемпотентность платежей.

Чего этот метод не умеет

• Нет предикатных анти-зависимостей. Полное G2 требует предикатных чтений вида SELECT … WHERE; в таком наборе операций их нет, выводить их не из чего, и заявлять проверку G2 значило бы обещать больше, чем показано. Проверяется только G2-item.
• Прохождение — не доказательство. Сотни расписаний из пространства, которое несопоставимо больше. Хороший фаззинг, не теорема; TLA+-спецификации SSI доказывают то, чего выборка доказать не может.
• Чекер полный не на всём. Он находит кратчайший цикл через каждую вершину компоненты, а не перечисляет все циклы: для таких историй этого достаточно, но обещать исчерпывающий перебор было бы неправдой.
• Это не база данных. Ни долговечности, ни восстановления, ни индексов, ни сборки старых версий: движок изоляции и ничего сверх того.

Что спросить у себя и у подрядчика

Эти вопросы мы задаём себе на проектах, где цена ошибки в данных выше цены отказа: финансовые системы, учёт и складские остатки, CRM и ERP. Остальные технические разборы — в рубрике «Инженерия».