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

Введение

В этой статье рассмотрим, что такое «Сериализуемость» (Serializability) и какие гарантии она предоставляет.

В реляционных СУБД уровень изоляции Serializable (сериализуемость), как следует из названия, обеспечивает сериализуемость транзакций. Однако, как вы увидите далее, в некоторых базах данных реализована также строгая сериализуемость (Strict Serializability), которая представляет собой комбинацию сериализуемости и линеаризуемости (Linearizability).

Последовательное выполнение

Прежде чем говорить о сериализуемости, давайте рассмотрим последовательное выполнение (Serial execution). Сериализуемость и последовательное выполнение — это не одно и то же.

Последовательное выполнение обеспечивает монопольный доступ к общему ресурсу одному и только одному клиенту в каждый отдельно взятый момент времени. Это показано на диаграмме ниже:

Предоставляя монопольный доступ к разделяемым ресурсам, можно предотвратить появление аномалий данных, поскольку каждая транзакция будет видеть базу данных в согласованном состоянии, в котором ее оставила предыдущая транзакция.

Существует множество технологий, использующих последовательное выполнение, например, JavaScript, Node.js, Volt DB.

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

Следовательно, последовательное выполнение плохо масштабируется, то есть оно ограничено системами, хранящими данные в памяти, с очень быстрыми операциями.

Конфликты конкурентного доступа

Большинство реляционных СУБД позволяет одновременно работать через несколько соединений. Таким образом, в каждый момент времени может выполняться несколько транзакций, читающих и изменяющих данные.

При отсутствии сериализуемости есть вероятность появления конфликтов. В контексте транзакций баз данных эти конфликты называются феноменами (phenomena) или аномалиями (anomalies) данных.

Например, на диаграмме ниже показана аномалия потерянного обновления (Lost Update), которая может возникнуть при отсутствии сериализуемости:

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

Для предотвращения аномалий журнал транзакций должен линеаризовать транзакции, чтобы не было чередования операций чтения и записи, относящихся к разным транзакциям.

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

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

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

То есть, если Алиса и Боб выполняют одновременно две транзакции, то возможно только два варианта последовательного выполнения:

• сначала транзакция Алисы (Alice), потом транзакция Боба (Bob);

• сначала транзакция Боба (Bob), потом транзакция Алисы (Alice).

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

В случае трех транзакций (A, B и C) будет 3! = 6 вариантов последовательного выполнения. Для достижения сериализуемости порядок не имеет значения. Единственное ограничение — результат должен быть как при последовательном выполнении.

Для N одновременных транзакций получается N! возможных вариантов последовательного выполнения, каждый из которых представляет собой сериализуемый поток выполнения.

Если поток транзакций является одновременно сериализуемым и линаризуемым (операции применяются мгновенно), то мы получаем модель строгой сериализуемости (Strict Serializable).

Реализация сериализуемости

Для реализации сериализуемости есть два подхода:

• 2PL (Two-Phase Locking, двухфазная блокировка) — используется в SQL Server и MySQL для реализации уровня изоляции Serializable.

• Serializable Snapshot Isolation — реализован в PostgreSQL.

Уровень изоляции Serializable в Oracle на самом деле является Snapshot Isolation (изоляцией снимков состояния), и хотя это решает многие проблемы, но не защищает от всех возможных аномалий ассиметрии записи (Write Skew).

Заключение

Сериализуемость (Serializability) позволяет предотвратить конфликты конкурентного доступа, не жертвуя параллелизмом, как в случае с последовательным выполнением (Serial execution).

Пока результат будет эквивалентен любому из последовательных выполнений, несколько транзакций могут быть успешно зафиксированы (commit). Для реализации сериализуемости могут использовать либо блокировки, либо механизм MVCC (Multi-Version Concurrency Control).

Всех желающих приглашаем на открытое занятие курса OTUS «Java Developer. Professional» — «Вредные советы по созданию кода».