Причинно-следственная связь
Причинная согласованность — одна из основных моделей согласованности памяти . В параллельном программировании , когда параллельные процессы обращаются к общей памяти, модель согласованности ограничивает допустимый доступ. Это полезно для определения правильных структур данных в распределенной общей памяти или распределенных транзакциях .
Причинная согласованность «Доступна в разделе» , что означает, что процесс может читать и записывать память (память доступна), даже если между процессами нет действующего сетевого соединения (сеть разделена); это асинхронная модель. В отличие от моделей строгой согласованности, таких как последовательная согласованность или линеаризуемость , которые не могут быть одновременно безопасными и жить под разделением и медленно реагируют, поскольку требуют синхронизации.
Причинно-следственная связь была предложена в 1990-х годах. [1] как более слабая модель согласованности для моделей с общей памятью. Причинная согласованность тесно связана с концепцией причинной трансляции в протоколах связи. [2] В этих моделях распределенное исполнение представлено как частичный порядок, основанный на случилось до» Лэмпорта. концепции потенциальной причинности « [3]
Причинная согласованность — полезная модель согласованности, поскольку она соответствует представлениям программистов о времени, более доступна, чем модели строгой согласованности, но при этом обеспечивает более полезные гарантии, чем итоговая согласованность . Например, в распределенных базах данных причинная согласованность поддерживает порядок операций, в отличие от итоговой согласованности . [4] Кроме того, причинно-следственная согласованность помогает при разработке абстрактных типов данных, таких как очереди или счетчики. [5]
Поскольку время и порядок столь важны для нашей интуиции, труднорассуждать о системе, которая не обеспечивает причинно-следственной связи.Однако многие распределенные базы данных лишены этой гарантии, даже те, которыеобеспечить сериализуемость. [6] Spanner не гарантирует причинно-следственную согласованность, но он также обеспечивает строгую согласованность, избегая таким образом доступности в разделе .Более доступные базы данных, обеспечивающие причинно-следственную связь, включают MongoDB. и АнтидотДБ .
Определение
[ редактировать ]Причинно-следственная связь фиксирует потенциальные причинно-следственные связи между операциями и гарантирует, что все процессы наблюдают причинно-связанные операции в общем порядке. Другими словами, все процессы в системе согласовывают порядок причинно-связанных операций. Они могут расходиться во мнениях относительно порядка операций, которые причинно не связаны. [1]
Определим следующее соотношение. Если некоторый процесс выполняет операцию записи A, а некоторый (тот же или другой) процесс, наблюдавший A, затем выполняет операцию записи B, то возможно, что A является причиной B; мы говорим, что А «потенциально вызывает» или «каузально предшествует» Б. Причинная согласованность гарантирует, что если A причинно предшествует B, то каждый процесс в системе наблюдает A раньше, чем наблюдает B. И наоборот, две операции записи C и D называются параллельными или причинно независимыми, если ни одна из них не предшествует другой. В этом случае процесс может наблюдать либо C перед D, либо D перед C. Отношение причинного приоритета в общей памяти связано с отношением «произошло до» в коммуникации на основе сообщений. [3]
Таким образом, система обеспечивает причинную согласованность, если выполняется следующее условие: операции записи, связанные потенциальной причинностью, рассматриваются каждым процессом системы в порядке их причинного приоритета. Разные процессы могут наблюдать одновременную запись в разном порядке. [7]
Модель причинной согласованности слабее, чем последовательная согласованность , которая гарантирует, что все процессы выполняют все операции записи в общем порядке, независимо от того, имеют ли они причинно-следственную связь или нет. [8] Однако причинно-следственная согласованность сильнее, чем согласованность PRAM , которая требует, чтобы только операции записи, выполняемые одним процессом, наблюдались в общем порядке всеми другими процессами. [9] Отсюда следует, что когда система секвенциально непротиворечива, она также каузально непротиворечива. Кроме того, причинно-следственная согласованность подразумевает согласованность PRAM, но не наоборот.
Пример
[ редактировать ]Вот пример причинно-следственной связи. [10]
Причинно-следственные связи соблюдаются в следующей последовательности событий:
| Вопрос 1: | Вт(х)1 | Вт(х)3 | |||
| П2: | Р(х)1 | Вт(х)2 | |||
| П3: | Р(х)1 | Р(х)3 | Р(х)2 | ||
| П4: | Р(х)1 | Р(х)2 | Р(х)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) Процесс, получивший некоторое событие обновления, может доставить его только в том случае, если тег события причинно предшествует причинному контексту принимающего процесса.(В качестве побочного эффекта доставки добавьте новое событие в причинный контекст принимающего процесса.)В противном случае обновление было получено слишком рано и должно оставаться в буфере до тех пор, пока событие не совпадет с контекстом.Тем временем реализация либо пассивно ожидает получения недостающих событий, либо активно извлекает их из источника.
Этот подход обеспечивает доступность в разделе . [13]
Существует два распространенных представления метаданных причинного контекста.Один из них — поддерживать явный граф зависимости отношения причинной зависимости.Поскольку такой граф может вырасти до произвольного размера, событие часто помечается только его непосредственными предшественниками; определение его транзитивных предшественников требует обхода распределенного графа.Другой — поддерживать векторные часы с одной записью на каждый процесс (или группу процессов), подсчитывая количество событий, генерируемых процессом или группой.Это представление имеет фиксированный размер, а порядок событий можно определить путем простого сравнения векторов .
Чтобы точно определить, какие события являются зависимыми, а какие одновременными в полностью одноранговой системе, размер метаданных должен быть как минимум пропорционален количеству активных записывающих устройств. [14] Однако точное определение параллелизма обычно является излишним.Причинная последовательность требует лишь того, чтобы причинно-зависимые события происходили в определенном порядке; не имеет значения, будут ли в конечном итоге упорядочены два одновременных события.Следовательно, размер можно уменьшить произвольно, используя методы безопасной аппроксимации. [15] В пределе один скаляр (часы Лэмпорта) [3] ) достаточно за счет устранения любого параллелизма.Размер метаданных также можно уменьшить, ограничив топологию связи; например, в звездообразной, древовидной или линейной топологии достаточно одного скаляра.
Поиск эффективных реализаций причинной непротиворечивости является очень важной задачей.активная исследовательская область.
Ссылки
[ редактировать ]- ^ Jump up to: а б Ахамад, Мустак; Нейгер, Гил; Бернс, Джеймс Э.; Кохли, князь; Хатто, Филлип В. (март 1995 г.), «Причинная память: определения, реализация и программирование», Distributed Computing , 9 (1): 37–49, doi : 10.1007/bf01784241 , hdl : 1853/6781 , S2CID 6435056
- ^ Бирман, Кеннет П.; Джозеф, Томас А. (январь 1987 г.), «Надежная связь при наличии сбоев», Транзакции ACM в компьютерных системах , 5 (1): 47–76, doi : 10.1145/7351.7478 , hdl : 1813/6534 , S2CID 11224827
- ^ Jump up to: а б с Лампорт, Лесли (1978), «Время, часы и порядок событий в распределенной системе», Communications of the ACM , 21 (7): 558–565, doi : 10.1145/359545.359563 , S2CID 215822405
- ^ Эльбушра, Мавахиб Муса; Линдстрём, январь (2015 г.), «Причинно-согласованные базы данных» , Открытый журнал баз данных , 2 (1): 17–35.
- ^ Перрен, Матье; Мостефауи, Ашур; Жард, Клод (2016), «Причинно-следственная последовательность: за пределами памяти», в Асенхо, Рафаэль; Харрис, Тим (ред.), Труды 21-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, PPoPP 2016, Барселона, Испания, 12–16 марта 2016 г. , стр. 26: 1–26: 12, arXiv : 1603.04199 , doi : 10.1145/2851141.2851170 , S2CID 3010991
- ^ Дауджи, Хузайма; Салем, Кеннет (2004), «Ленивая репликация базы данных с гарантиями порядка», в Озсойоглу, З. Мерал; Здоник, Стэнли Б. (ред.), Труды 20-й Международной конференции по инженерии данных, ICDE 2004, 30 марта – 2 апреля 2004 г., Бостон, Массачусетс, США , Компьютерное общество IEEE, стр. 424–435, CiteSeerX 10.1.1.564 .1562 , doi : 10.1109/ICDE.2004.1320016 , S2CID 1850131
- ^ Гогиа Р., Чхабра П. и Кумари Р. (2014). Модели согласованности в распределенных системах с общей памятью. Международный журнал компьютерных наук и мобильных вычислений, 196-201.
- ^ Лэмпорт, Л. (1979). Как сделать многопроцессорный компьютер, корректно выполняющий многопроцессные программы. Транзакции IEEE на компьютерах, 100(9), 690-691.
- ^ Липтон, Р.Дж., и Сандберг, Дж.С. (1988). PRAM: масштабируемая общая память. Принстонский университет, факультет компьютерных наук. Чикаго.
- ^ Мосбергер, Д. (1993). Модели согласованности памяти. Обзор операционных систем ACM SIGOPS, 27 (1), 18-26.
- ^ Дж. Бжезинский, К. Собанец и Д. Вавжиняк, «От сеансовой причинности к причинной последовательности», 12-я конференция Euromicro по параллельной, распределенной и сетевой обработке, 2004. Труды, Корунья, Испания, 2004, стр. 152- 158, номер документа: 10.1109/EMDPP.2004.1271440.
- ^ К. Дауджи и К. Салем. Отложенная репликация базы данных с изоляцией моментальных снимков. ВЛДБ 2006.
- ^ Карлос Бакеро и Нуно Прегиса. Почему логические часы просты. Комм. ACM 59(4), стр. 43–47, апрель 2016 г.
- ^ Чаррон-Бост, Бернадетт (июль 1991 г.), «О размере логических часов в распределенных системах», Information Processing Letters , 39 (1): 11–16, doi : 10.1016/0020-0190(91)90055-m
- ^ Торрес-Рохас, Франсиско Х.; Ахамад, Мустак (сентябрь 1999 г.), «Правдоподобные часы: логические часы постоянного размера для распределенных систем», Distributed Computing , 12 (4): 179–195, doi : 10.1007/s004460050065 , S2CID 2936350