CRDT — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Репликация на основе состояния (CRDT))
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 2 участников)
Строка 9: Строка 9:
 
Нам требуется, чтобы операции образовывали '''полурешётку''' (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций.
 
Нам требуется, чтобы операции образовывали '''полурешётку''' (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций.
 
Более формально: для любых двух операций $a$, $b$, $c$ верно:
 
Более формально: для любых двух операций $a$, $b$, $c$ верно:
# $a \wedge a = a$
+
# $a \sqcup a = a$
# $(a \wedge b) \wedge c = a \wedge (b \wedge c)$
+
# $(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$
# $a \wedge b = b \wedge a$
+
# $a \sqcup b = b \sqcup a$
  
 
Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием.
 
Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием.
Строка 30: Строка 30:
  
 
Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций.
 
Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций.
 +
 +
Это обобщается: просто говорим, что операция — это множество операций, которые надо применить. У каждой операции есть время: пара из логических часов и номера процесса. Тогда, конечно, тяжёлое состояние и сложно получать реальные данные, зато работает.
  
 
== Репликация на основе состояния ==
 
== Репликация на основе состояния ==
Строка 42: Строка 44:
  
 
== $\delta$-CRDT ==
 
== $\delta$-CRDT ==
 +
 +
Оптимизация CRDT: отсылаем не весь вектор, а только изменения в этом векторе: установить такую-то компоненту в такое-то значение.
 +
 +
То есть у нас теперь есть не только операции, но и "кусочки операций", которые надо не только уметь применять, но ещё и склеивать между собой.
 +
 +
Относится к обоим видам CRDT.

Текущая версия на 19:44, 4 сентября 2022

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.