Операционные преобразования как алгоритм автоматического разрешения конфликтов

1. Введение

Алгоритмы автоматического разрешения конфликтов в распределенных системах с более чем одним узлом-лидером (в этой статье под узлом-лидером мы подразумеваем узел, который принимает запросы на изменение данных) - довольно интересное направление исследований. В этой области существуют различные подходы и алгоритмы со своими собственными компромиссами, и в этой статье мы сосредоточимся на технологии оперативного преобразования, которая направлена на разрешение конфликтов в приложениях для совместного редактирования, таких как Google Docs или Etherpad.

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

1.1 Первые версии Google Документов

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

Часто такой подход не работает. Например, представьте, что Алиса, Боб и сервер начинают с синхронизированного документа «Быстрая коричневая лисица».

Алиса выделяет слова «коричневая лиса» жирным шрифтом, и в то же время Боб меняет «лисицу» на «собаку». Изменения Алисы сначала поступают на сервер, он применяется и отправляет изменения Бобу. Правильный результат слияния должен быть «Быстрая коричневая собака», но алгоритмы слияния не обладают достаточной информацией для выполнения правильного слияния. С их точки зрения «Быстрая коричневая собака», «Быстрая коричневая собака», «Быстрая коричневая собака лиса» - это правильные и действительные результаты. (В таких случаях в git возникнут конфликты слияния, и вам придется слить вручную). Это основная проблема - мы не можем полагаться на слияние при таком подходе.

1.2 Последние версии Документов Google

В последних версиях Google Docs используется другой подход - документ хранится как последовательность операций, и они применяются по порядку (под порядком здесь мы подразумеваем общий порядок) вместо сравнения версий документов.

Хорошо, теперь нам нужно понять, когда применять изменения - нам нужен протокол сотрудничества. В Google Docs все операции делятся на 3 возможных типа:

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

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

(Первым (публичным) проектом Google с поддержкой OT был Google Wave, и его набор возможных операций был намного богаче)

1.3 Пример

Пусть Алиса и Боб начнут с синхронизированного документа «ЖИЗНЬ 2017».

Алиса меняет 2017 на 2018 и фактически создает 2 операции:

В то же время Боб меняет текст на «БЕЗУМНАЯ ЖИЗНЬ 2017»:

Если Боб просто применяет операцию удаления Алисы, когда получает ее, то он получает неверный документ (вместо этого должна была быть удалена цифра 7):

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

Теперь это прекрасно.

Чтобы сделать его более формальным, давайте рассмотрим следующий пример:

тогда

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

2. Операционная трансформация

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

Несколько моделей согласованности были разработаны для обеспечения согласованности для OT. Рассмотрим одну из них - модель CCI.

Модель CCI состоит из следующих свойств:

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

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

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

Алиса и Боб начинают с одного и того же состояния документа, а затем вносят свои локальные изменения. Цель операции Алисы - вставить «12» в позицию 1, а цель операции Боба - удалить «CD». После синхронизации намерение Боба нарушается. Мы также можем наблюдать расхождение реплик, но это не является требованием для свойства сохранения намерения. Упражнение: каково правильное конечное состояние в этом примере?

3. Сохранение причинности: операции должны выполняться в соответствии с их естественным причинно-следственным порядком в процессе сотрудничества (на основе отношения произошло-до).
Рассмотрим пример, когда это свойство нарушается:

Алиса, Боб, агент Смит начинают с того же состояния документа. Алиса вносит сдачу и отправляет ее другим клиентам. Боб первым получает его, исправляет опечатку и отправляет это изменение другим клиентам. Из-за задержки сети агент Смит сначала получает от Боба операцию, которая заключается в удалении символа, которого еще нет в его реплике.

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

2.2 Дизайн ОТ

Одна из стратегий проектирования ОТ - разделить его на 3 части:

Алгоритмы управления преобразованием: отвечают за определение того, когда операция (цель преобразования) готова к преобразованию, какие операции (ссылка преобразования) должны быть преобразованы и в каком порядке должны выполняться преобразования.
Функции преобразования: отвечают за выполнение фактических преобразований в целевой операции в соответствии с влиянием эталонной операции.
Свойства и условия: определяют отношения между алгоритмами и функциями управления преобразованием и служат в качестве требования корректности алгоритма ОТ.

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

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

Включение / прямое преобразование: преобразовать операцию Oa перед Ob, чтобы эффект Ob был включен (например, две вставки)
Исключение / обратное преобразование: преобразовать операцию Oa перед Ob, чтобы исключить эффект Ob (например, вставка после удаления)

Вот пример функций преобразования, которые работают с изменениями символов:

3. Протокол совместной работы в Google Документах.

Рассмотрим подробнее, как работает протокол совместной работы с Документами Google.

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

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

Сервер хранит следующую информацию:

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

Предположим, у нас есть Алиса, Сервер, Боб, и они начинают с синхронизированного пустого документа.

Алиса печатает «Привет»:

Ее изменение было добавлено в список ожидающих изменений, а затем отправлено на сервер и перемещено в список отправленных изменений.

Тем временем Алиса печатала и добавляла «мир». В то же время Боб набрал «!» в его пустом документе (он не получил изменений Алисы):

{Insert ‘World’, @ 5} Алисы был добавлен к ожидающим изменениям, но не был отправлен, потому что ее первое изменение не было подтверждено, и мы отправляем только одно изменение за раз. Обратите внимание, что сервер обработал первое изменение Алисы и переместил его в журнал изменений. Затем он отправляет подтверждение Алисе и передает ее изменение Бобу:

Боб получает изменение и применяет к нему функцию преобразования, в результате индекс ожидаемого изменения был сдвинут с 0 на 5. Обратите внимание, что и Алиса, и Боб обновили свою последнюю синхронизированную ревизию до 1. Алиса наконец удалила свое первое изменение из отправленных. изменения.

Затем Алиса и Боб отправляют на сервер неотправленные изменения:

Сервер сначала получает изменение Алисы, поэтому он обрабатывает его, отправляет Алисе подтверждение и передает его Бобу. Боб должен снова применить функцию преобразования и перенести свое локальное изменение на индекс 11.

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

Теперь процесс для Алисы завершен, Бобу все еще нужно получить преобразованное изменение и отправить подтверждение.

4. Etherpad

Давайте посмотрим на еще одно приложение для коллективного редактирования, в котором используется технология OT - http://etherpad.org

Etherpad использует несколько иные функции преобразования - он отправляет изменения на сервер в виде набора изменений в следующем формате:

(p1 -> p2)[c_1, c_2, …],

куда:

p1 - длина документа до изменения
p2 - длина документа после изменения
c_i - определение, если документ:
если c_i - число или диапазон чисел, то это означает индексы сохраненного символа, или
если c_i - символ или строка, то это означает вставку

Пример:

«» + (0 - ›5) [« Привет »] =« Привет »
«Hllo World» + (10 - ›14) [0,« e », 1–9,« !!! »] =« Hello World !!! »

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

Мы можем отметить, что сервер не может просто применять изменения от клиентов (хотя это возможно в Google Docs), потому что длина документов может быть разной, например, если клиенты A и B запускались из одного и того же документа X длины n и выполните следующие изменения соответственно:

A: (n -> n_a)[…],

B: (n -> n_b)[…]

то B (A (X)) невозможно, потому что B требует документ длины n, но он имеет длину n_a после A. Для решения этой проблемы etherpad вводит так называемую функцию merge, которая принимает 2 набора изменений, которые применяются в то же состояние документа и вычисляет новый единый набор изменений. Требуется, чтобы

Не очень полезно вычислять m (A, B), когда клиент A получает изменения от клиента B, потому что m (A, B) применяется к состоянию X, но A находится в состоянии A (X). Вместо этого мы должны вычислить A ’и B’ так, чтобы

Для простоты определим функцию follow f:

который строится по следующему алгоритму (для f (A, B)):

Вставки в A становятся сохраненными символами
Вставки в B становятся вставками
Сохраните все сохраненные символы как в A, так и в B

Пример

потом

Попробуйте теперь вычислить конечное состояние m (A, B) (X) после слияния.

5. Критика ОТ

Все изменения документа должны быть сохранены в наборе операций
Цитата из Википедии: реализация OT может быть очень сложной задачей:
Точно так же Джозеф Джентл, бывший инженер Google Wave и автор библиотеки Share.JS, написал: «К сожалению, реализация OT - отстой. Существует миллион алгоритмов с различными компромиссами, в основном изучаемых в научных статьях. Алгоритмы действительно сложны и требуют времени для правильной реализации. […] На написание волны ушло 2 года, и если бы мы переписали ее сегодня, на то, чтобы написать второй раз, потребовалось бы почти столько же времени ».