Глава про CRDT важна тем, что показывает путь, обратный консенсусу: реплики сходятся к одному состоянию автоматически, без лидера, кворума и блокировок — за счёт математических свойств слияния, а не координации.
На практике это основа local-first и совместного редактирования: правки применяются локально и мгновенно, работают офлайн и сливаются без конфликтов, когда связь восстанавливается.
В интервью и архитектурных обсуждениях материал даёт язык, чтобы обосновать выбор между координацией (консенсус) и конвергентностью (CRDT) и честно назвать цену CRDT — метаданные, tombstone'ы и сборку мусора.
Практическая польза главы
Конвергентность без координации
Реплики сходятся через коммутативное слияние на полурешётке — без лидера и кворума, в отличие от консенсуса.
Два семейства
CvRDT (состояние, merge=join) и CmRDT (операции с причинной доставкой) — выбор по каналу связи и стоимости передачи.
Текст и local-first
Sequence-CRDT (RGA и др.) и системы Automerge/Yjs дают офлайн-правки и слияние без конфликтов в реальных редакторах.
Цена конвергентности
Метаданные, tombstone'ы и сборка мусора — главные издержки; их нужно планировать заранее, а не после роста состояния.
Контрастная соседняя глава
Консенсус: Paxos и Raft
Соседняя глава решает ту же проблему расхождения реплик противоположным способом — через координацию, кворумы и единого лидера. Эта глава показывает обратный полюс.
Соседняя глава про решает проблему расходящихся реплик через координацию: , единого лидера и . Каждая запись там проходит через сетевой раунд согласования, поэтому без связи с большинством узел писать не может — а офлайн-правка невозможна по определению.
Эта глава про обратный подход. — бесконфликтно реплицируемые типы данных — позволяют каждой реплике принимать запись локально, без всякой координации, а потом детерминированно сливать состояния. Гарантия называется сильной итоговой (strong eventual consistency, SEC): реплики, получившие один и тот же набор обновлений, обязаны прийти к идентичному состоянию — без выборов лидера, без блокировок и без ручного .
Дальше важны термины: CvRDT (state-based, слияние через join полурешётки) и CmRDT (op-based, коммутативные операции), для отслеживания причинности, OR-Set и регистры со стратегией «последняя запись побеждает» (LWW) как базовые конструкции, а также, которыми платят за корректность удалений.
нужны там, где реплики должны принимать записи независимо — офлайн, на разных континентах, в мобильном приложении без сети — и при этом гарантированно сходиться к одному и тому же состоянию, как только обмен обновлениями завершится. Цена этого удобства — метаданные, метки удаления и ограниченный набор операций, которые в принципе можно сделать коммутативными.
Фундамент
Синхронизация часов
Стратегия «последний-кто-записал» опирается на физические часы. Их рассинхронизация напрямую превращается в потерянные правки — об этом глава о времени.
Задача: офлайн-правки и почему «последний победил» теряет данные
Представим совместный документ или корзину покупок, которые редактируются с нескольких устройств, включая офлайн. Узел должен принять правку немедленно — иначе интерфейс «залипнет» в ожидании сети. Значит, конкурентные изменения неизбежны, и вопрос лишь в том, что система с ними сделает.
Последний-кто-записал (LWW)
Побеждает запись с большей меткой времени, остальные молча отбрасываются. Просто, но при рассинхронизации часов теряются реальные правки, а две конкурентные записи с одинаковой меткой требуют произвольного разрыва ничьей.
Блокировки и координация
Прежде чем писать, узел берёт блокировку или собирает кворум. Корректно, но требует связи с большинством на каждую запись — офлайн-узел писать не может вовсе, а задержка добавляет сетевой раунд.
Слияние без координации (CRDT)
Запись принимается локально, а конкурентные версии сливаются по детерминированному правилу — так, что результат не зависит от порядка доставки и не теряет ни одной зафиксированной операции.
Ключевое наблюдение: — это не «отсутствие конфликта», а скрытая потеря данных. Если Алиса добавила товар в корзину офлайн, а Боб параллельно очистил её, наивный «последний победил» по часам выкинет одну из правок. Знаменитый пример Amazon Dynamo — корзина, где конкурентные изменения нужно сливать, а не выбирать одно из них: удалённый товар не должен «воскресать», но и добавленный не должен пропадать.
Связанная теорема
Теорема CAP
CRDT — это инженерный ответ AP-стороны CAP: сохранить доступность и устойчивость к разделению, сведя «отложенность» согласованности к автоматической конвергенции.
Модель консистентности: SEC, полурешётка и почему реплики сходятся
Обычная обещает только то, что «когда-нибудь» реплики совпадут, но не говорит, как именно разрешать конкурентные записи — это перекладывается на приложение. CRDT усиливают обещание до сильной итоговой (strong eventual consistency, SEC): любые две реплики, доставившие один и тот же набор обновлений, находятся в идентичном состоянии. Разрешение конфликтов встроено в сам тип данных и детерминировано.
Решётка и операция join
Состояния реплики образуют полурешётку с верхними гранями (join-semilattice): на множестве состояний задан частичный порядок, и у любой пары есть наименьшая верхняя грань — результат слияния ⊔ (join). Слияние двух реплик — это вычисление их join.
Чтобы реплики сходились, операция слияния обязана быть коммутативной (a ⊔ b = b ⊔ a), ассоциативной ((a ⊔ b) ⊔ c = a ⊔ (b ⊔ c)) и идемпотентной (a ⊔ a = a). Эти три свойства означают, что порядок, группировка и повторы доставки обновлений не влияют на итог.
Монотонность как двигатель
Каждое обновление двигает состояние реплики вверх по решётке — к большей верхней грани, никогда назад. Слияние тоже монотонно: join двух состояний не меньше каждого из них.
Именно монотонность спасает от перестановки, потери и дублирования сообщений в сети: повтор обновления ничего не ломает (идемпотентность), а разный порядок приводит в одну точку (коммутативность и ассоциативность). Поэтому CRDT не нужна надёжная упорядоченная доставка — достаточно, чтобы каждое обновление в конце концов дошло.
Как сливаются две реплики: счётчик роста
Самый наглядный CRDT — растущий счётчик G-Counter. Каждая реплика держит вектор: «сколько насчитала каждая из них». Реплика инкрементит только свою позицию, а слияние берёт поэлементный максимум двух векторов. Максимум коммутативен, ассоциативен и идемпотентен — значит, реплики сойдутся при любом порядке доставки. Значение счётчика — сумма вектора.
Почему нельзя просто сложить два числа? Потому что сложение не идемпотентно: если одно и то же обновление дойдёт дважды (а сеть это допускает), сумма удвоится. Вектор «по реплике» с операцией max устраняет двойной учёт: повторная доставка [A:2] не меняет максимум. Это типичный приём CRDT — заменить неидемпотентную операцию на монотонный рост по координатам.
Справочник
crdt.tech
Курируемый каталог статей и реализаций CRDT, поддерживаемый сообществом исследователей и авторами основополагающих работ.
Два семейства: CvRDT (state-based) и CmRDT (op-based)
Шапиро, Прегиса, Бакеро и Завирски в работах 2011 года выделили два эквивалентных по выразительности способа построить CRDT. Они отличаются тем, что именно реплики пересылают друг другу — целое состояние или отдельные операции — и какие требования это накладывает на сеть.
CvRDT — convergent, state-based
- Реплики пересылают друг другу целое состояние; слияние — это
joinполурешётки (наименьшая верхняя грань). - Требование к слиянию: коммутативность, ассоциативность, идемпотентность. Требование к обновлению: монотонность (только «вверх»).
- Терпит потерю, дублирование и переупорядочивание сообщений: достаточно, чтобы состояния периодически обменивались любым каналом, включая через gossip.
- Минус: пересылать полное состояние дорого. Лечится delta-CRDT — отправкой только «приращений» решётки вместо всего состояния.
CmRDT — commutative, op-based
- Реплики пересылают операции (например, «добавить элемент x с тэгом t»). Применять их можно в любом порядке, если операции коммутируют.
- Требование к доставке строже: каждая операция должна дойти ровно один раз и с соблюдением причинного порядка — это даёт надёжную причинную (causal broadcast) с гарантией .
- Плюс: пересылается мало данных — только дельта-операция, без полного состояния.
- Минус: требование «ровно один раз + причинный порядок» нужно реально обеспечить транспортом, иначе сходимость нарушается.
Главный компромисс — где платить: CvRDT перекладывает сложность на размер состояния (и почти не требует ничего от сети), CmRDT — на гарантии доставки (зато экономит трафик). На практике популярны гибриды: delta-state CRDT сочетают компактность op-based с устойчивостью state-based к переупорядочиванию.
Базовый зоопарк CRDT и подвохи каждого
Из нескольких простых конструкций собираются почти все практические CRDT. Важно не столько запомнить их, сколько понять подвох — место, где наивная реализация теряет данные или ведёт себя неожиданно.
| Тип | Идея и слияние | Подвох |
|---|---|---|
| G-Counter | Растущий счётчик: вектор по репликам, слияние — поэлементный max, значение — сумма. | Умеет только инкремент. Декремент нарушил бы монотонность max. |
| PN-Counter | Два G-Counter'а: P (плюсы) и N (минусы); значение — сумма(P) − сумма(N). | Метаданные растут линейно по числу реплик; «отрицательный баланс» формально возможен. |
| G-Set | Растущее множество: слияние — объединение, добавление монотонно. | Удалять элементы нельзя в принципе — это сломало бы монотонность. |
| 2P-Set | Two-phase set: множество добавленных + множество удалённых (метки удаления, tombstones). | Удаление необратимо: однажды удалённый элемент нельзя добавить заново. |
| OR-Set | Observed-Remove Set: каждый add получает уникальный тэг; remove убирает только наблюдавшиеся тэги. Add-wins. | Конкурентные add и remove → элемент остаётся (add-wins). Тэги накапливаются — нужна сборка мусора. |
| LWW-Register / LWW-Map | Регистр (или карта) с меткой времени: при слиянии побеждает запись с большей меткой. | Конкурентная запись с меньшей меткой теряется молча; корректность зависит от часов и правила разрыва ничьих. |
Почему OR-Set лучше 2P-Set
В 2P-Set удаление необратимо: добавить заново уже нельзя. OR-Set решает это уникальными тэгами на каждый add. Удаление убирает только те тэги, которые видела реплика на момент удаления, поэтому новый, конкурентный add с новым тэгом переживает удаление. Семантика «add-wins» обычно совпадает с интуицией пользователя: если кто-то параллельно добавил элемент, он остаётся.
Когда LWW допустим
Стратегия «последняя запись побеждает» () — самый дешёвый CRDT, часто достаточный для полей, где «последнее значение и есть истина»: статус заказа, имя в профиле, настройка. Но по построению она теряет конкурентную запись, поэтому не годится там, где обе правки несут смысл (текст, множества, корзина). Riak и Cassandra широко полагаются на этот подход — и именно поэтому требуют осторожности с рассинхронизацией часов.
Статья
Interleaving anomalies, PaPoC 2019
Клеппманн, Гомес, Маллиган и Бересфорд показывают, что некоторые последовательные CRDT при конкурентных вставках «перемешивают» символы соседних слов.
Текст: последовательные CRDT, позиционные идентификаторы и OT
Совместное редактирование текста — самая сложная для CRDT задача, потому что элемент здесь не просто «есть/нет», а занимает позицию в последовательности, и позиции конкурентно сдвигаются. Числовые индексы не годятся: вставка в начало смещает все остальные. Решение — стабильные позиционные идентификаторы, которые не меняются при чужих вставках.
Sequence CRDT (RGA, Logoot, LSEQ, Treedoc)
Каждому символу присваивается уникальный, плотно упорядочиваемый идентификатор: между любыми двумя позициями всегда можно вставить новую. RGA (Replicated Growable Array) связывает символы ссылками на «левого соседа» и разрывает ничьи по идентификатору реплики; Logoot/LSEQ кодируют позицию как путь в дереве дробных индексов.
Удалённый символ превращается в : его нельзя стереть сразу, иначе сосед потеряет якорь позиции.
Проблема interleaving
Клеппманн и соавторы (PaPoC 2019) показали тонкий дефект: если две реплики конкурентно вставляют целые слова в одно место, некоторые sequence-CRDT могут перемежать их символы — «HELLO» и «WORLD» превращаются в «HWEOLRLLOD». Полнее всего дефект проявляют Logoot и LSEQ; RGA подвержена лишь ослабленному варианту (для вставок справа налево).
Это не теряет данные (SEC сохраняется), но даёт бессмысленный текст. Правильно спроектированный sequence-CRDT обязан держать конкурентные вставки от одного автора вместе, а не вперемешку.
OT — альтернатива: преобразование операций вместо встроенной коммутативности
(OT) решает ту же задачу иначе. Вместо стабильных идентификаторов оно хранит обычные индексы, но преобразует входящую операцию относительно уже применённых: если кто-то вставил символ слева, индекс вашей вставки сдвигается на единицу. Так работали Google Wave и работает Google Docs.
Подвох операционного преобразования (OT) — функции трансформации сложно сделать корректными для всех пар операций, и классический OT обычно требует центрального сервера, упорядочивающего операции. CRDT популярнее для и одноранговых (p2p) сценариев именно потому, что коммутативность встроена в тип данных и не нужен сервер-упорядочиватель — ценой метаданных и меток удаления.
Фундамент
Логическое время и причинность
Вектор версий — родственник векторных часов: он фиксирует «что узел уже видел», позволяя отличить причинно-связанные обновления от конкурентных без физических часов.
Причинность: векторы версий и обнаружение конкурентности
Чтобы решить, «победила» одна правка или они конкурентны, нужно отслеживать причинность — а для этого не годятся физические часы. CRDT опираются на логическое время.
Вектор версий и dotted version vector
хранит по счётчику на каждую реплику и отвечает на вопрос «что я уже видел». Сравнивая два вектора, можно понять: одна версия предшествует другой (один доминирует покомпонентно) или они конкурентны (ни один не доминирует) — и тогда нужно сливать.
Точечный (dotted version vector) — уточнение, которое точно различает конкурентные записи даже от одного клиента и избавляет от ложных конфликтов; именно его применяет Riak для версионирования объектов.
Причинная доставка для op-based
CmRDT требуют, чтобы операция применялась только после всех, от которых она причинно зависит. Это обеспечивает причинную (causal broadcast): каждое сообщение несёт информацию о том, что автор уже видел, а получатель буферизует операцию, пока не доедут её предшественники.
Без причинного порядка op-based может, например, попытаться удалить элемент раньше, чем дойдёт его добавление, — и сходимость нарушится. Поэтому «ровно один раз + причинность» для CmRDT не пожелание, а условие корректности.
Издержки: метаданные, метки удаления, рост состояния
За автоматическую сходимость без координации приходится платить памятью и сложностью. Это главная причина, по которой CRDT не универсальны.
Метаданные растут
Тэги OR-Set, идентификаторы позиций, векторы версий — всё это метаданные на каждый элемент. Для текста объём метаданных легко превышает сам текст в разы.
Метки удаления накапливаются
Удалённый элемент нельзя стереть сразу: он остаётся меткой удаления (tombstone), чтобы конкурентные реплики не «воскресили» удалённое и не потеряли якоря позиций.
Сборка мусора сложна
Убрать метку удаления (tombstone) безопасно можно, лишь когда все реплики гарантированно увидели удаление. Это требует знания о прогрессе всех реплик — отдельная распределённая задача.
Когда CRDT дороги: при огромном числе реплик (метаданные на реплику в счётчиках), при долгой истории правок одного документа (накопленные метки удаления, tombstones), при операциях, которые в принципе плохо коммутируют (перемещение элемента, транзакционные инварианты вроде «уникальность» или «сумма = 100»). Современные реализации вроде Yjs и Automerge много сил вкладывают именно в компактное кодирование и сборку мусора, чтобы удержать издержки.
Реализация
Yjs
Высокопроизводительная CRDT-библиотека для совместного редактирования: shared-типы, интеграции с ProseMirror, Monaco, CodeMirror и транспорт-агностичная синхронизация.
Системы на практике и local-first
| Система | Где и как применяет CRDT |
|---|---|
| Automerge | JSON-подобный документ как CRDT для локально-ориентированных (local-first) приложений: работает офлайн, сливает конкурентные правки без потерь, хранит полную историю изменений. Соавтор — Мартин Клеппманн. |
| Yjs | Самая быстрая по заявлениям реализация для совместного редактирования: shared-типы (Text, Array, Map), интеграции с редакторами, транспорт-агностичная синхронизация без центрального сервера. |
| Redis Active-Active (CRDB) | Гео-распределённая мультимастер-репликация целиком на CRDT: предсказуемое разрешение конфликтов плюс векторные часы дают strong eventual consistency между кластерами. |
| Riak | Распределённое KV-хранилище с библиотекой Riak DT (счётчики, множества, карты, регистры) и точечными векторами версий (dotted version vectors) для версионирования объектов. |
Local-first: за что любят CRDT
Идея софта (local-first software — термин из работы команды Ink & Switch с участием Клеппманна) — данные живут на устройстве пользователя, работают офлайн и мгновенно, а сеть нужна только для синхронизации. CRDT — естественный фундамент такого подхода: они позволяют редактировать без сервера-арбитра и сходиться при встрече реплик. Поэтому CRDT популярнее операционного преобразования (OT) там, где важны офлайн, одноранговый (p2p) обмен и владение данными, тогда как OT остаётся практичным в классической клиент-серверной модели вроде Google Docs.
Компромиссы и частые ошибки
Частые ошибки
- Считать «бесконфликтным» — на деле он молча теряет конкурентную запись.
- Брать op-based CRDT, не обеспечив доставку «ровно один раз + причинный порядок».
- Ожидать инвариантов («сумма всегда = 100», «уникальность ника») — CRDT гарантируют сходимость, но не глобальные ограничения.
- Забыть про сборку мусора — состояние растёт неограниченно.
Когда CRDT — правильный выбор
- Нужна офлайн-правка и мгновенный локальный отклик.
- Конкурентные изменения нужно сливать, а не выбирать одно (текст, множества, корзина).
- Допустима отложенная согласованность — нет жёсткого требования линеаризуемости на запись.
- Операции домена в принципе можно сделать коммутативными.
Что важно запомнить
- CRDT дают сильную итоговую консистентность (strong eventual consistency, SEC) без координации: реплики с одинаковым набором обновлений приходят к идентичному состоянию.
- Сходимость держится на математике полурешётки: слияние коммутативно, ассоциативно и идемпотентно, а обновления монотонны.
- CvRDT платят размером состояния и почти ничего не требуют от сети; CmRDT экономят трафик, но требуют доставки «ровно один раз + причинный порядок».
- Стратегия «последняя запись побеждает» (LWW) не бесконфликтна — она теряет конкурентную запись; OR-Set с тэгами и add-wins ближе к интуиции пользователя.
- Текстовые CRDT используют стабильные позиционные идентификаторы и метки удаления (tombstones); следить за переплетением символов (interleaving) и сборкой мусора обязательно.
- Цена удобства — метаданные и метки удаления; для жёстких инвариантов и линеаризуемости нужен консенсус из соседней главы.
Когда CRDT могут навредить
CRDT убирают координацию, но не отменяют физику: они не дают линеаризуемости, не обеспечивают глобальных инвариантов и накапливают метаданные. Там, где домену нужно единственное согласованное решение прямо сейчас (списание денег, уникальность, кворумная фиксация), правильный инструмент — из соседней главы, а не бесконфликтное слияние.
Источники и материалы
Карта источников: Shapiro/Preguiça/Baquero/Zawirski держат формальную основу CRDT; Kleppmann et al. — аномалии текстовых CRDT; crdt.tech — навигацию по работам; Yjs, Automerge и Redis — практические реализации. Выводы про метаданные, GC, порядок символов и UX конфликтов надо проверять на выбранном CRDT-типе и модели синхронизации.
Связанные главы
- Консенсус: Paxos и Raft - Контрастный соседний подход: согласие через координацию, кворумы и лидера вместо координационно-свободной конвергентности.
- Теорема CAP - Объясняет, почему CRDT выбирают доступность и устойчивость к разделению, расплачиваясь отложенной согласованностью.
- Синхронизация часов в распределённых системах - Показывает, почему стратегия «последняя запись побеждает» (LWW) на физических часах теряет данные, а причинность приходится отслеживать логически.
- Кейс: совместный редактор уровня Google Docs - Прикладная сборка совместного редактирования, где встречаются OT, CRDT, presence и синхронизация курсоров.