Это второй пост, связанный с Оперативным преобразованием, алгоритмом совместного редактирования в реальном времени. Первый пост был Как работают совместные редакторы в реальном времени? [Оперативное преобразование] ».

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

Функция трансформации

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

По сути, существует два вида функций преобразования:

  • Преобразование включения: обозначается как IT (a, b), которое преобразует операцию a в другую операцию b таким образом, что влияние b эффективно учитывается.
  • Преобразование исключения: обозначается как ET (a, b), которое преобразует операцию a в другую операцию b таким образом, что влияние b фактически исключено.

Функции преобразования называются по-разному в разных системах OT, и некоторые составные функции преобразования могут объединять функции ИТ и ET в одной функции. Одна из статей, Анализ алгоритмов оперативного преобразования, действительно хороша и анализирует все различные системы ОТ.

Функция трансформации персонажей

Алгоритм функции преобразования символов (для поддержания согласованности) прост. Например, для пары посимвольных операций Ins[p, c] (для вставки символа c в позицию p) и Del[p] (для удаления символа в позиции p) четыре ИТ-функции, обозначенные как Tii, Tid, Tdi, Tdd, можно определить следующим образом:

Tii(Ins[p1,c1], Ins[p2, c2]) {
      if p1 < p2  or (p1 = p2 and u1 > u2) // breaking insert-tie using user identifiers (u1, u2)
            return Ins[p1, c1];  // e.g. 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]; // e.g. 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, c2]) {
      if p1 < p2 return Del[p1];  // e.g.  Tdi(Del[3], Ins[4, “b”]) = Del[3]
      else return Del[p1+1]; } // Tdi(Del[3], Ins[1, “b”]) = Del[4]
 
Tdd(Del[p1], Del[p2]) {
      if p1 < p2 return Del[p1]; // e.g.   Tdd(Del[3], Del[4]) = Del[3]
      else if p1 > p2 return Del[p1-1]; // Tdd(Del[3], Del[1]) = Del[2]
      else return I; } // breaking delete-tie using I (identity op)  Tdd(Del[3]. Del[3]) = I

Алгоритм функции строкового преобразования значительно сложнее, чем символьные операции, потому что:

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

Отменить связанное приложение

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

  • Один из них - это эффект отмены, который требует, чтобы при отмене операции O достигался эффект устранения эффекта O, но сохранялись эффекты других операций в документе. Другими словами, эффект отмены O должен transform преобразовать состояние документа в такое, в которое он перешел бы, если бы O никогда не выполнялся, но были выполнены другие операции. Этот эффект отмены согласуется с линейным эффектом отмены в однопользовательских средах редактирования, а также подходит для нелинейной отмены (например, «отмена любой операции в любое время») в многопользовательских и параллельных средах редактирования.
  • Другое - свойство отмены, которое требует, чтобы документ был восстановлен в любое предыдущее состояние путем отмены всех операций, выполненных после этого состояния, независимо от порядка, в котором эти операции были отменены. Это свойство требуется для обеспечения возможности «восстановления любого предыдущего состояния», что необходимо для решения отмены для поддержки восстановления после ошибок и альтернативного исследования.

Подход с подтверждением клиент-сервер

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

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

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

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

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

Комплексная операционная трансформация

Отличное руководство по сложному операционному преобразованию - Понимание и применение операционного преобразования Дэниела Спивака. Это необходимо прочитать, чтобы понять, как работает сложное операционное преобразование.

Заключение

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

Цитата со страницы Википедии:

В то время как классический подход ОТ к определению операций через их смещения в тексте кажется простым и естественным, в реальных распределенных системах возникают серьезные проблемы. А именно, эти операции распространяются с конечной скоростью, состояния участников часто различны, поэтому результирующие комбинации состояний и операций чрезвычайно трудно предвидеть и понимать. Как выразились Ли и Ли: «Из-за необходимости учитывать сложное покрытие случаев формальные доказательства очень сложны и подвержены ошибкам даже для алгоритмов ОТ, которые обрабатывают только два посимвольных примитива (вставка и удаление)».

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

Для работы OT необходимо фиксировать каждое изменение данных: «Получение снимка состояния обычно тривиально, но фиксирование изменений - это совсем другое дело. […] Богатство современных пользовательских интерфейсов может сделать это проблематичным, особенно в среде на основе браузера ». Альтернативой OT является дифференциальная синхронизация.

использованная литература

Я прочитал следующие документы и статьи, чтобы узнать об оперативной трансформации.