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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 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$
  
 
Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием.
 
Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием.
Строка 20: Строка 20:
 
А вот как построить такую полурешётку, чтобы было не больно пересылать — интересный вопрос, см. ниже.
 
А вот как построить такую полурешётку, чтобы было не больно пересылать — интересный вопрос, см. ниже.
  
== Репликация на основе состояния (CRDT) ==
+
== Репликация на основе операций ==
  
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д..  
+
Данные: целочисленный счётчик.
  
Достаточные условия согласованности:
+
Операция: добавить $x$ к значению счётчика.
  
1. Множество возможных состояний образует полурешетку, т.е. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;
+
Эта операция коммутативна, но не идемпотентна.
 +
Поэтому добавим в каждой операции уникальный идентификатор.
  
2. Обновления возрастают.
+
Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций.
  
== Репликация на основе операций ==
+
Это обобщается: просто говорим, что операция — это множество операций, которые надо применить. У каждой операции есть время: пара из логических часов и номера процесса. Тогда, конечно, тяжёлое состояние и сложно получать реальные данные, зато работает.
 +
 
 +
== Репликация на основе состояния ==
 +
 
 +
Теперь данные хранятся как $n$ независимых счётчиков: по одному на каждый процесс.
 +
 
 +
Операция: установить компоненты в такие-то значения.
 +
 
 +
Объединение операций: покомпонентный максимум (коммутативно и идемпотентно).
  
Реплика посылает не все состояние, а только обновление всем репликам. Согласованность можно гарантировать, если обновления коммутативны. Кроме того, требуется чтобы каждая операция была доставлена ровно один раз.
+
Теперь у нас состояние не растёт со временем, а инкремент всё ещё можно делать: процесс увеличивает свой локальный счётчик и рассылает своё новое состояние всем.
  
 
== $\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.