Причинная консистентность

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание[править | править вики-текст]

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

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

1. Последовательность операций чтения и записи на узле определяет локальный причинный порядок.

2. Операция записи причинно предшествует операции чтения на другом узле, если чтение возвращает значение, записанное с помощью этой операции записи. Это отношение межпроцессного порядка.

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

Достоинства и недостатки[править | править вики-текст]

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

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

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

Примечания[править | править вики-текст]

  1. Одинцов И. О. Профессиональное программировании. Системный подход. — 2-е. — СПб.: БХВ-Петербург, 2004. — С. 520-521.
  2. Vijay K. Garg Concurrent and Distributed Computing in Java. John Wiley & Sons, 28 Jan 2005 — Computers — 336 pages. p 60
  3. Kshemkalyani, Singhal, 2011, pp. 420-423.
  4. Kshemkalyani, Singhal, 2011, 12.2.3 Causal consistency.
  5. 1 2 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.

Литература[править | править вики-текст]