WikiSort.ru - Не сортированное

Причинная консистентность (англ. causal consistency) — модель консистентности, которая не требует, чтобы все процессы видели одну и ту же последовательность записей в памяти, проводя различие между потенциально-зависимыми (запись одной может зависеть от результата чтения другой ячейки) и потенциально-независимыми (параллельными) операциями записи^[1].

Описание

Система обеспечивает причинную консистентность, если операции с памятью, которые потенциально причинно связаны, рассматриваются всеми узлами системы в том же порядке. Одновременные операции записи (то есть те, которые причинно не связаны), могут рассматриваться в различном порядке разными узлами. Этот вид консистентности слабее, чем последовательная консистентность, которая требует, чтобы все узлы видели все записи в том же порядке^[2], но сильнее, чем PRAM-консистентность^[en], при которой только записи, сделанные одним узлом, были бы видимы в том же порядке любым другим узлом^[3].

Отношения причинности между операциями (событиями) для систем с распределённой общей памятью^[en] можно определить следующим образом^[4]:

1. Последовательность операций чтения и записи на узле определяет локальный причинный порядок.
2. Операция записи причинно предшествует операции чтения на другом узле, если чтение возвращает значение, записанное с помощью этой операции записи. Это отношение межпроцессного порядка.
3. И, наконец, причинный порядок считается транзитивным: то есть, если операция А (причинно) следует до В, а В — до С, то А находится в порядке причинности перед С. То есть, транзитивное замыкание отношений локального и межпроцессного порядков определяет глобальный причинный порядок.

Достоинства и недостатки

Сохраняя свойство гарантированных операций с небольшой задержкой (англ. latency), причинная консистентность лучше согласованности в конечном счёте как для пользователей, так и для программистов. Она учитывает причинно-следственные связи между операциями и гарантирует, что каждый узел видит операции в заданном порядке. Причинная согласованность также делает программирование проще, устраняя необходимость рассматривать не относящиеся к делу операции^[5].

Тем не менее, причинной консистентности присущи и некоторые недостатки^[5]:

• Не все причинные связи могут быть установлены в рамках системы
• Не всегда возможно требовать выполнения глобальных инвариантов
• Логика реализации одновременной записи может представлять трудности при реализации. В частности, требуется установить, достаточно ли простого затирания старых данных или требуются отдельные механизмы разрешения конфликтующих записей.

Примечания

Литература

• Крюков В. А. Курс лекций «Распределенные ОС» 6. Распределенная общая память
• Pradeep K. Sinha. Causal Consistency Model // Distributed Operating Systems: Concepts and Design. — PHI Learning Pvt. Ltd., 1998. — С. 239—240. — 761 с. — ISBN 9788120313804.
• Kshemkalyani, A.D. and Singhal, M. Distributed Computing: Principles, Algorithms, and Systems. — Cambridge University Press, 2011. — ISBN 9781139470315.
• M. Ahamad, G. Neiger, J. E. Burns, P. Kohli, and P. Hutto. Causal memory: Definitions, implementation and programming. Distributed Computing, 9(1), 19
• Bailis, Peter and Ghodsi, Ali and Hellerstein, Joseph M. and Stoica, Ion (2013). "Bolt-on Causal Consistency" in SIGMOD '13. Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data: 761—772, New York, New York, USA: ACM. DOI:10.1145/2463676.2465279. Проверено 2013-12-06.