Комментарии 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», а у Боба после
Тут есть два варинта ввода:
- Вставить пробел, набрать слово. В этом случае была бага, я её пофиксил. Сейчас должно быть всё ок. Спасибо за тесткейс.
- Набрать слово, потом пробел. Тут сложнее, так как фактически сначала изменяется слово, а потом оно разрывается на два. Причём исходный идентификатор остаётся за первой половиной, а для второй генерится новый. Хз, что тут можно придумать без костылей в духе "буферизируем ввод, пока каретка не покинет слово или оно не будет разорвано".
Неочевидные сложности CRDT