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

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