Logoot CRDT: чередование данных о параллельных изменениях в одном месте?
Я хочу реализовать Logoot для в конечном счете конвергентного редактирования текста P2P, и я столкнулся с небольшой проблемой.
Насколько я понимаю, Логотип состоит в том, что интервалы между объектами (строки текста в оригинальной статье, но могут быть символами или словами) могут быть разделены бесконечно из-за неограниченного идентификатора. Это означает, что положение объекта определяется не его соседями, как в WOOT (для этого потребуются надгробия), а фиксированной числовой точкой по длине строки. В сочетании с уникальным идентификатором сайта это также дает нам полный заказ и обеспечивает возможность конвергенции.
Однако... не вызывает ли это проблемы, когда одновременные правки производятся в одном месте? Если два отключенных клиента начинают писать новые предложения в одной и той же позиции курсора, а затем объединяются, их предложения имеют хороший шанс чередования.
Ниже приведен пример того, о чем я говорю на доске:
Как вы можете видеть, и сайт B, и сайт C делят интервал между "I" и "завоеванным" согласно правилам Logoot, давая нам случайные точки между позициями (20,A) и (25,A). Но ничто не упорядочивает эти точки относительно друг друга, заставляя их смешиваться при объединении. Между тем, основанные на соседях алгоритмы могут объяснить эту проблему, поскольку цепочка причинности каждого объекта сохраняется.
Вышеприведенный пример является детским, но в более общем случае представьте, если два пользователя хотят вставить разные предложения между двумя существующими предложениями. Если один из пользователей оказался в автономном режиме, ему не следует возвращаться к искаженному беспорядку! Очевидно, что для сохранения намерения одно предложение должно следовать за другим.
Я что-то упускаю при чтении газеты или это неотъемлемая сторона логотипа?
(Кроме того, почему существует записанное значение часов, которое, по-видимому, не используется в алгоритме? В документе даже указывается, что идентификатор каждого объекта обязательно уникален без часов.)
1 ответ
Вы правы, это настоящая аномалия в Logoot и LSEQ. Является ли оно намеренным нарушением, зависит от того, каково ваше определение намерения. Расширение определения, требующее, чтобы смежные последовательности оставались смежными, если только они не были разделены случайно последующей операцией, имело бы интуитивный смысл.
Часы не нужны. Скорее всего, авторы использовали пару (сайт, часы) или метку времени Лампорта в качестве своих UUID вне соглашения. Один сайт никогда не сможет создать две одинаковые позиции, поэтому часы никогда не нужно будет сравнивать. (Предполагается, что сообщения поступают с сайта по порядку, что необходимо и для других аспектов Logoot/LSEQ.)