Операциональное преобразование (ОП) представляет собой технологию для поддержки целого ряда функциональных возможностей сотрудничества в передовых системах groupware. ОП изначально предназначалось для поддержания согласованности и concurrency control при совместном редактировании простых текстовых документов. Два десятилетия исследований расширили его возможности и области применения: групповая отмена, блокировка, разрешение конфликтов, уведомления и операции сжатия, развитие осознанности групповой работы, редактирование HTML/XML и древовидных документов, высокопроизводительные инструменты совместной работы в офисе, совместные приложения для общего доступа и инструменты совместного компьютерно-ориентированного медиа-дизайна. Недавно ОП была использована в качестве технологического ядра в Google Wave благодаря своим возможностям совместной работы, что вывело ОП на новый уровень веб-приложений.
История Впервые концепцию Операционального Преобразования разработали С. Эллис, С. Гиббс в системе GROVE (GRoup Outtie Viewing Edit) в 1989 году. Несколько лет спустя были определены некоторые вопросы корректности и несколько независимых подходов решения этих вопросов, которые привели к следующему десятилетию продолжающихся усилий расширения и улучшения ОП сообществом посвященных этому исследователей. В 1998 году для развития связей и сотрудничества между исследователями СР и ОП была создана Группа Особого Интереса в Совместном Редактировании — Special Interest Group of Collaborative Editing (SIGCE) . С тех пор SIGCE проводит ежегодные семинары по СР в ходе основных конференций CSCW (Компьютерная Поддержка Совместной Работы), таких как ACM CSCW, GROUP и ECSCW.
Архитектура системы Системы совместной работы используют ОП, обычно повторяющую архитектуру хранения общих документов, чтобы обеспечить достаточное время отклика в средах с высокой задержкой, таких как Интернет. Общие документы копируются в локальное хранилище каждого сайта совместной работы, так что операции редактирования могут быть выполнены сразу на локальных сайтах, а затем переданы на удаленные сайты. Операции редактирования с удаленных сайтов, поступающие на локальный сайт, обычно уже преобразуются, а затем применяются. Преобразование гарантирует, что критерий согласованности, зависящий от приложения, будет достигнут на всех сайтах. Не блокируемое свойство ОП делает локальное время отклика не чувствительным к сетевым задержкам. В результате ОП очень хорошо подходят для реализации возможностей совместной работы, таких как групповое редактирование в контексте Web/Internet.
Основы Основная идея ОП может быть проиллюстрирована на примере сценария редактирования простого текста следующим образом: Дан текстовый документ со строкой "abc", реплицированный на двух сайтах совместной работы; а также две одновременных операции:
O1 = Insert[0, "x"] (вставить символ "x" в позиции "0") O2 = Delete[2, "c"] (удалить символ "c" в позиции "2")
генерируемые двумя пользователями на сайтах совместной работы 1 и 2, соответственно. Предположим, что две операции выполняются в следующем порядке: сначала O1 и затем O2 (на сайте 1). После выполнения O1 текст в документе становится "xabc". Для выполнения O2 после O1, O2 должна быть уже преобразована относительно O1 и предстать в следующем виде: O2'= Delete[3, "c"], где параметр позиции увеличен на единицу в связи со вставкой символа "x" операцией O1. Выполнение O2' на "xabc" должно удалить правильный символ "c" и текст этого документа становится "xab". Если же выполнять операцию O2 без преобразования, тогда будет неправильно удален символ "b" вместо "c". Основной идеей ОП является преобразование (или изменение) параметров операций редактирования в согласии с эффектами выполнения в предыдущих одновременных операциях так, чтобы преобразованная операция могла сработать корректно и не нарушать согласованность в документе.
Модели согласованности Одной из функций операционной трансформации является поддержка согласованных инструментов в системах совместного редактирования, некоторые согласованные модели были предложены исследовательским сообществом, некоторые из них являются общими для систем совместного редактирования, а некоторые являются особыми для их алгоритмов.
CC модель В для систем совместного редактирования потребовались два свойства согласованности:
Causality (Каузальность) или свойство старшинства по предшествованию: гарантирует, что порядок выполнения причинно-зависимых операций будет таким же, как их естественный причинно-следственный порядок, согласно процессу совместной работы. Каузальная связь между двумя операциями формально определяется соотношением Лампорта "happened-before". Если две операции каузально независимы, они являются параллельными. Две параллельных операции могут выполняться в различном порядке на двух разных копиях документов. Сonvergence (Сходимость): гарантирует, что реплицированные копии общего документа будут идентичными на всех сайтах (то есть, все генерируемые операции будут выполнены на всех сайтах).
Так как параллельные операции могут быть выполнены в разном порядке и операции редактирования обычно не коммутативны, копии документа на различных сайтах могут отличаться (быть несовместимыми). Первый алгоритм ОП был предложен в для достижения конвергенции в групповом текстовом редакторе; для хранения свойства старшинства использовался вектор состояния (или вектор часов в классических распределенных вычислениях).
CCI модель CCI модель была предложена в качестве общего фреймворка для управления согласованностью в системах совместного редактирования . Внутри CCI модели, сгруппированы вместе три свойства согласованности:
Сausality Preservation (Сохранность Каузальности): то же самое, что и свойство старшинства по предшествованию в CC модели. Сonvergence: то же самое, что свойство конвергентности в CC модели. Intention Preservation (Сохранность Намерения): гарантирует, что эффект выполнения операции в любом состоянии документа, будет таким же, как и намеревалось при выполнении операции. Намерение операции O определяется как эффект выполнения, который может быть достигнут путём применения O на состоянии документа, из которого О была сгенерирована.
CCI модель расширяет CC модель новым критерием: Сохранность Намерения. Существенная разница между конвергенцией и сохранностью намерения состоит в том, что первое всегда может быть достигнуто путём сериализации протокола, однако последнее не может быть достигнуто за счёт сериализации какого-либо протокола, если операции всегда будут выполняться в их первоначальных формах. Обеспечение свойства сохранности несериализуемого намерения являлось главной технической задачей. Обнаружилось, что ОП очень хорошо подходит для обеспечения конвергенции и сохранности намерения в системах совместного редактирования.
CCI модель не зависима от типов документов или моделей данных, видов операций, или вспомогательных технологий (ОП, мульти-версионность, сериализация, undo/redo). Она не предназначена для проверки правильности методов (например ОП), которые разрабатывались для конкретных данных и операционных моделей и для конкретных приложений. В понятие сохранности намерения определялось и уточнялось на трёх уровнях: во-первых, оно было определено как исходное требование согласованности в системах совместного редактирования; во-вторых, оно была определено как операция, основанная на контексте условий пред- и пост-преобразования для исходных функций ОП; в-третьих, оно было определено как специфичная операция проверки критериев, которыми следует руководствоваться при разработке функций OП для двух простейших операций: строковые функции вставки и удаления в простых текстовых редакторах для совместной работы.
CSM модель Условие сохранности намерения не было формально определено в CCI модели для целей формальных доказательств. В SDT и LBT подходах сделаны попытки формализовать альтернативные условия, которые могут быть использованы для доказательств. Модель согласованности, предложенная в этих двух подходах, состоит из следующих формальных условий:
Causality (Каузальность): определяет то же самое, что и в CC модели Single-operation effects (Следствия выполнения одной операции): следствие от выполнения любой операции в любом состоянии выполнения достигает того же эффекта, что и в его исходном состоянии Мulti-operation effects (Следствия выполнения нескольких операций): зависимость следствий любых двух операций поддерживаются и после того, как они оба будут выполнены в любых состояниях
CA модель Приведенная выше CSM модель требует, чтобы в системе был определен общий порядок всех объектов. Следовательно, спецификация сводится к новым объектам, представляемым операциями вставки. Однако, спецификация общего порядка влечет за собой применение зависимых от приложения стратегий, таких как при разрыве связей для вставки (т.е., когда новые объекты вставляются двумя текущими операций в одну и ту же позицию). Таким образом, общий порядок становится зависимым от приложения. Более того, в функциях преобразования и процедуре управления алгоритма общий порядок должен сохраняться, что приводит к увеличению сложности времени/пространства алгоритма.
В качестве альтернативы, CA модель основывается на Admissibilty Theory (Теории допустимости). CA модель включает в себя два аспекта:
Сausality (Каузальность): определяет то же самое, что и в CC модели Аdmissibility (Допустимость): Вызов каждой операции является допустимым в своем состоянии исполнения, т.е. каждый вызов не должен нарушать каких-либо связанных следствий (построения объектов), которые были созданы более ранними вызовами.
Эти два условия подразумевают собой конвергенцию. Все кооперирущие между собой сайты сходятся в одном и том же состоянии, в котором имеется один и тот же набор объектов, что находятся в одном и том же порядке. Более того, порядок фактически определяет следствия операций, которые они генерируют. Поскольку два условия также вводят дополнительные ограничения на порядок объектов, они фактически имеют больший приоритет, чем конвергенция. CA модель и подходы к его дизайну/обоснованиям были разработаны в 2005 году в статье . Это уже не требовало того, чтобы общий порядок объектов был определен в модели согласованности и поддерживался алгоритмом, что, соответственно, приводет к уменьшению сложности времени/пространства алгоритма.
Структура системы ОП ОП представляет собой систему из нескольких компонентов. Одна установленная стратегия проектирования систем ОП состоит в том, чтобы отделить высокоуровневые алгоритмы управления преобразованием (или интеграцией) от функций преобразования низкого уровня. Алгоритм управления преобразованием связан с определением:
Какая операция должна быть преобразована перед каузально-произошедшей новой операцией Порядка преобразований
Управляющий алгоритм вводит соответствующий набор функций преобразования, которые определяют, как преобразовать одну операцию перед другой в зависимости от типов операции, позиций и других параметров. Корректность распределения обязанностей этих двух уровней формально конкретизируется набором свойств и условий преобразования. Различные системы ОП с разными алгоритмами управления, функций и коммуникационными топологиями требуют поддержки разных наборов свойств преобразования. Разделение систем ОП на эти два уровня позволяет разрабатывать исходные управляющие алгоритмы, которые могут применяться для различных типов приложений с разными данными и операционными моделями.
Другой альтернативный подход предложен в .В этом подходе, алгоритм ОП является корректным, если он удовлетворяет двум формализованным критериям корректности:
Сохранности каузальности Сохранности допустимости