CRDT

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

Модель

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

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

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

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

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

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

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

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

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

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

Это обобщается: просто говорим, что операция — это множество операций, которые надо применить. У каждой операции есть время: пара из логических часов и номера процесса. Тогда, конечно, тяжёлое состояние и сложно получать реальные данные, зато работает.

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

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

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

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

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

$\delta$-CRDT

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

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

Относится к обоим видам CRDT.