- PVSM.RU - https://www.pvsm.ru -
Как считать хиты страницы google.com? А как хранить счётчик лайков очень популярных пользователей? В этой статье предлагается рассмотреть решение этих задач с помощью CRDT (Conflict-free Replicated Data Types, что по-русски переводится примерно как Бесконфликтные реплицированные типы данных), а в более общем случае — задачи синхронизации реплик в распределённой системе с несколькими ведущими узлами.
Мы уже давно привыкли пользоваться такими приложениями, как календарь или сервис заметок типа Evernote. Их объединяет то, что они позволяют работать оффлайн, с нескольких устройств и нескольким людям одновременно (над одними и теми же данными). Задача, стоящая перед разработчиками каждого такого приложения — как обеспечить максимально «гладкую» синхронизацию данных, изменённых одновременно на нескольких устройствах. В идеале участие пользователя не должно требоваться вообще для разрешения конфликтов слияния.
В предыдущей статье [1] уже был рассмотрен подход для решения таких задач — Operational Transformation, здесь же будет описан очень похожий способ, обладающий как преимуществами, так и недостатками (например, пока ещё не придумали CRDT для JSON)
В последнее время было написано много работ и сделано много исследований в области eventual consistency. По моему мнению, сейчас идёт сильный тренд на смещение от strong consistency к различным вариантам согласованности, к исследованиям какую согласованность в каких ситуациях/системах выгоднее применять, к переосмыслению существующих определений. Это приводит к некоторой путанице, например, когда авторы одних работ, рассуждая о согласованности, имеют в виду eventual consistency с некоторым дополнительным свойством, а другие авторы используют определённую терминологию для этого.
Вопрос, поднятый авторами одной из статей, критикует текущее определение eventual consistency: согласно ему, если ваша система всё время на все запросы выдаёт ответ «42», то всё ОК, она eventually consistent.
Не нарушая корректности данной статьи, я, вслед за авторами оригинальных статей, буду использовать следующую терминологию (пожалуйста заметьте, это не строгие определения, это различия):
Заметим, что SEC (как бы) решает проблему CAP теоремы: все три свойства выполняются.
Итак, мы готовы пожертвовать SC и хотим иметь некий набор базовых типов данных для нашей потенциально нестабильной распределённой системы, который будет автоматически разрешать конфликты записи за нас (не требуется взаимодействие с пользователем или запрос в некий арбитр)
Несомненно, существует несколько алгоритмов решения таких задач. CRDT предлагает довольно элегантный и простой способ.
google.com обрабатывает примерно 150000 запросов в секунду со всех точек планеты. Очевидно, счётчик нужно обновлять асинхронно. Очереди решают проблему частично — например, если мы предоставляем внешний API для получения этого значения, то нам придётся делать репликацию, чтобы не положить хранилище запросами на чтение. А если уже есть репликация, может можно и без глобальных очередей?
Задача очень похожа на предыдущую, только теперь нужно считать уникальные хиты.
Для более полного понимания статьи необходимо знать о следующих терминах:
Также называется пассивной синхронизацией, образует Convergent Replicated Data Type — CvRDT.
Используется в таких файловых системах, как NFS, AFS, Coda и в KV-хранилищах Riak, Dynamo
В этом случае реплики обмениваются непосредственно состояниями, принимающая реплика сливает (merge) полученное состояние со своим текущим состоянием.
Для выполнения сходимости реплик с использованием данной синхронизации необходимо, чтобы:
Пример:
Такие требования дают нам коммутативную и идемпотентную функцию слияния, которая монотонно растёт на заданном множестве данных:
Это гарантирует, что реплики рано или поздно сойдутся и позволяет не беспокоится о протоколе передачи данных — мы можем терять сообщения с новым состоянием, отправлять их несколько раз, и даже отправлять в любом порядке.
Также называется активной синхронизацией, образует Commutative Replicated Data Type — CmRDT.
Используется в таких кооперативных системах, как Bayou, Rover, IceCube, Telex.
В этом случае реплики обмениваются операциями обновления состояния. При обновлении данных исходная реплика:
Для выполнения сходимости реплик необходимо выполнение следующих условий:
Рассматривая state/op based легко заметить, что если обновление изменяет только часть состояния, то нет смысла пересылать состояние целиком, а также если большое количество изменений затрагивает одно состояние (например, счётчик), то можно выслать одно, агрегированное изменение, а не все операции изменения.
Дельта-синхронизация объединяет в себе оба подхода и рассылает delta-mutators, которые обновляют состояние согласно последней даты синхронизации. При первоначальной синхронизации необходимо выслать состояние полностью, а некоторые реализации в таких случаях уже учитывают состояние остальных реплик при построении delta-mutators.
Следующий способ оптимизации — компрессия op-based лога, если разрешены задержки.
В op-based синхронизации присутствует задержка на создание effector. В некоторых системах это может быть неприемлемо, тогда приходится рассылать оригинальное изменение ценой усложнения протокола и дополнительного количества метаданных.
1) Накатить все пропущенные операции с момента отказа
2) Полная копия одной из реплик и накат пропущенных операций
Два подхода можно эмулировать друг через друга, так что в дальнейшем мы будем рассматривать CRDT без привязки к какой-либо конкретной модели синхронизации.
Целое число с поддержкой двух операций: inc и dec. В качестве примера рассмотрим возможные реализации для op-based и state-based синхронизаций:
Достаточно очевидно, просто рассылаем обновления. Пример для inc:
function generator() { return function (counter) { counter += 1 } }
Реализация уже не настолько очевидна, так как непонятно, как должна выглядеть функция слияния.
Рассмотрим следующие варианты:
Монотонно увеличивающийся счётчик (Increment only counter, G-Counter):
Данные будут храниться как вектор размерности равной количеству нод (вектор версий) и каждая реплика будет увеличивать значение в позиции со своим id.
Функция слияния будет брать максимум в соответствующих позициях, а итоговое значение — сумма всех элементов вектора
Также можно использовать G-Set (см ниже)
Применение:
Счётчик с поддержкой декремента (PN-counter)
Заводим два G-counter — один для операций инкремента, второй — для декремента
Применение:
Неотрицательный счётчик (Non-negative counter)
Простой реализации пока не существует. Предлагайте в комментариях ваши идеи, обсудим.
Ячейка памяти с двумя операциями — assign (запись) и value (чтение).
Проблема — assign не коммутативна. Существует два подхода для решения этой проблемы:
Вводим полный порядок через генерацию уникальных id на каждую операцию (timestamp, например).
Пример синхронизирования — обмен парами (значение, id):
Применение:
Подход похож на G-счётчик — храним набор (значение, вектор версий). Значение регистра — все значения, при слиянии — LWW по отдельности на каждое значение в векторе.
Применение:
Объяснение бага в амазоне:
Множество является базовым типом для построения контейнеров, отображений и графов и поддерживает операции — add и rmv, которые не коммутативны.
Рассмотрим наивную реализацию op-based множества, в которой add и rmv выполняются по мере поступления (На 1 и 2 реплику одновременно приходит add, затем rmv на 1)
Как видно, в конечном итоге реплики разошлись. Рассмотрим различные варианты построения бесконфликтных множеств:
Самое простое решение — запретить удалять элементы. Остаётся только операция add, которая коммутативна. Функция слияния — объединение множеств.
Разрешаем удалять, но после удаления добавить ещё раз нельзя. Для реализации заводим отдельное множество удалённых элементов G-set (такое множество называется tombstone set)
Пример для state-based:
Следующий способ реализации бесконфликтного множества состоит во введении полного порядка, один из вариантов — генерация уникальных timestamp для каждого элемента.
Заводим два множества — add-set и remove-set, при вызове add() добавляем (element, unique_id()), при проверке есть ли элемент в множестве — смотрим где timestamp больше — в remove-set или в add-set
Вариация с упорядочиванием множества — на каждый элемент заводим счётчик, при добавлении — увеличиваем, при удалении — уменьшаем. Элемент находится в множестве, если его счётчик положителен.
Заметьте интересный эффект — в третьей реплике добавление элемента не приводит к его появлению.
В данном типе add имеет приоритет над remove. Пример реализации: каждому новому добавленному элементу присваиваем уникальный тэг (относительно элемента, а не всего множества). Rmv удаляет элемент из множества и рассылает все увиденные пары (элемент, тэг) на удаление репликам.
Аналогично предыдущему, но при одновременном add/rmv выигрывает rmv.
Данный тип строится на основе множества. Проблема состоит в следующем: если есть одновременные операции addEdge(u, v) и removeVertex(u) — как поступить? Возможны такие варианты:
Самый простой вариант — первый, для его реализации (2P2P-Graph) достаточно завести два 2P-Set, один для вершин, второй для ребёр
Две проблемы, требующие решения:
Более интересный случай, т.к. позволяет строить вложенные отображения. Мы не рассматриваем случаи изменения вложенных типов — это должно решаться самим вложенным CRDT.
Remove-as-recursive-reset map
Операция remove “сбрасывает” значение типа в некое стартовое состояние. Например, для счётчика — это нулевое значение.
Рассмотрим пример — общий список покупок. Один из пользователей добавляет муки, а второй делает чекаут (это приводит к вызову операции удаления на всех элементах). В итоге в списке остаётся одна единица муки, что выглядит логичным.
Remove-wins map
Операция rmv имеет приоритет.
Пример: в онлайн-игре у игрока Alice есть 10 монет и молоток. Далее одновременно происходит два события: на реплике А она добыла гвоздь, а на реплике В её персонаж удалён с удалением всех предметов:
Заметим, что при использовании remove-as-recursive в итоге остался бы гвоздь, что не является правильным состоянием, когда персонаж удалён.
Update-wins map
Обновления имеют приоритет, а точнее — отменяют предыдущие операции удаления одновременных rmv.
Пример: в онлайн игре персонаж Alice на реплике В удаляется из-за неактивности, но в это же время на реплике А активность происходит. Очевидно, операция удаления должна быть отменена.
Есть один интересный эффект при работе с такой реализацией — предположим, что у нас две реплики, А и В, и они хранят множество по какому-то ключу k. Тогда, если А удаляет значение ключа k, а В удаляет все элементы множества, то в итоге в репликах останется пустое множество по ключу k.
Заметим, что наивная реализация будет работать некорректно — нельзя просто отменить все предыдущие операции удаления. В следующем примере при таком подходе итоговое состояние было бы как изначальное, что неверно:
Проблема с этим типом состоит в том, что индексы элементов на различных репликах будут различными после локальный операций вставок/удаления. Для решения этой проблемы применяется Operational Transformation подход — при применении полученного изменения должен учитываться индекс элемента в оригинальной реплике.
В качестве примера рассмотрим CRDT в Riak:
Раздел в вики [7] содержит хорошие примеры
Автор: amberovsky
Источник [18]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/287906
Ссылки в тексте:
[1] предыдущей статье: https://habr.com/post/416961/
[2] Идемпотентность: https://ru.wikipedia.org/wiki/%D0%98%D0%B4%D0%B5%D0%BC%D0%BF%D0%BE%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C
[3] Коммутативность: https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BC%D1%83%D1%82%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D1%8F
[4] Частичный порядок: https://ru.wikipedia.org/wiki/%D0%A7%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%BD%D0%BE_%D1%83%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE
[5] Полурешётка: https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D1%83%D1%80%D0%B5%D1%88%D1%91%D1%82%D0%BA%D0%B0
[6] Вектор версий: https://en.wikipedia.org/wiki/Version_vector
[7] вики: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type#Industry_use
[8] Key-CRDT Stores: https://run.unl.pt/bitstream/10362/7802/1/Sousa_2012.pdf
[9] A Conflict-Free Replicated JSON Datatype: https://arxiv.org/abs/1608.03960
[10] A comprehensive study of Convergent and Commutative Replicated Data Types: https://hal.inria.fr/inria-00555588/document
[11] Convergent and Commutative Replicated Data Type: https://core.ac.uk/download/pdf/55634119.pdf
[12] Conflict-free replicated data type: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
[13] A Bluffers Guide to CRDTs in Riak: https://gist.github.com/russelldb/f92f44bdfb619e089a4d
[14] CRDTs: An UPDATE (or just a PUT): https://speakerdeck.com/lenary/crdts-an-update-or-just-a-put?slide=8
[15] Conflict-free Replicated Data Types: An Overview: https://arxiv.org/pdf/1806.10254.pdf
[16] Strong Eventual Consistency and Conflict-free Replicated Data Types: https://www.youtube.com/watch?v=oyUHd894w18
[17] Eventually-Consistent Data Structures: https://www.infoq.com/presentations/CRDT
[18] Источник: https://habr.com/post/418897/?utm_campaign=418897
Нажмите здесь для печати.