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$ к значению счётчика.
Эта операция коммутативна, но не идемпотентна. Поэтому добавим в каждой операции уникальный идентификатор.
Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций.
Репликация на основе состояния
Теперь данные хранятся как $n$ независимых счётчиков: по одному на каждый процесс.
Операция: установить компоненты в такие-то значения.
Объединение операций: покомпонентный максимум (коммутативно и идемпотентно).
Теперь у нас состояние не растёт со временем, а инкремент всё ещё можно делать: процесс увеличивает свой локальный счётчик и рассылает своё новое состояние всем.
$\delta$-CRDT
Оптимизация CRDT на основе состояния: отсылаем не весь вектор, а только изменения в этом векторе: установить такую-то компоненту в такое-то значение.
