Совместное редактирование. Часть 1

Добрый день. Последний год я занимаюсь в проекте «МойОфис» вопросами совместного редактирования (collaboration). Оглядываясь назад, могу констатировать, что это непростая и очень интересная задача. Поэтому я хотел бы подробно рассказать о ней и дать ответы на следующие вопросы:

1. Какие существуют подходы к обеспечению совместного редактирования?
2. Насколько они сложны в реализации?
3. Можно ли взять готовую библиотеку и использовать ее в своем проекте?
4. Можно ли вести разработку без оглядки на совместное редактирование?

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

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

Блокировка всего документа при редактировании

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

• В один момент времени только один пользователь может вносить правки. Чем больше будет такой документ и чем чаще его будут редактировать, тем более явным становится это неудобство. Представьте себе ТЗ на сотню с лишним страниц, при этом один пользователь вынужден ждать, пока его коллега закончит править раздел в другой части документа.
• Каждое изменение в документе приводит к необходимости полностью передать его на сервер, а затем скачать всем участникам, что сильно ухудшает скорость работы и увеличивает объем пересылаемых данных.
• Данное решение не может обеспечить офлайн-работу, ведь чтобы приступить к редактированию документа, требуется заблокировать его на сервере от изменения другими пользователями. А без соединения с сервером сделать это нельзя.
• Неснятая блокировка. Представим, что один пользователь забыл снять блокировку, да еще и ушел домой или вовсе уехал в отпуск. Всем остальным приходится ждать или искать нерадивого пользователя. Частично от этого можно уйти, контролируя время активности или предоставив администратору возможность принудительно снять блокировку. Впрочем, ни то ни другое не является идеальным решением, так как в первом случае нельзя понять, на основе чего можно отличить пропавший интернет от недисциплинированности пользователя, а во втором нельзя обойтись без вмешательства человека и чьи-то изменения могут быть потеряны.

Такой вариант можно часто встретить в решениях для корпоративных порталов, ERP, СЭД.

Блокировка части документа

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

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

Но и этот подход нельзя назвать идеальным:

• По-прежнему нельзя обеспечить офлайн-работу. Для блокировки любой из частей документа необходимо связаться с сервером.
• Часть документа, заблокированная при редактировании, может быть значительной. Действительно, абзац может быть довольно большим и содержать несколько сотен или тысяч знаков текста. Еще больше сложностей возникает при работе с таблицами. Без дополнительных ухищрений нельзя одновременно разрешить менять содержимое ячеек и структуру таблицы — вставлять и удалять строки или столбцы. Это означает, что при любом изменении одной из ячеек требуется блокировать всю таблицу. В офисных документах таблицы могут быть разного уровня вложенности или же очень большого размера. Особенно неприятным этот момент становится при работе с табличными документами, где рабочий лист и вовсе состоит из одной таблицы, а значит при любых изменениях надо его блокировать полностью.
• С точки зрения структуры, документ можно упрощенно представить как последовательность абзацев и таблиц. И когда мы вставляем или удаляем таблицы и абзацы, то мы редактируем эту последовательность. А это значит, что корректность совместного редактирования такой последовательности также необходимо обеспечить (кстати, принципиальной разницы между редактированием списка абзацев или списка букв нет, разве что первое происходит реже). Без введения принципиально другого метода синхронизации это должна быть опять же блокировка, только на этот раз объект блокировки будет один на весь документ.

Некоторые читатели могут заметить, что задача совместного редактирования успешно решается в системах контроля версий, с последовательной историей (SVN или CVS) или с возможностью ветвлений (GIT, Mercurial). Да, вы правы, но и здесь есть свои нюансы, которые делают невозможным применить в нашем случае тот же принцип:

• Merge. Во-первых, для пользователей офисных пакетов это понятие как правило незнакомо. Во-вторых, объединение разных версий документа становится принципиально более трудным при переходе от простого текста к документу со сложной (как правило иерархической) структурой, где есть текст, вложенные таблицы, изображения и различные настройки форматирования. Просто представьте себе подобный 3-way merge.
• Даже при использовании kdiff3 или winmerge случаются ошибки, а ведь они работают с простым текстом.
• Обычному пользователю офисных приложений будет непросто вникнуть в мир ветвлений и слияний. А вникнув, использовать будет не очень быстро и удобно.

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

Для нас это диктует дополнительные требования:

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

Отсюда следует, что состояния документа у клиентов и на сервере могут отличаться. Это формирует следующее требование:

2. Сходимость (convergence). Когда все пользователи закончат свою работу и все уведомления о правках будут доставлены, как на сервере, так и у клиентов должно быть одно и то же состояние документа.

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

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

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

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

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

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

Первый. Differential synchronization. Который в итоге нам не подошел

Алгоритм предполагает постоянный 3-way merge на стороне клиента и сервера, который сопровождается пересылкой патчей в обе стороны. На схеме представлена общая идея.

Более подробное описание можно увидеть на сайте автора.

Вероятно, вы уже догадались, по какой причине этот алгоритм нам не подходит. Правильно, как уже упоминалось, 3-way merge для документа со сложной структурой нетривиален. При этом необходимо иметь формальную гарантию того, что он даст одинаковые результаты при слияниях в разных порядках и направлениях… Это ставит крест на перспективе применения у нас данного подхода.

Второй. Operation Transformation (OT)

Это скорее общий подход, на основе которого разработаны различные алгоритмы.

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

Давайте посмотрим на еще одну схему, которая популярна в статьях об OT.

Операция О2:

• Пользователю 1 приходит операция О2 del[2, “c”] от пользователя 2.
• Операция О2 трансформируется относительно операции О1, которой не было у пользователя 2 на момент создания О2.
• В результате получается del[3, “c”], так как перед позицией 2 уже успели вставить один символ и у “с” позиция стала 3.

Операция О1:

• Пользователю 2 от пользователя 1 приходит операция О1 ins[0, “x”].
• O1 трансформируется относительно О2, но на этот раз при трансформации операция не меняется и применяется в таком же виде, как и у автора операции — пользователя 1.

Здесь используется трансформация включения (в некоторых алгоритмах используется и трансформация исключения). В дальнейшем я буду использовать обозначение Inc(O1, O2) для операции О1 с учетом эффектов операции О2, то есть, если кратко, мы включили О2 в О1.

Основное требование, которому должны удовлетворять трансформации включения (известное как Transition Property 1), — это:

Inc(O2, O1) * O1 = Inc(O1, O2) * O2,

где * — последовательное применение, справа налево. Для простоты понимания посмотрите на изображение:

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

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

Дело в том, что первые алгоритмы на основе ОТ не предусматривали использования центрального сервера. Все клиенты связывались между собой peer-to-peer. Соответственно, текущее состояние документа у пользователей выражалось последовательностью операций (О1, О2… ОN), при этом в каждый момент времени количество, состав и порядок этих операций у каждого клиента может быть свой. В этом случае нельзя определить единый строгий порядок среди всех генерируемых операций, можно ввести только слабый порядок по happens before критерию. Операции, между которыми нет такого отношения, считаются конкурирующими или параллельными (concurrent).

Подобный подход также несет с собой определенные сложности:

• Производительность. Количество трансформаций может быть очень большим, клиентам приходится хранить всю историю, так как в любой момент может прийти сколь угодно «древняя» операция от другого пользователя.
• Для корректной реализации требования TP-1 уже недостаточно. Приходится требовать еще и как минимум TP-2: Inc(O3, Inc(O1, O2) * O2) = Inc(O3, Inc(O2, O1) * O1). В зависимости от конкретного алгоритма может понадобиться выполнение других требований к трансформациям и обратным операциям (полный список здесь). Если у вас есть набор операций, то эти требования должны быть выполнены для любой пары или тройки, а это далеко не всегда так. При этом, чтобы иметь уверенность в сходимости алгоритма, эти требования необходимо формально верифицировать, то есть доказать, как теорему.
• Сложность. Подобные алгоритмы действительно непростые, и порой в них находят ошибки. Например, один из случаев, потенциально приводящий к ошибке, выглядит вот так:

Интересующиеся классическими peer-to-peer алгоритмами могут найти подробный их обзор и сравнение тут.

Перечисленные выше трудности можно разрешить, если отказаться от равноправности всех клиентов и peer-to-peer соединений. При добавлении центрального сервера состояние документов можно описывать простой ревизией и требовать выполнения не более чем TP-1… Но этой теме будет посвящена уже следующая статья. Обещаю, что для любителей алгоритмов там будет больше интересного.

Первая статья из цикла тем временем подошла к финалу. Буду рад увидеть в комментариях ваши вопросы и пожелания по поводу содержания следующих статей.

Пока!

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.