Совместное редактирование сложнее, чем кажется

Google Docs обеспечивает совместное редактирование в реальном времени для миллионов пользователей. Выглядит это без усилий: вы печатаете, курсор движется, правки коллеги появляются мгновенно. Но эта простота обманчива. Под капотом совместное редактирование — одна из самых сложных задач в распределённых системах, а два основных подхода к ней (Operational Transformation и CRDT) имеют компромиссы, которые становятся очевидны только тогда, когда пытаешься что-то на них построить.

Идея CRDT (Conflict-free Replicated Data Types) выглядит заманчиво: структуры данных, которые сливаются без конфликтов, не требуют центрального сервера, а сходимость в итоге гарантирована математикой. Но реальность, как обнаружили несколько команд, выбравших CRDT для своих редакторов, беспорядочнее. Теория красивая. Инженерия жестокая.

Проблема: конкурентные правки

Суть проблемы: два пользователя редактируют один документ одновременно, а между ними есть сетевая задержка. Пользователь A вставляет «Hello» на позицию 5. Пользователь B, который ещё не видел правку A, удаляет символ на позиции 5. Каким должен быть итоговый документ?

Однозначного ответа здесь нет. Должно ли удаление B относиться к символу, который стоял на позиции 5 до вставки A, или после? Если до, удаляется исходный символ, и «Hello» остаётся. Если после, удаляется «H» из «Hello». Обе трактовки разумны. Система должна выбрать одну и гарантировать, что все клиенты придут к одному результату. Расхождение означает, что два пользователя видят разные документы, а это единственный непростительный сбой.

The convergence problem:
Initial document: "The quick brown fox"
^ position 10
User A (at time T):  Insert "very " at position 10
User B (at time T):  Delete character at position 10
A sees locally: "The quick very brown fox"
B sees locally: "The quick rown fox"  (deleted 'b')
Now A receives B's operation: delete at position 10
But A already inserted 5 chars at position 10...
Should B's delete now apply at position 10? (deletes 'v' from 'very')
Or at position 15? (deletes 'b' from 'brown' — the original target)
Both A and B must arrive at the same document.
This is the problem OT and CRDTs solve differently.

Operational Transformation (OT)

OT — более старый подход (1989), он решает задачу, трансформируя операции друг относительно друга. Когда A получает от B операцию «удалить на позиции 10», система A проверяет, какие операции она уже применила, а B ещё не видел. Затем операция B пересчитывается с учётом этих изменений: раз A вставила 5 символов на позицию 10, удаление B теперь должно применяться к позиции 15, ведь исходный символ сдвинулся вправо.

Это работает, и Google Docs использует именно этот подход. Проблема в функциях трансформации. Для текстового редактора с операциями вставки и удаления нужно описать, как каждая пара операций трансформируется относительно другой. Для двух типов операций это четыре случая. Добавьте форматирование, таблицы, изображения, списки и комментарии, и количество случаев начнёт расти комбинаторно. Каждый случай должен быть корректным, а тонкие баги приводят к расхождению документа, которое почти невозможно воспроизвести и отладить.

OT традиционно также требует центрального сервера, который задаёт общий порядок операций. Без сервера конкурентные операции могут трансформироваться в разном порядке на разных клиентах, и результаты разойдутся. Google может позволить себе центральный сервер для Docs. Peer-to-peer приложение на OT так просто не построишь.

CRDT: теоретические обещания

CRDT идут принципиально другим путём. Вместо трансформации операций они используют структуры данных, в которых любой порядок слияния даёт один и тот же результат. Это математическая гарантия: если структура данных является корректным CRDT, сходимость достигается автоматически. Никаких функций трансформации, никакого центрального сервера, никакой зависимости от порядка.

Для редактирования текста ключевые варианты — RGA (Replicated Growable Array) и похожие последовательные CRDT. Вместо отслеживания позиций, которые сдвигаются при правках, каждому символу присваивается уникальный глобально упорядоченный идентификатор. Вставки создают новые идентификаторы между существующими. Удаления помечают идентификатор как tombstone: его не убирают физически (подробнее об этом позже).

CRDT sequence representation:
Document: "cat"
Internal representation (simplified):
ID: (A,1) → 'c'   (user A, logical clock 1)
ID: (A,2) → 'a'   (user A, logical clock 2)
ID: (A,3) → 't'   (user A, logical clock 3)
User B inserts 'h' between 'c' and 'a':
ID: (B,1) → 'h'   position: between (A,1) and (A,2)
Document: "chat"
User A (concurrently) inserts 'r' between 'c' and 'a':
ID: (A,4) → 'r'   position: between (A,1) and (A,2)
Both IDs go between the same characters.
The CRDT uses a deterministic tie-breaking rule
(e.g., higher user ID wins) to order them.
Final document: "chart" or "chrat"
(deterministic — all clients get the same result)

CRDT: практическая реальность

Обещание CRDT (отсутствие конфликтов, децентрализация и математически гарантированная сходимость) действительно работает. Но инженерные сложности серьёзны.

Надгробные метки накапливаются. Когда вы удаляете символ в CRDT, его нельзя убрать из структуры: другие реплики могут ещё не получить это удаление, и им нужен идентификатор, чтобы правильно расположить свои правки. Поэтому удалённые символы помечаются как tombstones: невидимые, но всё ещё присутствующие. Сильно отредактированный документ накапливает тысячи таких записей. В документе из 1000 символов может быть 50 000 tombstones из истории правок. Это раздувает память и замедляет операции.

Накладные расходы на метаданные огромны. Каждому символу нужен уникальный идентификатор (идентификатор пользователя плюс логическая временная метка), указатели на соседние идентификаторы и флаг tombstone. Метаданные на один символ могут занимать 50–100 байт. Для документа размером 100 КБ представление в CRDT может весить 5–10 МБ. Это важно для синхронизации: передавать полное состояние CRDT по сети дорого.

Производительность падает с ростом истории. Операции над последовательным CRDT не выполняются за O(1): вставка символа требует найти правильную позицию в последовательности, упорядоченной по идентификаторам, а это зависит от общего количества идентификаторов, включая tombstones. Для документов с длинной историей правок это становится заметно медленным.

Сохранение намерения — сложная задача. CRDT гарантируют сходимость: все реплики приходят к одному состоянию. Но приходят ли они к правильному состоянию? Когда два пользователя одновременно редактируют одно слово, CRDT детерминированно переплетает их символы. Результат сходится, но может оказаться бессмысленным. OT можно настроить так, чтобы правка одного пользователя оставалась целой, а правка другого применялась вокруг неё. CRDT сливают механически.

Yjs и практический компромисс

Yjs — самая популярная CRDT-библиотека для JavaScript, на ней работают совместные функции во многих веб-приложениях. Она хорошо спроектирована и решает многие теоретические проблемы CRDT практическими оптимизациями: компактная бинарная кодировка снижает накладные расходы на метаданные, а сборка мусора tombstones работает, когда все клиенты онлайн.

Но Yjs не волшебство. Команды, которые её внедряют, обнаруживают, что CRDT-библиотека решает проблему сходимости, но не проблему совместной работы. Всё равно нужны: сигнальный сервер для обнаружения пиров, слой хранения для офлайн-изменений, разрешение конфликтов для высокоуровневых операций (что делать, если два пользователя перестраивают один и тот же раздел?), отслеживание присутствия (курсоры, выделения), undo/redo, который учитывает правки других пользователей, и управление правами.

Некоторые команды, построив совместный редактор на Yjs, пришли к выводу, что подход CRDT добавляет сложность, которая им не нужна. Если в вашем приложении есть центральный сервер (а в большинстве он есть), OT или даже более простые подходы, например last-write-wins с обнаружением конфликтов, могут быть практичнее. CRDT раскрываются в по-настоящему peer-to-peer сценариях: офлайн-первых приложениях, local-first софте и системах, где нельзя предполагать наличие центрального органа.

Что делать большинству приложений

Если вы добавляете совместное редактирование в своё приложение, вот прагматичная схема решения.

• Если у вас есть центральный сервер и документы небольшие: используйте OT. Подход Google работает. Для Node.js OT реализован в библиотеках вроде ShareDB. Центральный сервер упрощает всё: порядок операций, хранение, разрешение конфликтов, права доступа.
• Если нужна офлайн-работа или peer-to-peer: используйте CRDT (Yjs или Automerge). CRDT — единственный подход, который корректно обрабатывает по-настоящему офлайн-редактирование и синхронизацию peer-to-peer. Принимайте накладные расходы на метаданные и накопление tombstones как цену децентрализации.
• Если соавторы редко правят один и тот же раздел одновременно: возможно, не нужно ни то, ни другое. Простая блокировка (один редактор на раздел) или last-write-wins с хорошим интерфейсом разрешения конфликтов покрывает многие реальные сценарии совместной работы без сложности OT или CRDT.
• Если вы строите конкурента Google Docs: вам нужна команда инженеров распределённых систем и годы разработки. Это не проект на выходные. Поверхностная простота совместного редактирования скрывает огромную сложность.

Честная оценка

Совместное редактирование относится к тем задачам, где сложность неочевидна. Счастливый путь, когда два пользователя вносят непересекающиеся правки, работает почти с любым подходом. Трудные случаи (конкурентные правки в одной и той же области, офлайн-редактирование с последующей синхронизацией, сложные структуры документа вроде таблиц, вложенных списков и встроенных объектов) требуют глубокого понимания компромиссов между OT и CRDT.

Ни один подход не является строго лучше. OT проще с сервером и сложнее без него. CRDT работают без сервера, но несут накладные расходы на метаданные и накопление tombstones. Оба требуют тщательной инженерной работы помимо самого алгоритма, и эта работа (присутствие, хранение, права, undo) часто оказывается сложнее самой проблемы сходимости.

Индустрия медленно сходится к прагматичному гибриду: CRDT для модели данных (автоматические гарантии слияния) и сервер для координации (присутствие, права, сборка мусора). Это даёт лучшее из двух миров, то есть математическую сходимость плюс практическую инфраструктуру. Но это также означает сложность обоих миров, поэтому совместное редактирование остаётся трудной задачей и спустя 35 лет исследований.