CRDT

CRDT (Conflict-Free Replicated Data Type) — типы данных, которые можно реплицировать на много узлов и обновлять параллельно без координации между узлами.

Модель

Мы отслеживаем состояние некоторых данных. Всем узлам известно начальное состояние. На самом деле мы отслеживанием не состояние данных, а операцию, которую надо применить к начальным данным, чтобы получить текущие.

Нам требуется, чтобы операции образовывали полурешётку (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций. Более формально: для любых двух операций $a$, $b$, $c$ верно:

1. $a \wedge a = a$
2. $(a \wedge b) \wedge c = a \wedge (b \wedge c)$
3. $a \wedge b = b \wedge a$

Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием. Так как операции коммутативны, нам неважен порядок и не нужен total order. Так как операции идемпотентны, нам не нужна надёжная доставка (exactly once), достаточно at least once. Так что достаточно просто когда-нибудь как-нибудь услышать о проведённой операции, чтобы применить её к своему состоянию.

А вот как построить такую полурешётку, чтобы было не больно пересылать — интересный вопрос, см. ниже.

Репликация на основе операций

Данные: целочисленный счётчик.

Операция: добавить $x$ к значению счётчика.

Эта операция коммутативна, но не идемпотентна. Поэтому добавим в каждой операции уникальный идентификатор.

Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций.

Репликация на основе состояния

Теперь данные хранятся как $n$ независимых счётчиков: по одному на каждый процесс.

Операция: установить компоненты в такие-то значения.

Объединение операций: покомпонентный максимум (коммутативно и идемпотентно).

Теперь у нас состояние не растёт со временем, а инкремент всё ещё можно делать: процесс увеличивает свой локальный счётчик и рассылает своё новое состояние всем.