Причинна узгодженість

Причинна узгодженість (англ. causal consistency ) — модель узгодженості, яка не потрибує, щоб всі процеси бачили однакову послідовність записів у пам'яті. Вона розрізняє потенційно залежні (запис однієї комірки може залежати від результату читання іншої) та потенційно незалежні (паралельними) операції запису.

Система забезпечує причинну узгодженість, якщо операції з пам'яттю, потенційно причинно пов'язані, розглядаються всіма вузлами системи у тому ж порядку. Одночасні операції запису (тобто ті, які причинно не пов'язані) можуть розглядатися в різному порядку різними вузлами.

Відносини причинності між операціями (подіями) для систем із ^[en] визначаються так  :

• Локальний причинно-наслідковий порядок - порядок визначається послідовністю операцій читання та запису на вузлі.
• Міжпроцесний причинно-наслідковий порядок - операція запису причинно передує операції читання на іншому вузлі, якщо читання повертає записане, за допомогою цієї операції запису.
• Транзитивність - якщо операція А причинно слідує за B, а B за C, то А знаходиться в порядку причинності перед C.

Модель причинної узгодженості є слабшою за модель послідовної узгодженості, яка гарантує, що всі процеси спостерігатимуть усі операції запису в спільному порядку, незалежно від причинно-наслідкового зв'язку. Водночас, причинна узгодженість є сильнішою за модель PRAM-узгодженості, яка вимагає лише того, щоб операції запису, виконані одним процесом, спостерігались у спільному порядку кожним іншим процесом.

З цього випливає, що якщо система послідовно узгоджена, то вона також причинно узгоджена. Додатково, причинна узгодженість означає PRAM-узгодженість, але не навпаки.

Причинна узгодженість забезпечує доступність в розділі (shared nothing, sharding) - тобто процеси можуть працювати навіть за відсутності мережевого з'єднання, і вони асинхронні (немає умовно-глобального годинника для синхронізації).

Концепція причинної узгодженості з'явилася в 1990-х роках як слабша модель узгодженості для моделей із спільною пам'яттю. Вона тісно пов'язана з поняттям причинного мовлення в комунікаційних протоколах. У цих моделях розподілене виконання представляється як частковий порядок, що базується на концепції Леслі Лампорта про "потенційну причинність".

Оскільки час і порядок є фундаментальними для нашої інтуїції, то складно проєктувати системи, які не забезпечують причинну узгодженість. Проте багато розподілених баз даних не гарантують її, навіть ті, що забезпечують серіалізованість. Spanner забезпечує причинну узгодженість, але також вимагає сильної узгодженості, що ставить під загрозу доступність у випадку розділення. Деякі високо-доступні бази даних, що забезпечують причинну узгодженість це MongoDB та AntidoteDB.

Переваги та недоліки

Причинна узгодженість враховує причинно-наслідкові зв'язки між операціями та гарантує, що кожен вузол бачить операції у заданому порядку. Причинна узгодженість також робить програмування простіше, усуваючи необхідність розглядати операції, що не відносяться до справи

• доступність - навіть при розділенні мережі.
• асинхронність
• відповідність інтуїції щодо уявлення про час.

Тим не менш, у причинної узгодженості є таки недоліки

• Фіксація лише видимої (локальної) причини
• Складність забезпечення глобальних інваріантів.
• Складність при необхідності враховувати одночасні записи, конфлікти.

Примітки

1. Одинцов И. О. Профессиональное программировании. Системный подход. — 2-е. — СПб. : БХВ-Петербург, 2004. — С. 520—521.
2. Kshemkalyani, Singhal, 2011, 12.2.3 Causal consistency.
3. Birman, Kenneth P.; Joseph, Thomas A. (5 січня 1987). Reliable communication in the presence of failures. ACM Transactions on Computer Systems (англ.). Т. 5, № 1. с. 47—76. doi:10.1145/7351.7478. ISSN 0734-2071. Процитовано 24 березня 2024.
4. Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, David G. Andersen. A Short Primer on Causal Consistency ;login: The USENIX Magazine, Vol 38, Number 4, August 2013. https://www.usenix.org/system/files/login/articles/08_lloyd_41-43_online.pdf