Прямой ответ
CRDT (Conflict-free Replicated Data Type) — тип данных, реплики которого можно обновлять независимо и объединять в любом порядке, получая одинаковый результат на всех узлах. Формальная основа — коммутативность, ассоциативность и идемпотентность операции слияния (join): такие структуры образуют полурешётку, а состояние реплик монотонно растёт.
Два семейства:
- CvRDT (state-based). Реплики периодически обмениваются полным состоянием, слияние — операция join. Требует надёжной, но не обязательно упорядоченной доставки; хорошо ложится на gossip.
- CmRDT (operation-based). Реплики рассылают операции. Требует доставки каждой операции ровно один раз (causal broadcast), зато передаёт меньше данных.
Базовые типы:
| Тип | Что делает | Пример |
|---|---|---|
| G-Counter | Счётчик только на увеличение; слияние — покомпонентный максимум | Просмотры, лайки |
| PN-Counter | Два G-Counter: прибавление и вычитание | Остатки, рейтинги |
| LWW-Register | Значение с меткой; побеждает последняя по метке | Профиль пользователя |
| OR-Set | Множество с уникальными метками добавления | Корзина, теги |
| RGA / LWW-Sequence | Последовательность символов | Совместное редактирование текста |
Ключевое свойство: порядок слияния не важен, поэтому не нужен координатор, кворум или консенсус. Цена — eventual consistency: в конкретный момент реплики могут отличаться, но после обмена все придут к одному состоянию. Место CRDT в общем ландшафте — в статье про модели согласованности.
Практика: где CRDT реально применяют
Счётчики и агрегаты. G-Counter/PN-Counter решают задачу «считать в разных узлах без центра»: каждая реплика пишет в свой компонент, при слиянии берётся максимум по компонентам. Это убирает гонку UPDATE ... SET c = c + 1 между узлами.
Множества (OR-Set). Классический пример — корзина покупок из Dynamo: два независимых добавления не конфликтуют, а удаление «стирает» конкретные метки добавления, поэтому удалённый товар не воскресает из другой реплики.
Совместное редактирование. CRDT-последовательности (Yjs, Automerge) позволяют нескольким клиентам править документ офлайн и сходиться после синхронизации без центрального сервера.
Что важно учесть на практике:
- Рост состояния. OR-Set хранит метки удалённых элементов, пока о них не узнали все реплики; без «сборки мусора» (causal stability) состояние растёт. В промышленных реализациях это решают обрезкой по стабильности.
- Метки и уникальные id. Каждое добавление несёт уникальный тег (узел + счётчик). Если id узлов повторяются (пересозданные поды без стабильного имени), возможны ложные слияния.
- LWW внутри CRDT — это компромисс. LWW-Register по сути «разрешает» конфликт отбрасыванием, поэтому требует аккуратных меток времени или гибридных логических часов; иначе возможны тихие потери обновлений. Разбор причинности — в статье про векторные часы.
- Не всё можно выразить CRDT-ом. Инварианты вроде «баланс не может уйти в минус» при независимых обновлениях не гарантируются: две реплики могут независимо потратить одну и ту же сумму. Такие правила требуют координации (консенсус, кворум, единый писатель).
Пример на Redis (PN-Counter через хеш):
# каждая реплика пишет в своё поле
HINCRBY metrics:pageviews node-a 1
HINCRBY metrics:pageviews node-b 3
# слияние = сумма полей (частный случай PN-Counter)
HVALS metrics:pageviews
Практический сценарий: офлайн-режим мобильного приложения
Контекст: приложение позволяет отмечать задачи выполнёнными без сети; синхронизация происходит позже, сервер реплицирован в два региона.
- Проблема. Пользователь отметил задачу в самолёте, второй пользователь в это время добавил подзадачи через другой регион. При синхронизации наивное LWW-слияние потеряло бы одно из изменений.
- Решение по типам. Флаг «выполнено» — OR-Set/LWW с явной семантикой «последнее действие пользователя» и сохранением истории; список подзадач — OR-Set, поэтому добавления объединяются; счётчик прогресса — PN-Counter.
- Синхронизация. Клиент отправляет дельту своего состояния; сервер выполняет join. Повторная доставка той же дельты безопасна благодаря идемпотентности слияния — это упрощает ретраи, см. надёжность очередей.
- Инварианты. Проверку «нельзя закрыть задачу, пока открыты блокирующие подзадачи» оставляем на стороне сервера в момент слияния, а не на клиенте: CRDT не гарантирует бизнес-инварианты.
- Тесты. Юнит-тесты на свойства слияния: коммутативность (
join(a,b) == join(b,a)), ассоциативность, идемпотентность (join(a,a) == a). Такие тесты ловят ошибки реализации, которые не видны в обычных сценариях.
Результат: офлайн-правки объединяются без потери данных и без центрального арбитра. Вывод: CRDT снимает необходимость координации для тех операций, где допустима eventual consistency; для строгих инвариантов остаётся консенсус.
FAQ
Чем CRDT отличается от репликации с кворумом? Кворум (NWR) управляет тем, сколько реплик должно подтвердить операцию, и даёт гарантию видимости последней записи. CRDT управляет тем, как объединять независимые изменения, и гарантирует сходимость без кворума. Подходы комбинируются: например, кворум для строгих сценариев, CRDT — для фоновых данных.
Нужен ли CRDT, если есть единый писатель? Нет. Если все записи проходят через один узел (лидер в Raft или единственная реплика БД), конфликтов независимых обновлений не возникает. CRDT оправдан при мульти-мастер записи, офлайн-клиентах и географическом распределении.
Можно ли хранить CRDT в обычной SQL-БД? Да: состояние хранят как структуру (JSONB, отдельные таблицы меток), а слияние реализуют в приложении или в функциях БД. Важно, чтобы слияние было атомарным и учитывало идемпотентность — иначе повторная доставка дельты сломает сходимость. Для строгих сценариев пригодятся транзакции и изоляция.
Что выбрать: CRDT или OT (operational transformation)? OT требует центрального сервера для трансформации операций и исторически использовался в Google Docs. CRDT децентрализован и проще переносит офлайн-работу, но требует больше памяти на метаданные. Для локальных и P2P-сценариев обычно выбирают CRDT.
Источники: crdt.tech, Wikipedia (CRDT), Redis docs (data types) — ссылки в шапке.