Окончательная согласованность

Итоговая согласованность — это модель согласованности, используемая в распределенных вычислениях для достижения высокой доступности , которая неформально гарантирует, что, если к данному элементу данных не производится никаких новых обновлений, в конечном итоге все обращения к этому элементу будут возвращать последнее обновленное значение. ^[1] Окончательная согласованность, также называемая оптимистической репликацией . ^[2] широко применяется в распределенных системах и берет свое начало в ранних проектах мобильных вычислений. ^[3] О системе, достигшей конечной согласованности, часто говорят, что она конвергентна или достигла конвергенции реплик . ^[4] Окончательная непротиворечивость является слабой гарантией: большинство более сильных моделей, таких как линеаризуемость , тривиально в конечном итоге непротиворечивы.

Службы, согласованные в конечном итоге, часто классифицируются как обеспечивающие семантику BASE (базовая доступность, мягкое состояние, конечная согласованность), в отличие от традиционных ACID (атомарность, согласованность, изоляция, надежность) . ^[5]^[6] В химии основание является противоположностью кислоты, что помогает запомнить аббревиатуру. ^[7] Согласно тому же ресурсу, вот приблизительные определения каждого термина в BASE:

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

Окончательная последовательность иногда подвергается критике. ^[8] как увеличение сложности распределенных программных приложений. Частично это связано с тем, что итоговая согласованность — это просто гарантия жизнеспособности (чтения в конечном итоге возвращают одно и то же значение) и не гарантирует безопасность : окончательно согласованная система может возвращать любое значение до того, как оно сходится.

Разрешение конфликтов

Чтобы обеспечить конвергенцию реплик, система должна согласовывать различия между несколькими копиями распределенных данных. Он состоит из двух частей:

обмен версиями или обновлениями данных между серверами (часто известный как антиэнтропия ); ^[9] и
выбор подходящего конечного состояния при возникновении одновременных обновлений, называемого согласованием .

Наиболее подходящий подход к согласованию зависит от приложения. Распространенный подход - «побеждает последний писатель». ^[1] Другой вариант — вызвать указанный пользователем обработчик конфликтов. ^[4] Временные метки и векторные часы часто используются для обнаружения параллелизма между обновлениями. Некоторые люди используют фразу «побеждает первый автор» в ситуациях, когда фраза «побеждает последний автор» неприемлема. ^[10]

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

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

Сильная конечная последовательность

В то время как итоговая согласованность является лишь гарантией жизнеспособности (со временем обновления будут наблюдаться), строгая итоговая согласованность (SEC) добавляет гарантию безопасности , согласно которой любые два узла, получившие одинаковый (неупорядоченный) набор обновлений, будут находиться в одном и том же состоянии. Кроме того, если система монотонна , приложение никогда не будет подвергаться откатам. Распространенный подход к обеспечению SEC — бесконфликтные реплицируемые типы данных . ^[12]

См. также

Ссылки

^ Jump up to: ^а ^б Фогельс, В. (2009). «В конечном итоге последовательно» . Коммуникации АКМ . 52 : 40–44. дои : 10.1145/1435417.1435432 .
^ Фогельс, В. (2008). «В конечном итоге согласованный» . Очередь . 6 (6): 14–19. дои : 10.1145/1466443.1466448 .
^ Jump up to: ^а ^б Терри, Д.Б.; Теймер, ММ; Петерсен, К.; Демерс, Эй Джей; Спрейцер, MJ; Хаузер, CH (1995). «Управление конфликтами обновлений в Bayou, слабосвязанной реплицируемой системе хранения». Материалы пятнадцатого симпозиума ACM по принципам операционных систем - СОСП '95 . п. 172. CiteSeerX 10.1.1.12.7323 . дои : 10.1145/224056.224070 . ISBN 978-0897917155 . S2CID 7834967 .
^ Jump up to: ^а ^б Петерсен, К.; Спрейцер, MJ; Терри, Д.Б.; Теймер, ММ; Демерс, Эй Джей (1997). «Гибкое распространение обновлений для слабосогласованной репликации». Обзор операционных систем ACM SIGOPS . 31 (5): 288. CiteSeerX 10.1.1.17.555 . дои : 10.1145/269005.266711 .
^ Притчетт, Д. (2008). «База: кислотная альтернатива» . Очередь . 6 (3): 48–55. дои : 10.1145/1394127.1394128 .
^ Бейлис, П.; Годси, А. (2013). «Возможная согласованность сегодня: ограничения, расширения и многое другое» . Очередь . 11 (3): 20. дои : 10.1145/2460276.2462076 .
^ Роу, Чарльз (март 2012 г.). «ACID против BASE: изменение pH обработки транзакций базы данных» . ДАННЫЕ . ДАТАВЕРСИТИ Образование, ООО . Проверено 29 августа 2019 г.
^ Ч Янив Пессах (2013), Распределенное хранилище (ред. Распределенное хранилище: концепции, алгоритмы и реализации), Amazon, OL 25423189M , Системы, использующие событийную согласованность, приводят к снижению нагрузки на систему и повышению ее доступности, но приводят к увеличению когнитивной сложности для пользователей и разработчиков.
^ Демерс, А.; Грин, Д.; Хаузер, К.; Ирландский, В.; Ларсон, Дж. (1987). «Эпидемические алгоритмы для обслуживания реплицируемых баз данных». Материалы шестого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '87 . п. 1. дои : 10.1145/41840.41841 . ISBN 978-0-89791-239-6 . S2CID 1889203 .
^ Рокфорд Лхотка. «Методы параллелизма». Архивировано 11 мая 2018 г. на Wayback Machine . 2003.
^ Оливье Малласси (9 июня 2010 г.). «Давайте поиграем с Кассандрой… (Часть 1/3)» . Окто-разговоры! . Проверено 23 марта 2011 г. Конечно, в определенный момент времени высока вероятность того, что каждый узел будет иметь свою версию данных. Разрешение конфликтов осуществляется во время запросов на чтение (так называемое восстановление чтения), и текущая версия Cassandra не предоставляет механизмы разрешения конфликтов Vector Clock [sic] (должны быть доступны в версии 0.7). Разрешение конфликтов основано на временной метке (той, которая устанавливается при вставке строки или столбца): за это отвечает более высокая временная метка win[s] и узел, из которого вы читаете данные. Это важный момент, поскольку отметка времени указывается клиентом в момент вставки столбца. Таким образом, все клиенты Cassandra должны быть синхронизированы...
^ Шапиро, Марк; Прегиса, Нуно; Бакеро, Карлос; Завирски, Марек (10 октября 2011 г.). «Бесконфликтные реплицируемые типы данных». SSS'11 Материалы 13-й Международной конференции по стабилизации, безопасности и защищенности распределенных систем . Springer-Verlag Berlin, Гейдельберг: 386–400.

Дальнейшее чтение

Буркхардт, Себастьян (9 октября 2014 г.). «Принципы эвентуальной согласованности» . Основы и тенденции в языках программирования . 1 (1–2): 1–150. дои : 10.1561/2500000011 . ISSN 2325-1107 .

[Vogels-1] Jump up to: ^а ^б Фогельс, В. (2009). «В конечном итоге последовательно» . Коммуникации АКМ . 52 : 40–44. дои : 10.1145/1435417.1435432 .

[2] Фогельс, В. (2008). «В конечном итоге согласованный» . Очередь . 6 (6): 14–19. дои : 10.1145/1466443.1466448 .

[Bayou-3] Jump up to: ^а ^б Терри, Д.Б.; Теймер, ММ; Петерсен, К.; Демерс, Эй Джей; Спрейцер, MJ; Хаузер, CH (1995). «Управление конфликтами обновлений в Bayou, слабосвязанной реплицируемой системе хранения». Материалы пятнадцатого симпозиума ACM по принципам операционных систем - СОСП '95 . п. 172. CiteSeerX 10.1.1.12.7323 . дои : 10.1145/224056.224070 . ISBN 978-0897917155 . S2CID 7834967 .

[Bayou-Conflicts-4] Jump up to: ^а ^б Петерсен, К.; Спрейцер, MJ; Терри, Д.Б.; Теймер, ММ; Демерс, Эй Джей (1997). «Гибкое распространение обновлений для слабосогласованной репликации». Обзор операционных систем ACM SIGOPS . 31 (5): 288. CiteSeerX 10.1.1.17.555 . дои : 10.1145/269005.266711 .

[5] Притчетт, Д. (2008). «База: кислотная альтернатива» . Очередь . 6 (3): 48–55. дои : 10.1145/1394127.1394128 .

[6] Бейлис, П.; Годси, А. (2013). «Возможная согласованность сегодня: ограничения, расширения и многое другое» . Очередь . 11 (3): 20. дои : 10.1145/2460276.2462076 .

[7] Роу, Чарльз (март 2012 г.). «ACID против BASE: изменение pH обработки транзакций базы данных» . ДАННЫЕ . ДАТАВЕРСИТИ Образование, ООО . Проверено 29 августа 2019 г.

[8] Ч Янив Пессах (2013), Распределенное хранилище (ред. Распределенное хранилище: концепции, алгоритмы и реализации), Amazon, OL 25423189M , Системы, использующие событийную согласованность, приводят к снижению нагрузки на систему и повышению ее доступности, но приводят к увеличению когнитивной сложности для пользователей и разработчиков.

[9] Демерс, А.; Грин, Д.; Хаузер, К.; Ирландский, В.; Ларсон, Дж. (1987). «Эпидемические алгоритмы для обслуживания реплицируемых баз данных». Материалы шестого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '87 . п. 1. дои : 10.1145/41840.41841 . ISBN 978-0-89791-239-6 . S2CID 1889203 .

[10] Рокфорд Лхотка. «Методы параллелизма». Архивировано 11 мая 2018 г. на Wayback Machine . 2003.

[Confront-11] Оливье Малласси (9 июня 2010 г.). «Давайте поиграем с Кассандрой… (Часть 1/3)» . Окто-разговоры! . Проверено 23 марта 2011 г. Конечно, в определенный момент времени высока вероятность того, что каждый узел будет иметь свою версию данных. Разрешение конфликтов осуществляется во время запросов на чтение (так называемое восстановление чтения), и текущая версия Cassandra не предоставляет механизмы разрешения конфликтов Vector Clock [sic] (должны быть доступны в версии 0.7). Разрешение конфликтов основано на временной метке (той, которая устанавливается при вставке строки или столбца): за это отвечает более высокая временная метка win[s] и узел, из которого вы читаете данные. Это важный момент, поскольку отметка времени указывается клиентом в момент вставки столбца. Таким образом, все клиенты Cassandra должны быть синхронизированы...

[12] Шапиро, Марк; Прегиса, Нуно; Бакеро, Карлос; Завирски, Марек (10 октября 2011 г.). «Бесконфликтные реплицируемые типы данных». SSS'11 Материалы 13-й Международной конференции по стабилизации, безопасности и защищенности распределенных систем . Springer-Verlag Berlin, Гейдельберг: 386–400.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]