ОБЗОР СОСТОЯНИЯ ВОПРОСА
Системы совместного редактирования позволяют пользователям одновременно просматривать и изменять документы через сеть. В качестве документа могут выступать компьютерные программы и документация к ним, веб-страницы, онлайн-энциклопедии, изображения и даже 3D-сцены [13].
Системы управления базами данных нельзя отнести к системам совместного редактирования, поскольку те, как правило, не сообщают подключенным пользователям о том, что данные изменились. Для того, чтобы узнать об изменении данных, клиент должен явно запросить данные у СУБД.
Важной проблемой создания систем совместного редактирования является проблема контроля синхронизации и разрешения конфликтов: независимо от действий пользователей, все их действия должны быть отображены на всех клиентах через время, мало превышающее реакцию системы. Чем больше время реакции системы, тем острее встает проблема разрешения конфликтов. Не зная о действиях друг друга два пользователя могут, например, удалить один и тот же символ, и система должна распознавать такие случаи и решать подобные проблемы. Существует несколько вариантов решения:
— Блокировка данных. Если пользователь начинает редактировать блок текста (строку, слово или даже весь документ), он блокируется и другие пользователи не могут вносить в него изменения. Этот вариант прост в реализации, но неудобен в пользовании, особенно в случаях, когда несколько пользователей одновременно редактируют блок текста (строку).
— Транзакции. Широко используемый в СУБД механизм, который, однако, достаточно ресурсоемок. Кроме того, для транзакций, реализованных через блокировки, верны все перечисленные выше недостатки. Здесь проявляется также разница в философии. Если в СУБД стараются создать для каждого пользователя иллюзию, что он — единственный пользователь системы, то системы совместного редактирования должны максимально быстро отображать изменения, вносимые другими пользователями.
— Единственный пользователь. В каждый момент времени только один пользователь имеет доступ к редактированию документа, что не подходит для ситуаций с активным участием в редактировании нескольких человек.
— Обнаружение зависимостей. Порядок выполнения операций определяется их временем генерации, все конфликты разрешаются вручную.
— Обратимое исполнение. Все операции исполняются немедленно, но любая из них может быть отменена, для чего приложение может сохранять дополнительную информацию.
— Операциональное преобразование. Техника операционального преобразования впервые предложена в работе [14] и состоит в том, что все последующие операции преобразовываются так, чтобы учитывать эффект предыдущих. При этом не используются блокировки, и в любой момент любому пользователю доступно редактирование любого фрагмента текста. Сегодня операциональное преобразование широко используется в системах совместного редактирования. Дополнительную известность эта группа алгоритмов получила в связи с её использованием в проекте Google Wave [15].
Техника операционального преобразования, несмотря на сравнительную сложность реализации, предоставляет пользователям наибольшее удобство при работе с текстом, и одновременно обеспечивает достаточно качественное поддержание синхронности текста у разных пользователей. Именно она использована при разработке приложения.
Рассмотрим подробнее эту группу алгоритмов.
Основная идея ОП может быть проиллюстрирована на примере сценария редактирования простого текста следующим образом: Дан текстовый документ со строкой "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 модель
В [14] для систем совместного редактирования потребовались два свойства согласованности:
Causality (Каузальность) или свойство старшинства по предшествованию: гарантирует, что порядок выполнения причинно-зависимых операций будет таким же, как их естественный причинно-следственный порядок, согласно процессу совместной работы. Каузальная связь между двумя операциями формально определяется соотношением Лампорта "happened-before". Если две операции каузально независимы, они являются параллельными. Две параллельных операции могут выполняться в различном порядке на двух разных копиях документов.
Сonvergence (Сходимость): гарантирует, что реплицированные копии общего документа будут идентичными на всех сайтах (то есть, все генерируемые операции будут выполнены на всех сайтах).
Так как параллельные операции могут быть выполнены в разном порядке и операции редактирования обычно не коммутативны, копии документа на различных сайтах могут отличаться (быть несовместимыми).
CCI модель
CCI модель была предложена в качестве общего фреймворка для управления согласованностью в системах совместного редактирования. Внутри CCI модели сгруппированы вместе три свойства согласованности:
Сausality Preservation (Сохранность Каузальности): то же самое, что и свойство старшинства по предшествованию в CC модели.
Сonvergence: то же самое, что свойство конвергентности в CC модели.
Intention Preservation (Сохранность Намерения): гарантирует, что эффект выполнения операции в любом состоянии документа, будет таким же, как и намеревалось при выполнении операции. Намерение операции O определяется как эффект выполнения, который может быть достигнут путем применения O на состоянии документа, из которого О была сгенерирована.
CCI модель расширяет CC модель новым критерием: Сохранность Намерения. Существенная разница между конвергенцией и сохранностью намерения состоит в том, что первое всегда может быть достигнуто путем сериализации протокола, однако последнее не может быть достигнуто за счёт сериализации какого-либо протокола, если операции всегда будут выполняться в их первоначальных формах. Обеспечение свойства сохранности несериализуемого намерения являлась главной технической задачей. Обнаружилось, что ОП очень хорошо подходит для обеспечения конвергенции и сохранности намерения в системах совместного редактирования.
CSM модель
Условие сохранности намерения не было формально определено в CCI модели для целей формальных доказательств. Модель согласованности CSM состоит из следующих формальных условий:
Causality (Каузальность): определяет то же самое, что и в CC модели
Single-operation effects (Следствия выполнения одной операции): следствие от выполнения любой операции в любом состоянии выполнения достигает того же эффекта, что и в его исходном состоянии
Мulti-operation effects (Следствия выполнения нескольких операций): зависимость следствий любых двух операций поддерживаются и после того, как они оба будут выполнены в любых состояниях
CA модель
Приведенная выше CSM модель требует, чтобы в системе был определен общий порядок всех объектов. Следовательно, спецификация сводится к новым объектам, представляемым операциями вставки. Однако, спецификация общего порядка влечет за собой применение зависимых от приложения стратегий, таких как при разрыве связей для вставки (т.е., когда новые объекты вставляются двумя текущими операций в одну и ту же позицию). Таким образом, общий порядок становится зависимым от приложения. Более того, в функциях преобразования и процедуре управления алгоритма общий порядок должен сохраняться, что приводит к увеличению сложности времени/пространства алгоритма.
В качестве альтернативы, CA модель основывается на Admissibilty Theory [11] (Теории допустимости). CA модель включает в себя два аспекта:
Сausality (Каузальность): определяет то же самое, что и в CC модели
Аdmissibility (Допустимость): Вызов каждой операции является допустимым в своем состоянии исполнения, т.е. каждый вызов не должен нарушать каких-либо связанных следствий (построения объектов), которые были созданы более ранними вызовами.
Эти два условия подразумевают собой конвергенцию. Все кооперирущие между собой сайты сходятся в одном и том же состоянии, в котором имеется один и тот же набор объектов, что находятся в одном и том же порядке. Более того, порядок фактически определяет следствия операций, которые они генерируют. Поскольку два условия также вводят дополнительные ограничения на порядок объектов, они фактически имеют больший приоритет, чем конвергенция. CA модель и подходы к его дизайну/обоснованиям были разработаны в 2005 году в статье [11]. Это уже не требовало того, чтобы общий порядок объектов был определен в модели согласованности и поддерживался алгоритмом, что, соответственно, приводит к уменьшению сложности времени/пространства алгоритма. [15]
Именно описанный в статье [11] алгоритм использован при реализации приложения.
ЦЕЛЬ И ЗАДАЧИ ПРОЕКТА
Основная задача данного дипломного проекта — создание браузерного текстового редактора, позволяющего одновременное редактирование текста несколькими пользователями. Приложение должно работать в современных браузерах, поддерживать форматирование текста, обладать возможностью простого отката нежелательных изменений в документе.
Для достижения поставленной цели необходимо решить следующие задачи:
Обосновать выбор платформы и технологию разработки, используемую для достижения цели дипломного проекта;
На основе предлагаемой методики разработать алгоритмы и структуру системы;
На основе предлагаемой структуры разработать программное обеспечение на языке C#;
Провести сравнительный анализ выполненной работы;
Системы совместного редактирования позволяют пользователям одновременно просматривать и изменять документы через сеть. В качестве документа могут выступать компьютерные программы и документация к ним, веб-страницы, онлайн-энциклопедии, изображения и даже 3D-сцены [13].
Системы управления базами данных нельзя отнести к системам совместного редактирования, поскольку те, как правило, не сообщают подключенным пользователям о том, что данные изменились. Для того, чтобы узнать об изменении данных, клиент должен явно запросить данные у СУБД.
Важной проблемой создания систем совместного редактирования является проблема контроля синхронизации и разрешения конфликтов: независимо от действий пользователей, все их действия должны быть отображены на всех клиентах через время, мало превышающее реакцию системы. Чем больше время реакции системы, тем острее встает проблема разрешения конфликтов. Не зная о действиях друг друга два пользователя могут, например, удалить один и тот же символ, и система должна распознавать такие случаи и решать подобные проблемы. Существует несколько вариантов решения:
— Блокировка данных. Если пользователь начинает редактировать блок текста (строку, слово или даже весь документ), он блокируется и другие пользователи не могут вносить в него изменения. Этот вариант прост в реализации, но неудобен в пользовании, особенно в случаях, когда несколько пользователей одновременно редактируют блок текста (строку).
— Транзакции. Широко используемый в СУБД механизм, который, однако, достаточно ресурсоемок. Кроме того, для транзакций, реализованных через блокировки, верны все перечисленные выше недостатки. Здесь проявляется также разница в философии. Если в СУБД стараются создать для каждого пользователя иллюзию, что он — единственный пользователь системы, то системы совместного редактирования должны максимально быстро отображать изменения, вносимые другими пользователями.
— Единственный пользователь. В каждый момент времени только один пользователь имеет доступ к редактированию документа, что не подходит для ситуаций с активным участием в редактировании нескольких человек.
— Обнаружение зависимостей. Порядок выполнения операций определяется их временем генерации, все конфликты разрешаются вручную.
— Обратимое исполнение. Все операции исполняются немедленно, но любая из них может быть отменена, для чего приложение может сохранять дополнительную информацию.
— Операциональное преобразование. Техника операционального преобразования впервые предложена в работе [14] и состоит в том, что все последующие операции преобразовываются так, чтобы учитывать эффект предыдущих. При этом не используются блокировки, и в любой момент любому пользователю доступно редактирование любого фрагмента текста. Сегодня операциональное преобразование широко используется в системах совместного редактирования. Дополнительную известность эта группа алгоритмов получила в связи с её использованием в проекте Google Wave [15].
Техника операционального преобразования, несмотря на сравнительную сложность реализации, предоставляет пользователям наибольшее удобство при работе с текстом, и одновременно обеспечивает достаточно качественное поддержание синхронности текста у разных пользователей. Именно она использована при разработке приложения.
Рассмотрим подробнее эту группу алгоритмов.
Основная идея ОП может быть проиллюстрирована на примере сценария редактирования простого текста следующим образом: Дан текстовый документ со строкой "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 модель
В [14] для систем совместного редактирования потребовались два свойства согласованности:
Causality (Каузальность) или свойство старшинства по предшествованию: гарантирует, что порядок выполнения причинно-зависимых операций будет таким же, как их естественный причинно-следственный порядок, согласно процессу совместной работы. Каузальная связь между двумя операциями формально определяется соотношением Лампорта "happened-before". Если две операции каузально независимы, они являются параллельными. Две параллельных операции могут выполняться в различном порядке на двух разных копиях документов.
Сonvergence (Сходимость): гарантирует, что реплицированные копии общего документа будут идентичными на всех сайтах (то есть, все генерируемые операции будут выполнены на всех сайтах).
Так как параллельные операции могут быть выполнены в разном порядке и операции редактирования обычно не коммутативны, копии документа на различных сайтах могут отличаться (быть несовместимыми).
CCI модель
CCI модель была предложена в качестве общего фреймворка для управления согласованностью в системах совместного редактирования. Внутри CCI модели сгруппированы вместе три свойства согласованности:
Сausality Preservation (Сохранность Каузальности): то же самое, что и свойство старшинства по предшествованию в CC модели.
Сonvergence: то же самое, что свойство конвергентности в CC модели.
Intention Preservation (Сохранность Намерения): гарантирует, что эффект выполнения операции в любом состоянии документа, будет таким же, как и намеревалось при выполнении операции. Намерение операции O определяется как эффект выполнения, который может быть достигнут путем применения O на состоянии документа, из которого О была сгенерирована.
CCI модель расширяет CC модель новым критерием: Сохранность Намерения. Существенная разница между конвергенцией и сохранностью намерения состоит в том, что первое всегда может быть достигнуто путем сериализации протокола, однако последнее не может быть достигнуто за счёт сериализации какого-либо протокола, если операции всегда будут выполняться в их первоначальных формах. Обеспечение свойства сохранности несериализуемого намерения являлась главной технической задачей. Обнаружилось, что ОП очень хорошо подходит для обеспечения конвергенции и сохранности намерения в системах совместного редактирования.
CSM модель
Условие сохранности намерения не было формально определено в CCI модели для целей формальных доказательств. Модель согласованности CSM состоит из следующих формальных условий:
Causality (Каузальность): определяет то же самое, что и в CC модели
Single-operation effects (Следствия выполнения одной операции): следствие от выполнения любой операции в любом состоянии выполнения достигает того же эффекта, что и в его исходном состоянии
Мulti-operation effects (Следствия выполнения нескольких операций): зависимость следствий любых двух операций поддерживаются и после того, как они оба будут выполнены в любых состояниях
CA модель
Приведенная выше CSM модель требует, чтобы в системе был определен общий порядок всех объектов. Следовательно, спецификация сводится к новым объектам, представляемым операциями вставки. Однако, спецификация общего порядка влечет за собой применение зависимых от приложения стратегий, таких как при разрыве связей для вставки (т.е., когда новые объекты вставляются двумя текущими операций в одну и ту же позицию). Таким образом, общий порядок становится зависимым от приложения. Более того, в функциях преобразования и процедуре управления алгоритма общий порядок должен сохраняться, что приводит к увеличению сложности времени/пространства алгоритма.
В качестве альтернативы, CA модель основывается на Admissibilty Theory [11] (Теории допустимости). CA модель включает в себя два аспекта:
Сausality (Каузальность): определяет то же самое, что и в CC модели
Аdmissibility (Допустимость): Вызов каждой операции является допустимым в своем состоянии исполнения, т.е. каждый вызов не должен нарушать каких-либо связанных следствий (построения объектов), которые были созданы более ранними вызовами.
Эти два условия подразумевают собой конвергенцию. Все кооперирущие между собой сайты сходятся в одном и том же состоянии, в котором имеется один и тот же набор объектов, что находятся в одном и том же порядке. Более того, порядок фактически определяет следствия операций, которые они генерируют. Поскольку два условия также вводят дополнительные ограничения на порядок объектов, они фактически имеют больший приоритет, чем конвергенция. CA модель и подходы к его дизайну/обоснованиям были разработаны в 2005 году в статье [11]. Это уже не требовало того, чтобы общий порядок объектов был определен в модели согласованности и поддерживался алгоритмом, что, соответственно, приводит к уменьшению сложности времени/пространства алгоритма. [15]
Именно описанный в статье [11] алгоритм использован при реализации приложения.
ЦЕЛЬ И ЗАДАЧИ ПРОЕКТА
Основная задача данного дипломного проекта — создание браузерного текстового редактора, позволяющего одновременное редактирование текста несколькими пользователями. Приложение должно работать в современных браузерах, поддерживать форматирование текста, обладать возможностью простого отката нежелательных изменений в документе.
Для достижения поставленной цели необходимо решить следующие задачи:
Обосновать выбор платформы и технологию разработки, используемую для достижения цели дипломного проекта;
На основе предлагаемой методики разработать алгоритмы и структуру системы;
На основе предлагаемой структуры разработать программное обеспечение на языке C#;
Провести сравнительный анализ выполненной работы;