Что больнее OT или CRDT в совместном редактировании? И почему до сих пор нет идеала?

Меня зовут Антон Леонтьев, я старший разработчик в команде ядра редакторов МойОфис. Мы создаём офисные приложения, которыми ежедневно пользуются более 12 500 организаций, и совместное редактирование — одна из ключевых возможностей наших продуктов.

И знаете, что самое обидное в этой теме? За 35 лет исследований были опубликованы сотни научных работ. Google Docs работает с 2006 года. У Figma, Notion и Linear свои реализации. Казалось бы, задача давно решена, но стоит копнуть глубже, и становится понятно: универсального решения нет.

В Google Drive и Dropbox до сих пор всплывают баги с одновременным перемещением папок. В Notion при параллельном редактировании одного и того же абзаца можно потерять часть изменений. Даже Yjs — самая популярная CRDT-библиотека — не хранит полную историю документа в привычном для нас виде.

В этой статье разберём теорию, узнаем, какие проблемы решают Operational Transformation (OT) и Conflict-free Replicated Data Types (CRDT), на каких математических идеях они основаны, чем отличаются архитектурно и какие компромиссы неизбежно возникают в каждом подходе.

Интересно узнать, почему даже Google не смог сделать идеальное решение? Детали под катом.

---

Содержание

1. Почему до сих пор нет идеального решения

2. Что видят пользователь и разработчик

3. Постановка задачи

4. Историческая справка

5. OT: математика трансформаций

6. CRDT: структуры данных без конфликтов

7. Сравнение подходов: «налоги» OT и CRDT

8. Архитектура системы совместного редактирования

9. Библиография

Почему до сих пор нет идеального решения

Потому что каждый подход — это набор компромиссов. Реализации OT традиционно опираются на центральный сервер, который знает «истинную» версию документа и трансформирует операции клиентов относительно друг друга, что упрощает контроль, но усложняет реализацию. Трансформации нужно писать аккуратно, учитывать порядок, причинность, зависимые операции.

В реальной жизни всплывают десятки граничных случаев — от одновременного удаления одного и того же диапазона до каскадных изменений структуры документа. Любая ошибка в логике трансформации, и реплики начинают расходиться.

CRDT, наоборот, изначально проектировались так, чтобы узлы могли работать автономно и сходиться без центрального координатора. Звучит красиво: нет единой точки отказа, офлайн — естественный режим работы. Но за это приходится платить: документ внутри превращается в сложную структуру с уникальными идентификаторами, метаданными и так называемыми «надгробиями» (tombstones) — записями об удалённых элементах, которые нельзя просто выбросить, иначе нарушится сходимость. Со временем такие структуры разрастаются, потребляют память и требуют механизмов очистки.

Гибридные подходы, например, Eg-walker, появившийся в 2024 году, пытаются совместить сильные стороны обоих миров. Но это пока свежие идеи без десятилетий эксплуатации под нагрузкой. А в системах совместного редактирования проверка временем — критически важный фактор.

Кстати, если тема кажется знакомой – это не дежавю. Мои коллеги из МойОфис уже писали на Хабре про совместное редактирование почти десять лет назад. Та серия статей была посвящена деталям реализации OT в нашем продукте. Сейчас, с высоты прошедших лет и накопившегося опыта, хочется дать более широкий взгляд: сравнить подходы, посмотреть на эволюцию CRDT и понять, изменилось ли что-то принципиально за это время.

Спойлер: изменилось многое, но универсального решения по-прежнему нет.

А теперь давайте посмотрим на проблему глазами человека, для которого всё это вообще делается, — пользователя.

Что видят пользователь и разработчик

Сценарий 1: Нестабильная сеть

Представим: пользователь едет в метро и редактирует документ, интернет пропадает на 30 секунд, за это время коллега меняет тот же абзац. Связь восстанавливается и начинается синхронизация. С точки зрения алгоритма это просто две конкурентные ветки изменений. С точки зрения пользователя это тревожный момент: «Мой текст сейчас исчезнет?»

Если после подключения текст внезапно «перепрыгнул», перемешался или часть правок пропала — доверие к продукту падает мгновенно.

Сценарий 2: Большой документ

Техническая документация на 500 страниц, одновременно над ней работают 10 человек, документ открывается 15 секунд. При каждом изменении интерфейс подвисает на 200 миллисекунд.

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

Сценарий 3: Долгий офлайн

Инженер три дня в командировке без интернета и за это время переписал целый раздел в документе. Когда он возвращается, то видит, что коллеги за это время изменили структуру документа, переместили главы и удалили старые блоки. Теперь нужно слить две большие и логически сложные ветки изменений. Это уже не просто «вставка против удаления», а конфликт на уровне структуры.

Если алгоритм недостаточно аккуратен, то результат может быть формально корректным, но логически странным: текст окажется в неожиданном месте, форматирование собьётся, ссылки сломаются. И снова пользователь будет винить продукт, а не распределённые системы.

Сценарий 4: Форматирование и намерение

Маша выделяет слово жирным. В этот же момент Боря дописывает текст сразу после этого слова. Должен ли новый текст быть жирным? С точки зрения позиции курсора — возможно, да. С точки зрения намерения Маши — она хотела выделить конкретное слово, а не всё, что появится после него. Боря вообще не думал про форматирование.

Алгоритм не умеет читать мысли. Он оперирует диапазонами, индексами и идентификаторами, а намерение пользователя — это семантика, которая не всегда выводится из операций. И вот здесь становится понятно: задача совместного редактирования — это не только про математическую сходимость, но и про баланс между строгой формальной моделью и человеческим ожиданием «чтобы работало логично».

А что видит разработчик?

Если для пользователя «пропал текст» или «редактор тормозит», то для разработчика за каждым таким кейсом стоят вполне конкретные технические боли.

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

Порядок операций. В распределённой системе нет глобальных часов. Сообщения могут прийти не в том порядке, в котором были отправлены. Более того, разные клиенты могут увидеть разный порядок действий. Алгоритм должен гарантировать одинаковый финальный результат при любом допустимом порядке доставки.

Потеря сообщений. Пакет потерялся, соединение оборвалось, клиент переподключился. Нужна повторная отправка, дедупликация, проверка причинно-следственных зависимостей и всё это без дублирования операций.

Согласованность состояния. В конечном итоге все реплики документа обязаны прийти к одному и тому же состоянию. Не «примерно одинаковому», а бит-в-бит совпадающему, иначе расхождение будет накапливаться.

Намерение пользователя. Пожалуй, самая сложная часть. Операция должна делать то, что хотел пользователь, а не просто то, что получается после механического применения индексов. Если человек удалял «последнюю букву слова», он ожидает, что именно она исчезнет, даже если параллельно кто-то что-то вставил рядом.

Чтобы понять, как всё это решается, рассмотрим простейший пример и увидим, что даже он не так прост, как кажется.

Постановка задачи

Есть документ с таблицей 2×2:

Два пользователя редактируют её одновременно, без координации.

Mr. X вставляет новую итоговую строку между «Январь» и «Февраль»:

InsertRow(1, ["Итого","300"])

Он ожидает результат — таблицу 3×2:

Mr. Y в это же время удаляет второй столбец, убирая числовые значения:

DeleteColumn(1)

Если аккуратно объединить оба намерения, логичный итог — таблица 3×1( три строки в одном столбце: «Январь», «Итог», «Февраль»). Но проблема возникает в реальном распределённом сценарии.

Mr. X и Mr. Y работают параллельно, каждый на своём клиенте, и не знают о действиях друг друга. Представим ситуацию на стороне Mr. X: он уже вставил строку локально, и его таблица выглядит как 3 на 2. В этот момент к нему приходит операция от Mr. Y:

DeleteColumn(1)

Проблема в том, что Mr. Y составлял эту команду для исходной таблицы 2×2, ещё не зная о вставке строки. В его версии индексы столбцов не изменились, но в текущей версии Mr. X появилась строка «Итого» с двумя ячейками.

Если без дополнительной логики просто применить DeleteColumn(1), строка «Итого» останется, ячейка «300» тоже останется, так как у обеих есть id, но столбец, которому принадлежит ячейка «300» удален. Получается что ячейка есть, а столбца нет. Так мы и получаем структурный конфликт. Формально ничего не потеряно, но документ невалиден.

Итог — таблица 3×1, но с неопределенным состоянием. Новая строка создавалась для двух столбцов, но второй удален. Разные реализации решат проблему по-разному и результаты разойдутся.

Это и есть классическая проблема concurrency control в распределённых системах: одна и та же операция, применённая в разных контекстах, даёт разный результат.

И вот здесь пути расходятся.

Operational Transformation (OT) пытается трансформировать входящие операции относительно уже применённых, чтобы сохранить намерение пользователя. Удалялся второй столбец — значит, нужно скорректировать операцию так, чтобы она по по-прежнему удалила именно его, независимо от того, что вставил Mr.X.

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

Чтобы понять, откуда вообще появились эти идеи и почему они устроены именно так, заглянем в историю.

Историческая справка

Появление OT (1989)

Operational Transformation появилась в работе Clarence A. Ellis и Simon J. Gibbs в исследовательском центре MCC. Их система GROVE (GRoup Outline Viewing Edit) представила первый алгоритм операционной трансформации — dOPT.

Ключевая идея по тем временам была по-настоящему революционной: вместо того чтобы блокировать документ во время редактирования, как это делали многие системы того времени, операции предлагалось трансформировать относительно уже выполненных конкурентных операций. Иными словами, пользователи могли редактировать параллельно, без ожидания «свободной блокировки», а система сама приводила их изменения к согласованному виду. Консистентность сохраняется, работа не останавливается.

Jupiter (1995)

Система Jupiter, созданная в Xerox PARC, упростила модель и сделала её более практичной. Она перешла к клиент-серверной архитектуре и ввела двумерное пространство состояний для отслеживания истории операций. Одна ось — это количество операций, примененных клиентом локально, вторая — количество операций, полученных от сервера. Каждая пара (клиент, сервер) однозначно описывает состояние, в котором находится клиент в момент создания операции. Это позволят серверу понять, относительно какой версии документа была сформирована операция, и корректно трансформировать её перед применением.

Если перевести это с академического языка на инженерный: сервер стал точкой координации, а состояние клиента и сервера отслеживалось так, чтобы корректно трансформировать операции при расхождении версий.

Именно алгоритм Jupiter позже лёг в основу Google Wave, а затем повлиял на современные реализации Google Docs.

Google Wave (2009)

Google Wave стал самым масштабным промышленным внедрением OT своего времени. Это был амбициозный проект: почта, чат и совместное редактирование в одном продукте.

В технической документации Wave говорилось:

«Отправной точкой для OT в Wave стала статья “Окна взаимодействия в условиях высокой задержки и низкой пропускной способности в системе совместной работы Jupiter”. Как и система Jupiter, описанная в статье, Google Wave реализует OT на основе клиент-серверной архитектуры».

Google не изобрёл OT заново, а взял академические наработки, адаптировал их под масштаб интернета и довёл до промышленного уровня. И именно с этого момента OT окончательно перестал быть чисто исследовательской темой и стал основой для массовых редакторов.

Появление CRDT (2006–2011)

Если OT вырос из идеи «давайте трансформировать операции», то CRDT родились из другого направления — исследований распределённых систем с так называемой eventual consistency, согласованностью «в конечном итоге».

Одним из предшественников CRDT считается система Bayou (1995) из Xerox PARC. Она разрабатывалась для мобильных устройств — по тем временам это звучало почти футуристично. Основная идея Bayou: любая реплика может принимать изменения локально, без немедленной синхронизации с другими узлами, согласование произойдёт позже.

Это был важный сдвиг мышления: сеть ненадёжна, соединение прерывается — значит, архитектура должна это принимать как норму, а не как исключение.

Первым текстовым CRDT принято считать WOOT (2006). В нём каждый символ строки получал уникальный идентификатор и хранил ссылки на соседние элементы. Строка превращалась не в массив символов, а в связную структуру с явными отношениями «кто за кем следует». Удаление символа не уничтожало его физически — он помечался как удалённый. Так появилось понятие «надгробий» (tombstones).

Сам термин «Conflict-free Replicated Data Type» был формально введён в 2011 году Марком Шапиро, Нуно Прегисой, Карлосом Бакейро и Мареком Завирски. В их работе говорится:

«Репликация данных при согласованности в конечном итоге позволяет любой реплике принимать обновления без удалённой синхронизации. Это обеспечивает производительность и масштабируемость в крупномасштабных распределённых системах (например, в облаках)».

Это значит: мы строим такие структуры данных, для которых математически доказано, что они сойдутся к одному состоянию независимо от порядка доставки операций.

В том же 2011 году появился RGA (Replicated Growable Array) — одна из наиболее практичных реализаций последовательности как CRDT. Позже именно эта идея легла в основу Automerge и других библиотек.

Хронология развития

Если собрать всё в единую картину, эволюция выглядит примерно так:

Если внимательно посмотреть на таблицу, то видно, что OT появился раньше и долго доминировал в промышленных системах. CRDT сначала развивались в академической среде, а активный рост библиотек и production-решений начался заметно позже.

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

Математика трансформаций OT

Базовая модель

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

Формально это записывают так:

Функция трансформации принимает операцию O1 и «учитывает» операцию O2, которая уже была применена к документу.

Если O1 создавалась для состояния S, а O2 превратила S в S’, то O1′ — это версия O1, корректная уже для состояния S’. Идея в том, что O1′ должна выражать то же намерение пользователя, что и исходная O1, но в обновлённом контексте.

На бумаге всё выглядит элегантно, на практике же даже для примитивной модели «вставка одного символа / удаление одного символа» приходится описывать целый набор функций.

Transformation Functions

Для базовой текстовой модели с двумя типами операций Insert и Delete нам нужно четыре функции трансформации.

Insert–Insert

Operation transform_II(Insert o1, Insert o2)
{
    if (o1.position < o2.position)
    {
       return Insert(o1.position, o1.char, o1.siteId);
    }
    else if (o1.position > o2.position)
    {
       return Insert(o1.position + 1, o1.char, o1.siteId);
    }
    else
    {
       // Tie-breaker: используем site ID 
       if (o1.siteId < o2.siteId)
       {
           return Insert(o1.position, o1.char, o1.siteId);
       }
      else
      {
           return Insert(o1.position + 1, o1.char, o1.siteId);
      }
    }
}

Когда два пользователя одновременно вставляют символы, всё сводится к сравнению позиций.

Если o1 вставляется раньше, чем o2 — позиция не меняется.
Если позже — позицию нужно сдвинуть вправо на 1, потому что o2 уже добавила символ перед ней.

Если же позиции совпадают, то начинается самое интересное. Нужно правило разрешения конфликта. Обычно используют siteId (идентификатор клиента): например, операция от «меньшего» siteId идёт первой, а вторая сдвигается вправо.

Это и есть tie-breaker — детерминированное правило, чтобы все реплики приняли одинаковое решение.

Insert–Delete

Operation transform_ID(Insert o1, Delete o2)
{
    if (o1.position <= o2.position)
    {
        return Insert(o1.position, o1.char, o1.siteId);
    }
    else
    {
        return Insert(o1.position - 1, o1.char, o1.siteId);
    }
}

Если вставка происходит до удаляемого символа, то ничего менять не нужно.
Если после — позицию нужно уменьшить на 1, потому что документ уже стал короче.

Здесь логика чуть проще, но важно помнить: мы не просто пересчитываем индекс. Мы пытаемся сохранить намерение «вставить в то же логическое место».

Delete–Insert

Operation transform_DI(Delete o1, Insert o2)
{
    if (o1.position < o2.position)
    {
        return Delete(o1.position);
    }
    else
    {
        return Delete(o1.position + 1);
    }
}

Зеркальная ситуация. Если удаление происходит до вставки — индекс не меняется.
Если после или на той же позиции, то его нужно сдвинуть вправо, потому что вставка увеличила длину документа.

Delete–Delete

Operation transform_DD(Delete o1, Delete o2)
{
   if (o1.position < o2.position)
   {
       return Delete(o1.position);
   }
   else if (o1.position > o2.position)
   {
       return Delete(o1.position - 1);
   }
   else
   {
       // Обе удаляют один символ – становится no-op return NoOp();
   }
}

Если удаляются разные позиции, то просто корректируем индекс аналогично предыдущим случаям. Но если обе операции удаляют один и тот же символ, одна из них должна превратиться в no-op (пустую операцию), иначе символ будет «удалён дважды», и индексы поползут.

На этом этапе может показаться: «Ну да, четыре функции, немного условий — вполне управляемо». И вот тут начинается самое интересное.

Во-первых, это только для модели «один символ». Как только появляются диапазоны, форматирование, структурные элементы, вложенные объекты, то количество случаев растёт экспоненциально.

Во-вторых, этих функций недостаточно. Чтобы OT был корректным, должны выполняться строгие свойства, например:

• Convergence — все реплики приходят к одному состоянию.

• Inclusion Transformation property (TP1).

• Transformation Composition property (TP2).

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

Свойства корректности TP1 и TP2

Чтобы OT работал математически корректно, должны выполняться специальные свойства трансформации. Самые известные из них — TP1 и TP2.

TP1 — «ромбовидное свойство»

Формально оно записывается так:

Идея такая — из одного и того же состояния S есть два пути:

1. применить O1, а затем трансформированную версию O2

2. применить O2, а затем трансформированную версию O1

Оба пути обязаны привести к одному и тому же итоговому состоянию.

Если изобразить это схемой, получится «ромб»: верхняя вершина — исходное состояние, две ветки вниз — разные порядки применения операций, нижняя точка — один и тот же результат.

TP1 необходимо для корректной обработки двух конкурентных операций. Без него система гарантированно будет расходиться.

TP2 — для трёх и более операций

Когда операций становится три и больше, всё усложняется.

Формально TP2 записывается так:

Смысл в следующем: если есть три конкурентные операции, то не должно иметь значения, в каком порядке мы «склеим» первые две перед трансформацией третьей.

Иначе говоря, независимо от того, какую пару операций мы сначала согласовали между собой, трансформация третьей операции должна дать одинаковый результат.

Если TP1 про «ромб» из двух операций, то TP2 уже про объёмную геометрию состояний.

Почему TP2 — это кошмар

И вот тут начинается настоящая боль.

В исследовании Randolph и соавторов (2013) говорится:

«Используя метод синтеза контроллера, мы показываем, что существуют такие функции трансформации, которые удовлетворяют только свойству TP1 для базовых сигнатур операций вставки и удаления. Более того, с этими простыми сигнатурами невозможно одновременно удовлетворить и TP1, и TP2».

Проще говоря: если у вас есть только Insert и Delete с позицией и символом, то реализовать корректный OT, удовлетворяющий обоим свойствам, в принципе невозможно. Нужно расширять модель: добавлять дополнительные параметры, контекст, историю.

Более того, многие опубликованные функции трансформации, которые заявляли поддержку TP2, позже оказались некорректными:

• IT-функция трансформации Эллиса нарушает TP1 в определённых сценариях;

• IT-функция Ресселя нарушает TP2;

• IT-функция Сулеймана, даже с дополнительными параметрами, тоже может приводить к расхождению состояний.

То есть даже академические решения, прошедшие рецензирование, со временем находили контрпримеры.

Joseph Gentle, бывший инженер Google Wave и автор ShareJS, сформулировал это так:

«К сожалению, реализовывать OT — это мучение. Существует миллион алгоритмов с разными компромиссами, и большинство из них застряли в академических статьях. Эти алгоритмы чрезвычайно сложны и требуют огромных усилий, чтобы реализовать их корректно. […] На написание Wave ушло два года, и если бы мы переписывали его сегодня, это заняло бы почти столько же времени».

Два года. И это Google с их ресурсами, исследовательскими командами и доступом к авторам оригинальных алгоритмов. В этот момент становится понятно, почему сообщество начало искать альтернативу. И почему спустя почти 20 лет после появления OT на сцену вышли CRDT с обещанием: «никаких трансформаций, сходимость гарантирована по определению».

Но, как мы увидим дальше, за это обещание тоже приходится платить.

Exclusion Transformation и Undo

Но даже TP1 и TP2 — это ещё не весь набор проблем.

В классическом OT есть не только Inclusion Transformation (IT) — трансформация операции с учётом уже применённой. Есть ещё и Exclusion Transformation (ET), «обратная» трансформация, которая нужна для реализации undo.

Если пользователь отменяет операцию, нам нужно как бы «вычесть» её влияние из системы, при этом корректно обработав все последующие изменения.

ET(O1, O2) -> O1′, где O1′ — версия операции O1, из которой исключён эффект O2.

Звучит логично: если мы когда-то учли влияние операции, при отмене нужно его корректно убрать. На практике это означает ещё четыре функции трансформации (по аналогии с Insert/Insert, Insert/Delete и т.д.) плюс отдельные свойства корректности — IP1, IP2, IP3. То есть поверх уже сложной математики IT добавляется ещё один слой.

Конкретный edge case с Undo

Исходный документ: ""

Mr. X локально: ins(0,"Hello") -> "Hello"

Mr. Y видит тот же документ и вставляет "!" внутрь слова, после "Hel":

ins(3,"!") -> у Mr. Y: "Hel!lo"

После синхронизации сервер упорядочивает операции.

ins(0,"Hello") от Mr. X уже в истории и состояние документа "Hello"

ins(3,"!") от Mr. Y создавался для того же состояние "Hello" и трансформация не нужна.

Итоговый документ у обоих "Hel!lo"

Mr. X нажимает Undo своего ins(0, "Hello")

Inverse(ins(0,"Hello")) = del(0,5)

ET трансформирует del(0,5) против ins(3,"!"):

• Шаг 1: вставка символа "!" попадает внутрь удаляемого диапазона [0,5) и ET определяет это как случай «вставка внутри удаления».

• Шаг 2: ET расширяет диапазон на 1, чтобы захватить вставленный символ del(0,5) -> del(0,6)

• Шаг 3: применяем del(0,6) к "Hel!lo" и получаем ""

Ожидалось "!", ведь Mr. X убрал своё слово, а знак от Mr. Y должен был остаться.

Получилось "", потому как ET удалил вместе с "Hello" , "!" и оставшиеся символы Mr. X.

Математически ET отработал верно, так как вставка внутри удаляемого диапазона расширяет удаление. Но намерение Mr. Y потеряно полностью. Чем сложнее пересечение между операцией Undo и параллельной историей — тем выше шанс, что ET сохранит корректность формально, но сломает смысл.

Академические исследования (например, Sun, 2000) показывают, что ни одно существующее решение не способно гарантировать корректную отмену любой операции в произвольный момент времени в полностью коллаборативном сценарии. Пример выше — это штатная ситуация для любого редактора.

Даже production-системы вроде Google Docs используют компромиссные подходы: undo работает в рамках «локальной» истории пользователя, а не как глобальная математически строгая операция над всей историей документа.

Undo в collaborative-контексте — отдельная головная боль, и зачастую именно он ломает красивые теоретические модели.

Сервер как арбитр — спасение от TP2

Так как же с этим живут реальные системы?

Jupiter и Google Docs пошли архитектурным путём. Вместо того чтобы полностью удовлетворять TP2 в децентрализованной модели, они ввели центральный сервер, который устанавливает глобальный порядок операций.

Протокол упрощённо выглядит так:

1. Клиент создаёт операцию и применяет её локально — оптимистичный UI.

2. Отправляет операцию серверу и ждёт подтверждения.

3. Сервер трансформирует операцию относительно серверной истории.

4. Применяет её к канонической версии документа.

5. Рассылает трансформированную операцию всем клиентам, включая инициатора.

6. Инициатор получает свою операцию обратно уже в серверной версии. Если сервер её трансформировал (потому что пришли чужие операции), инициатор должен применить diff между тем, что он отправил и тем, что вернулось. Pending-операции инициатора тоже трансформируются относительно полученной.

7. Остальные клиенты трансформируют свои pending-операции относительно полученной.

Сервер становится единственным источником истины. Он линеаризует поток изменений, и в системе фактически не возникает трёх по-настоящему конкурентных операций, так как они упорядочиваются централизованно. Благодаря этому строгая необходимость выполнения TP2 исчезает. Архитектура компенсирует математическую сложность.

Но у этого решения есть фундаментальное ограничение: сервер обязателен. Полноценный офлайн-режим невозможен без очереди отложенных операций и последующей синхронизации с центральной историей.

И именно это ограничение OT — зависимость от координатора и сложность глобальной истории — во многом подтолкнуло сообщество к поиску альтернатив. Так на сцену и вышли CRDT.

CRDT: структуры данных без конфликтов

Философия подхода

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

Ключевое свойство здесь — Strong Eventual Consistency (SEC), строгая согласованность в конечном итоге. Она включает два требования:

• Eventual Delivery — если обновление доставлено хотя бы одной реплике, то в конечном итоге оно будет доставлено всем;

• Strong Convergence — если две реплики получили одинаковый набор обновлений, то их состояние немедленно становится эквивалентным.

Обратите внимание на формулировку. Не «когда-нибудь станут одинаковыми», а сразу после получения одинаковых обновлений. Порядок доставки не имеет значения. Нет необходимости в глобальном упорядочивании. Как такое вообще возможно? Ответ в алгебре.

Join-полурешётки

Формально CRDT описываются через структуру, называемую join-полурешёткой. Если упростить определение: это множество состояний с частичным порядком и операцией слияния (merge), которая вычисляет наименьшую верхнюю границу двух состояний.

Обозначается это обычно как:

(S, <=) с операцией U

Где U — это операция объединения (merge).

Чтобы структура гарантировала сходимость, операция merge должна обладать тремя свойствами:

1. Коммутативность:

Не важно, в каком порядке объединять состояния.

2. Ассоциативность:

Можно сливать постепенно, по частям.

3. Идемпотентность:

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

И вот именно эта тройка свойств делает CRDT устойчивыми к типичным проблемам распределённых систем:

• переупорядочивание сообщений не страшно (коммутативность);

• дублирование сообщений безопасно (идемпотентность);

• состояние можно синхронизировать инкрементально (ассоциативность).

Обратите внимание на контраст с OT, в котором мы боремся с порядком применения операций. В CRDT порядок просто перестаёт иметь значение, так как он вынесен из модели. Звучит абстрактно и немного академично.

На самом деле это значит, что мы проектируем структуру данных так, чтобы merge всегда был безопасным, независимо от того, как именно и когда прилетели обновления. Дальше становится интереснее, потому что для текста обычное «множество» не подходит. Нужно уметь моделировать последовательность символов, вставки между вставками и удаления.

Посмотрим, как это делается в реальных текстовых CRDT.

State-based vs Operation-based vs Delta-state

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

State-based CRDT (CvRDT) отправляют между репликами полное состояние.

Идея простая: у нас есть функция merge, которая вычисляет наименьшую верхнюю границу двух состояний.

def merge(state1, state2):
    return least_upper_bound(state1, state2)

Каждая реплика периодически шлёт своё состояние другим, а получатель просто делает merge.

Плюс такого подхода — высокая устойчивость к сетевым проблемам. Сообщения могут теряться, приходить повторно, в любом порядке. Итоговое состояние всё равно сойдётся благодаря свойствам полурешётки.

Минус — неэффективность. Если структура большая, например, документ на сотни страниц, пересылать её целиком дорого.

Operation-based CRDT (CmRDT) отправляют не состояние, а операции.

def apply(state, operation):
    return state.apply(operation)

Здесь важное требование: операции должны быть коммутативными. Если две реплики применят одинаковый набор операций, в любом порядке, результат должен совпасть.

Сообщения компактные, но при этом сеть должна гарантировать доставку каждой операции ровно один раз (exactly-once delivery) или разработчик должен сам обеспечивать дедупликацию.

Delta-state CRDT — гибридный подход. Вместо полного состояния отправляется дельта — «кусочек состояния», отражающий изменения после операции.

def apply_delta(state, delta):
    return merge(state, delta) # дельта = «разница» после операции

Дельты должны быть композируемыми (если есть d12 и d23, их объединение даёт d13), идемпотентными и существенно меньше полного состояния. Это компромисс между надёжностью state-based и компактностью operation-based. Именно такой подход использует Yjs.

Базовые типы CRDT

Прежде чем говорить о текстовых структурах, полезно понять строительные блоки.

G-Counter (Grow-only Counter)

Самый простой CRDT — счётчик, который можно только увеличивать. Каждая реплика хранит свой собственный слот в словаре:

class GCounter:
    def_init_(self, replica_id):
       self.counts = {} # Map<ReplicaId, int> 
       self.replica_id = replica_id

    def increment(self):
        self.counts[self.replica_id] = self.counts.get(self.replica_id, 0) + 1

    def value(self):
        return sum(self.counts.values())

    def merge(self, other):
        for rid, count in other.counts.items():
            self.counts[rid] = max(self.counts.get(rid, 0), count)

Каждая реплика увеличивает только своё значение. Merge — это поэлементный max. Итоговое значение — сумма всех слотов. Просто, прозрачно и идеально укладывается в свойства полурешётки.

PN-Counter

Если нужно поддержать и инкременты, и декременты, берут два G-Counter:
один для плюсов, другой для минусов.

Значение считается как:

OR-Set (Observed-Remove Set)

Набор с более интересной логикой. Каждая операция add создаёт уникальный тег.
Операция remove удаляет только те теги, которые она «наблюдала».

Если add и remove происходят конкурентно, элемент остаётся в множестве — это так называемая add-wins семантика. Такая модель позволяет избежать конфликта «добавили и удалили одновременно».

LWW-Register (Last-Writer-Wins)

Здесь всё проще: у каждого значения есть timestamp. При конфликте побеждает запись с более поздней меткой времени.

Это не идеально с точки зрения семантики (кто последний — тот и прав), но предсказуемо и просто. Именно такой подход используется в Figma для свойств объектов: если два пользователя одновременно меняют, например, цвет, побеждает последнее изменение по времени.

Все эти структуры по сути кирпичики, но текст гораздо более сложная сущность, чем счётчик или множество. В тексте есть порядок, вложенность, форматирование, семантика. И вот там начинается настоящая инженерная магия CRDT.

Сравнение сложности доказательств

Если посмотреть на оба подхода с точки зрения математики, разница становится довольно заметной.

В OT корректность держится на целом наборе свойств: TP1, TP2 для трансформаций включения и IP1, IP2, IP3 для исключающих трансформаций (undo). Каждое из них нужно не просто «интуитивно понимать», а формально доказывать для конкретного набора операций и их сигнатур.

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

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

На простом тексте это выглядит так: вместо строки с индексами каждый символ получает уникальный ID вида (clientId, localClock) и хранит ссылку на символ, после которого он вставлен. Mr. X вставляет «H» с ID (X,1) после начала документа, Mr. Y вставляет «W» с ID (Y,1) туда же. При слиянии оба символа сохраняются – никто не теряется, порядок определяется детерменированным tie-breaker по clientId. Никаких трансформаций, никаких функций ET/IT – структура данных сама гарантирует сходимость.

Сравнение подходов: «налоги» OT и CRDT

Но математика — только часть картины. В реальном продукте важно, какую «цену» вы платите за каждый подход. Если разложить по ключевым аспектам, получается так:

Не существует «победителя» в вакууме.

OT платит налог сложностью трансформаций и зависимостью от сервера, но выигрывает в компактности состояния и предсказуемости загрузки.

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

Но прежде чем принимать решение, полезно посмотреть, как эти подходы ведут себя в реальных продуктах и где именно начинают ломаться.

Архитектура системы совместного редактирования

Какой бы подход вы ни выбрали — OT или CRDT — «скелет» системы обычно похож. Есть клиенты, канал связи, слой синхронизации и модель документа. Разница в том, что именно считается «истиной» и как именно изменения приводятся к общему виду, но точки, где всё может пойти не так, почти одинаковые. Если смотреть на систему глазами инженера, она обычно разваливается (или начинает вести себя странно) в пяти местах.

Сеть. Это классика распределённых систем: задержки, потеря пакетов, переупорядочивание сообщений, внезапные разрывы соединения, переподключения. Даже если вы тестируете на «идеальном» Wi-Fi, у пользователей будет метро, VPN, корпоративные прокси и «интернет от соседей». И всё это влияет не только на скорость, но и на корректность, если протокол где-то подразумевает идеальную доставку.

Сервер. Если у вас OT с обязательным сервером-арбитром, сервер становится центральной осью всей механики. Любая деградация там — деградация всего продукта. Падает сервер — падает коллаборация. Отвалилась база истории операций — начинаются странные рассинхроны. В CRDT сервер может быть опциональным, но на практике он всё равно часто появляется как ретранслятор, хранилище и точка входа, просто требования к нему другие.

Sync Layer. Самое «вкусное» место для багов. В OT — это трансформации и управление очередями pending/ack. В CRDT — merge/интеграция дельт, доставка причинности, дедупликация, очистка метаданных. Там редко бывают красивые падения. Чаще всё выглядит как «иногда у пары пользователей документ расходится», «иногда пропадает форматирование», «иногда курсор прыгает». И вы потом неделю пытаетесь понять, что именно было “иногда”.

Document Model. Это представление состояния, на котором вообще живут операции/дельты. В CRDT сюда добавляются идентификаторы, ссылки, «надгробия», компактация. В OT логика применения операций к модели, инварианты структуры, преобразования позиции в конкретный объект/узел и обратно. Чем богаче модель (таблицы, списки, стили, комментарии, трекинг изменений), тем больше вероятность, что какой-то редкий порядок событий создаст состояние, которое «формально получилось», но документ уже невалиден.

Интеграция с UI. Обычно про неё забывают, а она бьёт больнее всего. Оптимистичное применение, отображение курсоров и выделений, “input method editor” для восточных языков, автозамены, автонумерация, автослияние параграфов — всё это генерирует дополнительные операции, которые тоже должны быть согласованы. Иногда алгоритм корректен, а пользователь всё равно видит хаос, потому что UI показывает промежуточные состояния слишком буквально.

Где ломаются реальные системы

А теперь самое интересное: примеры из жизни, которые показывают, что даже сильные команды не застрахованы от неприятных сюрпризов. Причём сюрпризы обычно не в «сложной математике», а на стыке модели, синхронизации и бизнес-логики.

Google Drive и Dropbox (OT / проприетарные алгоритмы): циклы в дереве

Кейс выглядит почти анекдотично, пока не попробуешь реализовать сам.

Есть дерево папок. Пользователь X перемещает папку A внутрь B. Пользователь Y одновременно перемещает B внутрь A. В нормальном дереве такое невозможно — получится цикл.

Но вот беда: в момент выполнения у каждого пользователя своя локальная реальность, а операции по отдельности выглядят валидно. Каждая из них — «перемести узел». Конфликт проявляется только при попытке совместить оба изменения.

UX-последствия здесь очень неприятные: папки могут «исчезнуть» из интерфейса, потому что дерево больше не дерево, обход ломается, индексация ломается, некоторые клиенты начинают фильтровать «некорректные» узлы. Пользователь видит не “у нас цикл в графе”, а “мои файлы пропали”.

Notion (CRDT, Yjs): потеря изменений

Самый болезненный для пользователя класс проблем, когда изменения пропали без следа.

При конкурентном редактировании одного и того же параграфа некоторые системы — в том числе ранние версии Notion на базе CRDT — выбирают простую стратегию на уровне блока: «кто последний записал, тот и прав», а второй набор изменений отбрасывается. Технически это дешёвый способ избежать сложных конфликтов. Продуктово — это мина.

UX-последствия очевидны: пользователь набрал текст, увидел его на экране, отвлёкся, сеть мигнула, синхронизация прошла и текст исчез. Особенно жёстко, когда это была не строка, а час работы. После такого люди начинают делать копии в сторонние заметки “на всякий случай”.

Interleaving (проблема перемежения): нечитаемый текст

Есть отдельная категория «всё сохранилось, но читать невозможно».

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

Вместо ожидаемого «мама папа» получается что-то вроде «мпаампаа». Формально система молодец: ничего не потеряла, всё честно объединила. А пользователь смотрит и думает: “вы издеваетесь?”

UX-последствия: документ приходится переписывать руками. История правок тоже бесполезна, потому что она показывает «всё было введено», но итог — каша. И самое неприятное, что проблема может всплывать редко, но один такой кейс убивает ощущение надёжности.

Опыт МойОфис (OT): коллизии свойств

Мы выбрали ОТ для совместного редактирования. Основная проблема в том, что пользователи любят редактировать одну и ту же область документа.

Типичный сценарий из жизни: один пользователь меняет шрифт абзаца, второй — отступы этого же абзаца, третий — вставляет туда текст. Каждая операция по отдельности валидна, но их композиция может создать состояние, которое нарушает инварианты модели: стиль применился к уже “разрезанному” диапазону, отступы уехали на несуществующий блок, текст оказался внутри узла, где его быть не должно.

И это не обязательно проявляется сразу как «ой, форматирование не то». Иногда это проявляется как падение, потому что где-то глубоко в коде есть допущение “такого состояния быть не может”, и оно внезапно становится возможным именно в коллаборации.

UX-последствия тут самые обидные: приложение падает, пользователь теряет несохранённые изменения, а команда разработки потом неделю пытается воспроизвести баг. Потому что воспроизведение — это не “нажми кнопку”, а “повтори вот этот тайминг из трёх клиентов под нестабильной сетью”.

Об этом я подробнее расскажу в другой статье, потому что именно на таких кейсах становится видно: совместное редактирование — это не «алгоритм и готово», а постоянная борьба с краевыми случаями модели.

Заключение

В этой статье мы прошли по теории: посмотрели, как OT и CRDT решают проблему конкурентных операций, какие математические свойства стоят за их корректностью и какие архитектурные последствия из этого вытекают.

Если упростить всё до нескольких тезисов, картина такая.

OT — зрелый, проверенный временем подход. Он лежит в основе таких систем, как Google Docs, и десятилетиями используется в production. Но за эту зрелость приходится платить: обязательный сервер, сложные трансформации, тонкие граничные случаи (TP1, TP2, undo), высокая стоимость корректной реализации.

CRDT — математически более «чистая» модель. Сходимость гарантируется алгеброй, возможна полноценная офлайн-работа и даже P2P-синхронизация. Но и здесь есть налог: рост метаданных, tombstones, усложнение структуры документа и потребление памяти, особенно в больших и долго живущих документах.

Гибридные подходы вроде Eg-walker обещают взять лучшее из двух миров — уменьшить метаданные CRDT и при этом избежать хрупкости классического OT. Но это очень свежие решения, и пока не известно, как они поведут себя под многолетней production-нагрузкой.

Главный вывод простой и одновременно неприятный: простого решения не существует. Нет «правильного» алгоритма для всех случаев. Каждый подход — компромисс между сложностью, производительностью, требованиями к сети, объёмом памяти и удобством разработки.

Задача архитектора выбрать тот компромисс, который соответствует требованиям конкретного продукта: нужен ли полноценный офлайн, допустим ли центральный сервер, критична ли память, каковы требования к rich text и истории изменений.

Библиография

Основополагающие работы

OT Origin: Ellis C.A., Gibbs S.J. (1989), «Concurrency Control in Groupware Systems», ACM SIGMOD Record – первая публикация Operational Transformation. DOI: 10.1145/67544.66963

Jupiter: Nichols D.A. et al. (1995), «High-Latency, Low-Bandwidth Windowing in the Jupiter Collaboration System», UIST – модель, которая легла в основу Google Docs. DOI: 10.1145/215585.215706

TP1/TP2: Ressel M. et al. (1996), «An Integrating, Transformation-Oriented Approach to Concurrency Control and Undo in Group Editors», CSCW – формальные требования к корректности OT. DOI: 10.1145/240080.240305

CRDT Definition: Shapiro M. et al. (2011), «Conflict-free Replicated Data Types», SSS – формальное определение CRDT. DOI: 10.1007/978-3-642-24550-3_29

Undo Theorem: Sun C. (2000), «Undo any operation at any time in group editors», CSCW — доказательство невозможности гарантированной отмены произвольной операции в коллаборативных системах. DOI: 10.1145/358916.358990