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

Модель согласованности, используемая в распределенных вычислениях для достижения высокой доступности.

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

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

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

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

Решение конфликта

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

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

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

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

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

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

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

Смотрите также

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

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

1. Фогельс, В. (2009). «В конце концов последовательно». Коммуникации АКМ . 52 : 40–44. дои : 10.1145/1435417.1435432 .
2. Фогельс, В. (2008). «В конечном итоге согласованный». Очередь . 6 (6): 14–19. дои : 10.1145/1466443.1466448 .
3. Терри, Д.Б.; Теймер, ММ; Петерсен, К.; Демерс, Эй Джей; Спрейцер, MJ; Хаузер, CH (1995). «Управление конфликтами обновлений в Bayou, слабосвязанной реплицируемой системе хранения». Материалы пятнадцатого симпозиума ACM по принципам операционных систем - СОСП '95 . п. 172. CiteSeerX 10.1.1.12.7323 . дои : 10.1145/224056.224070. ISBN  978-0897917155. S2CID  7834967.
4. Петерсен, К.; Спрейцер, 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. H Янив Песах (2013), Распределенное хранилище (Распределенное хранилище: концепции, алгоритмы и реализации, ред.), Amazon, OL  25423189M, Системы, использующие событийную согласованность, приводят к снижению нагрузки на систему и повышению ее доступности, но приводят к увеличению когнитивной сложности для пользователей. и разработчики
9. Демерс, А.; Грин, Д.; Хаузер, К.; Ирландский, В.; Ларсон, Дж. (1987). «Эпидемические алгоритмы для обслуживания реплицируемых баз данных». Материалы шестого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '87 . п. 1. дои : 10.1145/41840.41841. ISBN 978-0-89791-239-6. S2CID  1889203.
10. Рокфорд Лхотка. «Техники параллелизма». 2003.
11. Оливье Малласси (09.06.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.