crdts.js·4 scenarios
CRDTs (Conflict-Free Replicated Data Types) concept page. Three replicas R1/R2/R3 with three clients hitting nearest replica (no central coordinator, AP system). Anti-entropy gossip mesh between all replicas. Four scenarios: G-Counter element-wise max merge, OR-Set add-wins with tagged elements, RGA concurrent text insert with deterministic tie-break, and LWW pitfall showing how naive last-write-wins loses updates under clock skew. ADR on CRDTs vs Operational Transform.
В распределённой системе с несколькими репликами клиенты пишут параллельно, сеть рвётся, узлы уходят в офлайн. Если использовать обычные структуры данных (int counter++, set.add(), string + char), то при слиянии двух дивергентных состояний возникает конфликт — кто-то теряет инкремент, кто-то получает мусор. Классические решения: либо центральный координатор (Paxos/Raft — дорого, не работает в офлайне), либо last-write-wins (теряет данные при skew часов).
CRDT — это алгебраический трюк: подбираем такую структуру данных, чтобы операция merge была коммутативной, ассоциативной и идемпотентной. Тогда любые две реплики, обменявшись состояниями в любом порядке, через любое количество раз, гарантированно сойдутся к одинаковому значению. Без координатора. Без потерь. Математически доказуемо.
Это базис offline-first приложений (Notion, Linear, Figma multiplayer), peer-to-peer редакторов (Yjs, Automerge), key-value хранилищ с AP-семантикой (Riak, Redis Enterprise CRDB) и shopping cart из оригинальной Dynamo paper.
CRDT = структура данных, для которой
merge(a, b) = merge(b, a),merge(merge(a,b), c) = merge(a, merge(b,c))иmerge(a, a) = a. Эти три свойства = коммутативность + ассоциативность + идемпотентность = математическая гарантия сходимости без координации.
Две семьи реализации:
Yjs/Automerge — op-based с компромиссами; Riak — state-based.
Три реплики R1/R2/R3 в одном кластере без координатора (AP-система). К каждой подключён свой клиент (A/B/C) — они шлют операции напрямую в ближайшую реплику, не ждут глобального консенсуса. Между репликами — full-mesh anti-entropy gossip: периодический обмен состояниями. Стрелки gossip двунаправленные (анимация использует reverse-edges).
На ноде R1 — ADR-001 с разбором CRDT vs OT для collaborative editing: когда выбирать CRDT (offline-first, P2P, провабельность), когда OT (есть центральный сервер, дорогая metadata). Тренд с ~2020 — CRDT выигрывают (Yjs в Notion/Linear/JupyterLab, Figma multiplayer).
G-Counter — самая простая CRDT. Состояние = вектор [r1: n1, r2: n2, r3: n3], инкремент трогает только свою ячейку, merge — поэлементный max. Тотал = сумма ячеек. Три клиента параллельно инкрементят разные реплики (+5, +3, +7), gossip разносит состояния, любой порядок доставки и любые дубликаты дают одинаковый результат {r1:5, r2:3, r3:7}, total = 15. Ни один инкремент не теряется. PN-Counter = два G-Counter (positive минус negative), даёт decrement.
OR-Set (Observed-Remove Set) — корректное множество с add и remove. Наивный 2P-Set с tombstone-ами имеет фатальный баг: если кто-то параллельно add+remove одного элемента, remove «выигрывает» навсегда. OR-Set чинит это, тегируя каждый add уникальным идентификатором (add("a", t1)); remove удаляет только наблюдённые теги. В сценарии: R1 добавляет a@t1, потом удаляет (видит t1, выкидывает его); параллельно R2, ещё не знающий про remove, добавляет свой a@t2. После gossip остаётся {a@t2} — add wins. Это поведение по умолчанию в Yjs Map, Riak Set, Automerge.
RGA (Replicated Growable Array) для текста — основа Yjs/Automerge. Каждый символ получает уникальный id (replicaId, lamportClock). Параллельные вставки в один и тот же anchor разрешаются детерминированным tie-break по replicaId. На диаграмме: оба клиента вставляют после "Hello" (R1 пишет " world", R2 пишет "!"); все реплики приходят к одному порядку "Hello world!" без сервера и без conflict-resolution UI. Аналогично работают LSEQ, YATA, Logoot — отличаются density метаданных и поведением при удалении.
Failure mode — LWW-Register с wall-clock. Самая частая ошибка: «возьму timestamp от Date.now(), при merge оставлю свежий». R1 пишет x="A" с ts=12:00
x="B" с ts=12:00 (реальное время позже, но часы отстают). LWW-merge оставит "A", "B" пропадает без следа. Лечится: логические часы (vector clocks, Hybrid Logical Clocks) или MV-Register (хранит обе concurrent ветки, разрешение отдаётся приложению — классический Dynamo shopping cart).
ADR-001: CRDT vs Operational Transform. Обе семьи решают concurrent editing. OT (Google Docs, EtherPad) трансформирует входящие операции против локальной истории — нужен центральный сервер для канонического порядка; transformation-функции славятся багами (Google Wave годами чинил OT). CRDT (Yjs, Automerge, Figma) делает merge коммутативным по построению через unique-ids — P2P-friendly, провабельно, но тяжелее по metadata (tombstones, vector versions). С ~2020 CRDT выигрывают в новых продуктах; OT остаётся в legacy и там, где metadata-budget критичен. Ограничение CRDT: нельзя без координации гарантировать глобальные инварианты (balance >= 0, unique-username). Это требует консенсуса.
Что вы платите за CRDT:
| Стоимость | Природа |
|---|---|
| Metadata | Каждый элемент таскает tag/uid/vector; OR-Set хранит tombstones; RGA не удаляет узлы, маркирует deleted |
| GC tombstones | Без causal-stability оракула tombstones накапливаются вечно; нужен периодический epoch-GC |
| Модельные ограничения | Не все операции выражаются как commutative merge; иногда приходится переписывать домен (счётчик likes легко, банковский счёт — нет) |
| Trafic / battery (op-based) | Causal broadcast = передача vector-clock с каждой op; на мобильном дорого |
Что вы получаете:
max не работает с отрицательными правильно). Используйте PN-Counter.stock >= 0), резервирование уникальных ресурсов (имя пользователя, бронь места) — это работа для Raft/Paxos/2PC, не CRDT.