CRDT для текста

Google Docs открыт в двух вкладках, оба редактируют один абзац - как изменения не теряются и не конфликтуют без единого сервера-арбитра?

• **Figma** перешла с OT на кастомный CRDT в 2019 - это позволило убрать merge-сервер из критического пути и снизить latency с 80ms до 12ms для европейских пользователей при американском сервере.
• **Linear** использует Yjs для real-time коллаборации в issues и docs - в их 2022 benchmark Yjs обрабатывает 150 000 операций в секунду на документ, что покрывает любой реальный сценарий.
• **Notion** реализовала собственный block-level CRDT в 2021 после того, как ни Yjs ни Automerge не поддерживали вложенные блоки с rich text - migration затронула 30M+ документов без потери данных.
• **Gitpod** интегрировал Yjs в Monaco Editor для pair programming - два разработчика редактируют один файл с cursor awareness, merge работает peer-to-peer даже при временной недоступности сервера.

Text CRDT

Collaborative text editing - это задача, где два пользователя одновременно редактируют один документ, и оба изменения должны слиться без потерь. Operational Transform (OT), который использует Google Docs с 2006 года, решает это через сервер-арбитр: каждая операция трансформируется относительно уже применённых. Проблема - сервер становится единственной точкой отказа и bottleneck при >100 одновременных редакторов.

Text CRDT убирает сервер из критического пути. Вместо операций ("вставь 'x' в позицию 5") каждый символ получает глобально уникальный идентификатор и хранит ссылки на соседей. Merge двух состояний детерминирован: одинаковый порядок символов гарантируется алгоритмически, а не сервером. Figma, Linear, Notion - все перешли с OT на CRDT в 2019-2022.

Ключевое свойство text CRDT - **convergence**: любые два реплики, получившие одинаковые операции в любом порядке, приходят к идентичному состоянию. Доказывается математически, не тестами.

RGA (Replicated Growable Array)

RGA (Replicated Growable Array) - первый практичный text CRDT, предложен Рохом в 2011. Идея: документ - это связный список узлов, где каждый узел содержит символ, уникальный timestamp (clock, site_id) и ссылку на левого соседа. Вставка 'x' после узла P означает: создать узел (x, my_clock, P). При конфликтах (два узла ссылаются на одного предшественника) побеждает узел с бо`льшим timestamp - это детерминировано на всех репликах.

**Tombstone problem**: удалённые узлы нельзя выбросить немедленно - другой клиент может вставить символ после удалённого. Yjs решает это через garbage collection когда все реплики подтвердили удаление. В документах Notion накапливается ~30% tombstone overhead для долгоживущих документов.

RGA используется в Atom телетайп, ShareDB (альтернативный backend), и как основа для Y.Array в Yjs. Память: O(n) для n символов + O(t) для tombstones. Сложность merge: O(n*m) в худшем случае, где n и m - размеры двух наборов операций.

LSEQ

RGA использует timestamps для идентификации позиций - это работает, но идентификаторы растут линейно. LSEQ (Logarithmic SEQuence) - альтернативный подход, предложенный в 2013. Вместо linked list - дерево позиций с дробными адресами. Символ между позициями 0 и 1 получает адрес 0.5, между 0 и 0.5 - 0.25, и так далее. Ключевой insight: если аллоцировать адреса случайно в свободном интервале, дерево остаётся сбалансированным с высокой вероятностью.

Проблема LSEQ: при sequential prepend (вставка всегда в начало) дерево вырождается - каждый новый адрес в [0, min_existing] и глубина растёт линейно. PaperTrail провёл benchmark в 2021: для 10k символов LSEQ IDs занимают в среднем 40 bytes против 16 bytes у RGA timestamp. На практике Yjs выбрал гибридный подход - RGA с оптимизацией через runs (последовательные вставки объединяются в один узел).

**Runs optimization в Yjs**: если пользователь набирает 'hello' последовательно, Yjs хранит это как один Item с length=5, а не 5 отдельных узлов. Это даёт 5x уменьшение памяти и 3x ускорение encode для типичного набора текста.

Yjs и Automerge

Yjs (Kevin Jahns, 2015) и Automerge (Martin Kleppmann, 2017) - два production-ready CRDT фреймворка, реализующие разные компромиссы. Yjs: оптимизирован для скорости, написан на JS, 11k stars на GitHub. Automerge: оптимизирован для correctness и история изменений, есть Rust core с WASM биндингами.

• **Yjs**: Y.Text использует RGA с runs-оптимизацией. encode/decode через Uint8Array delta updates. Интеграции: Prosemirror, CodeMirror, Monaco, TipTap. Linear использует Yjs для real-time коллаборации - 150k операций/сек на одном документе в их benchmark 2022.
• **Automerge**: каждый документ - неизменяемый snapshot + список changes. Поддерживает полную историю как git. Ink & Switch использует Automerge в Pushpin - локальная коллаборация без сервера вообще.
• **y-websocket** vs **Automerge Repo**: Yjs предполагает центральный awareness-сервер (не для merge, но для presence). Automerge Repo использует sync protocol peer-to-peer - ближе к идеалу CRDT.
• **Размер encode**: Yjs v2 update для 10k символов - ~15KB. Automerge - ~40KB (хранит полный change history). Для мобильных клиентов Figma выбрала кастомный CRDT близкий к Yjs по размеру.

Выбор между Yjs и Automerge - это в первую очередь выбор между throughput и feature completeness. Notion перешла на кастомный CRDT в 2021, потому что ни Yjs ни Automerge не поддерживали их block-level структуру с nested rich text. Для 90% задач достаточно Yjs + y-websocket: setup за 30 минут, production-proven в Linear, Gitpod, Liveblocks.

Итоги

• Text CRDT заменяет позиционные индексы на stable ID символов - merge детерминирован без сервера-арбитра, latency локального apply = 0ms.
• RGA использует linked list с timestamp IDs и tombstone для удалённых символов; LSEQ использует дерево дробных позиций - оба конвергируют, но с разными trade-off по размеру ID и скорости.
• Yjs (RGA + runs-оптимизация) лучше по throughput и размеру для реального набора текста; Automerge (immutable history) лучше для time-travel и offline-first без сервера вообще.

Связанные темы

Text CRDT строится на базе общих CRDT принципов и применяется в связке с несколькими паттернами реального времени:

• CRDT - основы — Text CRDT - специализация общего CRDT для последовательностей символов с учётом порядка вставок
• Vector Clocks — RGA использует hybrid logical clock для генерации уникальных timestamp ID - без clock не было бы детерминированного порядка при конфликтах
• WebSocket и real-time транспорт — Yjs y-websocket и Automerge Repo sync protocol передают delta updates через WebSocket - транспорт определяет latency доставки операций
• Eventual Consistency — Text CRDT - практическая реализация eventual consistency для документов: convergence гарантирована алгоритмически, а не через координацию

Вопросы для размышления

• Tombstone накапливают память - как бы спроектировать garbage collection для RGA документа, который редактируют 1000 пользователей с нестабильным соединением?
• Yjs показывает 150k ops/sec, но semantic merge всё равно может дать нечитаемый текст. Какой UX паттерн мог бы снизить вероятность конфликтных merge без потери real-time коллаборации?
• Automerge хранит полную историю как git - как бы использовать это для автоматического разрешения конфликтов на основе анализа намерений пользователя?

Связанные уроки

• ds-10-crdts