Главная
Автоматическое разрешение конфликтов с помощью операциональных преобразований

Автоматическое разрешение конфликтов с помощью операциональных преобразований +12

12.07.2018 11:51

amberovsky 0 1000 Источник

Автоматическое разрешение конфликтов в среде с более, чем одним ведущим узлом (в данной статье под ведущим узлом понимается узел, который принимает запросы на изменение данных) – очень интересная область исследований. Существует несколько различных подходов и алгоритмов, в зависимости от области применения, и в данной статье будет рассмотрена технология Операциональных Преобразований (Operational Transformations, OT) для разрешения конфликтов в приложениях совместного редактирования, таких как Google Docs и Etherpad.

1. Введение

Совместная работа сложна с технической точки зрения, потому что несколько людей могут вносить различные изменения в один и тот же участок текста в практически одинаковые моменты времени. Так как доставка данных через интернет не осуществляется мгновенно (скорость передачи данных в оптоволокне имеет ограничения), то для имитации мгновенного отклика в каждый момент времени каждый клиент работает с локальной версией (репликой) редактируемого документа, которая может отличаться от версий других участников. И основная загвоздка – обеспечить согласованность (consistency) между локальными версиями, или другими словами – как обеспечить, что все локальные версии рано или поздно сходятся (converge) в одну и ту же, корректную версию документа (мы не можем требовать, чтобы все клиенты в какие-то моменты времени одновременно имели одну и ту же версию, так как процесс редактирования может быть бесконечным).

Старая версия Google Docs

Изначально Google Docs, как и многие другие приложения совместного редактирования документов, использовал простое сравнение содержимого различных версий документа. Предположим, что у нас два клиента – Петя и Вася и текущее состояние документа синхронизировано между ними. В старой версии гуглодоков сервер, при получении обновления от Пети, вычисляет разницу (diff) между его версией и своей и пытается слить (merge) две версии в одну наилучшим доступным способом. Затем сервер отсылает полученную версию Васе. Если у Васи есть какие-то неотправленные на сервер изменения, то процесс повторяется – необходимо слить версию от сервера с локальной Васиной и отправить снова на сервер.

Очень часто такой подход работает не очень хорошо. Например, предположим что Петя, Вася и сервер начинают с синхронизированного документа с текстом “The quick brown fox”.

Петя выделяет жирным слова brown fox, а Вася в то же время заменяет слово fox на dog. Пусть Петины изменения пришли первыми на сервер и тот пересылает обновлённую версию Васе. Понятно, что итоговым результатом должно быть The quick brown dog, но для алгоритмов слияния недостаточно информации чтобы это понять, варианты The quick brown fox dog, The quick brown dog, The quick brown dog fox являются абсолютно корректными. (Например, в git в таких случаях вы получите конфликт слияния и придётся править руками). В этом и состоит основная проблема такого подхода – не получится быть уверенным в результатах слияния, если опираться только на содержимое документа.

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

Новая версия Google Docs

В новой версии Google Docs был применён совершенно другой подход: документы хранятся как последовательность изменений и вместо сравнения содержимого мы накатываем изменения по порядку (Под порядком здесь и далее понимается отношение порядка). Зная, как пользователь изменял документ и учитывая его намерения (intentions) мы можем корректно определить итоговую версию после объединения всех правок.

Окей, теперь нужно понять когда применять изменения – нам нужен протокол взаимодействия (collaboration protocol).

В Google Docs все правки документа сводятся к трём различным операциям (operations):

Вставка текста
Удаление текста
Применение стилей к тексту

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

Небольшая ремарка: первым (публичном) продуктом гугла с поддержкой OT был, по всей видимости, Google Wave. Он поддерживал гораздо более широкий набор операций.

Пример

Пусть Петя и Вася начинают с одного и того же состояния “ХАБР 2017”.
Петя меняет 2017 на 2018, это на самом деле создаёт 2 операции:

В это же время Вася меняет текст на “ПРИВЕТ ХАБР 2017”:

Васе приходит Петина операция на удаление, если он просто применит её, то получится неверный текст (должна была быть удалена цифра 7):

Чтобы избежать этого, Вася должен преобразовать (transform) Петину операцию в соответствии с его текущими локальными изменениями (другими словами, операции являются контекстно-зависимыми):

$\{Delete\ \ @8\} \rightarrow \{Delete\ \ @15\}$

Говоря чуть более формально, рассмотрим такой пример:

Тогда:

$display$

Вуаля! Описанный алгоритм и называтся Operational Transformation.

2. Operational Transformation

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

Для обеспечения согласованности было разработано несколько моделей согласованности (consistency models), рассмотрим одну из них – CCI.

CCI модель обеспечивает выполнение трёх свойств:

Сходимость (converge): Все реплики общего документа должны быть идентичными после выполнения всех операций:

В данном примере оба пользователя начинают с идентичных реплик. Затем они изменяют документ и реплики расходятся (diverge) – так достигается минимальное время отклика. После отправки локальных изменений остальным клиентам свойство сходимости требует, чтобы итоговое состояние документа у всех клиентов стало идентичным.
Сохранность намерения (intention preservation): Намерение операции дожно сохраняться на всех репликах, в независимости от наложения выполнения нескольких операций одновременно. Намерение операции (intention of an operation) определяется как эффект от её выполнения на той копии, где она была создана.

Рассмотрим пример, где это свойство не выполняется:

Оба клиента начинают с одинаковых реплик, затем оба делают изменения. Для Пети, намерение его операции – это вставить ‘12’ на первый индекс, а для Васи – удалить символы с индексами 2 и 3. После синхронизации у Пети Васино намерение и у Васи Петино намерение нарушены. Заметим также, что реплики разошлись, но это не является требованием для рассматриваемого свойства. Корректный итоговый вариант предлагается определить читателю в качестве маленького упражнения.
Сохранность причинности (Causality Preservation): операции должны быть выполнены в причинно-следственном порядке (основываясь на отношении произошло-до (happened before)).

Рассмотрим пример, где это свойство не выполняется:

Как вы видите, Петя отправил Васе и агенту Смиту своё изменение документа, Вася получил его первым и удалил последний символ. Из-за сетевого лага Смит получает первым Васину операцию на удаление символа, которого ещё не существует.

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

Дизайн OT

Одной из стратегией дизайна OT системы является разделение на три части:

Алгоритмы контроля преобразования (transformation control algorithms): определить, когда операция (target) готова к преобразованию, относительно каких операций (reference) преобразования проводить, и в каком порядке их выполнять.
Функции преобразования (transformation functions): выполнение преобразования на target операции с учётом влияния reference операций.
Требования и свойства преобразований (properties and conditions): обеспечить связь между этими компонентами и выполнять проверки на корректность.

Функции преобразования

Функции преобразования можно разделить на два типа:

Включения/прямое (Inclusion/Forward Transformation): преобразовании операции $inline$ перед операцией $inline$ таким образом, что учитывается эффект от $inline$ (например, две вставки)
Исключения/обратное (Exclusion/Backward Transformation): преобразование операции $inline$ перед операцией $inline$ таким образом, что эффект от $inline$ исключается (например, вставка после удаления)

Пример для посимвольных операций вставок/удаления (i – вставка, d – удаление):

Tii(Ins[p1, c1], Ins[p2, c2]) {
  if (p1 < p2) || ((p1 == p2) && (order() == -1))  // order() – вычисление порядка
	return Ins[p1, c1]; // Tii(Ins[3, ‘a’], Ins[4, ‘b’]) = Ins[3, ‘a’]
  else
	return Ins[p1 + 1, c1]; // Tii(Ins[3, ‘a’], Ins[1, ‘b’]) = Ins[4, ‘a’]
}

Tid(Ins[p1, c1], Del[p2]) {
  if (p1 <= p2)
    return Ins[p1, c1]; // Tid(Ins[3, ‘a’], Del[4]) = Ins[3, ‘a’]
  else
    return Ins[p1 – 1, c1]; // Tid(Ins[3, ‘a’], Del[1]) = Ins[2, ‘a’]
}

Tdi(Del[p1], Ins[p2, c1]) {
  // Попробуйте придумать сами, в качестве упражнения
}

Tdd(Del[p1], Del[p2]) {
  if (p1 < p2)
    return Del[p1]; // Tdd(Del[3], Del[4]) = Del[3]
  else
    if (p1 > p2) return Del[p1 – 1]; // Tdd(Del[3], Del[1]) = Del[2]
  else
    return Id; // Id – тождественный оператор
}

3. Протокол взаимодействия в Google Docs

Давайте рассмотрим как работает протокол взаимодействия в Google Docs более детально. Пусть у нас есть сервер, Петя и Вася, и у них синхронизированная версия пустого документа.

Каждый клиент запоминает следующую информацию:

Версия (id, ревизия) последнего изменения, полученного от сервера.
Все изменения, сделанные локально, но не отправленные на сервер (ожидающие отправки)
Все изменения, сделанные локально, отправленные на сервер, но без подтверждения от сервера.
Текущее состояние документа, которое видит пользователь.

Сервер, в свою очередь, запоминает:

Список всех полученных, но не обработанных изменений (ожидающие обработки).
Полная история всех обработанных изменений (revision log).
Состояние документа на момент последнего обработанного изменения.

Итак, Петя начинает со слова “Hello” в начале документа:

Клиент сначала добавил это изменение в список ожидающих отправки, а затем отправил на сервер и переместил изменения в список отправленных.

Петя продолжает печатать и уже добавил слово “Habr”. В это же время Вася напечатал “!” в его пустом (он же ещё не получил Петины изменения) документе.

Петино

$\{Insert\ \ ' Habr',\ @5\}$ было добавлено в список ожидающих отправки, но не было ещё отправлено, потому что мы не отправляем больше одного изменения за раз, а предыдущее ещё не было подтверждено. Заметим также, что сервер сохранил изменения Пети в своём логе ревизий. Далее сервер отправляет их Васе и посылает подтверждение Пете (о том, что Петины первые изменения успешно обработаны)

Клиент Васи получает Петины изменения от сервера и применяет OT относительно его ожидающих отправки на сервер

$\{Insert\ \ '!',\ @0\}$ . Результатом становится изменение индекса вставки с 0 на 5. Отметим также, что оба клиента обновили номер последней синхронизированной ревизии с сервером на 1. И наконец, Петин клиент удаляет соответствующее изменение из списка ожидающих подтверждение от сервера.

Далее Петя и Вася отправляют свои изменения на сервер.

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

$\{Insert\ \ '!',\ @5\}$ .

Затем происходит важный момент. Сервер начинает обрабатывать изменения Васи, те, которые, по мнению Васи, имеют номер ревизии 2. Но сервер уже зафиксировал изменения у себя под номером 2, поэтому он применяет преобразование ко всем изменениям, о которых клиент Васи ещё не в курсе (в данном случае —

$\{Insert\ \ ' Habr',\ @5\}$ ), и сохраняет результат под номером 3.

Как мы видим, индекс в Васином изменении был увеличен на 5, чтобы вместить Петин текст.

Процесс закончен для Пети, а Васе осталось получить новое изменение от сервера и послать подтверждение.

4. Etherpad

Рассмотрим ещё одно похожее приложение, где применяется OT – опенсорсный проект онлайн-редактора с совместным редактированием etherpad.org

В Etherpad функции преобразования слегка другие – изменения отправляются на сервер в виде набора изменений (changeset), определяемого как

$(\ell_1 \rightarrow \ell_2)[c_1,c_2,c_3,...],$

где

$\ell_1$ : длина документа до редактирования.
$\ell_2$ : длина документа после редактирования.
— описание документа после редактирования. Если – число (или диапазон чисел), то это индексы символов исходного документа, которые останутся после редактирования (retained), а если – символ (или строка), то это вставка (insertion).

Пример:
1. $$inline$``" +\ (0 \rightarrow 6)[``Привет"] = ``Привет"$inline$$
2. $$inline$``Бобр” + (4 \rightarrow 4)[``Ха”,\ 2-3] = ``Хабр"$inline$$

Как вы уже понимаете, итоговый документ формируется как последовательность таких изменений, применённых по порядку к пустому документу.

Заметим, что мы не можем просто применять изменения от других участников (это, в принципе, возможно в Google Docs), потому что итоговые длины документов могут быть различны.
Например, если исходный документ был длины n, и у нас есть два изменения:

$A = (n\rightarrow n_a)[\cdots]\\ B = (n\rightarrow n_b)[\cdots],$

то

$inline$ невозможно, т.к.

$inline$ требует документ длины

$inline$ , а после

$inline$ он будет длины

$inline$ .
Для разрешения этой ситуации в Etherpad используется механизм слияния (merge): это функция, обозначаемая как

$inline$ , принимает на вход два изменения на одном и том же состоянии документа (здесь и далее обозначаемое как

$inline$ ) и производит новое изменение.

Требуется, что

$display$

Заметим, что для клиента с изменениями

$inline$ , получившему изменения

$inline$ , нет особого смысла вычислять

$inline$ , так как

$inline$ применяется к

$inline$ , а у

$inline$ текущее состояние

$inline$ . На самом деле, нам нужно вычислить

$inline$ и

$inline$ , такие, что

$display$

Функция, вычисляющая

$inline$ и

$inline$ , называется follow и определяется так:

$inline$
Алгоритм построения

$inline$ следующий:

Вставка в A становится индексами в $inline$
Вставка в B становится вставкой в $inline$
Совпадающие индексы в A и B переносятся в $inline$

Пример:

$$$display$$X = (0\rightarrow 8)[``baseball”]\\ A = (8\rightarrow 5)[0 – 1, ``si”, 7]\ /\!\!/ == ``basil”\\ B = (8\rightarrow 5)[0, ``e", 6, ``ow"]\ /\!\!/ == ``below"$$display$$$

Вычисляем:

$A’ = f(B, A) = (5\rightarrow 6)[0, 1, ``si", 3, 4]\\ B’ = f(A, B) = (5\rightarrow 6)[0, “e”, 2, 3, ``ow"]\\ m(A, B) = m(B, A) = A(B’) = B(A’) = (8\rightarrow 6)[0, ``esiow"]\\$

Вычислить

$inline$ предлагается в качестве упражнения.

Протокол взаимодействия по своей сути совпадает с Google Docs, разве что вычисления чуть более сложны.

5. Критика OT

Реализация OT является очень сложной задачей с точки зрения программирования. Цитируя из википедии: Joseph Gentle, разработчик библиотеки Share.JS и бывший инженер Google Wave сказал, что “Unfortunately, implementing OT sucks. There's a million algorithms with different tradeoffs, mostly trapped in academic papers. The algorithms are really hard and time consuming to implement correctly. […] Wave took 2 years to write and if we rewrote it today, it would take almost as long to write a second time.”

(К сожалению, написать OT очень сложно. Существует миллион алгоритмов со своими плюсами и минусами, но большинство из них – только академические исследования. Алгоритмы на самом деле очень сложны и требуют много времени для корректной их реализации. […] Мы потратили 2 года на написание Wave, и если бы пришлось сегодня написать его заново – нам потребовалось бы столько же времени)
Необходимо сохранять абсолютно каждое изменение документа

Автоматическое разрешение конфликтов с помощью операциональных преобразований +12

1. Введение

Старая версия Google Docs

Новая версия Google Docs

Пример

2. Operational Transformation

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

Дизайн OT

Функции преобразования

3. Протокол взаимодействия в Google Docs

4. Etherpad

Пример:

5. Критика OT

6. Ссылки

Комментарии (0)