В данной статье рассмотрим технологию операционального преобразования, изучим теорию, проанализируем и применим на практике.
Теория без практики пуста, а практика без теории слепа.
Введение
Операциональное преобразование это технология для автоматического разрешения конфликтов в программном обеспечении для совместной работы.
Изначально была придумана для редактирования простых текстовых документов.
Дальнейшие исследования расширили ее возможности и области применения, что в свою очередь породило несколько алгоритмов.
В данной работе я не буду рассматривать все, а только один из них.
Цель
Целью для себя я определил реализовать редактирование документа в режиме реального времени, чтобы клиенты могли совместно вносить изменения в документ, сохраняя при этом внесенные каждым клиентом изменения. Предполагается, что любые операции, применяемые к документу в данный момент на любом клиенте, не будут конфликтовать с операциями, которые применяются в тот же момент времени другим клиентом. Пользовательский интерфейс обновляется в режиме реального времени без необходимости запрашивать блокировку документа у сервера.
Блокировка и другие пессимистичные алгоритмы параллельного доступа малоприменимы из-за высокой задержки. Пока один клиент заблокирует документ, остальные не смогут вносить изменения.
Операциональное преобразование хорошо подходит для такой цели благодаря своему оптимистичному подходу и позволяет рассматривать только две операции в любой момент времени.
Идея
Основная идея заключается в преобразовании операций, позволяющих применить их к документам для поддержания согласованности между всеми версиями документа и его сходимости, чтобы у всех участников редактирования была одна и та же копия документа.
Основой является функция OT.xform(a, b) = {a', b'}, где a и b это исходные сообщения сервера и клиента. Сообщения a и b должны обладать следующим свойством: если клиент применит b, а затем a', а сервер применит a, а затем b', то клиент и сервер окажутся в одном и том же конечном состоянии.
Другими словами, если применение операции a, а затем операции b' к документу D приводит к получению документа D', то применение операции b, а затем операции a' к документу D также должно привести к получению документа D'.
Таким образом получается:
OT.xform(a, b) = {a', b'}
a'(b(D)) = b'(a(D))
Пример
Прогоним основную идею на простом примере.
Текстовый документ, содержащий строку olay, реплицирован между двумя участниками.
Первый участник вставляет символ h в нулевую позицию.
Представим эту операцию в виде: Op1 = Ins(0, h)
В результате строка становится holay
Второй участник удаляет символ y с третьей позиции.
Представим эту операцию в виде: Op2 = Del(3, 1)
В результате строка становится ola.
На основании идеи операционального преобразования, преобразуем операции в согласии с эффектами выполнения в предыдущих одновременных операций так, чтобы преобразованная операция мог��а выполниться корректно и не нарушить согласованность в документе.
OT.xform(Op1, Op2) = {Op1', Op2'}, где
Op1' = Ins(0, h)
Op2' = Del(4, 1)
Таким образом, для выполнения Op2 после Op1, Op2 должна быть уже преобразована относительно Op1.
Согласно формуле выше выходит:
Ins(0, h)(Del(3, 1)(olay)) = Del(4, 1)(Ins(0, h)(olay)) = hola
Проектирование
Все редактирование документа определим через две операции:
Вставка (
Ins)Удаление (
Del)
Соответственно, замена будет содержать обе операции.
Основная функция принимает две операции и отдает две производные операции.
Для того, чтобы понять как создать производные, нужно определить вариативность операций и их отношения друг к другу.
Варианты входных операций:
Вставка, вставка (
Ins,Ins)Вставка, удаление (
Ins,Del)Удаление, вставка (
Del,Ins)Удаление, удаление (
Del,Del)
Производные входных операций это отношение первой операции ко второй и второй операции к первой.
OT.xform(A, B) = {A', B'} = {relAtoB, relBtoA}
Определим четыре функции отношений и таким образом покроем все вариации входных операций.
Функции отношений:
Отношение вставки к вставки (
relInsIns)Отношение вставки к удалению (
relInsDel)Отношение удаления к вставки (
relDelIns)Отношение удаления к удалению (
relDelDel)
Применение операций вставки и удаления к тексту будут являться действиями редактирования текста.
Само редактирование представим множеством операций. В дальнейшем будем называть это множество историей документа.
Вся история документа будет храниться на сервере, который будет выступать центральным узлом системы.
Клиентами системы будут Android приложения. Для получения лучшего пользовательского опыта надо бы сделать свою реализацию виджета для редактирования текста, в котором будет поддержка отрисовки курсоров для всех клиентов текущей сессии редактирования документа. Но оставим эту задачу на потом и ограничимся входящим в состав SDK виджетом для редактирования текста android.widget.EditText. Для получения изменений ввода текста будет использоваться своя реализация интерфейса android.text.TextWatcher. Других курсоров не будет, и свой курсор можно будет устанавливать только тапом.
Взаимодействия межд�� клиентами и сервером будет по TCP соединениям. Разделим наш протокол взаимодействия на команды и уведомления. Команды будут формироваться на клиентах, а уведомления на сервере.
Определим следующие команды:
Создать редактирование
Присоединиться к редактированию
Редактировать
Определим следующие уведомления:
По присоединению к редактированию
По выходу из редактирования
По редактированию
Представим историю изменений в виде графа, направленного сверху вниз. Если нет конфликтов, то сообщения обрабатываются в одинаковом порядке, и переход от одного состояния в другое происходит по одинаковому пути. Если есть конфликт, то переход от одного состояния в другое происходит по разным путям.
Например:
В этом случае, для того, чтобы они снова сошлись, необходимо будет применить функцию OT.xform(a, b) = {a', b'}.
Протокол взаимодействия не подразумевает какого-либо блокирования, что в условиях сетевого взаимодействия не дает гарантий на упорядоченный поток операций. Это значит, что они могут разойтись дальше, что приведет к более сложной ситуации.
Например:
В этом случае клиент выполнил a и получает конфликтующее сообщение b1 от сервера. Он использует функцию OT.xform для вычисления b1', чтобы достичь состояния (1|1). Затем сервер генерирует сообщение b2 из состояния (0|1). Однако, сервер еще не обработал a. Что делать клиенту? Он не может использовать OT.xform(a, b2), поскольку a и b2 были сгенерированы из разных начальных состояний. Решение будет заключаться в запоминании промежуточных производных.
Например:
Когда клиент вычисляет b1', он должен запомнить a', другую производную функции OT.xform(a, b1) = {a', b1'}. И когда придет b2, клиент сможет использовать a' для вычисления OT.xform(a', b2) = {a'', b2'}. Он выполняет b2', чтобы перейти в состояние (1|2), и снова запоминает a''. Если сервер обработал сообщение клиента, он также будет в состоянии (1|2). В противном случае его следующее сообщение будет из (0|3), и для обработки этого сообщения клиент сможет использовать a''.
Реализация
Исходя из изложенного выше, получается клиент-серверная реализация.
Долговременное хранение истории документа не предусматривается, вся история будет храниться только в оперативной памяти, так как целью является автоматическое разрешение конфликтов при редактировании, а не хранение документов. При редактировании клиенты будут держать постоянное соединение, поэтому не придется вычислять изменения на клиентах.
Определим интерфейс операций и сами операции:
public interface Op {…}
public record Ins(int pos, String val, boolean ord) implements Op {...}
public record Del(int pos, String val) implements Op {...}Отношения между операциями вынесем в утилитный класс:
class Rel {
static Ins relInsIns(final Ins a, final Ins b) {...}
static Ins relInsDel(final Ins a, final Del b) {...}
static Object relDelIns(final Del a, final Ins b) {...}
static Del relDelDel(final Del a, final Del b) {...}
}Добавим запись для получения производных:
public record XOp(Object a, Object b) {...}Основные функции преобразования также вынесем в утилитный класс:
public class OT {
public static String apply(String text, final Object ops) {...}
public static XOp xform(final Op a, final Op b) {...}
public static XOp xform(Op a, Object b) {...}
public static XOp xform(Object a, Object b) {...}
}Сделаем все это в виде отдельной библиотеки для того, чтобы использовать на клиенте и сервере.
Реализация сервера, клиента, взаимодействия клиента с сервером, команд и уведомлений не является основной целью, а лишь необходимостью для получения рабочей верс��и, поэтому эти детали оставим без описания.
Отдельная сложность это поддержка редактирования в отсутствии подключения к серверу. Эта задача выходит за рамки данной темы, поэтому оставим ее на потом.
В итоге остаются следующие случаи:
Один участник редактирует, другой видит изменения
Два участника редактируют, оба видят изменения каждого
Один участник уходит в офлайн, другой продолжает редактировать, первый участник переходит в онлайн и видит все изменения, произведенные во время нахождения в офлайн
В результате получилось приложение OTXform– https://play.google.com/store/apps/details?id=ru.dwerty.otxform.android. Проверял только с двумя участниками, поэтому могут быть баги.
Сделал небольшое виде��, в котором произвел вышеизложенные случаи. Убрал лишние кадры и немного ускорил для того, чтобы перевести в GIF.
Заключение
В заключение хочу сказать следующее – тема не самая простая несмотря на кажущуюся простоту основной идеи – преобразуй и применяй операции.
