CRDT — различия между версиями
Yeputons (обсуждение | вклад) (→$\delta$-CRDT) |
Yeputons (обсуждение | вклад) (→Модель) |
||
| Строка 9: | Строка 9: | ||
Нам требуется, чтобы операции образовывали '''полурешётку''' (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций. | Нам требуется, чтобы операции образовывали '''полурешётку''' (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций. | ||
Более формально: для любых двух операций $a$, $b$, $c$ верно: | Более формально: для любых двух операций $a$, $b$, $c$ верно: | ||
| − | # $a \ | + | # $a \sqcup a = a$ |
| − | # $(a \ | + | # $(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$ |
| − | # $a \ | + | # $a \sqcup b = b \sqcup a$ |
Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием. | Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием. | ||
Версия 22:26, 3 июня 2019
CRDT (Conflict-Free Replicated Data Type) — типы данных, которые можно реплицировать на много узлов и обновлять параллельно без координации между узлами.
Содержание
Модель
Мы отслеживаем состояние некоторых данных. Всем узлам известно начальное состояние. На самом деле мы отслеживанием не состояние данных, а операцию, которую надо применить к начальным данным, чтобы получить текущие.
Нам требуется, чтобы операции образовывали полурешётку (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций. Более формально: для любых двух операций $a$, $b$, $c$ верно:
- $a \sqcup a = a$
- $(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$
- $a \sqcup b = b \sqcup a$
Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием. Так как операции коммутативны, нам неважен порядок и не нужен total order. Так как операции идемпотентны, нам не нужна надёжная доставка (exactly once), достаточно at least once. Так что достаточно просто когда-нибудь как-нибудь услышать о проведённой операции, чтобы применить её к своему состоянию.
А вот как построить такую полурешётку, чтобы было не больно пересылать — интересный вопрос, см. ниже.
Репликация на основе операций
Данные: целочисленный счётчик.
Операция: добавить $x$ к значению счётчика.
Эта операция коммутативна, но не идемпотентна. Поэтому добавим в каждой операции уникальный идентификатор.
Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций.
Репликация на основе состояния
Теперь данные хранятся как $n$ независимых счётчиков: по одному на каждый процесс.
Операция: установить компоненты в такие-то значения.
Объединение операций: покомпонентный максимум (коммутативно и идемпотентно).
Теперь у нас состояние не растёт со временем, а инкремент всё ещё можно делать: процесс увеличивает свой локальный счётчик и рассылает своё новое состояние всем.
$\delta$-CRDT
Оптимизация CRDT на основе состояния: отсылаем не весь вектор, а только изменения в этом векторе: установить такую-то компоненту в такое-то значение.
То есть у нас теперь есть не только операции, но и "кусочки операций", которые надо не только уметь применять, но ещё и склеивать между собой.
