CRDT — различия между версиями
Yeputons (обсуждение | вклад) |
Yeputons (обсуждение | вклад) (→$\delta$-CRDT) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 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: | Строка 22: | ||
== Репликация на основе операций == | == Репликация на основе операций == | ||
| − | + | Данные: целочисленный счётчик. | |
| − | + | Операция: добавить $x$ к значению счётчика. | |
| − | + | Эта операция коммутативна, но не идемпотентна. | |
| + | Поэтому добавим в каждой операции уникальный идентификатор. | ||
| − | + | Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций. | |
| − | + | Это обобщается: просто говорим, что операция — это множество операций, которые надо применить. У каждой операции есть время: пара из логических часов и номера процесса. Тогда, конечно, тяжёлое состояние и сложно получать реальные данные, зато работает. | |
| − | + | == Репликация на основе состояния == | |
| + | |||
| + | Теперь данные хранятся как $n$ независимых счётчиков: по одному на каждый процесс. | ||
| + | |||
| + | Операция: установить компоненты в такие-то значения. | ||
| + | |||
| + | Объединение операций: покомпонентный максимум (коммутативно и идемпотентно). | ||
| + | |||
| + | Теперь у нас состояние не растёт со временем, а инкремент всё ещё можно делать: процесс увеличивает свой локальный счётчик и рассылает своё новое состояние всем. | ||
== $\delta$-CRDT == | == $\delta$-CRDT == | ||
| + | |||
| + | Оптимизация CRDT: отсылаем не весь вектор, а только изменения в этом векторе: установить такую-то компоненту в такое-то значение. | ||
| + | |||
| + | То есть у нас теперь есть не только операции, но и "кусочки операций", которые надо не только уметь применять, но ещё и склеивать между собой. | ||
| + | |||
| + | Относится к обоим видам CRDT. | ||
Версия 22:31, 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: отсылаем не весь вектор, а только изменения в этом векторе: установить такую-то компоненту в такое-то значение.
То есть у нас теперь есть не только операции, но и "кусочки операций", которые надо не только уметь применять, но ещё и склеивать между собой.
Относится к обоим видам CRDT.
