Как стать автором
Обновить

Комментарии 5

Большинство алгоритмов операционального преобразования исходят из предположения о том, что все взаимодействия выполняются через единый сервер.

На самом деле CRDT тоже в большинстве случаев работает через сервер, а не напрямую между пирами. По разным причинам:


  • проще проверять права (на клиенте для этого надо подписывать каждое изменение)
  • проще обеспечить отзывчивость (сервер может батчить апдейты, из-за одного тормозного клиента остальные не тупят)
  • меньше нагрузка на сеть (послать на сервер горядо дешевле, чем послать всем пирам… и на сервер)

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

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


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

Далее Мартин описывает алгоритм ОТ, где все операции строго упорядочены, и чтобы внести изменение приходится откатывать/накатывать историю. То есть это по факту уже не CRDT. Основная проблема OT в том, что время наложения патча перестаёт быть константным и начинает зависеть от размера пропущенной истории. И это помимо того, что всю эту историю придётся хранить целиком.


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


  • Нет проблем со смешиванием текста, введённого параллельно в одной и той же позиции. (запоминается какие узлы должны быть до данного)
  • Нет проблем с перемещением элементов, даже если пользователь использует операции "вырезать" и "вставить". (раздельное хранение списка идентификаторов токенов и их значений)
  • Нет проблем с параллельным перемещением блоков текста и их изменением. (каждый блок — отдельный узел дерева)
  • Нет проблем с перемещением деревьев. (циклы могут образовываться, но при "отображении" выбирается лишь один из вариантов)
  • Нет проблем с соотношением данные/метаданные. (метаданные имеют фиксированный размер и хранятся для токенов, которые хранят уже не 1, а в среднем 10 байт данных, что сопоставимо с объёмом метаданных)

Кроме того, там нет и ряда проблем, не упомянутых в статье, но наблюдающихся во многих алгоритмах:


  • Параллельные разные изменения одного слова не приводят к белиберде. (текст разбивается на токены, каждое слово — отдельный токен с атомарным значением)
  • История не раздувает хранимый объём данных. (она просто не хранится)

Тем не менее остаются открытыми следующие проблемы:


  • Хранимый объём раздувается из-за "надгробий" (идентификаторы и метки удалённых узлов).
  • Дельты могут быть увесистыми, ибо содержат полный список. Впрочем, в обычном тексте списки узлов не превышают нескольких сотен.

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


И это, кстати, отдельная проблема с такими алгоритмами — им нужен специальный редактор, чтобы они работали хорошо. Более того, тут нужна ещё и специальная субд, чтобы она умела строить индексы по conflict-free представлениям данных.

Спасибо за подробный комментарий, интересно.

Но когда в вашей песочнице попробовал от Алисы и Боба в одном месте одной строки («in the middle of it i will write two things») вставить два разных слова («first» и «second») и нажать «sync», возникли следующие не упомянутые вами проблемы:

  • Слово «second» просто пропало
  • У слова «i» появилась лишняя копия
  • Порядок слов оказался разным: у Алисы первая «i» идёт до «first», а у Боба после


Тут есть два варинта ввода:


  1. Вставить пробел, набрать слово. В этом случае была бага, я её пофиксил. Сейчас должно быть всё ок. Спасибо за тесткейс.
  2. Набрать слово, потом пробел. Тут сложнее, так как фактически сначала изменяется слово, а потом оно разрывается на два. Причём исходный идентификатор остаётся за первой половиной, а для второй генерится новый. Хз, что тут можно придумать без костылей в духе "буферизируем ввод, пока каретка не покинет слово или оно не будет разорвано".

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

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