Операционная трансформация

«Операция Трансформация» перенаправляется сюда. Информацию о межмедийном мероприятии см. в разделе «Операция Трансформация» (сериал) .

Операционная трансформация ( OT ) — это технология поддержки ряда функций совместной работы в передовых программных системах для совместной работы. Изначально OT был изобретен для обеспечения согласованности и управления параллелизмом при совместном редактировании текстовых документов. Его возможности были расширены, а его приложения расширены, включив в себя групповую отмену, блокировку, разрешение конфликтов, уведомление об операциях и сжатие, осведомленность о группах, редактирование документов HTML / XML и древовидной структуры, инструменты для совместной работы в офисе, совместное использование приложений и совместный компьютер. вспомогательные инструменты медиадизайна. В 2009 году OT был принят в качестве основного метода функций совместной работы в Apache Wave и Google Docs .

История

Операционную трансформацию впервые предложили К. Эллис и С. Гиббс. в системе GROVE (GRoup Outline Viewing Edit) в 1989 году. Несколько лет спустя были выявлены некоторые проблемы с корректностью и предложено несколько подходов. были независимо предложены для решения этих проблем, за которым последовало еще одно десятилетие непрерывных усилий по расширению и совершенствованию ОТ сообществом преданных своему делу исследователей. В 1998 году Специальная группа по совместному редактированию был создан для содействия общению и сотрудничеству между исследователями CE и OT. С тех пор SIGCE проводит ежегодные семинары CE совместно с крупными конференциями CSCW ( совместная работа с компьютерной поддержкой ), такими как ACM, CSCW, GROUP и ECSCW.

Архитектура системы

Системы совместной работы, использующие операционные преобразования, обычно используют реплицированное хранилище документов, где каждый клиент имеет свою собственную копию документа; клиенты работают со своими локальными копиями без блокировки неблокируя и , а затем изменения распространяются на остальных клиентов; это обеспечивает высокую скорость реагирования клиента в среде с высокой задержкой, такой как Интернет. Когда клиент получает изменения, переданные от другого клиента, он обычно преобразует изменения перед их выполнением; преобразование гарантирует, что критерии согласованности, зависящие от приложения ( инварианты ), поддерживаются всеми сайтами. В результате такого режима работы система особенно подходит для реализации функций совместной работы, таких как одновременное редактирование документов, в среде с высокой задержкой, такой как Интернет .

Основы

Basic idea behind OT

Основную идею OT можно проиллюстрировать с помощью простого сценария редактирования текста, как показано ниже. Дан текстовый документ со строкой «abc», реплицированный на двух взаимодействующих сайтах; и две параллельные операции:

1. O1 = Insert[0, «x»] (чтобы вставить символ «x» в позицию «0»)
2. O2 = Удалить[2, «c»] (чтобы удалить символ «c» в позиции «2»)

созданный двумя пользователями на взаимодействующих сайтах 1 и 2 соответственно. Предположим, что две операции выполняются в порядке O1 и O2 (на сайте 1). После выполнения O1 документ становится «xabc». Чтобы выполнить O2 после O1, O2 должен быть преобразован в O1, чтобы стать: O2' = Удалить[3, «c»], чей позиционный параметр увеличивается на единицу из-за вставки одного символа «x» с помощью O1. Выполнение O2 для «xabc» удаляет правильный символ «c», и документ становится «xab». Однако если O2 выполняется без преобразования, он неправильно удаляет символ «b», а не «c». Основная идея OT заключается в преобразовании (или корректировке) параметров операции редактирования в соответствии с эффектами ранее выполненных параллельных операций, чтобы преобразованная операция могла достичь правильного эффекта и поддерживать согласованность документа.

Модели согласованности

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

Модель CC

В статье Эллиса и Гиббса 1989 года «Управление параллелизмом в системах группового программного обеспечения» Для систем совместного редактирования требуются два свойства согласованности:

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

Поскольку одновременные операции могут выполняться в разном порядке, а операции редактирования, как правило, не являются коммутативными, копии документа на разных сайтах могут расходиться (несовместимы). Первый алгоритм ОТ был предложен в статье Эллиса и Гиббса. добиться сходимости в групповом текстовом редакторе; вектор состояния (или векторные часы в классических распределенных вычислениях) использовался для сохранения свойства приоритета.

Модель CCI

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

• Сохранение причинно - следственной связи: то же, что и в модели CC.
• Конвергенция C : та же, что и в модели CC.
• Сохранение намерения : гарантирует, что эффект выполнения операции на любое состояние документа будет таким же, как и намерение операции. Цель операции O определяется как эффект выполнения, которого можно достичь, применив O к состоянию документа, из которого был создан O.

Модель CCI расширяет модель CC новым критерием: сохранение намерения. Существенная разница между конвергенцией и сохранением намерения состоит в том, что первое всегда может быть достигнуто с помощью протокола сериализации, но последнее невозможно достичь ни с помощью какого-либо протокола сериализации, если операции всегда выполнялись в их исходных формах. Достижение свойства сохранения несериализуемого намерения было серьезной технической проблемой. Было обнаружено, что ОТ особенно подходит для достижения конвергенции и сохранения намерений в системах совместного редактирования.

Модель CCI не зависит от типов документов или моделей данных, типов операций или вспомогательных методов (OT, многоверсионность, сериализация, отмена/повтор). Он не предназначен для проверки правильности методов (например, ОТ), разработанных для конкретных данных и моделей операций, а также для конкретных приложений. В, понятие сохранения намерения было определено и уточнено на трех уровнях: во-первых, оно было определено как общее требование согласованности для систем совместного редактирования; Во-вторых, оно было определено как условия до и после преобразования на основе контекста операции для общих функций OT; В-третьих, он был определен как конкретные критерии проверки операций, которые помогут разработать функции OT для двух примитивных операций: построчной вставки и удаления в совместных текстовых редакторах.

Модель CSM

Условие сохранения намерения формально не было указано в модели ТПП для целей формальных доказательств. СДТ и ЛБТ Подходы пытаются формализовать альтернативные условия, которые можно доказать. Модель согласованности, предложенная в этих двух подходах, состоит из следующих формальных условий:

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

Модель CA

Приведенная выше модель CSM требует указания общего порядка всех объектов в системе. По сути, спецификация сводится к новым объектам, добавляемым операциями вставки. Однако указание общего порядка влечет за собой политику, специфичную для приложения, например, политику разрыва связей вставки (т. е. новые объекты, вставленные двумя текущими операциями в одну и ту же позицию). Следовательно, общий порядок становится специфичным для приложения. Более того, в алгоритме должен поддерживаться полный порядок в функциях преобразования и процедуре управления, что увеличивает временную/пространственную сложность алгоритма.

Альтернативно, модель CA основана на теории допустимости . Модель CA включает в себя два аспекта:

• Причинно -следственная связь : то же определение, что и в модели CC.
• Допустимость : вызов каждой операции допустим в состоянии ее выполнения, т. е. каждый вызов не должен нарушать никаких отношений эффектов (упорядочения объектов) , установленных предыдущими вызовами.

Эти два условия подразумевают конвергенцию. Все взаимодействующие сайты сходятся в состоянии, в котором имеется одинаковый набор объектов, находящихся в одном и том же порядке. Более того, порядок фактически определяется эффектами операций, когда они генерируются. Поскольку эти два условия также накладывают дополнительные ограничения на упорядочивание объектов, они на самом деле сильнее, чем сходимость. Модель CA и подход «проектирование/доказательство» подробно описаны в статье 2005 года. Больше не требуется, чтобы общий порядок объектов был указан в модели согласованности и сохранялся в алгоритме, что, следовательно, приводит к уменьшению временных и пространственных сложностей в алгоритме.

Структура системы ОТ

ОТ представляет собой систему из множества компонентов. Одна устоявшаяся стратегия проектирования ОТ-систем заключается в отделении алгоритмов управления преобразованием (или интеграции) высокого уровня от функций преобразования низкого уровня.

Алгоритмы управления ОТ (определить, какие операции преобразуются против других в соответствии с их отношениями параллелизма/контекста)

Свойства и условия ОТ (распределить обязанности между алгоритмами и функциями)

Функции преобразования ОТ (определить, как преобразовать пару примитивных операций в соответствии с типами операций, позициями и другими параметрами)

Алгоритм управления преобразованием направлен на определение:

1. Какую операцию следует преобразовать против каузально готовой новой операции?
2. Порядок преобразований

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

Другой альтернативный подход был предложен в. В их подходе алгоритм ОТ является правильным, если он удовлетворяет двум формализованным критериям корректности:

1. Сохранение причинно-следственной связи
2. Сохранение приемлемости

Пока эти два критерия удовлетворяются, реплики данных сходятся (с дополнительными ограничениями) после выполнения всех операций на всех сайтах. Нет необходимости навязывать полный порядок выполнения ради достижения конвергенции. Их подход обычно заключается в том, чтобы сначала определить и доказать достаточные условия для нескольких функций преобразования, а затем разработать процедуру управления для обеспечения этих достаточных условий. Таким образом, процедура управления и функции преобразования работают синергетически для достижения корректности, т. е. сохранения причинности и допустимости. В их подходе нет необходимости удовлетворять свойствам преобразования, таким как TP2, поскольку он не требует, чтобы (инклюзивные) функции преобразования работали во всех возможных случаях.

Данные ОТ и модели работы

В каждой системе OT существуют две базовые модели: модель данных, определяющая способ обращения к объектам данных в документе с помощью операций, и модель операций, определяющая набор операций, которые могут быть напрямую преобразованы функциями OT. Различные OT-системы могут иметь разные модели данных и операций. Например, модель данных первой ОТ-системы представляет собой единое линейное адресное пространство; и его модель работы состоит из двух примитивных операций: посимвольной вставки и удаления. Базовая модель операций была расширена за счет включения третьего обновления примитивной операции для поддержки совместной обработки документов Word. and 3D model editing. Базовая модель данных OT была расширена до иерархии нескольких доменов линейной адресации. который способен моделировать широкий спектр документов. Процесс адаптации данных часто требуется для сопоставления моделей данных, специфичных для приложения, с моделью данных, совместимой с OT.

Существует два подхода к поддержке операций уровня приложения в OT-системе:

1. Подход к общей операционной модели: он заключается в разработке функций преобразования для трех примитивных операций: вставки, удаления и обновления. Этот подход требует процесса адаптации операций для сопоставления операций приложения с этими примитивными операциями. В этом подходе модель работы OT является универсальной, поэтому функции преобразования можно повторно использовать для разных приложений.
2. Подход к модели операций, специфичный для приложения: который заключается в разработке функций преобразования для каждой пары операций приложения. Для приложения с m различными операциями для поддержки этого приложения необходимы функции преобразования mxm. В этом подходе функции преобразования зависят от приложения и не могут быть повторно использованы в разных приложениях.

ОТ-функции

Различные функции OT были разработаны для систем OT с разными возможностями и используются для разных приложений. Функции ОТ, используемые в разных системах ОТ, могут называться по-разному, но их можно разделить на две категории:

• Преобразование включения (или прямое преобразование): ИТ(Оа, Обь) или $T(op_{1},op_{2})$, который преобразует операцию Oa в другую операцию Ob таким образом, что влияние Ob эффективно учитывается. Это, например, случай двух вставок в разные узлы.
• Преобразование исключения (или обратное преобразование): ET (Оа, Об) или $T^{-1}(op_{1},op_{2})$, который преобразует операцию Oa в другую операцию Ob таким образом, что влияние Ob фактически исключается. Это, например, случай вставки и удаления в разных узлах.

Например, предположим, что тип String имеет операцию ins(p, c, sid), где p — позиция вставки, c — символ для вставки, а sid — идентификатор сайта, сгенерировавшего операцию. Мы можем написать следующую функцию преобразования включения:

T(ins($p_{1},c_{1},sid_{1}$),ins($p_{2},c_{2},sid_{2}$)) :- if ($p_{1}<p_{2}$) return ins($p_{1},c_{1},sid_{1}$) else if ($p_{1}=p_{2}$ and $sid_{1}<sid_{2}$) return ins($p_{1},c_{1},sid_{1}$) else return ins($p_{1}+1,c_{1},sid_{1}$)

Мы также можем написать следующую функцию преобразования исключения:

$T^{-1}$(ins($p_{1},c_{1},sid_{1}$),ins($p_{2},sid_{2}$)) :- if ($p_{1}<p_{2}$) return ins($p_{1},c_{1},sid_{1}$) else if ($p_{1}=p_{2}$ and $sid_{1}<sid_{2}$) return ins($p_{1},c_{1},sid_{1}$) else return ins($p_{1}-1,c_{1},sid_{1}$)

Некоторые ОТ-системы используют как функции ИТ, так и функции ET, а некоторые используют только функции ИТ. Сложность проектирования функции ОТ определяется различными факторами:

• функциональность системы OT: поддерживает ли система OT выполнение (поддержание согласованности), отмену, блокировку, осведомленность, обмен приложениями, и т. д.;
• ответственность за корректность в системе ОТ: каким свойствам преобразования (CP1/TP1, CP2/TP2, IP2, IP3, RP) соответствовать; используется ли ЭТ;
• модель работы системы OT: является ли модель работы OT общей (например, примитивная вставка, удаление, обновление) или специфичной для приложения (все операции целевого приложения); и
• модель данных системы OT: являются ли данные в каждой операции символьными (отдельный объект), строковыми (последовательность объектов), иерархическими или другими структурами.

Свойства трансформации

Выявлены различные свойства преобразования для обеспечения корректности ОТ-системы. Эти свойства могут поддерживаться либо алгоритмом управления преобразованием или с помощью функций преобразования. Различные конструкции OT-систем имеют разное разделение обязанностей между этими компонентами. Характеристики этих свойств и предварительные условия их требования приведены ниже.

Свойства сходимости

Иллюстрация свойства TP1

Иллюстрация свойства TP2

Следующие два свойства связаны с достижением сходимости.

• CP1/TP1 : для каждой пары одновременных операций. $op_{1}$ и $op_{2}$ определенная в одном и том же состоянии, функция преобразования T удовлетворяет свойству CP1/TP1 тогда и только тогда, когда: $op_{1}\circ T(op_{2},op_{1})\equiv op_{2}\circ T(op_{1},op_{2})$ где $op_{i}\circ op_{j}$ обозначает последовательность операций, содержащую $op_{i}$ с последующим $op_{j}$;и где $\equiv$ обозначает эквивалентность двух последовательностей операций. Предварительное условие CP1/TP1 : CP1/TP1 требуется только в том случае, если система OT позволяет выполнять любые две операции в разных порядках.
• CP2/TP2 : на каждые три одновременных операции. $op_{1},op_{2}$ и $op_{3}$ определенная для того же состояния документа, функция преобразования T удовлетворяет свойству CP2/TP2 тогда и только тогда, когда: $T(op_{3},op_{1}\circ T(op_{2},op_{1}))=T(op_{3},op_{2}\circ T(op_{1},op_{2}))$. CP2/TP2 предусматривает равенство двух операций, преобразованных относительно двух эквивалентных последовательностей операций: преобразования $op_{3}$ против последовательности действий $op_{2}$ с последующим $T(op_{1},op_{2})$ должна дать ту же операцию, что и преобразование $op_{3}$ против последовательности, образованной $op_{1}$ и $T(op_{2},op_{1})$. Предварительное условие CP2/TP2 : CP2/TP2 требуется только в том случае, если системы OT допускают две операции. $op_{1}$ и $op_{2}$ быть ИТ-трансформирован в двух разных состояниях документа (или контекстах).

Обратные свойства

Следующие три свойства связаны с достижением желаемого эффекта отмены группы. Они есть:

• IP1 : Учитывая любое состояние документа S и последовательность $op\circ {\overline {op}}$, у нас есть $S\circ op\circ {\overline {op}}=S$, что означает последовательность $op\circ {\overline {op}}$ эквивалентно одной операции идентификации I в отношении воздействия на состояние документа. Это свойство требуется в системе OT для достижения правильного эффекта отмены, но не связано с функциями ИТ.
• IP2 : Свойство IP2 означает, что последовательность $op\circ {\overline {op}}$ не влияет на преобразование других операций. Функции преобразования удовлетворяют IP2 тогда и только тогда, когда: $T(op_{x},op\circ {\overline {op}})=op_{x}$, что означает, что результат преобразования $op_{x}$ против последовательности $op\circ {\overline {op}}$ эквивалентно результату преобразования $op_{x}$ против операции идентификации I. Предварительное условие IP2 : IP2 требуется только в том случае, если системы OT разрешают операцию. $op_{x}$ быть преобразовано с помощью пары операций do и undo $op\circ {\overline {op}}$, по одному.
• IP3 : Учитывая две одновременные операции $op_{1}$ и $op_{2}$ определено в том же состоянии документа (или контексте), если ${\overline {op_{1}}}'=T({\overline {op_{1}}},T(op_{2},op_{1}))$ и ${\overline {op_{1}'}}={\overline {T(op_{1},op_{2})}}$. Функции преобразования удовлетворяют свойству IP3 тогда и только тогда, когда ${\overline {op_{1}}}'={\overline {op_{1}'}}$, что означает, что преобразованная обратная операция ${\overline {op_{1}}}'$ равно обратной преобразованной операции ${\overline {op_{1}'}}$. Предварительное условие IP3 : IP3 требуется только в том случае, если система OT допускает обратную операцию. ${\overline {op_{1}}}$ трансформироваться в ходе операции $op_{2}$ который является параллельным и определен в том же состоянии документа, что и (или контекстно-эквивалентен) $op_{1}$.

Алгоритмы управления (интеграции) ОТ

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

• распределение ответственности за правильность между алгоритмом управления и функциями преобразования, и
• пространственно-временная сложность системы ОТ.

Большинство существующих алгоритмов управления ОТ для управления параллелизмом принимают теорию причинности/параллелизма в качестве теоретической основы: причинно связанные операции должны выполняться в их причинном порядке; параллельные операции должны быть преобразованы перед их выполнением. Однако было хорошо известно, что одно только условие параллелизма не может охватить все условия преобразования OT. В недавней работе была предложена теория контекста операции для явного представления понятия состояния документа, которое можно использовать для формального выражения условий преобразования ОП для поддержки разработки и проверки алгоритмов управления ОП.

В следующей таблице представлен обзор некоторых существующих алгоритмов управления/интеграции OT.

Алгоритмы управления/интеграции ОТ (системы)	Требуемые типы функций преобразования	Поддержка Do? на основе OT	Поддержка отмены на основе OT?	Свойства преобразования, поддерживаемые алгоритмом управления	Свойства преобразования, поддерживаемые функциями преобразования	Ограничения порядка преобразования и распространения	Временная метка
дОПТ (РОЩА)	Т (ИТ)	Да	Нет	Никто	КП1/ТР1, КП2/ТР2	Причинно-следственный порядок	Вектор состояния
выборочная отмена (Дистредит)	Транспонирование (IT и ET)	Нет	Выборочная отмена	ЧТО	CP1/TP1, CP2/TP2, РП, ИП1, ИП2, ИП3	Причинно-следственный порядок	??
усыновленный (ОБЪЕДИНЕННАЯ EMACS)	LТрансформация (ИТ)	Да	Хронологическая отмена	ИП2, ИП3	CP1/TP1, CP2/TP2, IP1	Причинно-следственный порядок	Вектор состояния
Юпитер	xform (ИТ)	Да	Нет	КП2/ТП2	CP1/TP1	Причинно-следственный порядок + Центральный сервер трансформации	Скаляр
Гугл Вэйв ОТ	преобразование и композиция (ИТ)	Да	Нет	КП2/ТП2	CP1/TP1	Причинно-следственный порядок + Центральный сервер преобразования + протокол остановки и ожидания распространения	Скаляр
ПОЛУЧИЛ (УМЕНЬШАТЬ)	ИТ и ЕТ	Да	Нет	КП1/ТР1, КП2/ТР2	Никто	Причинный порядок + Прерывистый общий порядок	Вектор состояния
ПЕРЕЙТИ К (REDUCE, CoWord , CoPPT, CoMaya)	ИТ и ЕТ	Да	Нет	Никто	КП1/ТР1, КП2/ТР2	Причинно-следственный порядок	Вектор состояния
ЛюбоеОтменить (REDUCE, CoWord , CoPPT, CoMaya)	ИТ и ЕТ	Нет	Отменить любую операцию	ИП2, ИП3, РП	ИП1, CP1/TP1, CP2/TP2	Причинно-следственный порядок	Вектор состояния
ОБЪЕМ (ХОРОШИЙ)	ЭТО	Да	Нет	КП2/ТП2	CP1/TP1	Причинно-следственный порядок + Центральный сервер трансформации	Скаляр
СОТ (REDUCE, CoWord , CoPPT, CoMaya)	ЭТО	Да	Отменить любую операцию	КП2/ТП2, ИП2, ИП3	CP1/TP1 (нет ET, поэтому IP1 не требуется)	Причинный порядок + Прерывистый общий порядок	Вектор контекста
СТРЕЛЯТЬ	ЭТО	Да	Нет	КП2/ТП2	CP1/TP1	Причинно-следственный порядок	Скаляр
SOCT4	Форвардная трансформация (ИТ)	Да	Нет	КП2/ТП2	CP1/TP1	Причинный порядок + Непрерывный общий порядок	Скаляр
СОКТ2	Прямая трансформация (IT) и обратная трансформация (ET)	Да	Нет	Никто	CP1/TP1, CP2/TP2, РП	Причинно-следственный порядок	Вектор состояния
ТО2	Форвардная трансформация (ИТ)	Да	Нет	??	КП1/ТР1, КП2/ТР2	??	скаляр

Непрерывный общий порядок — это строгий общий порядок , в котором можно обнаружить недостающий элемент, т. е. 1,2,3,4,... — это непрерывный общий порядок, 1,2,3,5,… — не непрерывный общий порядок.

Алгоритмы на основе преобразований, предложенные в основаны на альтернативных моделях согласованности «CSM» и «CA», как описано выше. Их подходы отличаются от перечисленных в таблице. Они используют векторные временные метки для сохранения причинно-следственной связи. Другими условиями корректности являются сохранение отношения эффектов «однократной»/«множественной» операции или сохранение «допустимости». Эти условия обеспечиваются процедурой управления и трансформационными функциями синергетически. В их работе нет необходимости обсуждать TP1/TP2. Поэтому они не указаны в приведенной выше таблице.

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

Проблемы корректности ОТ привели к введению нетрансформационных схем пост-ОТ, таких как WOOT, Логотип и причинные деревья (CT). Схемы «Post-OT» разлагают документ на атомарные операции, но они позволяют обойти необходимость преобразования операций, используя комбинацию уникальных идентификаторов символов, векторных временных меток и/или надгробий.

Критика ОТ

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

Точно так же Джозеф Джентл, бывший инженер Google Wave и автор библиотеки Share.JS, написал: «К сожалению, реализация OT — отстой. Существует миллион алгоритмов с различными компромиссами, большинство из которых заперты в научных статьях. […] Wave занял 2 года». написать, и если бы мы переписали это сегодня, написание второго раза заняло бы почти столько же времени». Но позже он исправляет свой комментарий: «Я больше не верю, что для реализации этой волны потребуется два года - в основном из-за достижений в веб-фреймворках и веб-браузерах».

Чтобы OT работало, необходимо фиксировать каждое изменение данных: «Получение снимка состояния обычно тривиально, но фиксация изменений — совсем другое дело. […] Богатство современных пользовательских интерфейсов может сделать это проблематичным. особенно в среде браузера». Альтернативой OT является дифференциальная синхронизация .

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

См. также

• Синхронизация данных
• Совместные редакторы в реальном времени
• Бесконфликтные реплицируемые типы данных
• Модели согласованности
• Оптимистическая репликация

Внешние ссылки

• Часто задаваемые вопросы по OT: Часто задаваемые вопросы и ответы по операционной трансформации
• SIGCE: Специальная группа совместного редактирования по интересам
• Международный семинар по системам совместного редактирования
• Распределенная система онлайн — совместное редактирование
• Простое объяснение ОТ в Google Docs
• Основы ОТ в Open Coweb Framework

Соответствующие онлайн-переговоры

• Google Wave: совместное редактирование в реальном времени
• Google Tech Talk: Проблемы и опыт разработки систем совместного редактирования в реальном времени
• Доклад Microsoft Research: Обеспечение согласованности в системах совместного редактирования в реальном времени