Последовательная консистентность¶
Последовательная консистентность (англ. sequential consistency) — это модель согласованности памяти в многопроцессорных системах и распределённых вычислениях, при которой результаты выполнения операций над общей памятью соответствуют некоторому последовательному порядку, совпадающему с порядком операций в каждом отдельном потоке (процессе). Формально модель была определена Лесли Лампортом в 1979 году как требование, чтобы «результат любого выполнения был таким же, как если бы операции всех процессоров выполнялись в некотором последовательном порядке, а операции каждого отдельного процессора следовали в том порядке, который задан его программой».
¶Определение и формальные требования
Последовательная консистентность является одной из наиболее строгих моделей ослабленной согласованности, занимая промежуточное положение между строгой консистентностью (linearizability) и более слабыми моделями, такими как причинная консистентность (causal consistency) или консистентность в конечном счёте (eventual consistency). Для обеспечения последовательной консистентности необходимо выполнение двух условий:
- Порядок в каждом процессе: операции чтения и записи, выполняемые одним потоком, должны наблюдаться всеми остальными потоками в том же порядке, в котором они были инициированы этим потоком.
- Глобальный порядок: существует единый для всех потоков порядок выполнения всех операций, который является тотальным (линейным) и согласован с порядком внутри каждого потока.
При этом модель не гарантирует, что операции выполняются в реальном времени (в отличие от строгой консистентности) — допускается, что запись может быть видна другим потокам с некоторой задержкой, но после того, как она стала видна, все последующие обращения должны видеть её значение.
¶История
Понятие последовательной консистентности было введено Лесли Лампортом в статье «How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs» (1979). Лампорт сформулировал модель как ответ на проблему недетерминизма в многопроцессорных системах, где из-за кэширования, переупорядочивания инструкций и конвейеризации результаты выполнения программ могли различаться от запуска к запуску. Предложенная модель стала основой для разработки многих реальных архитектур, включая процессоры x86 (в режиме TSO — Total Store Order) и SPARC.
В 1990-е годы последовательная консистентность была адаптирована для распределённых систем, в частности, для систем управления базами данных (СУБД) и распределённых хранилищ. В 2000-е годы, с развитием облачных вычислений и NoSQL-баз данных, модель стала использоваться как эталон для сравнения с более слабыми моделями, обеспечивающими более высокую производительность и доступность.
¶Классификация и сравнение с другими моделями
Последовательная консистентность относится к группе «сильных» моделей согласованности, но уступает по строгости строгой консистентности (linearizability), которая требует, чтобы операции были видны всем потокам немедленно после завершения, в соответствии с глобальным временем. В отличие от неё, последовательная консистентность допускает задержки в распространении записей, но при этом гарантирует, что все потоки видят операции в одном и том же порядке.
¶Сравнительная таблица моделей согласованности
| Модель | Гарантии | Примеры применения |
|---|---|---|
| Строгая консистентность (linearizability) | Каждая операция видна всем потокам сразу после завершения, порядок соответствует реальному времени | Базы данных с транзакциями ACID, распределённые блокировки |
| Последовательная консистентность | Единый глобальный порядок, но с возможными задержками | Многопроцессорные системы, некоторые СУБД (например, CockroachDB) |
| Причинная консистентность | Гарантируется порядок только для причинно-связанных событий | Распределённые чаты, социальные сети |
| Консистентность в конечном счёте | Все копии данных в итоге придут к одному значению, но без гарантий порядка | DNS-системы, кэши CDN |
¶Реализация в многопроцессорных системах
В аппаратных архитектурах последовательная консистентность реализуется через механизмы когерентности кэша (cache coherence) и барьеры памяти (memory barriers). Наиболее распространённый протокол когерентности — MESI (Modified, Exclusive, Shared, Invalid) — обеспечивает, что все процессоры видят одинаковое значение для каждой ячейки памяти, но не гарантирует глобального порядка операций. Для достижения последовательной консистентности требуется дополнительное упорядочивание, например, через инструкции mfence (x86) или sync (PowerPC).
В процессорах архитектуры x86 используется модель Total Store Order (TSO), которая является ослабленной версией последовательной консистентности: она допускает переупорядочивание операций записи с последующими чтениями, но сохраняет порядок между записями и между чтениями. Для полной последовательной консистентности в x86 необходимо явно использовать барьеры памяти.
¶Применение в распределённых системах
В распределённых системах последовательная консистентность часто реализуется через протоколы репликации, такие как Paxos или Raft. Эти протоколы обеспечивают, что все узлы системы соглашаются на единый порядок операций, что соответствует требованиям модели. Примеры систем, поддерживающих последовательную консистентность:
- Apache ZooKeeper — распределённый координационный сервис, используемый для управления конфигурациями и синхронизации.
- etcd — распределённое хранилище ключ-значение, применяемое в Kubernetes.
- CockroachDB — распределённая SQL-СУБД, которая по умолчанию использует последовательную консистентность для транзакций.
Однако в системах, требующих высокой доступности и низкой задержки (например, Amazon DynamoDB, Cassandra), последовательная консистентность не применяется из-за её ограничений по производительности — вместо неё используется консистентность в конечном счёте.
¶Критика и ограничения
Основным недостатком последовательной консистентности является её влияние на производительность. В многопроцессорных системах для обеспечения глобального порядка требуется синхронизация между кэшами и барьеры памяти, что увеличивает задержки и снижает пропускную способность. В распределённых системах протоколы консенсуса (Paxos, Raft) требуют нескольких раундов обмена сообщениями, что также приводит к росту времени отклика.
Кроме того, последовательная консистентность не гарантирует «свежести» данных в реальном времени — поток может прочитать устаревшее значение, если между записью и чтением прошло недостаточно времени для распространения. Это делает модель непригодной для систем, где требуется строгая актуальность данных (например, в финансовых транзакциях).
¶Интересные факты
- Лесли Лампорт, введя понятие последовательной консистентности, также разработал протокол Paxos, который стал основой для многих распределённых систем.
- В 2011 году Джефф Дин (Google) в своей работе «Designs, Lessons and Advice from Building Large Distributed Systems» отметил, что последовательная консистентность «слишком дорога» для большинства интернет-сервисов, что привело к популяризации более слабых моделей.
- В стандарте языка C++11 модель памяти по умолчанию является последовательно-консистентной для атомарных операций, если не указано иное (например,
memory_order_relaxed).
¶Источники
- Lamport L. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs // IEEE Transactions on Computers. — 1979. — Vol. C-28, No. 9. — P. 690–691.
- Adve S. V., Gharachorloo K. Shared Memory Consistency Models: A Tutorial // IEEE Computer. — 1996. — Vol. 29, No. 12. — P. 66–76.
- Tanenbaum A. S., Van Steen M. Distributed Systems: Principles and Paradigms. — 2nd ed. — Pearson, 2007. — Chapter 6.
- Документация Apache ZooKeeper: https://zookeeper.apache.org/doc/current/zookeeperOver.html
- Документация etcd: https://etcd.io/docs/latest/learning/why/