stringtranslate.com

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

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

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

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

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

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

Определение

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

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

Процесс 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] ), ценой устранения любого параллелизма. Размер метаданных также можно уменьшить, ограничив топологию связи; например, в топологии типа «звезда», «дерево» или «линейная топология» достаточно одного скаляра.

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

Ссылки

  1. ^ ab Ахамад, Мустак; Нейгер, Джил; Бернс, Джеймс Э.; Кохли, Принс; Хатто, Филипп У. (март 1995 г.), «Причинная память: определения, реализация и программирование», Распределенные вычисления , 9 (1): 37–49, doi :10.1007/bf01784241, hdl : 1853/6781 , S2CID  6435056
  2. ^ Бирман, Кеннет П.; Джозеф, Томас А. (январь 1987 г.), «Надежная связь при наличии сбоев», ACM Transactions on Computer Systems , 5 (1): 47–76, doi : 10.1145/7351.7478, hdl : 1813/6534 , S2CID  11224827
  3. ^ abc Лампорт, Лесли (1978), «Время, часы и порядок событий в распределенной системе», Communications of the ACM , 21 (7): 558–565, doi : 10.1145/359545.359563 , S2CID  215822405
  4. ^ Эльбушра, Мавахиб Муса; Линдстрём, Ян (2015), «Причинно-согласованные базы данных», Открытый журнал баз данных , 2 (1): 17–35
  5. ^ Перрен, Матье; Мостефауи, Ашур; Жард, Клод (2016), «Причинная согласованность: за пределами памяти», в Asenjo, Рафаэль; Харрис, Тим (ред.), Труды 21-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, PPoPP 2016, Барселона, Испания, 12-16 марта 2016 г. , стр. 26:1–26:12, arXiv : 1603.04199 , doi : 10.1145/2851141.2851170, S2CID  3010991
  6. ^ Daudjee, Khuzaima; Salem, Kenneth (2004), "Отложенная репликация базы данных с гарантиями упорядочения", в Özsoyoglu, Z. Meral; Zdonik, Stanley B. (ред.), Труды 20-й Международной конференции по инжинирингу данных, ICDE 2004, 30 марта – 2 апреля 2004 г., Бостон, Массачусетс, США , IEEE Computer Society, стр. 424–435, CiteSeerX 10.1.1.564.1562 , doi :10.1109/ICDE.2004.1320016, S2CID  1850131 
  7. ^ Gogia, R., Chhabra, P., & Kumari, R. (2014). Модели согласованности в распределенных системах с общей памятью. Международный журнал компьютерных наук и мобильных вычислений, 196-201
  8. ^ Лампорт, Л. (1979). Как сделать многопроцессорный компьютер, который правильно выполняет многопроцессорные программы. IEEE Transactions on computers, 100(9), 690-691.
  9. ^ Lipton, RJ, & Sandberg, JS (1988). PRAM: масштабируемая общая память. Принстонский университет, кафедра компьютерных наук. Чикаго
  10. ^ Мосбергер, Д. (1993). Модели согласованности памяти. Обзор операционных систем ACM SIGOPS, 27(1), 18-26.
  11. ^ J. Brzezinski, C. Sobaniec и D. Wawrzyniak, «От сеансовой причинности к причинной согласованности», 12-я конференция Euromicro по параллельной, распределенной и сетевой обработке, 2004. Труды., Корунья, Испания, 2004, стр. 152-158, doi: 10.1109/EMPDP.2004.1271440.
  12. ^ К. Даудджи и К. Салем. Ленивая репликация базы данных с изоляцией моментальных снимков. VLDB 2006.
  13. ^ Карлос Бакеро и Нуно Прегуиса. Почему логические часы просты. Comm. ACM 59(4), стр. 43–47, апрель 2016 г.
  14. ^ Чаррон-Бост, Бернадетт (июль 1991 г.), «О размере логических часов в распределенных системах», Information Processing Letters , 39 (1): 11–16, doi :10.1016/0020-0190(91)90055-m
  15. ^ Торрес-Рохас, Франциско Дж.; Ахамад, Мустак (сентябрь 1999 г.), «Правдоподобные часы: логические часы постоянного размера для распределенных систем», Distributed Computing , 12 (4): 179–195, doi :10.1007/s004460050065, S2CID  2936350