Теория без практики пуста, а практика без теории слепа.

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

Операциональное преобразование (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 {
    /**
     * Checks whether this operation is an insertion.
     *
     * @return {@code true} if the operation inserts new data; {@code false} otherwise.
     */
    boolean isIns();

    /**
     * Checks whether this operation is a deletion.
     *
     * @return {@code true} if the operation removes existing data; {@code false} otherwise.
     */
    boolean isDel();

    /**
     * Retrieves the position where this operation occurs.
     *
     * @return The zero-based position index for the operation.
     */
    int pos();

    /**
     * Retrieves the actual data value associated with this operation.
     *
     * @return The string content being inserted or modified.
     */
    String val();
}

Отношения между операциями вынесем в утилитный класс `Rel`:

Показать код

package ru.dwerty.otxform;

/**
 * Relations between operations Ins and Del.
 */
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 {
            // Additional condition when the delete operation should be split into two delete operations,
            // where the first is before the insertion and the second is after the insertion.
            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 {
            // Additional condition when the delete operation should be split into two delete operations,
            // where the first is before the insertion and the second is after the insertion.
            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()) {
            // Identity operation
            return new Del(a.pos(), "0");
        } else {
            // Additional value calculation when delete operation goes out of scope
            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.
     * @return The processed input operations object.
     */
    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;
        }
    }

    /**
     * Creates a copy of the provided operations object.
     *
     * @param ops The operations object to copy.
     * @return A copy of the input operations object.
     */
    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();
        }
    }

    /**
     * Calculates the position offset for a given position based on an operations.
     *
     * @param pos The original position before mutations are applied.
     * @param ops The operations containing transformations that affect position.
     * @return The newly computed position offset relative to the processed operations.
     */
    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;
        }
    }
}

Сделаем все это в виде отдельной библиотеки для того, чтобы использовать на клиенте и сервере.

Весь исходный код библиотеки можно посмотреть по ссылке https://github.com/dmitry-goncharov/otxform.

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

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

В итоге остаются следующие случаи:

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

В результате получилось приложение OTXform– https://play.google.com/store/apps/details?id=ru.dwerty.otxform.android. Проверял только с двумя участниками, поэтому могут быть баги.

Сделал небольшое видео, в котором произвел вышеизложенные случаи. Убрал лишние кадры и немного ускорил для того, чтобы перевести в GIF.

Заключение

В заключение хочу сказать следующее – тема не самая простая несмотря на кажущуюся простоту основной идеи – преобразуй и применяй операции.

Операциональное преобразование (OTXform – operational transformation)