CRDT — основы

Conflict-free Replicated Data Types — структуры данных, у которых операция merge коммутативна, идемпотентна и ассоциативна. Две реплики, изменённые независимо, сливаются без ручного разрешения конфликтов.

Зачем

В offline-first и distributed-системах два узла могут изменять одну сущность одновременно. Решения:

  • Pessimistic — блокировка, откат на предыдущее состояние при конфликте.
  • Last-write-wins — кто последний — тот прав.
  • Patch-based — как в git, ручное разрешение конфликтов.
  • CRDT — merge всегда корректен математически, без блокировок и ручных решений.

Свойства

Operation merge(a, b) должна быть:

  • Коммутативна: merge(a, b) == merge(b, a)
  • Ассоциативна: merge(merge(a, b), c) == merge(a, merge(b, c))
  • Идемпотентна: merge(a, a) == a

Это даёт strong eventual consistency: все реплики, видевшие один набор операций, сходятся в одно состояние независимо от порядка.

Четыре типа CRDT

Тип Что пересылается Размер
State-based (CvRDT) всё состояние объекта большой
Operation-based (CmRDT) лог операций средний
Delta-based дельта изменений малый
Schema-based дельта по схеме малый

автор: «Schema-based — это исключительно моя придумка, я экспериментирую».

State-based: пересылаем всё

Простейший: каждая реплика шлёт другой своё полное состояние. Merge — max/union/что-то монотонное.

  • Плюс: просто реализовать.
  • Минус: дорого по сети.

Operation-based: пересылаем лог

Каждая реплика шлёт операции (inc(3), add('a')). Merge — применить операции, которые ещё не применены.

  • Плюс: компактно.
  • Минус: требуется доставка exactly-once или дедупликация.

Delta-based: пересылаем дельты

Компромисс. Шлём только то, что изменилось со времени последней синхронизации.

Накладные расходы

«Во всех CRDT-структурах данных мы получаем дополнительные коллекции, в которых храним избыточные данные.»

Пример: тысячу элементов добавили, 999 удалили — в 2P-set лежит два массива по тысяче, хотя множество из одного элемента.

Решение — garbage collection. Сложная задача в distributed: нужно знать, что данные больше нигде не используются.

Где живёт

  • Документы: Google Docs (operational transformation, родственник CRDT).
  • Чаты: Slack, Telegram, WhatsApp Web.
  • Распределённые БД: Riak, Redis (CRDT-структуры), CouchDB.
  • JS-библиотеки: Yjs, Automerge.
  • Metarhia GlobalStorage — в разработке.

🎓 Источники

См. также