Теория без практики пуста, а практика без теории слепа.
В данной статье рассмотрим технологию операционального преобразования, изучим теорию, проанализируем и применим на практике.
Операциональное преобразование (Operational transformation) это технология для автоматического разрешения конфликтов в программном обеспечении для совместной работы.
Изначально была придумана для редактирования простых текстовых документов.
Дальнейшие исследования расширили ее возможности и области применения, что в свою очередь породило несколько алгоритмов.
В данной работе я не буду рассматривать все, а только один из них.
Цель
Целью для себя я определил реализовать редактирование документа в режиме реального времени, чтобы клиенты могли совместно вносить изменения в документ, сохраняя при этом внесенные каждым клиентом изменения. Предполагается, что любые операции, применяемые к документу в данный момент на любом клиенте, не будут конфликтовать с операциями, которые применяются в тот же момент времени другим клиентом. Пользовательский интерфейс обновляется в режиме реального времени без необходимости запрашивать блокировку документа у сервера.
Блокировка и другие пессимистичные алгоритмы параллельного доступа малоприменимы из-за высокой задержки. Пока один клиент заблокирует документ, остальные не смогут вносить изменения.
Операциональное преобразование хорошо подходит для такой цели благодаря своему оптимистичному подходу и позволяет рассматривать только две операции в любой момент времени.
Идея
Основная идея заключается в преобразовании операций, позволяющих применить их к документам для поддержания согласованности между всеми версиями документа и его сходимости, чтобы у всех участников редактирования была одна и та же копия документа.
Основой является функция 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''.
Реализация
Исходя из изложенного выше, получается клиент-серверная реализация.
Долговременное хранение истории документа не предусматривается, вся история будет храниться только в оперативной памяти, так как целью является автоматическое разрешение конфликтов при редактировании, а не хранение документов. При редактировании клиенты будут держать постоянное соединение, поэтому не придется вычислять изменения на клиентах.
Определим интерфейс операций `Op` и сами операции вставки `Ins` и удаления `Del`:
package ru.dwerty.otxform; /** * The operation. * <p> * The types of operations: * - Ins - insert operation * - Del - delete operation * <p> * The types of transformations: * <p> * - Inclusion/Forward transformation - transform "a" before "b" taking into account the influence of "b" * - Exclusion/Backward transformation - transform "a" before "b" without taking into account the influence of "b" */ public interface Op { boolean isIns(); boolean isDel(); int pos(); String val(); }
package ru.dwerty.otxform; /** * The insert operation. * * @param pos the position for insert. * @param val the insert symbols. * @param ord the ordering flag. */ public record Ins(int pos, String val, boolean ord) implements Op { /** * @param pos the position for insert. * @param val the insert symbols. */ public Ins(int pos, String val) { this(pos, val, false); } @Override public boolean isIns() { return true; } @Override public boolean isDel() { return false; } @Override public int pos() { return pos; } @Override public String val() { return val; } public boolean ord() { return ord; } }
package ru.dwerty.otxform; /** * The delete operation. * * @param pos the position for delete. * @param val the number of deleted symbols. */ public record Del(int pos, String val) implements Op { public Del(int pos) { this(pos, "1"); } public Del(int pos, int val) { this(pos, String.valueOf(val)); } @Override public boolean isIns() { return false; } @Override public boolean isDel() { return true; } }
Отношения между операциями вынесем в утилитный класс `Rel`:
package ru.dwerty.otxform; class Rel { private Rel() { } /** * Insert in relation to insert. * * @param a The insert operation. * @param b The insert operation. * @return the operation of relation. */ static Ins relInsIns(final Ins a, final Ins b) { if ((a.pos() < b.pos()) || (a.pos() == b.pos() && a.ord())) { return new Ins(a.pos(), a.val(), a.ord()); } else { return new Ins(a.pos() + b.val().length(), a.val(), a.ord()); } } /** * Insert in relation to delete. * * @param a The insert operation. * @param b The delete operation. * @return the operation of relation. */ static Ins relInsDel(final Ins a, final Del b) { if (a.pos() <= b.pos()) { return new Ins(a.pos(), a.val(), a.ord()); } else { if (a.pos() < b.pos() + Integer.parseInt(b.val())) { return new Ins(b.pos(), a.val(), a.ord()); } else { return new Ins(a.pos() - Integer.parseInt(b.val()), a.val(), a.ord()); } } } /** * Delete in relation to insert. * * @param a The delete operation. * @param b The insert operation. * @return the operations of relation. */ static Object relDelIns(final Del a, final Ins b) { if (a.pos() >= b.pos()) { return new Del(a.pos() + b.val().length(), a.val()); } else { if (a.pos() + Integer.parseInt(a.val()) <= b.pos()) { return new Del(a.pos(), a.val()); } else { final int d = b.pos() - a.pos(); return new Object[]{ new Del(a.pos(), d), new Del(a.pos() + b.val().length(), Integer.parseInt(a.val()) - d) }; } } } /** * Delete in relation to delete. * * @param a The delete operation. * @param b The delete operation. * @return the operation of relation. */ static Del relDelDel(final Del a, final Del b) { if (a.pos() == b.pos()) { return new Del(a.pos(), "0"); } else { final int aVal = Integer.parseInt(a.val()); final int bVal = Integer.parseInt(b.val()); final int val = Math.max(0, Math.min(aVal, Math.max(a.pos() + aVal, b.pos() + bVal) - Math.min(a.pos(), b.pos()) - bVal)); if (a.pos() < b.pos()) { return new Del(a.pos(), val); } else { return new Del(Math.max(b.pos(), a.pos() - bVal), val); } } } }
Добавим запись для получения производных `XOp`:
package ru.dwerty.otxform; /** * The pair of operation. * * @param a the server operation(s). * @param b the client operation(s). */ public record XOp(Object a, Object b) { }
Основные функции преобразования также вынесем в утилитный класс `OT`:
package ru.dwerty.otxform; import static ru.dwerty.otxform.Rel.relDelDel; import static ru.dwerty.otxform.Rel.relDelIns; import static ru.dwerty.otxform.Rel.relInsDel; import static ru.dwerty.otxform.Rel.relInsIns; /** * Operation transformation tool. * <p> * The main function of the tool is the function `OT.xform(a, b) = {a', b'}`, * where `a` and `b` are the original server and client messages. * The messages `a'` and `b'` must have the property that * if the client applies `b` followed by` a'`, and the server applies `a` followed by` b'`, * then the client and server will wind up in the same final state. */ public class OT { private OT() { } /** * Apply operations to transform the text. * * @param text the text. * @param ops the operations. * @return the new text. */ public static String apply(String text, final Object ops) { if (ops instanceof Object[]) { for (Object object : (Object[]) ops) { text = apply(text, object); } return text; } else if (ops instanceof Op op) { if (op.isDel()) { text = text.substring(0, op.pos()) + text.substring(op.pos() + Integer.parseInt(op.val())); } if (op.isIns()) { text = text.substring(0, op.pos()) + op.val() + text.substring(op.pos()); } } else { throw new UnsupportedOperationException(); } return text; } /** * Function xform(a, b) => {a', b'}, * the transform function takes two operations, one server and one client, and produces a pair of operations. * * @param a the server operation. * @param b the client operation. * @return the pair of operation. */ public static XOp xform(final Op a, final Op b) { if (a.isIns() && b.isIns()) { return new XOp(relInsIns((Ins) a, (Ins) b), relInsIns((Ins) b, (Ins) a)); } else if (a.isIns() && b.isDel()) { return new XOp(relInsDel((Ins) a, (Del) b), relDelIns((Del) b, (Ins) a)); } else if (a.isDel() && b.isIns()) { return new XOp(relDelIns((Del) a, (Ins) b), relInsDel((Ins) b, (Del) a)); } else if (a.isDel() && b.isDel()) { return new XOp(relDelDel((Del) a, (Del) b), relDelDel((Del) b, (Del) a)); } else { throw new UnsupportedOperationException(); } } /** * @param a the server operation. * @param b the array of client operations. * @return the pair of operation. */ public static XOp xform(Op a, Object b) { if (b instanceof Object[] arr) { Object updA = a; Object[] res = new Object[arr.length]; for (int i = 0; i < arr.length; i++) { XOp t = xform(updA, arr[i]); updA = copy(t.a()); res[i] = copy(t.b()); } return new XOp(updA, res); } else if (b instanceof Op opB) { return xform(a, opB); } else { throw new UnsupportedOperationException(); } } /** * @param a the array of server operations. * @param b the array of client operations. * @return the pair of operation. */ public static XOp xform(Object a, Object b) { if (a instanceof Object[] arr) { Object[] res = new Object[arr.length]; for (int i = 0; i < arr.length; i++) { XOp t = xform(arr[i], b); res[i] = copy(t.a()); b = copy(t.b()); } return new XOp(res, b); } else if (a instanceof Op opA) { return xform(opA, b); } else { throw new UnsupportedOperationException(); } } /** * Set flag ordering for every insert operation. * * @param op The arrays of operations or single operation. */ public static Object ord(final Object op) { if (op instanceof Object[] ops) { for (int i = 0; i < ops.length; i++) { ops[i] = ord(ops[i]); } return ops; } else if (op instanceof Ins ins) { return new Ins(ins.pos(), ins.val(), true); } else { return op; } } public static Object copy(final Object ops) { if (ops instanceof Object[] arr) { Object[] subOps = new Object[arr.length]; for (int i = 0; i < arr.length; i++) { subOps[i] = copy(arr[i]); } return subOps; } else if (ops instanceof Ins ins) { return new Ins(ins.pos(), ins.val(), ins.ord()); } else if (ops instanceof Del del) { return new Del(del.pos(), del.val()); } else { throw new UnsupportedOperationException(); } } public static int offset(final int pos, final Object ops) { int offset = 0; if (ops instanceof Object[] arr) { for (Object o : arr) { offset += offset(pos, o); } return offset; } else if (ops instanceof Ins ins && ins.pos() <= pos) { return ins.val().length(); } else if (ops instanceof Del del && del.pos() < pos) { return -Integer.parseInt(del.val()); } else { return 0; } } }
Сделаем все это в виде отдельной библиотеки для того, чтобы использовать на клиенте и сервере.
Реализация сервера, клиента, взаимодействия клиента с сервером, команд и уведомлений не является основной целью, а лишь необходимостью для получения рабочей версии, поэтому эти детали оставим без описания.
Отдельная сложность это поддержка редактирования в отсутствии подключения к серверу. Эта задача выходит за рамки данной темы, поэтому оставим ее на потом.
В итоге остаются следующие случаи:
Один участник редактирует, другой видит изменения
Два участника редактируют, оба видят изменения каждого
Один участник уходит в офлайн, другой продолжает редактировать, первый участник переходит в онлайн и видит все изменения, произведенные во время нахождения в офлайн
В результате получилось приложение OTXform– https://play.google.com/store/apps/details?id=ru.dwerty.otxform.android. Проверял только с двумя участниками, поэтому могут быть баги.
Сделал небольшое видео, в котором произвел вышеизложенные случаи. Убрал лишние кадры и немного ускорил для того, чтобы перевести в GIF.
Заключение
В заключение хочу сказать следующее – тема не самая простая несмотря на кажущуюся простоту основной идеи – преобразуй и применяй операции.
