Операционные преобразования

Операционные преобразования (англ. Operational Transformation, OT) — это класс алгоритмов, используемых в системах совместного редактирования в реальном времени (collaborative real-time editors) для обеспечения согласованности данных при одновременной работе нескольких пользователей над одним документом. Основная задача операционных преобразований — разрешение конфликтов, возникающих, когда два или более участника вносят изменения в один и тот же объект (например, текст, таблицу, графический элемент) практически одновременно, без блокировки доступа и без необходимости ручного разрешения коллизий. Алгоритмы OT лежат в основе таких систем, как Google Docs (до перехода на CRDT), Etherpad, Apache Wave и ряда других.

История

Предпосылки возникновения

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

Ранние работы

Первая формальная модель операционных преобразований была предложена в 1989 году группой исследователей из Университета Торонто (Кларенс Эллис, Саймон Гиббс и др.) в работе «Concurrency Control in Groupware Systems». В этой работе был описан алгоритм dOPT (distributed Operational Transformation), который позволял двум пользователям одновременно редактировать один текстовый документ. Алгоритм основывался на идее преобразования одной операции относительно другой, чтобы их последовательное применение на разных узлах давало одинаковый результат.

Развитие и стандартизация

В 1990-е годы алгоритмы OT активно развивались. Были предложены различные модификации, направленные на устранение недостатков dOPT, в частности, проблемы «каскадного преобразования» и «нестабильности» при большом числе участников. В 1998 году в рамках проекта «Jupiter» (позднее — Google Wave) был разработан алгоритм, использующий централизованную архитектуру с сервером, который выполнял все преобразования. Этот подход упрощал реализацию и обеспечивал детерминированность.

В 2000-х годах OT стали основой для многих коммерческих продуктов. Google Docs, запущенный в 2006 году, использовал собственную реализацию OT, которая позволяла десяткам пользователей одновременно редактировать документы. В 2009 году компания Google открыла спецификацию OT, используемую в Google Wave, что стимулировало дальнейшие исследования.

Современное состояние

В 2010-х годах на смену OT в некоторых системах стали приходить алгоритмы на основе CRDT (Conflict-free Replicated Data Types), которые не требуют преобразования операций и гарантируют согласованность на уровне структуры данных. Тем не менее, OT остаётся широко распространённым подходом, особенно в системах с централизованной архитектурой и в приложениях, где важна низкая задержка ввода. В 2020-х годах OT продолжают использоваться в таких проектах, как Etherpad, ShareJS, и в некоторых внутренних инструментах крупных компаний.

Принцип работы

Основные понятия

• Операция — элементарное изменение, которое пользователь вносит в документ (например, вставка символа, удаление строки, изменение форматирования). Каждая операция имеет тип, позицию и содержимое.
• Состояние документа — последовательность операций, применённых к исходному пустому документу.
• Конфликт — ситуация, когда две операции, выполненные на разных узлах, не могут быть применены в исходном виде, так как они меняют один и тот же участок документа.
• Преобразование — функция, которая принимает на вход две операции (A и B) и возвращает новую операцию A' (преобразованную A), которая может быть применена после B, и B' (преобразованную B), которая может быть применена после A. Результат применения A' после B должен быть эквивалентен результату применения B' после A.

Алгоритм

1. Локальное выполнение: Когда пользователь вносит изменение, операция немедленно применяется к его локальной копии документа. Это обеспечивает мгновенную обратную связь.
2. Отправка на сервер: Операция отправляется на центральный сервер (или другим узлам в пиринговой сети).
3. Приём и преобразование: Сервер получает операцию от одного пользователя. Если в очереди сервера уже есть операции от других пользователей, которые ещё не были применены к данному документу, сервер преобразует новую операцию относительно каждой из ожидающих операций.
4. Применение и рассылка: Преобразованная операция применяется к серверной копии документа, а затем рассылается всем остальным клиентам. Каждый клиент, получив операцию, также преобразует её относительно своих локальных, ещё не отправленных операций, и применяет результат.
5. Согласованность: В результате все клиенты, после применения всех операций, приходят к одному и тому же конечному состоянию документа.

Пример

Пусть два пользователя (A и B) одновременно редактируют строку «abc». Пользователь A вставляет символ «x» на позицию 1 (после «a»), получая «axbc». Пользователь B вставляет символ «y» на позицию 2 (после «b»), получая «abyc». Если обе операции применить в исходном виде к одной копии, результат будет разным:

• Если сначала применить A, затем B: «axbyc».
• Если сначала применить B, затем A: «aybxc».

Алгоритм OT преобразует операцию B относительно A: поскольку A вставил символ на позицию 1, все позиции после 1 сдвигаются на 1. Поэтому B, которая была на позиции 2, преобразуется в операцию на позицию 3. После применения A (получаем «axbc») и затем преобразованной B (вставка «y» на позицию 3) получаем «axbyc». Аналогично, операция A преобразуется относительно B, и результат также будет «axbyc». Таким образом, достигается согласованность.

Классификация алгоритмов OT

По архитектуре

• Централизованные (серверные): Все операции проходят через один сервер, который выполняет преобразования и рассылает результаты. Пример: Google Docs (до 2019 года), Etherpad. Преимущество — простота реализации и детерминированность. Недостаток — единая точка отказа.
• Децентрализованные (пиринговые): Каждый узел может отправлять операции напрямую другим узлам. Преобразования выполняются на каждом узле независимо. Пример: Apache Wave. Сложнее в реализации, но устойчивее к сбоям.

По типу преобразования

• Преобразование на основе состояния (State-based): Преобразование зависит от текущего состояния документа. Требуется хранить историю всех операций.
• Преобразование на основе операций (Operation-based): Преобразование зависит только от самих операций и их порядка. Более эффективно, но требует точного знания контекста.

По способу разрешения конфликтов

• Прямое преобразование (Direct): Операции преобразуются друг относительно друга в порядке их поступления.
• Каскадное преобразование (Cascade): При множественных конфликтах операции преобразуются последовательно, что может приводить к экспоненциальному росту числа преобразований.

Применение

Совместное редактирование текста

Наиболее известное применение OT — текстовые редакторы. Google Docs, Etherpad, Microsoft Office Online (частично) используют OT для синхронизации изменений. Алгоритмы OT позволяют нескольким пользователям одновременно печатать в одном документе, видеть курсоры друг друга и получать изменения в реальном времени.

Совместное редактирование кода

Среды разработки, такие как Visual Studio Code (с расширением Live Share), используют OT для совместного программирования. Разработчики могут одновременно редактировать один файл, видеть изменения друг друга и общаться в чате.

Совместное редактирование графики и схем

Некоторые инструменты для создания диаграмм (например, Draw.io, Miro) применяют OT для синхронизации перемещения объектов, изменения размеров и добавления элементов. Операции в этом случае включают не только текст, но и координаты, размеры, цвета.

Онлайн-доски и вики

Системы для совместной работы, такие как Notion, Confluence, используют OT для синхронизации страниц, таблиц и баз данных. Пользователи могут одновременно редактировать один документ, не опасаясь потери данных.

Критика и ограничения

Сложность реализации

Алгоритмы OT требуют тщательного проектирования и тестирования. Ошибки в преобразовании могут приводить к «разрыву» документа, когда разные пользователи видят разные версии. Особенно сложны случаи с множественными одновременными операциями и нелинейными изменениями (например, перемещение блоков текста).

Производительность

При большом числе участников (сотни и тысячи) и высокой частоте изменений OT может создавать значительную нагрузку на сервер. Каждая операция должна быть преобразована относительно всех ожидающих операций, что при росте числа пользователей может приводить к задержкам.

Ограниченная поддержка нелинейных структур

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

Альтернативы

CRDT (Conflict-free Replicated Data Types) предлагают другой подход: вместо преобразования операций они используют структуры данных, которые гарантируют согласованность без центрального сервера. CRDT проще в реализации для некоторых типов данных, но могут быть менее эффективны по памяти и скорости для больших документов. В 2020-х годах многие проекты (например, Figma, Notion) перешли на CRDT или гибридные решения.

Интересные факты

• Первый алгоритм OT (dOPT) был реализован в 1989 году в системе GROVE (Group Outline Viewing Editor), которая позволяла нескольким пользователям одновременно редактировать структурированный документ.
• Google Wave, запущенный в 2009 году, использовал OT для синхронизации «волн» — документов, объединяющих текст, изображения, видео и виджеты. Проект был закрыт в 2012 году, но его код и спецификации OT оказали большое влияние на развитие технологий совместной работы.
• В 2011 году компания Google опубликовала статью «Operational Transformation in Google Docs», в которой описали свою реализацию OT. Этот документ стал одним из наиболее цитируемых в области совместного редактирования.
• Etherpad, изначально разработанный для проекта AppJet, был приобретён компанией Google в 2009 году и открыт под лицензией Apache 2.0. Его кодовая база до сих пор используется в ряде образовательных и корпоративных систем.

Источники

• Ellis, C. A., & Gibbs, S. J. (1989). Concurrency control in groupware systems. Proceedings of the 1989 ACM SIGMOD international conference on Management of data.
• Sun, C., & Ellis, C. (1998). Operational transformation in real-time group editors: issues, algorithms, and achievements. Proceedings of the 1998 ACM conference on Computer supported cooperative work.
• Google Inc. (2011). Operational Transformation in Google Docs. Google Research Blog.
• Nichols, D. A., & Twidale, M. B. (2003). The usability of open source software. First Monday, 8(1).
• Shapiro, M., Preguiça, N., Baquero, C., & Zawirski, M. (2011). Conflict-free replicated data types. Proceedings of the 13th international conference on Stabilization, safety, and security of distributed systems.