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

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

История и происхождение

Понятие строгой сериализуемости возникло в контексте развития теории транзакций и распределённых вычислений. Термин был введён в 1980-х годах как уточнение более ранней концепции сериализуемости, предложенной Джимом Греем и другими исследователями. В 1983 году Филип Бернштейн, Вассос Хадзилакос и Натан Гудман в своей книге «Concurrency Control and Recovery in Database Systems» описали сериализуемость как стандарт изолированности. Однако для распределённых систем, где транзакции могут выполняться на разных узлах, требовалась более строгая гарантия, учитывающая временные метки. В 1990-х годах с развитием систем типа Spanner (Google) и CockroachDB строгая сериализуемость стала практическим требованием для финансовых, банковских и критически важных приложений.

Ключевые характеристики

Строгая сериализуемость обеспечивается двумя взаимодополняющими свойствами:

• Сериализуемость: Результат параллельного выполнения транзакций эквивалентен некоторому последовательному порядку их выполнения. Это предотвращает аномалии, такие как «грязное чтение», «неповторяющееся чтение» и «фантомное чтение». Однако сериализуемость не накладывает ограничений на то, в каком порядке транзакции будут упорядочены — он может не совпадать с реальным временем.
• Линеаризуемость: Каждая операция (чтение или запись) кажется атомарной и выполняется в некоторый момент времени между её началом и завершением. Для транзакций это означает, что если транзакция A завершилась до начала транзакции B, то в последовательном порядке A должна предшествовать B. Это исключает ситуации, когда более поздняя транзакция «видит» состояние до завершения более ранней.

Строгая сериализуемость объединяет эти требования: транзакции упорядочиваются в соответствии с реальным временем, а результат эквивалентен последовательному выполнению.

Сравнение с другими уровнями изолированности

В иерархии уровней изолированности транзакций (по стандарту SQL и теории баз данных) строгая сериализуемость занимает верхнюю позицию. Ниже приведено сравнение:

Строгая сериализуемость отличается от обычной сериализуемости тем, что накладывает дополнительное ограничение на порядок транзакций: он должен соответствовать реальному времени. Например, если транзакция A завершилась в 10:00:00, а транзакция B началась в 10:00:01, то в последовательном порядке A должна быть перед B. Обычная сериализуемость допускает обратный порядок, если это не нарушает изолированность.

Реализация в распределённых системах

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

• Использование глобальных часов: Системы, такие как Google Spanner, применяют аппаратные часы (TrueTime) с известной погрешностью. Каждая транзакция получает временную метку, и система гарантирует, что порядок меток соответствует реальному времени. Для обеспечения линеаризуемости используется протокол двухфазной фиксации (2PC) и распределённые блокировки.
• Протоколы на основе лидера: В системах типа CockroachDB используется протокол Raft для репликации лога. Транзакции координируются через лидера, который назначает временные метки на основе часов лидера. Для разрешения конфликтов применяется оптимистичное управление параллелизмом (OCC) с проверкой сериализуемости.
• Централизованные сервисы времени: Некоторые системы (например, FoundationDB) используют глобальный сервис времени, который генерирует уникальные временные метки. Все узлы обращаются к этому сервису для получения меток, что гарантирует глобальный порядок.

Основная сложность — обеспечение линеаризуемости в условиях сетевых задержек и сбоев. Для этого используются механизмы тайм-аутов, повторные попытки и протоколы консенсуса (Paxos, Raft).

Применение

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

• Финансовые системы: Обработка транзакций в банках, биржевых операциях, системах денежных переводов. Например, при списании средств с одного счёта и зачислении на другой строгая сериализуемость гарантирует, что балансы никогда не будут некорректны из-за параллельных операций.
• Системы бронирования: Авиабилеты, гостиницы, билеты на мероприятия. Строгая сериализуемость предотвращает двойное бронирование одного места.
• Критически важные базы данных: Системы управления данными в промышленности, медицине, государственных реестрах. Например, в системах электронного здравоохранения, где записи о пациентах должны быть согласованы.
• Блокчейн и распределённые реестры: Некоторые блокчейн-платформы (например, Hyperledger Fabric с поддержкой строгой сериализуемости) используют это свойство для обеспечения консенсуса.

Ограничения и критика

Несмотря на высокую надёжность, строгая сериализуемость имеет существенные недостатки:

• Производительность: Достижение строгой сериализуемости требует дополнительных накладных расходов на синхронизацию, блокировки и протоколы консенсуса. Это может снижать пропускную способность системы, особенно в географически распределённых сценариях.
• Задержки: В распределённых системах с глобальными часами (например, Spanner) задержки могут достигать десятков миллисекунд из-за необходимости ждать подтверждения от часов.
• Сложность реализации: Разработка и поддержка системы, обеспечивающей строгую сериализуемость, требует глубоких знаний в области распределённых вычислений и управления параллелизмом. Ошибки в реализации могут приводить к нарушению согласованности.
• Альтернативы: Для многих приложений достаточно более слабых уровней изолированности, таких как snapshot isolation или сериализуемость без линеаризуемости. Например, социальные сети или системы аналитики часто жертвуют строгой согласованностью в пользу производительности.

Примеры систем

• Google Spanner: Глобально распределённая база данных, использующая TrueTime для обеспечения строгой сериализуемости. Поддерживает транзакции с произвольным доступом к данным.
• CockroachDB: Распределённая SQL-база данных, реализующая строгую сериализуемость через протокол Raft и оптимистичное управление параллелизмом.
• FoundationDB: Распределённая база данных с архитектурой «ключ-значение», предоставляющая строгую сериализуемость через централизованный сервис времени.
• YugabyteDB: Распределённая SQL-база данных, основанная на протоколе Raft и поддерживающая строгую сериализуемость в режиме Serializable.

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

• В 2012 году Google Spanner стал первой крупной коммерческой системой, заявившей о поддержке строгой сериализуемости в глобальном масштабе. Это было достигнуто за счёт использования атомных часов и GPS-синхронизации.
• Термин «строгая сериализуемость» часто путают с «линеаризуемостью», но последнее относится к отдельным операциям, а не к транзакциям.
• В некоторых системах (например, PostgreSQL) уровень Serializable не гарантирует линеаризуемости, поэтому он не является строгой сериализуемостью.

Источники

• Bernstein, P. A., Hadzilacos, V., & Goodman, N. (1987). Concurrency Control and Recovery in Database Systems. Addison-Wesley.
• Corbett, J. C., et al. (2012). «Spanner: Google’s Globally-Distributed Database». Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation.
• CockroachDB Documentation. «Serializable Isolation». Cockroach Labs.
• Gray, J., & Reuter, A. (1993). Transaction Processing: Concepts and Techniques. Morgan Kaufmann.
• Kleppmann, M. (2017). Designing Data-Intensive Applications. O’Reilly Media.