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