State-based vs Operation-based CRDT

Два основных типа CRDT. State-based шлют состояние целиком. Operation-based шлют лог операций. Delta-based — компромисс.

State-based (CvRDT)

Каждая реплика шлёт своё полное состояние другой реплике. Merge — функция, объединяющая два состояния.

Реплика A: {a, b, c}
Реплика B: {b, c, d}
            ↓ merge (union)
Обе: {a, b, c, d}

Требование: merge должен быть коммутативен, ассоциативен, идемпотентен.

Плюсы:

  • Просто реализуется.
  • Не требует надёжной доставки (повтор не вредит — merge идемпотентен).
  • Доставка в любом порядке.

Минусы:

  • Большие пакеты.
  • Метаданные тоже шлются (timestamps, tags).
  • автор: «Это дорогие CRDT».

Operation-based (CmRDT)

Реплики шлют операции (inc(3), add('item')). Получатель применяет операции.

Реплика A: inc(5) → шлёт "inc(5)"
Реплика B: получает "inc(5)" → state += 5

Требования:

  • Reliable delivery (exactly-once или дедупликация на стороне получателя).
  • Операции должны быть commutative.
  • Не обязательно идемпотентны (доставка exactly-once).

Плюсы:

  • Маленькие пакеты.
  • Подходит для real-time (caret в редакторах).

Минусы:

  • Сложнее: нужна транспортная инфраструктура с гарантиями.
  • Дедупликация через ID операций → memory overhead.

Delta-based

Гибрид. Реплика хранит дельту изменений с последнего sync. Шлёт только дельту.

const deltas = new Map();
// при изменении — обновляем delta
// при sync — отправляем delta, очищаем

Плюсы:

  • Маленькие пакеты как у op-based.
  • Идемпотентность как у state-based (merge дельты с любым состоянием).

Минусы:

  • Сложнее реализовать (надо отслеживать «с какого момента считать дельту»).

Сравнение

State Operation Delta
Размер пакета большой малый малый
Reliable transport не нужен нужен не нужен
Идемпотентность да нет да
Простота высокая средняя низкая
Real-time плохо хорошо средне

Когда что выбирать

  • State-based: редкая синхронизация, простые структуры, важна устойчивость к сетевым проблемам.
  • Operation-based: real-time co-editing (Google Docs, Figma), большие объекты, мало операций.
  • Delta-based: large data + frequent sync, production-grade local-first.

Schema-based

Экспериментальный четвёртый тип. Дельта вычисляется автоматически по схеме данных:

const CRDT = (schema) => ({
  delta: (state, modified) => /* compute */,
  merge: (state, delta) => /* apply */,
});

Схема описывает структуру → CRDT-логика порождается из схемы.

🎓 Источники

См. также