Причинная последовательность - Causal consistency

Причинная последовательность это одно из главных воспоминаний модели согласованности. В параллельное программирование, где параллельные процессы обращаются к общей памяти, модель согласованности ограничивает, какой доступ является законным. Это полезно для определения правильного структуры данных в распределенная разделяемая память или же распределенные транзакции.

Причинная последовательность «Доступно в разделе», что означает, что процесс может читать и записывать память (память доступна) даже при отсутствии работающего сетевого соединения (сеть разделена) между процессами; это асинхронная модель. В отличие от моделей сильной согласованности, таких как последовательная последовательность или же линеаризуемость, которые не могут быть одновременно безопасный и жить под разделом и медленно реагируют, потому что требуют синхронизации.

Причинная последовательность была предложена в 1990-х годах. [1] как более слабая модель согласованности для моделей с общей памятью. Причинная последовательность тесно связана с концепцией причинной широковещательной передачи в протоколах связи.[2] В этих моделях распределенное выполнение представлено как частичный порядок, основанный на алгоритме Лампорта. случилось раньше понятие потенциальной причинности. [3]

Причинная согласованность - полезная модель согласованности, потому что она соответствует интуиции программистов относительно времени, более доступна, чем сильные модели согласованности, но дает более полезные гарантии, чем возможная последовательность. Например, в распределенных базах данных причинная согласованность поддерживает порядок операций, в отличие от возможная последовательность.[4] Кроме того, причинная последовательность помогает в развитии абстрактные типы данных например, очереди или стойки. [5]

Поскольку время и порядок являются фундаментальными для нашей интуиции, трудно рассуждать о системе, которая не обеспечивает причинно-следственную согласованность. Однако многие распределенные базы данных не имеют этой гарантии, даже те, которые обеспечивают сериализацию.[6]Гаечный ключ действительно гарантирует причинно-следственную последовательность, но также вызывает сильную последовательность, таким образом избегая наличие под перегородкой.Больше доступных баз данных, обеспечивающих причинно-следственную связь, включают: MongoDB и АнтидотDB.

Определение

Причинно-следственная последовательность отражает потенциальные причинно-следственные связи между операциями и гарантирует, что все процессы соблюдают причинно-связанные операции в общем порядке. Другими словами, все процессы в системе согласовывают порядок причинно-следственных операций. Они могут не соглашаться относительно порядка операций, которые не связаны между собой.[1]

Определим следующее соотношение. Если некоторый процесс выполняет операцию записи A, а некоторый (тот же или другой) процесс, который наблюдал A, затем выполняет операцию записи B, то возможно, что A является причиной B; мы говорим, что A «потенциально является причиной» или «причинно предшествует» B. Причинная согласованность гарантирует, что если A причинно предшествует B, то каждый процесс в системе наблюдает A перед наблюдением B. И наоборот, две операции записи C и D называются одновременными, или причинно независимым, если ни один из них причинно не предшествует другому. В этом случае процесс может наблюдать либо C перед D, либо D перед C. Отношение причинного приоритета в общей памяти связано с случилось раньше отношения в коммуникации на основе сообщений.[3]

Таким образом, система обеспечивает причинную непротиворечивость, если выполняется следующее условие: операции записи, которые связаны потенциальной причинностью, рассматриваются каждым процессом системы в порядке их причинного приоритета. Различные процессы могут наблюдать одновременную запись в разном порядке.[7]

Модель причинной согласованности слабее, чем последовательная последовательность, что гарантирует, что все процессы соблюдают все операции записи в общем порядке, независимо от того, связаны они причинно или нет. [8] Однако причинная последовательность сильнее, чем Последовательность PRAM, который требует, чтобы только те операции записи, которые выполняются одним процессом, наблюдались в общем порядке каждым другим процессом. [9] Отсюда следует, что, когда система последовательно непротиворечива, она также причинно непротиворечива. Кроме того, причинно-следственная согласованность подразумевает согласованность PRAM, но не наоборот.

Пример

Вот пример причинно-следственной связи. [10]

Причинно-следственные связи соблюдаются в следующей последовательности событий:

P1:Вт (х) 1Вт (х) 3
P2:R (х) 1Вт (х) 2
P3:R (х) 1R (х) 3R (х) 2
P4:R (х) 1R (х) 2R (х) 3

Процесс P2 наблюдает и считывает предыдущую запись W (x) 1, выполненную процессом P1. Следовательно, две записи W (x) 1 и W (x) 2 причинно связаны. При причинной согласованности каждый процесс сначала наблюдает за W (x) 1, а затем за W (x) 2. Обратите внимание, что две операции записи W (x) 2 и W (x) 3 без промежуточных операций чтения являются параллельными, и процессы P3 и P4 наблюдают (читают) их в разном порядке.

Сессионные гарантии

Модель причинно-следственной связи можно разделить на четыре сессионные гарантии..[11] Их можно резюмировать следующим образом:

  • Прочтите ваши записи: Если процесс выполняет запись, тот же процесс позже наблюдает за результатом своей записи.
  • Монотонное чтение: набор операций записи, наблюдаемых (считываемых) процессом, гарантированно не убывает.
  • Пишет, следует читать: если какой-то процесс выполняет чтение, за которым следует запись, а другой процесс наблюдает за результатом записи, то он также может наблюдать за чтением (если оно не было перезаписано).
  • Монотонные записи: Если какой-то процесс выполняет запись, за которой через некоторое время следует другая запись, другие процессы будут наблюдать за ними в том же порядке.

Гарантии транзакционного сеанса для сериализации и изоляции моментальных снимков представлены Дауджи и Салемом.[12]

Выполнение

Система абстрагируется как набор взаимодействующих процессов. Когда процесс записывает в общую память, реализация отправляет это событие другим процессам (через общую память или в виде сообщения). Из-за параллелизма и сбоев процесс может получать события в любом порядке. доставляет событие, то есть делает его видимым для процесса, только если все события, которые причинно ему предшествуют, сами были доставлены. Это требует, чтобы реализация поддерживала метаданные который представляет причинно-следственные связи между обращениями к памяти.

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

Такой подход позволяет наличие под перегородкой.[13]

Есть два общих представления метаданных причинного контекста: одно - поддерживать явное граф зависимостей отношения причинной зависимости. Поскольку такой граф может расти сколь угодно большим, событие часто помечается только его непосредственными предшественниками; определение своих транзитивных предшественников требует обхода распределенного графа. вектор часы, с одной записью на процесс (или группу процессов), подсчитывая количество событий, сгенерированных процессом или группой. Это представление имеет фиксированный размер, а порядок событий может быть выведен с помощью простое сравнение векторов.

Чтобы точно определить, какие события являются зависимыми, а какие одновременными в полностью одноранговой системе, размер метаданных должен быть по крайней мере пропорционален количеству активных писателей.[14]Однако точное определение параллелизма, как правило, является излишним. Причинная согласованность требует только того, чтобы причинно-зависимые события были доставлены по порядку; не имеет значения, будут ли упорядочены два параллельных события. Следовательно, размер можно произвольно уменьшить, используя безопасные методы приближения. [15]В пределе один скаляр (часы Лампорта[3]) достаточно, за счет устранения любого параллелизма. Размер метаданных также можно уменьшить, ограничив топологию связи; например, в звездной, древовидной или линейной топологии достаточно одного скаляра.

Поиск эффективных реализаций причинной согласованности - очень активная область исследований.

Рекомендации

  1. ^ а б Ахамад, М., Нейгер, Г., Бернс, Дж. Э., Кохли, П., и Хатто, П. В. (1995). Причинная память: определения, реализация и программирование. Распределенные вычисления, 9 (1), 37-49.
  2. ^ Кеннет П. Бирман, Томас А. Джозеф (1987). Надежная связь при наличии сбоев. Пер. на комп. Sys. (TOCS), 5 (1), 47–76.
  3. ^ а б c Лэмпорт, Л. (1978). Время, часы и порядок событий в распределенной системе. Сообщения ACM, 21 (7), 558-565.
  4. ^ Эльбушра, М., и Линдстрём, Дж. (2015). Причинно-согласованные базы данных. Открытый журнал баз данных (OJDB), 2 (1), 17-35.
  5. ^ Перрин, М., Мостефауи, А., & Джард, К. (2016, февраль). Причинная последовательность: вне памяти. В материалах 21-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования (стр. 26). ACM.
  6. ^ К. Дауджи и К. Салем. Ленивая репликация базы данных с гарантиями заказа. В Int. Конф. on Data Engineering, стр. 424–435, апрель 2004 г.
  7. ^ Гогиа Р., Чхабра П. и Кумари Р. (2014). Модели согласованности в системах с распределенной общей памятью. Международный журнал компьютерных наук и мобильных вычислений, 196-201
  8. ^ Лэмпорт, Л. (1979). Как сделать многопроцессорный компьютер, который правильно выполняет многопроцессорные программы. Транзакции IEEE на компьютерах, 100 (9), 690-691.
  9. ^ Липтон, Р. Дж., И Сандберг, Дж. С. (1988). PRAM: масштабируемая разделяемая память. Принстонский университет, факультет компьютерных наук, Чикаго
  10. ^ Мосбергер, Д. (1993). Модели согласованности памяти. Обзор операционных систем ACM SIGOPS, 27 (1), 18-26.
  11. ^ Терри, Д. Б., Демерс, А. Дж., Петерсен, К., Спрейцер, М. Дж., Таймер, М. М., и Велч, Б. Б. (1994, сентябрь). Гарантия сеанса для слабо согласованных реплицированных данных. В параллельных и распределенных информационных системах, 1994., Труды Третьей Международной конференции (стр. 140-149). IEEE.
  12. ^ К. Дауджи и К. Салем. Ленивая репликация базы данных с изоляцией моментальных снимков. VLDB 2006.
  13. ^ Карлос Бакеро и Нуно Прегуиса. Почему логические часы - это просто. Comm. ACM 59 (4), стр. 43–47, апрель 2016 г.
  14. ^ Б. Чаррон-Бост, Относительно размера логических часов в распределенных системах. In Information Processing Letters, 39 (1) p. 11-16, 1991.
  15. ^ Торрес-Рохас, Франсиско Дж. И Ахамад, Мустак. Правдоподобные часы: логические часы постоянного размера для распределенных систем. Распределенные вычисления, 12 (4), 1999.