292
правки
Изменения
CRDT
,Нет описания правки
[[Категория: Параллельное программирование]]
'''CRDT (Conflict-Free Replicated Data Type) — объект''' — типы данных, который которые можно реплицировать на много узлов и обновлять параллельно без координации между узлами.
== Модель ==Мы отслеживаем состояние некоторых '''данных'''.Всем узлам известно '''начальное состояние'''.На самом деле мы отслеживанием не состояние данных, а '''операцию''', которую надо применить к начальным данным, чтобы получить текущие. Нам требуется, чтобы операции образовывали '''полурешётку''' (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций.Более формально: для любых двух операций $a$, $b$, $c$ верно:# $a \wedge a = a$# $(a \wedge b) \wedge c = a \wedge (b \wedge c)$# $a \wedge b = b \wedge a$ Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием.Так как операции коммутативны, нам неважен порядок и не нужен total order.Так как операции идемпотентны, нам не нужна надёжная доставка (exactly once), достаточно at least once.Так что достаточно просто когда-нибудь как-нибудь услышать о проведённой операции, чтобы применить её к своему состоянию. А вот как построить такую полурешётку, чтобы было не больно пересылать — интересный вопрос, см. ниже. == Репликация на основе состояния'''(CRDT) ==
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д..
2. Обновления возрастают.
Реплика посылает не все состояние, а только обновление всем репликам. Согласованность можно гарантировать, если обновления коммутативны. Кроме того, требуется чтобы каждая операция была доставлена ровно один раз.
