Два человека правят один документ офлайн. Изобретаем гугл-док без сервера-арбитра

В свободное время пишу на чистом Go порты CRDT-движков: Yjs с JavaScript и Loro с Rust. CRDT это структуры, на которых держится совместное редактирование, когда несколько человек правят одно и то же одновременно. Пока портировал, пришлось разобрать алгоритмы до байта, и оказалось, что главный фокус там объясняется на пальцах, без формул. Эта статья про него: как два человека правят текст в разных местах, офлайн, а потом копии сходятся в одну и ту же строку. Символ в символ, без сервера, который решает, кто прав.

Все видели чужой курсор, бегающий по гугл-доку. Ощущение простоты обманчивое: гугл-док работает потому, что в центре сидит сервер, который получает правки от всех и выстраивает их в один порядок. Кто первым долетел, тот и первый. Пересчёт чужой правки под уже применённые изменения называется operational transformation, и занимаются им обе стороны. Но порядок в этой схеме назначает сервер, и без него она не работает.

А теперь отберите сервер. Два телефона в метро без сети, оба правят одну заметку, через полчаса выходят наверх и синхронизируются напрямую друг с другом. Порядок никто не назначал. У каждого своя история правок, и надо, чтобы после обмена оба пришли к одинаковому тексту. Не к похожему, к одинаковому. Вот это и решают CRDT, conflict-free replicated data types: структуры, устроенные так, что реплики сходятся сами, когда получили одни и те же изменения. Конкурентные правки при этом можно применять в любом порядке. Совсем без порядка не обходится, зависимую правку движок придержит, пока не приедет та, на которую она ссылается, но глобального арбитра не нужно.

Звучит как магия. Для текстовых CRDT, которые я разбирал, всё начинается с одного сдвига в голове, и он про адресацию.

Почему индексы не работают

Наивная правка выглядит как «вставить букву в позицию 5». Беда в том, что позиция 5 у меня и позиция 5 у вас это разные места, если кто-то из нас уже вставил что-то левее. Я добавил букву в начало, у меня всё сдвинулось на единицу, и ваша правка «в позицию 5» попадает не туда, куда вы целились. Один сдвиг, и документы разъехались.

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

У каждой буквы есть имя

Решение выглядит почти нагло. Каждому вставленному символу выдаётся уникальный и вечный идентификатор: обычно пара из номера клиента и счётчика, вроде «элемент клиента 7 со счётчиком 42». Счётчик у каждого свой и только растёт, причём считает он вставленные элементы: слово из трёх букв съедает три значения. Номера клиентов обязаны быть разными, и тогда два клиента никогда не выдадут одинаковое имя, сговариваться им не надо.

Вставка после этого перестаёт быть «в позицию 5» и становится «после буквы 7:42». Я вставляю не в индекс, а справа от конкретного символа, у которого есть имя. Имя не сдвигается, что бы кто ни писал левее, так что ссылка продолжит указывать на тот же символ на любой копии и при любом порядке доставки.

Остаётся дырка. Что если мы оба вставили «после 7:42», не зная друг о друге: у меня там буква А, у вас Б. Обе правки законные, обе ссылаются на одного соседа. Тут помогает правило, о котором договорились заранее и которое не требует связи: при прочих равных первым идёт тот, у кого номер клиента меньше. В такой ничьей вставка клиента 3 встанет раньше, и обе при этом сохранятся. Правило тупое, зато детерминированное, и у каждой копии на руках одна и та же информация для его применения. Значит, все решат спор одинаково, ни с кем не советуясь.

Так устроена адаптация алгоритма YATA внутри Yjs. В Loro последовательность упорядочена другим алгоритмом того же класса, он называется Fugue и при слиянии тоже опирается на имена элементов.

Когда правило ломает слова

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

Ломается оно на случаях похитрее, и у поломки есть имя, интерливинг. Представьте, что мы оба офлайн вставили в одно место не по букве, а по слову: я «привет», вы «мир». Если алгоритм разрешает спор побуквенно и ничего не знает о том, что буквы шли подряд, на выходе можно получить «пмрииврет». Каждая отдельная пара разрешена по честному правилу, а читать это невозможно.

Лечится это тем, что вставка помнит не только левого соседа, но и правого на момент вставки. YATA держит для этого пару origin и right origin у каждого элемента, и правила обхода не дают чужой последовательности вклиниться в середину моей. Полностью класс проблемы так не закрывается, и более поздние алгоритмы вроде Fugue целятся ровно в него.

Удаление, которого нет

Дальше начинается то, из-за чего я вообще полез в исходники.

Раз у каждой буквы есть имя и на неё ссылаются соседи, её нельзя просто удалить. Я стёр букву 7:42, а вы в это время офлайн вставили «после 7:42». Ваша правка ссылается на то, чего у меня уже нет, и поставить её некуда.

Поэтому удаление тут логическое. Символ помечается мёртвым и перестаёт показываться, а от него остаётся ровно столько, чтобы поздняя ссылка на него не повисла в воздухе. Такие пометки называют tombstone, надгробие.

Цена видна сразу: за каждым удалением тянется хвост метаданных. Движки с этим борются. Сборщик мусора выбрасывает содержимое мёртвых символов и оставляет только то, что нужно для адресации, подряд идущие удаления схлопываются в диапазон, а совместимые живые символы пакуются в блок. Тогда отдельное имя на каждую букву хранить не нужно, оно вычисляется из начала блока и смещения.

У меня был период, когда мой порт Yjs этого не делал и хранил каждое нажатие клавиши отдельным блоком. Я прогнал через порт и через оригинальный движок одну и ту же реальную историю набора статьи, четверть миллиона правок. Оригинал выдал около 160 килобайт, мой порт 1,97 мегабайта. Тексты при этом совпадали идеально, символ в символ, вся разница сидела в упаковке.

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

Чего это стоит и когда не надо

CRDT гарантируют сходимость, а не смысл. Если я выделил слово жирным, а вы это слово одновременно стёрли, копии сойдутся, но во что именно, решит правило. Два человека, правящие одно предложение с разных концов, получат текст, которого не хотел ни один из них. Конфликт позиций алгоритм разруливает, конфликт намерений он не видит и не обещал.

И я бы не тащил CRDT туда, где сервер всё равно обязателен. Если все правки и так идут через ваш бэкенд, центральный порядок проще в отладке, а метаданные CRDT это реальные байты, за которые кто-то платит. Оговорюсь честно: это мой выбор под мои требования, а не измеренное сравнение. Контраргумент приму такой: если копии обязаны сходиться напрямую друг с другом, не обращаясь к серверу, то назначать порядок некому по условию задачи, и тогда всё описанное выше оправдано.

Я долго думал, что внутри там что-то страшное. Оказалось, сложность не в выборе порядка, она в бухгалтерии вокруг имён, которые нельзя терять.