CRDT
CRDT (Conflict-Free Replicated Data Type) — типы данных, которые можно реплицировать на много узлов и обновлять параллельно без координации между узлами.
Модель
Мы отслеживаем состояние некоторых данных. Всем узлам известно начальное состояние. На самом деле мы отслеживанием не состояние данных, а операцию, которую надо применить к начальным данным, чтобы получить текущие.
Нам требуется, чтобы операции образовывали полурешётку (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций. Более формально: для любых двух операций $a$, $b$, $c$ верно:
- $a \wedge a = a$
- $(a \wedge b) \wedge c = a \wedge (b \wedge c)$
- $a \wedge b = b \wedge a$
Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием. Так как операции коммутативны, нам неважен порядок и не нужен total order. Так как операции идемпотентны, нам не нужна надёжная доставка (exactly once), достаточно at least once. Так что достаточно просто когда-нибудь как-нибудь услышать о проведённой операции, чтобы применить её к своему состоянию.
А вот как построить такую полурешётку, чтобы было не больно пересылать — интересный вопрос, см. ниже.
Репликация на основе операций
Данные: целочисленный счётчик.
Операция: добавить $x$ к значению счётчика.
Эта операция коммутативна, но не идемпотентна. Поэтому добавим в каждой операции уникальный идентификатор.
Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций.
Репликация на основе состояния (CRDT)
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д..
Достаточные условия согласованности:
1. Множество возможных состояний образует полурешетку, т.е. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;
2. Обновления возрастают.
