Конечная согласованность - это модель согласованности, используемая в распределенных вычислениях для достижения высокой доступности, которая неформально гарантирует, что, если не будут сделаны новые обновления для данного элемента данных, в конечном итоге все обращения к этому элементу вернут последнее обновленное значение. [1] Конечная согласованность, также называемая оптимистической репликацией , [2] широко применяется в распределенных системах и берет свое начало в ранних проектах мобильных вычислений. [3] Система, которая достигла конечной согласованности, часто называется конвергентной или достигла сходимости реплик . [4]Конечная согласованность является слабой гарантией: большинство более сильных моделей, таких как линеаризуемость , тривиально в конечном итоге согласованы, но система, которая просто в конечном итоге является согласованной, обычно не удовлетворяет этим более строгим ограничениям.
Согласованные в конечном итоге сервисы часто классифицируются как предоставляющие семантику BASE (базовая доступность, мягкое состояние, конечная согласованность), в отличие от традиционных гарантий ACID (атомарность, согласованность, изоляция, долговечность) . [5] [6] В химии BASE противоположна ACID, что помогает запоминать аббревиатуру. [7] Согласно тому же источнику, это приблизительные определения каждого термина в BASE:
- В основном доступны: базовые операции чтения и записи доступны в максимально возможной степени (с использованием всех узлов кластера базы данных), но без каких-либо гарантий согласованности (запись может не сохраняться после разрешения конфликтов, чтение может не получить последнюю запись )
- Мягкое состояние: без гарантий согласованности по прошествии некоторого времени у нас есть только некоторая вероятность узнать состояние, так как оно, возможно, еще не сошлось
- В конечном итоге согласованный: если система работает, и мы ждем достаточно долго после любого заданного набора входных данных, мы в конечном итоге сможем узнать, каково состояние базы данных, и поэтому любые дальнейшие чтения будут соответствовать нашим ожиданиям.
Конечная согласованность иногда критикуется [8] как увеличение сложности распределенных программных приложений. Отчасти это связано с тем, что конечная согласованность является чистой гарантией жизнеспособности (чтение в конечном итоге возвращает то же значение) и не дает гарантий безопасности : в конечном итоге согласованная система может возвращать любое значение до того, как оно сойдется.
Решение конфликта
Чтобы гарантировать конвергенцию реплик, система должна согласовывать различия между несколькими копиями распределенных данных. Он состоит из двух частей:
- обмен версиями или обновлениями данных между серверами (часто известный как антиэнтропия ); [9] и
- выбор подходящего конечного состояния при одновременных обновлениях, называемый согласованием .
Наиболее подходящий подход к сверки зависит от приложения. Распространенный подход - «побеждает последний писатель» . [1] Другой способ - вызвать указанный пользователем обработчик конфликтов. [4] Метки времени и векторные часы часто используются для обнаружения параллелизма между обновлениями. Некоторые люди используют «первый писатель побеждает» в ситуациях, когда «последний писатель побеждает» недопустимо. [10]
Согласование одновременных записей должно происходить где-то перед следующим чтением и может быть запланировано в разные моменты: [3] [11]
- Исправление при чтении: исправление выполняется, когда при чтении обнаруживается несоответствие. Это замедляет операцию чтения.
- Исправление записи: исправление происходит во время операции записи, если обнаружено несоответствие, что замедляет операцию записи.
- Асинхронное восстановление: исправление не является частью операции чтения или записи.
Сильная конечная согласованность
В то время как конечная согласованность - это только гарантия живучести (обновления будут наблюдаться в конечном итоге), строгая конечная согласованность (SEC) добавляет гарантию безопасности, что любые два узла, получившие один и тот же (неупорядоченный) набор обновлений, будут в одном и том же состоянии. Если к тому же система монотонна , откаты приложения не будут. Бесконфликтные реплицированные типы данных - распространенный подход к обеспечению SEC. [12]
Смотрите также
Рекомендации
- ^ a b Фогельс, W. (2009). «В конечном итоге последовательный» . Коммуникации ACM . 52 : 40. DOI : 10,1145 / 1435417,1435432 .
- ^ Фогельс, В. (2008). «В конечном итоге согласованный» . Очередь . 6 (6): 14. DOI : 10,1145 / 1466443,1466448 .
- ^ а б Терри, DB; Таймер, ММ; Петерсен, К .; Демерс, AJ; Spreitzer, MJ; Хаузер, CH (1995). «Управление конфликтами обновлений в Bayou, слабосвязанной реплицированной системе хранения». Материалы пятнадцатого симпозиума ACM по принципам операционных систем - SOSP '95 . п. 172. CiteSeerX 10.1.1.12.7323 . DOI : 10.1145 / 224056.224070 . ISBN 978-0897917155.
- ^ а б Петерсен, К .; Spreitzer, MJ; Терри, DB; Таймер, ММ; Демерс, AJ (1997). «Гибкое распространение обновлений для слабосогласованной репликации». Обзор операционных систем ACM SIGOPS . 31 (5): 288. CiteSeerX 10.1.1.17.555 . DOI : 10.1145 / 269005.266711 .
- ^ Притчетт, Д. (2008). «Основание: кислотная альтернатива» . Очередь . 6 (3): 48–55. DOI : 10.1145 / 1394127.1394128 .
- ^ Bailis, P .; Годси, А. (2013). «Возможная согласованность сегодня: ограничения, расширения и не только» . Очередь . 11 (3): 20. DOI : 10,1145 / 2460276,2462076 .
- ^ Роу, Чарльз. «КИСЛОТА против ОСНОВАНИЯ: изменение pH обработки транзакций базы данных» . ДАТАВЕРСИЯ . ДАТАВЕРСИТИ Образование, ООО . Проверено 29 августа 2019 .
- ^ HЯнив Пессач (2013), Распределенное хранилище (Распределенное хранилище: концепции, алгоритмы и реализации, ред.), Amazon, OL 25423189M ,
Системы, использующие
конечную согласованность ,приводят к снижению нагрузки на систему и повышению доступности системы, но приводят к увеличению когнитивной сложности для пользователей и разработчиков
- ^ Демерс, А .; Greene, D .; Hauser, C .; Ирландский, W .; Ларсон, Дж. (1987). «Эпидемические алгоритмы обслуживания реплицированных баз данных». Материалы шестого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '87 . п. 1. дои : 10,1145 / 41840,41841 . ISBN 978-0-89791-239-6.
- ^ Рокфорд Lhotka. «Методы параллелизма» . 2003 г.
- ^ Оливье Малласси (09.06.2010). «Давай поиграем с Кассандрой… (Часть 1/3)» . http://blog.octo.com/en/ : OCTO Talks! . Проверено 23 марта 2011 .
Конечно, в данный момент высока вероятность того, что каждый узел будет иметь свою собственную версию данных. Разрешение конфликтов выполняется во время запросов чтения (называемых чтением-восстановлением), а текущая версия Cassandra не предоставляет механизмов разрешения конфликтов векторных часов [sic] (должен быть доступен в версии 0.7). Разрешение конфликтов основано на временной метке (той, которая устанавливается при вставке строки или столбца): за это отвечает более высокая временная метка win [s] и узел, из которого вы читаете данные. Это важный момент, потому что метка времени указывается клиентом в момент вставки столбца. Таким образом, все клиенты Cassandra должны быть синхронизированы ...
- ^ Шапиро, Марк; Прегуиса, Нуно; Бакеро, Карлос; Завирски, Марек (10.10.2011). «Бесконфликтные реплицированные типы данных». SSS'11 Труды 13-й Международной конференции по стабилизации, безопасности и защищенности распределенных систем . Springer-Verlag Berlin, Гейдельберг: 386–400.