Окончательная согласованность
 | Эта статья может быть слишком технической для понимания большинства читателей . ( январь 2017 г. ) |
Итоговая согласованность — это модель согласованности, используемая в распределенных вычислениях для достижения высокой доступности , которая неформально гарантирует, что, если к данному элементу данных не производится никаких новых обновлений, в конечном итоге все обращения к этому элементу будут возвращать последнее обновленное значение. [1] Окончательная согласованность, также называемая оптимистической репликацией . [2] широко применяется в распределенных системах и берет свое начало в ранних проектах мобильных вычислений. [3] О системе, достигшей конечной согласованности, часто говорят, что она конвергентна или достигла конвергенции реплик . [4] Окончательная непротиворечивость является слабой гарантией: большинство более сильных моделей, таких как линеаризуемость , тривиально в конечном итоге непротиворечивы.
Службы, согласованные в конечном итоге, часто классифицируются как обеспечивающие семантику BASE (базовая доступность, мягкое состояние, конечная согласованность), в отличие от традиционных ACID (атомарность, согласованность, изоляция, надежность) . [5] [6] В химии основание является противоположностью кислоты, что помогает запомнить аббревиатуру. [7] Согласно тому же ресурсу, вот приблизительные определения каждого термина в BASE:
- В принципе доступно : операции чтения и записи доступны в максимально возможной степени (с использованием всех узлов кластера базы данных), но могут быть несогласованными (запись может не сохраняться после разрешения конфликтов, а операция чтения может не получить последнюю запись)
- Мягкое состояние : без гарантий согласованности через некоторое время у нас есть только некоторая вероятность узнать состояние, поскольку оно, возможно, еще не сошлось.
- В конечном итоге согласованный : если мы выполним несколько операций записи, а затем система будет работать достаточно долго, мы сможем узнать состояние данных; любые дальнейшие чтения этого элемента данных будут возвращать то же значение
Окончательная последовательность иногда подвергается критике. [8] как увеличение сложности распределенных программных приложений. Частично это связано с тем, что конечная согласованность — это просто гарантия жизнеспособности (чтения в конечном итоге возвращают одно и то же значение) и не гарантирует безопасность : окончательно согласованная система может возвращать любое значение до того, как оно сходится.
Разрешение конфликтов [ править ]
Чтобы обеспечить конвергенцию реплик, система должна согласовывать различия между несколькими копиями распределенных данных. Он состоит из двух частей:
- обмен версиями или обновлениями данных между серверами (часто известный как антиэнтропия ); [9] и
- выбор подходящего конечного состояния при возникновении одновременных обновлений, называемого согласованием .
Наиболее подходящий подход к согласованию зависит от приложения. Распространенный подход - «побеждает последний писатель». [1] Другой вариант — вызвать указанный пользователем обработчик конфликтов. [4] Временные метки и векторные часы часто используются для обнаружения параллелизма между обновлениями. Некоторые люди используют фразу «побеждает первый автор» в ситуациях, когда фраза «побеждает последний автор» неприемлема. [10]
Согласование одновременных записей должно произойти за какое-то время до следующего чтения и может быть запланировано на разные моменты времени: [3] [11]
- Восстановление чтения: исправление выполняется, когда при чтении обнаруживается несоответствие. Это замедляет операцию чтения.
- Восстановление записи: исправление происходит во время операции записи, что замедляет операцию записи.
- Асинхронное восстановление: исправление не является частью операции чтения или записи.
конечная согласованность Сильная
В то время как итоговая согласованность является лишь гарантией жизнеспособности (со временем обновления будут наблюдаться), строгая итоговая согласованность (SEC) добавляет гарантию безопасности , согласно которой любые два узла, получившие одинаковый (неупорядоченный) набор обновлений, будут находиться в одном и том же состоянии. Кроме того, если система монотонна , приложение никогда не будет подвергаться откатам. Распространенный подход к обеспечению SEC — бесконфликтные реплицируемые типы данных . [12]
См. также [ править ]
Ссылки [ править ]
- ^ Перейти обратно: а б Фогельс, В. (2009). «В конечном итоге последовательно» . Коммуникации АКМ . 52 : 40–44. дои : 10.1145/1435417.1435432 .
- ^ Фогельс, В. (2008). «В конечном итоге согласованный» . Очередь . 6 (6): 14–19. дои : 10.1145/1466443.1466448 .
- ^ Перейти обратно: а б Терри, Д.Б.; Теймер, ММ; Петерсен, К.; Демерс, Эй Джей; Спрейцер, MJ; Хаузер, CH (1995). «Управление конфликтами обновлений в Bayou, слабосвязанной реплицируемой системе хранения». Материалы пятнадцатого симпозиума ACM по принципам операционных систем - СОСП '95 . п. 172. CiteSeerX 10.1.1.12.7323 . дои : 10.1145/224056.224070 . ISBN 978-0897917155 . S2CID 7834967 .
- ^ Перейти обратно: а б Петерсен, К.; Спрейцер, 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 .