Сериализуемость транзакций

Сериализуемость транзакций — это свойство системы управления базами данных (СУБД) или распределённой системы обработки транзакций, гарантирующее, что результат параллельного выполнения набора транзакций эквивалентен результату некоторого последовательного (сериального) выполнения тех же транзакций. Иными словами, при сериализуемом расписании (плане выполнения) итоговое состояние базы данных и порядок чтения/записи данных оказываются такими же, как если бы транзакции выполнялись одна за другой, без перекрытия во времени. Это фундаментальное понятие теории транзакций, обеспечивающее согласованность данных в многопользовательских системах.

История и контекст

Понятие сериализуемости возникло в 1970-х годах в рамках развития реляционных баз данных и теории транзакций. Основополагающие работы были выполнены Джимом Греем, Андреасом Рейтером и другими исследователями. В 1983 году Фил Бернштейн, Вассо Хадзилакос и Натан Гудман опубликовали классическую работу «Concurrency Control and Recovery in Database Systems», где формализовали критерии сериализуемости и алгоритмы управления параллельным доступом. С развитием распределённых систем и NoSQL-баз данных понятие сериализуемости было адаптировано для распределённых транзакций (например, в протоколах типа Snapshot Isolation и Serializable Snapshot Isolation).

Основные понятия

Транзакция

Транзакция — это логически завершённая единица работы с базой данных, обладающая свойствами ACID (атомарность, согласованность, изоляция, долговечность). В контексте сериализуемости важнейшим является свойство изоляции, которое определяет, как параллельные транзакции видят изменения друг друга.

Расписание (Schedule)

Расписание — это последовательность операций (чтение, запись, фиксация, откат) из нескольких транзакций, упорядоченная по времени их выполнения. Расписание называется сериальным, если операции из разных транзакций не перемежаются (транзакции выполняются строго одна за другой). Сериализуемое расписание — это расписание, которое эквивалентно по результату некоторому сериальному расписанию.

Конфликт операций

Две операции конфликтуют, если они принадлежат разным транзакциям, обращаются к одному и тому же объекту данных и хотя бы одна из них является записью. Конфликты бывают трёх типов:

• Чтение-запись (RW): одна транзакция читает, другая пишет.
• Запись-чтение (WR): одна пишет, другая читает.
• Запись-запись (WW): обе пишут.

Сериализуемость гарантирует, что порядок конфликтующих операций в расписании соответствует порядку в некотором сериальном расписании.

Критерии сериализуемости

Конфликтная сериализуемость (Conflict Serializability)

Наиболее распространённый критерий. Расписание является конфликтно-сериализуемым, если его можно преобразовать в сериальное расписание путём перестановки неконфликтующих операций. Проверка осуществляется с помощью графа конфликтов (precedence graph):

• Вершины — транзакции.
• Направленное ребро от T1 к T2, если существует конфликтующая операция, где T1 выполняется раньше T2.

Расписание сериализуемо тогда и только тогда, когда граф конфликтов является ациклическим.

Просмотровая сериализуемость (View Serializability)

Более слабый критерий. Расписание является просмотрово-сериализуемым, если оно эквивалентно сериальному расписанию по набору читаемых значений (каждая транзакция видит те же данные, что и в некотором сериальном расписании). Просмотровая сериализуемость не требует строгого порядка конфликтующих операций, но её проверка является NP-полной задачей, поэтому на практике обычно используется конфликтная сериализуемость.

Алгоритмы обеспечения сериализуемости

Блокировки (Locking)

Классический подход, реализованный в большинстве реляционных СУБД (например, PostgreSQL, Oracle, MySQL с InnoDB).

• Двухфазная блокировка (2PL, Two-Phase Locking): транзакция сначала получает все необходимые блокировки (фаза расширения), затем освобождает их (фаза сжатия). Строгая двухфазная блокировка (Strict 2PL) удерживает все блокировки до фиксации или отката, что предотвращает каскадные откаты.
• Блокировки на уровне строк, страниц или таблиц — в зависимости от СУБД.

Оптимистическое управление (Optimistic Concurrency Control, OCC)

Предполагает, что конфликты редки. Транзакция выполняется без блокировок, а перед фиксацией проверяется, не было ли конфликтов с другими транзакциями. При обнаружении конфликта транзакция откатывается и повторяется. Используется в системах с низкой конкуренцией (например, в некоторых реализациях MongoDB).

Многоверсионность (MVCC, Multi-Version Concurrency Control)

Каждая транзакция видит «снимок» данных на момент своего начала. Изменения других транзакций становятся видны только после их фиксации. MVCC позволяет избежать многих блокировок, но не гарантирует сериализуемость по умолчанию (например, в PostgreSQL уровень изоляции Read Committed не является сериализуемым). Для достижения сериализуемости используется Serializable Snapshot Isolation (SSI), которая выявляет конфликты на основе графа зависимостей.

Временные метки (Timestamp Ordering)

Каждой транзакции присваивается временная метка. Операции выполняются в порядке возрастания меток. Если конфликт нарушает порядок, транзакция откатывается. Используется в распределённых системах (например, в Google Spanner с TrueTime).

Уровни изоляции транзакций

Стандарт SQL определяет четыре уровня изоляции, из которых только Serializable гарантирует сериализуемость. Остальные уровни (Read Uncommitted, Read Committed, Repeatable Read) допускают различные аномалии (грязное чтение, неповторяющееся чтение, фантомы). В реальных системах уровень Serializable часто реализуется через SSI или строгую двухфазную блокировку, что может снижать производительность.

Применение и ограничения

Где требуется сериализуемость

• Финансовые системы: переводы средств, расчёты остатков — любая ошибка согласованности недопустима.
• Бронирование: авиабилеты, отели — требуется избегать двойного бронирования.
• Системы управления запасами: точный учёт количества товаров.

Компромиссы

Сериализуемость обеспечивает максимальную согласованность, но снижает пропускную способность системы из-за блокировок или откатов. В высоконагруженных системах (например, социальные сети, аналитика) часто используют более слабые уровни изоляции (Read Committed, Snapshot Isolation) в обмен на производительность. В распределённых системах сериализуемость сложнее реализовать из-за сетевых задержек и частичных отказов.

Примеры аномалий при отсутствии сериализуемости

• Потерянное обновление: две транзакции одновременно читают и записывают одно значение, одна из записей теряется.
• Грязное чтение: транзакция читает данные, записанные незафиксированной транзакцией.
• Неповторяющееся чтение: при повторном чтении в рамках одной транзакции данные оказываются изменёнными.
• Фантомное чтение: при повторном выполнении запроса появляются новые строки, вставленные другой транзакцией.

Сериализуемость в распределённых системах

В распределённых базах данных (например, CockroachDB, Google Spanner) сериализуемость достигается за счёт глобальных временных меток и протоколов консенсуса (например, Paxos или Raft). В таких системах дополнительно вводится понятие линеаризуемости — более сильного свойства, требующего, чтобы операции были видны всем узлам в реальном времени. Сериализуемость в распределённом контексте часто называют распределённой сериализуемостью или глобальной сериализуемостью.

Критика и альтернативы

Некоторые исследователи (например, Патрик Хелланд) критикуют сериализуемость за излишнюю строгость, предлагая вместо неё использовать слабо согласованные модели (например, eventual consistency) для приложений, где допустимы временные расхождения. Однако в критически важных системах (финансы, медицина) сериализуемость остаётся обязательным требованием. В последние годы наблюдается тренд на автоматическое обнаружение и разрешение конфликтов (например, в системах типа Calvin или FoundationDB), что позволяет сочетать сериализуемость с высокой производительностью.

Источники

1. Bernstein, P. A., Hadzilacos, V., & Goodman, N. (1987). Concurrency Control and Recovery in Database Systems. Addison-Wesley.
2. Gray, J., & Reuter, A. (1993). Transaction Processing: Concepts and Techniques. Morgan Kaufmann.
3. Weikum, G., & Vossen, G. (2002). Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann.
4. Adya, A. (1999). Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions. PhD Thesis, MIT.
5. Ports, D. R. K., & Grittner, K. (2012). «Serializable Snapshot Isolation in PostgreSQL». Proceedings of the VLDB Endowment, 5(12), 1850–1861.
6. Corbett, J. C., et al. (2013). «Spanner: Google’s Globally-Distributed Database». ACM Transactions on Computer Systems, 31(3), Article 8.