Serializable Snapshot Isolation

Serializable Snapshot Isolation (SSI) — это уровень изоляции транзакций в системах управления базами данных (СУБД), обеспечивающий полную сериализуемость транзакций при использовании многоверсионного управления конкурентным доступом (MVCC). SSI сочетает производительность, характерную для snapshot-изоляции (Snapshot Isolation, SI), с гарантиями корректности, эквивалентными последовательному выполнению транзакций, что предотвращает аномалии, такие как потерянные обновления, неповторяемое чтение, фантомное чтение и, что наиболее важно, аномалии сериализации (например, «аномалия записи»).

История и предпосылки

Разработка SSI стала ответом на фундаментальную проблему в теории баз данных: классическая snapshot-изоляция, предложенная в 1995 году, была эффективной и предотвращала многие распространённые аномалии, но не гарантировала полной сериализуемости. В 2005 году Майкл Кэхилл и Алан Фекете из Университета Нового Южного Уэльса опубликовали работу, в которой доказали, что snapshot-изоляция не является сериализуемой, и предложили метод обнаружения конфликтов на основе графа зависимостей. В 2008 году они же совместно с исследователями из Microsoft Research представили алгоритм Serializable Snapshot Isolation, который был реализован в PostgreSQL 9.1 (выпущен в 2011 году) и впоследствии в других СУБД, таких как MySQL (с InnoDB) и CockroachDB.

Принцип работы

SSI основан на механизме MVCC, где каждая транзакция работает с «снимком» (snapshot) данных на момент её начала. Для обеспечения сериализуемости SSI отслеживает конфликты между транзакциями, которые могут привести к несериализуемому поведению. Основные этапы работы:

1. Создание снэпшота: При старте транзакции ей присваивается уникальный идентификатор (txid) и создаётся снимок всех зафиксированных версий строк на этот момент.
2. Выполнение операций: Транзакция читает и записывает данные, используя свой снэпшот. Записи (вставки, обновления, удаления) создают новые версии строк, которые не видны другим транзакциям до фиксации.
3. Обнаружение конфликтов (Conflict Detection): SSI использует два типа конфликтов:

• RW-конфликт (Read-Write): Возникает, когда транзакция T1 читает версию строки, которая позже изменяется транзакцией T2 (записывается новая версия). Если T1 и T2 выполняются параллельно, может возникнуть несериализуемое поведение.
• WR-конфликт (Write-Read): Возникает, когда транзакция T1 записывает новую версию строки, а транзакция T2 читает более старую версию (из своего снэпшота). Это также указывает на потенциальный конфликт.

1. Граф зависимостей (Serialization Graph): SSI строит граф, где вершины — транзакции, а рёбра — зависимости между ними (RW или WR). Если в графе возникает цикл, это означает, что транзакции не могут быть сериализованы.
2. Аборт транзакции: При обнаружении цикла в графе зависимостей одна из транзакций, участвующих в цикле, абортируется (откатывается). Обычно абортируется та транзакция, которая зафиксировалась позже или имеет меньший приоритет. Это предотвращает несериализуемое состояние.

Отличие от Snapshot Isolation

Ключевое отличие SSI от классической SI заключается в том, что SI допускает аномалии, такие как «аномалия записи» (write skew), когда две транзакции одновременно читают непересекающиеся наборы данных, а затем записывают их, нарушая бизнес-логику. SSI, отслеживая RW- и WR-конфликты, выявляет такие ситуации и абортирует одну из транзакций, гарантируя сериализуемость.

Применение

SSI применяется в системах, где требуется высокая согласованность данных при сохранении производительности, характерной для snapshot-изоляции. Основные области использования:

• Финансовые системы: Обработка транзакций, где требуется избежать аномалий (например, двойное списание средств).
• Системы бронирования: Управление параллельными заказами билетов, мест в отелях или товаров на складе.
• Многопользовательские онлайн-игры: Обеспечение корректности игрового состояния при одновременных действиях игроков.
• Распределённые базы данных: В системах, таких как CockroachDB и Google Spanner, SSI используется для обеспечения глобальной сериализуемости в распределённой среде.

Примеры СУБД с поддержкой SSI

• PostgreSQL: Начиная с версии 9.1 (2011 год) реализована полная поддержка SSI. Для включения необходимо установить уровень изоляции SERIALIZABLE для транзакции.
• MySQL (InnoDB): Начиная с версии 8.0.0 (2018 год) добавлена экспериментальная поддержка SSI через параметр transaction_isolation=SERIALIZABLE и включение innodb_serializable_snapshot_isolation.
• CockroachDB: Использует SSI как основной механизм изоляции для всех транзакций, обеспечивая сериализуемость по умолчанию.
• FoundationDB: Реализует SSI в своём ядре для обеспечения сильной согласованности.

Преимущества и недостатки

Преимущества

• Полная сериализуемость: Гарантирует, что результат параллельного выполнения транзакций эквивалентен некоторому последовательному порядку.
• Производительность: SSI обычно быстрее, чем классическая блокировочная сериализация (2PL), так как позволяет большую параллельность за счёт использования снэпшотов.
• Отсутствие тупиков (deadlocks): В отличие от 2PL, SSI не требует блокировок, что снижает риск взаимоблокировок. Однако аборты транзакций всё равно возможны.
• Прозрачность для разработчика: Разработчику не нужно вручную управлять блокировками или оптимизировать параллельность.

Недостатки

• Повышенные накладные расходы: Отслеживание конфликтов и построение графа зависимостей требует дополнительных вычислительных ресурсов и памяти, что может снизить производительность на сильно нагруженных системах.
• Увеличение числа абортов: В сценариях с высокой конкуренцией за одни и те же данные SSI может абортировать больше транзакций, чем SI, что снижает пропускную способность.
• Сложность реализации: Алгоритм SSI сложен для реализации и отладки, особенно в распределённых системах.

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

Несмотря на преимущества, SSI не является панацеей. В системах с очень высокой частотой конфликтов (например, при массовых обновлениях одной строки) SSI может приводить к чрезмерному числу абортов, что делает его менее эффективным, чем оптимистическое управление конкурентным доступом (OCC) или пессимистические методы. Кроме того, в распределённых системах с задержками сети обнаружение конфликтов может быть затруднено, что требует дополнительных механизмов, таких как глобальные часы (например, в Google Spanner). Некоторые исследователи отмечают, что SSI не полностью решает проблему «фантомного чтения» в некоторых реализациях, хотя в PostgreSQL это решено с помощью предикатных блокировок.

Интересные факты

• Алгоритм SSI был впервые реализован в PostgreSQL в 2011 году, что сделало его первой крупной СУБД с открытым исходным кодом, поддерживающей полную сериализуемость на основе MVCC.
• В 2012 году за работу над SSI Майкл Кэхилл и Алан Фекете получили награду ACM SIGMOD Test of Time Award.
• CockroachDB использует модифицированную версию SSI, адаптированную для распределённой среды, где каждая транзакция может выполняться на разных узлах кластера.

Источники

• Michael J. Cahill, Alan Fekete, Uwe Röhm. "Serializable Isolation for Snapshot Databases" (2008).
• PostgreSQL Documentation: "Serializable Snapshot Isolation" (Chapter 13.2.3).
• MySQL 8.0 Reference Manual: "InnoDB and Serializable Snapshot Isolation".
• CockroachDB Documentation: "Serializable Isolation".
• "A Critique of ANSI SQL Isolation Levels" (1995) — предшествующая работа, заложившая основы SSI.