292
правки
Изменения
CRDT
,→$\delta$-CRDT
Нам требуется, чтобы операции образовывали '''полурешётку''' (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций.
Более формально: для любых двух операций $a$, $b$, $c$ верно:
# $a \wedge sqcup a = a$# $(a \wedge sqcup b) \wedge sqcup c = a \wedge sqcup (b \wedge sqcup c)$# $a \wedge sqcup b = b \wedge sqcup a$
Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием.
Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций.
Это обобщается: просто говорим, что операция — это множество операций, которые надо применить. У каждой операции есть время: пара из логических часов и номера процесса. Тогда, конечно, тяжёлое состояние и сложно получать реальные данные, зато работает.
== Репликация на основе состояния ==
== $\delta$-CRDT ==
Оптимизация CRDT на основе состояния: отсылаем не весь вектор, а только изменения в этом векторе: установить такую-то компоненту в такое-то значение. То есть у нас теперь есть не только операции, но и "кусочки операций", которые надо не только уметь применять, но ещё и склеивать между собой. Относится к обоим видам CRDT.
