Почему мы выбрали CRDT, а не OT для совместного редактирования
Прошлой осенью мы стояли перед выбором алгоритма для real-time collaboration в заметках. Operational Transformation выглядел проще на первый взгляд. CRDT — теоретически элегантнее. Спойлер: явного победителя не было, но кейс склонил нас к CRDT.
Контекст задачи
В FocusWork заметки — это богатый Markdown с inline-задачами, mentions, checklists. Несколько человек могут одновременно редактировать одну заметку. Нужна устойчивость к offline-edit'ам и реалистичный merge без потери данных.
Кратко: что такое OT и CRDT
Operational Transformation (OT)
Изобретено в Google Wave/Docs. Идея: каждая операция (insert "x" at pos 5) при доставке на другой клиент трансформируется относительно операций которые этот клиент уже применил. Все клиенты в итоге сходятся к одинаковому состоянию.
CRDT (Conflict-Free Replicated Data Types)
Альтернативный подход. Структура данных проектируется так что merge — коммутативная операция. Не важно в каком порядке применяются операции — результат одинаковый. Не требуется central server для координации.
Сравнение по критериям
| Критерий | OT | CRDT |
|---|---|---|
| Простота имплементации | Сложная (особенно текст с tombstones) | Средняя |
| Нужен central server? | Да (для упорядочивания) | Нет |
| Размер данных | Мал | Больше (метаданные) |
| Offline-first | Сложно | Из коробки |
| Производительность | O(n) операции | O(log n) с хорошей структурой |
| Корректность доказана | Только для конкретных алгоритмов | Формально (по теории) |
Что нас зацепило в CRDT
Главное — offline-first архитектура без хака. Юзер пишет заметку в самолёте, потом приходит онлайн, мы синкаем — никаких "rebase" / "resolve conflicts" не требуется. С OT для этого нужен либо снапшотинг и replay, либо очень аккуратный server-side merging.
Также CRDT идеально ложится на нашу архитектуру "одно дерево событий". У нас уже было event-sourcing для других сущностей (задачи, проекты). CRDT-операции для текста встроились как ещё один тип событий в том же потоке.
Что было неприятно
- Размер истории растёт. Каждый символ — это insertion-event с unique ID. У больших заметок (10K+ символов) state может занимать 200-500 КБ.
- Garbage collection непросто. Tombstones нужно держать чтобы не получить "resurrected" символы при поздних concurrent inserts. Полная GC требует консенсуса всех реплик.
- Diff визуализация сложнее. У OT диф = "вот эта операция от Васи". У CRDT — "вот эти 47 микро-операций образуют один смысловой блок". Группировку приходится делать heuristically.
Технический выбор: какой CRDT
Мы посмотрели на несколько вариантов:
- Yjs — production-ready, большое сообщество, JavaScript-нативный
- Automerge — академически чистый, но performance-issues на больших doc'ах
- diamond-types (Rust) — очень быстрый, но менее зрелый
Выбрали Yjs. Главные причины:
- Нативная интеграция с ProseMirror (наш richtext-editor)
- Бенчмарки на нашем профиле нагрузки — 3-4× быстрее Automerge
- Уже используется в продах типа JupyterLab, Discourse, Maxapp
Цифры по результату
После 4 месяцев с Yjs в проде:
- Среднее время merge'а двух offline-веток заметки: ~12 мс
- p99 merge time на 10K-символной заметке: 78 мс
- Конфликтов потребовавших manual resolution: 0 за всё время
- Жалоб юзеров на "пропал текст" / "перепутался порядок": 2 (оказались UI-багами, не CRDT)
Если бы выбирали сегодня
Всё равно CRDT. Возможно посмотрели бы серьёзнее на diamond-types за perf, но Yjs — отличный workhorse и community огромное.
OT же отлично подходит когда у вас есть гарантированный central authoritative server и не нужен полноценный offline. Для Google Docs это работает прекрасно. Для нас с offline-first и P2P-перспективой — нет.
— Инженерная команда FocusWork