Когда мы переписывали редактор v2, перед нами стоял выбор: остаться на Operational Transforms (OT) или перейти на CRDT. В индустрии последние пять лет тренд на CRDT, и звучит много правильных аргументов «за». Мы посмотрели, посчитали, провели прототипирование — и остались на OT. Расскажу почему.
Проблема, которую обе технологии решают
Двое редактируют один документ. Алиса ставит курсор на позицию 5 и вставляет «привет». Боб одновременно ставит курсор на позицию 3 и вставляет «здрав». Если сервер просто применит их в порядке поступления — получится мусор: позиции «уехали», операции конфликтуют.
OT и CRDT — два разных подхода к тому, как разрулить эту ситуацию так, чтобы у Алисы и Боба после обмена операциями получился одинаковый документ.
OT в двух словах
Идея OT: операции линеаризуются на сервере (есть глобальный порядок), и при получении операции от клиента сервер «преобразует» её относительно операций, которые уже применил с момента, как клиент его в последний раз видел.
Простой пример. Документ "мама". Алиса (с версии 0) делает insert(pos=2, "_") — хочет получить "ма_ма". Параллельно Боб (тоже с версии 0) делает insert(pos=0, "Х"). Сервер получает Боба первым, применяет — документ "Хмама", версия 1. Дальше приходит операция Алисы, всё ещё с базовой версии 0. Сервер преобразует её: «после операции Боба позиции сдвинулись на 1 вправо начиная с 0» → insert(pos=3, "_"). Применяет — получается "Хма_ма".
CRDT в двух словах
CRDT не нужен сервер для линеаризации. Каждый символ имеет уникальный ID (обычно tuple из (siteId, counter)), и порядок между символами определяется правилами сравнения этих ID. Операции коммутативны: можно применять в любом порядке — результат сойдётся.
Почему мы выбрали OT
1. Память
CRDT-документ хранит метаданные про каждый символ. Удалённые символы либо остаются как tombstones, либо требуют отдельных алгоритмов сборки мусора (которые сами по себе небанальны). На документе с большим количеством правок CRDT тяжелее в 5–15 раз. У нас есть пользователи, которые редактируют документ месяцами — это реальная проблема, а не теоретическая.
2. Простота инвариантов
На бумаге CRDT выглядит изящнее. В реальной кодовой базе через два года изящность сменяется страхом тронуть алгоритм сравнения ID, потому что сломав его — сломаешь сходимость всех документов незаметно.
У нас сервер — единая точка истины. Это упрощает дебаг: история операций линейна, можно просто проиграть с любого момента и увидеть, что получилось. С CRDT нужно дополнительно восстанавливать порядок применения у каждого клиента.
3. Серверная авторизация
В корпоративном документе нам всё равно нужен сервер: для прав доступа, аудит-лога, билинга. Раз он всё равно есть, использовать его для линеаризации — естественно. Преимущество CRDT в виде «работает peer-to-peer без сервера» нам не нужно — это не наш сценарий.
Граничные случаи, которые нас укусили
Длинные офлайн-сессии
Если клиент отключился на час и нагенерил локально много правок, OT-преобразование становится дорогим: его операции нужно прогнать через все операции, накопившиеся за это время на сервере. Решение — сжатие истории на сервере (мерж серий вставок в один диапазон) и асимметричное преобразование: для редких офлайн-кейсов мы предпочли потратить больше CPU на сервере, чем держать сложность на каждом клиенте.
Операции над форматированием поверх движущегося текста
Алиса выделяет жирным фрагмент с позиции 10 до 20. Боб одновременно удаляет половину этого фрагмента. Что должно произойти? Сохраняем жирность на оставшейся части. Это очевидно. Но в OT для этого нужно явно прописать правила преобразования для каждой пары операций (вставка, формат), (удаление, формат), (формат, формат) — и не забыть симметричный случай. Мы написали property-based тесты, которые гоняют сотни тысяч случайных пар — это спасло нас от трёх багов, которые на глаз поймать невозможно.
Что почитать
- Ellis & Gibbs, 1989 — оригинальная статья по OT для groupware.
- Sun et al., 1998 — «Achieving Convergence... in Real-Time Cooperative Editing». Жёсткое чтиво, но обязательное.
- Marc Shapiro et al., 2011 — обзор по CRDT, понятный без формализма.