Как Google Docs справляется с редактированием коллизий?

Question

Я возился с написанием своего собственного редактора Javascript с функциональностью, аналогичной Google Docs (позволяющей работать над ней одновременно нескольким людям). Одна вещь, которую я не понимаю:

Допустим, у вас есть пользователь A и пользователь B, подключенные напрямую друг к другу с задержкой в ​​сети 10 мс. Я предполагаю, что редактор использует систему сравнения (как я понимаю, это делает Docs), где правки представлены как "вставка" текста "в индекс 3", и что различия имеют временную метку и вынуждены применять хронологически всеми клиентами.

Начнем с документа, содержащего текст: "xyz123"

Пользователь A вводит "abc" в начале документа на отметке времени 001ms, а пользователь B вводит "hello" между "xyz" и "123" на отметке времени 005ms.

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

• Пользователь B получит правки пользователя "вставьте abc" с индексом 0"в момент времени 011 мс. Чтобы сохранить хронологический порядок, пользователь B отменяет вставку пользователя B в индекс 3, вставляет "abc" пользователя A в индекс 0, а затем повторно вставляет вставку пользователя B в индекс 3, который теперь находится между "abc" и "xyz"., таким образом давая "abchelloxyz123"
• Пользователь A получит от пользователя B правки "insert 'hello' at index 3" в момент времени 015ms. Он распознал бы, что вставка пользователем B была выполнена после пользователя A, и просто вставил "hello" в индекс 3 (теперь между "abc" и "xyz"), давая "abchelloxyz123"

Конечно, "abchello xyz123" - это не то же самое, что "abc xyzhello123"

Кроме буквального присвоения каждому персонажу собственного уникального идентификатора, я не могу представить, как Google сможет эффективно решить эту проблему.

Некоторые возможности, о которых я подумал:

• Отслеживание точек вставки вместо отправки индексов с помощью различий будет работать, за исключением того, что у вас будет точно такая же проблема, если пользователь B переместит свою точку вставки за 1 мс до редактирования.
• Вы могли бы, чтобы пользователь B отправлял некоторую информацию с помощью своей разницы, например "вставка после" xyz "", чтобы пользователь A мог разумно распознать, что это произошло, но что если пользователь A вставит текст "xyz?"
• Пользователь B может распознать, что это произошло (когда он получает разность пользователя A и видит, что это конфликт), а затем отправить отсылку изменения, отменяющего правки пользователя B, и новую разность, которая дополнительно добавляет индекс "hello" "abc".length пользователя B право. Проблема с этим заключается в том, что (1) пользователь A увидит "скачок" в тексте и (2) если пользователь A продолжит редактирование, тогда пользователю B придется постоянно исправлять свои различия - даже изменения "fixer" будут отключены и потребуется исправить, экспоненциально увеличивая сложность.
• Пользователь B может отправить вместе со своим свойством diff, что последняя полученная им разность с меткой времени была -005ms или что-то в этом роде, тогда A мог бы распознать, что B не знал о его изменениях (поскольку diff для A был в 001ms), и затем разрешить конфликт. Проблема заключается в том, что (1) временные метки для всех пользователей будут слегка отключены, учитывая, что большинство часов компьютера не являются точными с точностью до мс, и (2) если есть третий пользователь C с задержкой в ​​25 мс с пользователем A, но с задержкой в ​​2 мс с пользователем B, и пользователь C добавляет текст между "x" и "y" в -003 мс, тогда пользователь B будет использовать редактирование пользователя C в качестве контрольной точки, но пользователь A не будет знать о редактировании пользователя C (и, следовательно, контрольной точки пользователя B) до 22 мс. Я считаю, что это можно решить, если вы используете общий сервер для отметки времени всех изменений, но это кажется довольно сложным.
• Вы можете присвоить каждому персонажу уникальный идентификатор, а затем отработать эти идентификаторы вместо индексов, но это кажется излишним...

Я читаю через http://www.waveprotocol.org/whitepapers/operational-transform, но хотел бы услышать любые и все подходы к решению этой проблемы.

Answer 1

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

Использование центрального сервера

Наиболее распространенный сценарий - это центральный сервер, с которым должны общаться все клиенты.

Сервер может отслеживать, как выглядит документ каждого участника. Затем A и B отправляют diff с их изменениями на сервер. Затем сервер применяет изменения к соответствующим документам отслеживания. Затем он выполнит трехстороннее объединение и применит изменения к основному документу. Затем он отправит разницу между основным документом и документами отслеживания соответствующим клиентам. Это называется дифференциальной синхронизацией.

Другой подход называется преобразованием операции (al), которое похоже на перебазирование в традиционных системах контроля версий. Для него не требуется центральный сервер, но его наличие значительно упрощает работу, если у вас более двух участников (см. Часто задаваемые вопросы OT). Суть в том, что вы преобразуете изменения в одном редактировании, так что редактирование предполагает, что изменения другого редактирования уже произошли. Например, А преобразовал бы редактирование Б insert(3, hello) против его редактирования insert(0, abc) с результатом insert(6, hello),

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

Нет центрального сервера

Существуют OT-алгоритмы, которые могут работать с одноранговыми сценариями (с компромиссом из-за повышенной сложности реализации на уровне управления и увеличения использования памяти). Вместо простой метки времени вектор Version может использоваться для отслеживания состояния, на котором основано редактирование. Затем (в зависимости от возможностей вашего алгоритма OT, в частности, свойства transform 2), входящие правки можно преобразовать так, чтобы они соответствовали порядку их получения, или вектор версии можно использовать для наложения частичного порядка на правки - в этом история болезни должна быть "переписана" путем отмены и преобразования правок, чтобы они соответствовали порядку, установленному векторами версий.

Наконец, есть группа алгоритмов, называемых CRDT, WOOT, treedoc и logoot, которые пытаются решить проблему с помощью специально разработанных типов данных, которые позволяют операциям коммутировать, поэтому порядок их применения не имеет значения (это похоже к вашей идее идентификатора для каждого персонажа). Компромиссами здесь являются потребление памяти и накладные расходы при построении операций.