Сериализуемость

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

История

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

Определение и формальная модель

Формально, пусть имеется множество транзакций \( T = \{T_1, T_2, \dots, T_n\} \), каждая из которых выполняет операции чтения (\( r \)) и записи (\( w \)) над объектами базы данных. План выполнения (или расписание) — это последовательность операций из всех транзакций, упорядоченная по времени. План называется сериализуемым, если существует некоторое последовательное (серийное) выполнение тех же транзакций, которое приводит к тому же конечному состоянию базы данных и тому же результату для каждой транзакции.

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

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

• Вершины графа — транзакции.
• Направленное ребро от \( T_i \) к \( T_j \) существует, если в плане есть конфликтующая пара операций, где операция \( T_i \) выполняется раньше операции \( T_j \).

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

Видовая сериализуемость

Существует также видовая сериализуемость (view-serializability), которая является более слабым критерием. План является видово-сериализуемым, если существует последовательное выполнение, которое приводит к тому же самому «виду» (то есть для каждой операции чтения значение, которое она читает, совпадает со значением, прочитанным в последовательном выполнении). Видовая сериализуемость сложнее для проверки (NP-полная задача), но допускает больше планов, чем конфликтная.

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

На практике обеспечение полной сериализуемости может снижать производительность из-за блокировок и конфликтов. Поэтому в стандарте SQL-92 и более поздних версиях определены четыре уровня изоляции транзакций, от наиболее строгого к наименее строгому:

Только уровень SERIALIZABLE гарантирует сериализуемость в классическом понимании. Однако некоторые СУБД (например, PostgreSQL) реализуют сериализуемость через механизм многоверсионного управления параллелизмом (MVCC) с дополнительными проверками, что может приводить к ложным конфликтам (аномалиям сериализации).

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

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

Наиболее распространённый метод — двухфазная блокировка (2PL, Two-Phase Locking). Транзакция проходит две фазы:

1. Фаза захвата блокировок (expanding phase): транзакция может только захватывать блокировки, но не освобождать их.
2. Фаза освобождения блокировок (shrinking phase): транзакция может только освобождать блокировки, но не захватывать новые.

Если все транзакции следуют протоколу 2PL, план гарантированно конфликтно-сериализуем. Однако 2PL может приводить к взаимоблокировкам (deadlocks), которые разрешаются откатом одной из транзакций.

Многоверсионное управление параллелизмом (MVCC)

В системах с MVCC (например, PostgreSQL, Oracle, MySQL с InnoDB) каждая операция записи создаёт новую версию строки, а транзакции видят снимок данных на момент своего начала. Это позволяет избежать блокировок при чтении. Однако для обеспечения сериализуемости требуется дополнительный механизм — сериализуемый снимок изоляции (SSI, Serializable Snapshot Isolation), который отслеживает конфликты между транзакциями и откатывает одну из них при обнаружении цикла.

Оптимистическое управление параллелизмом (OCC)

Транзакции выполняются без блокировок, а перед фиксацией проверяется, не было ли конфликтов с другими транзакциями. Если конфликт обнаружен, транзакция откатывается и повторяется. OCC эффективен при низкой конкуренции, но при высокой нагрузке может приводить к большому числу откатов.

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

Каждая транзакция получает временную метку (timestamp). Операции упорядочиваются по меткам, и конфликты разрешаются откатом транзакции с более поздней меткой, если она пытается выполнить операцию, нарушающую порядок.

Применение

Сериализуемость критически важна в системах, где требуется строгая согласованность данных:

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

В распределённых системах, таких как Google Spanner или CockroachDB, используется строгая сериализуемость (strict serializability), которая дополнительно гарантирует, что порядок транзакций соответствует реальному времени (линеаризуемость).

Критика и ограничения

• Производительность: полная сериализуемость может снижать пропускную способность системы из-за блокировок и откатов. Многие приложения обходятся более низкими уровнями изоляции (например, READ COMMITTED), жертвуя строгой согласованностью ради скорости.
• Сложность реализации: в распределённых системах обеспечение сериализуемости требует координации между узлами, что увеличивает задержки.
• Аномалии сериализации: даже при использовании сериализуемого уровня изоляции (например, в PostgreSQL с SSI) могут возникать ложные конфликты, когда транзакция откатывается из-за потенциальной, но нереализовавшейся аномалии.

Источники

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. Adya, A. (1999). Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions. PhD thesis, MIT.
4. Ports, D. R. K., & Grittner, K. (2012). «Serializable Snapshot Isolation in PostgreSQL». Proceedings of the VLDB Endowment, 5(12), 1850–1861.
5. Стандарт ISO/IEC 9075:2016 (SQL:2016), раздел «Transaction Isolation Levels».