Русская Википедия:Причинная согласованность
Причинная согласованность (Шаблон:Lang-en) — модель согласованности, которая не требует, чтобы все процессы видели одну и ту же последовательность записей в памяти, проводя различие между потенциально-зависимыми (запись одной может зависеть от результата чтения другой ячейки) и потенциально-независимыми (параллельными) операциями записи[1].
Система обеспечивает причинную согласованность, если операции с памятью, которые потенциально причинно связаны, рассматриваются всеми узлами системы в том же порядке. Одновременные операции записи (то есть те, которые причинно не связаны), могут рассматриваться в различном порядке разными узлами. Этот вид согласованности слабее, чем последовательная согласованность, которая требует, чтобы все узлы видели все записи в том же порядке[2], но сильнее, чем Шаблон:Iw, при которой только записи, сделанные одним узлом, были бы видимы в том же порядке любым другим узломШаблон:Sfn.
Отношения причинности между операциями (событиями) для систем с Шаблон:Iw можно определить следующим образомШаблон:Sfn:
- Последовательность операций чтения и записи на узле определяет локальный причинный порядок.
- Операция записи причинно предшествует операции чтения на другом узле, если чтение возвращает значение, записанное с помощью этой операции записи. Это отношение межпроцессного порядка.
- И, наконец, причинный порядок считается транзитивным: то есть, если операция А (причинно) следует до В, а В — до С, то А находится в порядке причинности перед С. То есть, транзитивное замыкание отношений локального и межпроцессного порядков определяет глобальный причинный порядок.
Достоинства и недостатки
Сохраняя свойство гарантированных операций с небольшой задержкой, причинная согласованность лучше согласованности в конечном счёте как для пользователей, так и для программистов. Она учитывает причинно-следственные связи между операциями и гарантирует, что каждый узел видит операции в заданном порядке. Причинная согласованность также делает программирование проще, устраняя необходимость рассматривать не относящиеся к делу операции[3].
Тем не менее, причинной согласованности присущи и некоторые недостатки[3]:
- не все причинные связи могут быть установлены в рамках системы,
- не всегда возможно требовать выполнения глобальных инвариантов,
- логика одновременной записи может представлять трудности при реализации.
В частности, требуется установить, достаточно ли простого затирания старых данных или требуются отдельные механизмы разрешения конфликтующих записей.
Примечания
Литература
- Крюков В. А. Курс лекций «Распределенные ОС» 6. Распределенная общая память
- Шаблон:Книга
- Шаблон:Книга
- M. Ahamad, G. Neiger, J. E. Burns, P. Kohli, and P. Hutto. Causal memory: Definitions, implementation and programming. Distributed Computing, 9(1), 19
- Шаблон:Cite conference
- ↑ Шаблон:Книга
- ↑ Vijay K. Garg Concurrent and Distributed Computing in Java. John Wiley & Sons, 28 Jan 2005 — Computers — 336 pages. p 60
- ↑ 3,0 3,1 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.
