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