Real-Time Backend
CRDT введение
Два человека одновременно редактируют Figma-файл. Один добавляет кнопку, другой удаляет тот же фрейм. Сеть падает на 3 секунды. Кто прав? CRDT делает этот вопрос математически разрешимым - без центрального арбитра, без блокировок, с гарантией что оба клиента придут к одному состоянию.
- **Figma** использует CmRDT для real-time коллаборации: 100+ редакторов в одном файле, 50 млн операций/день, p99 latency применения операции <10ms - без единого Lock на документ
- **Redis Enterprise** реализует CRDT-счётчики и CRDT-множества для geo-distributed кластеров: 5 датацентров синхронизируются через OR-Set и PN-Counter, конфликты разрешаются автоматически по Add-Wins семантике
- **Riak 2.0** (Basho, 2014) - первая production NoSQL БД с native CRDT типами: Maps, Sets, Counters, Registers. LinkedIn использовал Riak CRDT для хранения social graph с 400 млн пользователей
- **Apple Notes** и **iCloud** используют state-based CRDT для offline-first синхронизации: изменения на iPhone без сети применяются локально, при восстановлении соединения merge происходит детерминированно
Что такое CRDT
В 2011 году команды Google Docs и Riak столкнулись с одной и той же проблемой: два пользователя редактируют один документ, сеть на 200 мс разрывается - чьи изменения победят? Классический Last-Write-Wins уничтожает чужие правки. Operational Transformation требует центрального сервера-арбитра. Оба решения ломаются при реальных партициях.
CRDT (Conflict-free Replicated Data Type) - математически гарантированный способ сделать так, чтобы любые два узла, получив одинаковый набор операций в любом порядке, пришли к одному результату. Не «постараемся разрешить конфликт», а доказуемая сходимость.
Три свойства, которые делают это возможным
- **Associativity**: merge(merge(A,B),C) = merge(A,merge(B,C)) - порядок группировки не важен
- **Commutativity**: merge(A,B) = merge(B,A) - порядок операндов не важен
- **Idempotency**: merge(A,A) = A - повторное применение не меняет результат
Любая структура данных, реализующая эти три свойства для операции merge, автоматически становится CRDT. Два реплики, обменявшихся всеми операциями, сойдутся к одному состоянию без координации.
Какое из трёх свойств CRDT гарантирует, что повторная доставка одной операции не испортит состояние?
CvRDT - State-based (convergent)
State-based CRDT (CvRDT, Convergent) передаёт между репликами полное состояние и объединяет его через функцию merge. Redis использует эту модель в своём CRDT-счётчике; Riak строит на CvRDT всю свою eventual consistency. Узлы могут не быть онлайн одновременно - при следующем соединении они синхронизируются, обменявшись состояниями.
Решётка (lattice) как математический фундамент
CvRDT требует, чтобы множество состояний образовывало частично упорядоченную решётку (join-semilattice). Merge - это операция join (наименьшая верхняя грань). Она монотонна: состояние только растёт, никогда не уменьшается. Именно монотонность гарантирует сходимость.
**Недостаток CvRDT:** при большом состоянии полная синхронизация дорогостоящая. Riak решает это delta-state CvRDT - передаётся только «дельта» от последнего обмена, а не всё состояние целиком. Размер сообщений сокращается на 90-98% при частых синхронизациях.
Узел A имеет PN-Counter {P:{A:10}, N:{A:2}}, узел B имеет {P:{B:7}, N:{B:3}}. Чему равно значение после merge?
CmRDT - Operation-based (commutative)
Operation-based CRDT (CmRDT, Commutative) передаёт не состояние, а операции. Именно на этом принципе работает реальный time Google Docs с 2013 года и Figma с 2016-го: 50 млн операций в день, sub-100ms latency на редактирование, без центрального замка на документ.
CmRDT требует надёжного каузального broadcast: каждая операция должна прийти ко всем репликам ровно один раз и после всех операций, от которых она зависит. В обмен на это - компактные сообщения и O(1) применение операции.
**CvRDT vs CmRDT trade-off:** CvRDT проще реализовать (нет требований к транспорту), но дорог при большом состоянии. CmRDT компактен, но требует exactly-once causal delivery - нужен надёжный message broker (Kafka, NATS JetStream). Figma выбрала CmRDT + WebSocket с NATS за компактность операций при 100+ одновременных редакторах в одном файле.
Два клиента одновременно: A добавляет элемент 'x', B удаляет 'x' (который уже был). OR-Set с Add-Wins semantics - что будет в финальном состоянии?
Математика: join-semilattice и монотонные функции
За всеми CRDT стоит одна алгебраическая структура - join-semilattice. Это частично упорядоченное множество (S, ≤) с операцией join (⊔), которая возвращает наименьшую верхнюю грань любых двух элементов. Именно это математики называют «решёткой» (lattice).
CALM Theorem - граница применимости
CALM (Consistency As Logical Monotonicity) - теорема Хеллерстейна 2011 года, ставшая теоретическим фундаментом для Bloom DSL в Berkeley и повлиявшая на дизайн распределённых систем следующего десятилетия. Формулировка: программа является сходящейся без координации тогда и только тогда, когда она монотонна. Немонотонные операции (удаление, замена, условные ветки) требуют координации или специальной упаковки в CRDT.
- **Монотонные операции** (set-union, append, max, min) - бесплатная сходимость, CRDT-friendly
- **Немонотонные операции** (set-difference, overwrite) - требуют оборачивания в tombstone/tag механизм
- **Практика**: Figma хранит все удалённые объекты как «tombstone» записи - это превращает remove в монотонную операцию add-to-deleted-set
CRDT решает все проблемы согласованности - достаточно использовать CRDT и можно не думать о конфликтах
CRDT гарантирует сходимость состояния, но семантика результата (Add-Wins vs Remove-Wins, last-write wins) задаётся разработчиком. CRDT не решает вопрос «какой результат правильный» - только «все узлы придут к одному результату».
Figma выбирала между Add-Wins и Remove-Wins для concurrent delete+create объекта: оба варианта - валидные CRDT, но дают разный UX. Выбор семантики - продуктовое решение, не техническое. CRDT убирает недетерминизм, но не убирает необходимость проектировать поведение конфликтов.
По CALM theorem, какая операция НЕ требует координации между узлами для сходимости?
Итоги
- CRDT - структура данных с математически гарантированной сходимостью: любые два узла, получив одинаковый набор операций, придут к одному состоянию. Три свойства merge: associativity, commutativity, idempotency.
- CvRDT (state-based) передаёт полное состояние и объединяет через join в join-semilattice. Проще реализовать, дорог при большом состоянии. Используется в Redis CRDT, Riak.
- CmRDT (operation-based) передаёт операции, требует causal exactly-once delivery. Компактен, масштабируется лучше. Используется в Figma, Google Docs.
- CALM theorem: монотонные функции сходятся без координации. Немонотонные операции (delete, overwrite) требуют специальной упаковки в tombstone/tag-механизмы.
Связанные темы
CRDT опирается на несколько фундаментальных концепций распределённых систем:
- Eventual Consistency — CRDT - конкретная математическая реализация eventual consistency с доказуемой сходимостью вместо «постараемся»
- Vector Clocks — CmRDT использует vector clocks для causal ordering операций - без них невозможно определить зависимости между concurrent ops
- CAP Theorem — CRDT позволяют жертвовать strong consistency (C в CAP) предсказуемым образом - выбирая availability и partition tolerance с гарантированной eventual convergence
Вопросы для размышления
- Figma выбирает Add-Wins для конкурентных операций add/delete объекта. В каком продукте имело бы смысл выбрать Remove-Wins - и почему это изменило бы UX?
- G-Counter позволяет только increment. Как бы спроектировать CRDT для банковского счёта, где нужен и increment, и decrement, но баланс никогда не должен уходить в минус?
- CALM theorem говорит, что монотонные программы не требуют координации. Можно ли переписать любую распределённую систему в монотонных операциях - или есть фундаментальные ограничения?