Logoot CRDT:将并发编辑的数据交错到同一位置？

Question

我想实现Logoot最终收敛的P2P文本编辑,我遇到了一些问题.

我对Logoot的理解是,对象之间的间隔(原始文件中的文本行,但可以是字符或单词)可以根据无界标识符无限划分.这意味着对象的位置不是由其邻居确定的,如在WOOT中(这将需要墓碑),而是由沿着字符串长度的固定数字点确定.结合唯一的站点标识符,这也为我们提供了一个总订单,并实现了最终的融合.

但是......当对同一个点进行并发编辑时,这不会导致问题吗？如果两个断开连接的客户端开始在相同的光标位置写入新的句子然后合并,则他们的句子很有可能进行交错.

下面是我正在谈论的白板示例:

如您所见,站点B和站点C根据Logoot的规则划分"I"和"conquered"之间的间隔,给出了(20,A)和(25,A)位置之间的随机点.但是没有任何东西相对于彼此命令这些点,导致它们在合并时混合.同时,基于邻居的算法可以解决这个问题,因为保留了每个对象的因果链.

以上是一个婴儿示例,但在更一般的情况下,想象一下,如果两个用户想要在两个现有句子之间插入不同的句子.如果其中一个用户碰巧离线,他们不应该回到乱七八糟的混乱!显然,为了保持意图,一句话应该跟随另一句话.

我在阅读论文时遗漏了什么,或者这是Logoot的内在缺点？

(另外,为什么在算法中似乎没有使用记录的时钟值？本文甚至指出每个对象的标识符在没有时钟的情况下必然是唯一的.)

Answer 1

你是对的，这在 Logoot 和 LSEQ 中确实是一个异常现象。是否构成故意违法，取决于你对故意的定义是什么。对定义的扩展要求连续序列保持连续，除非它们被随意的后续操作分开，这将具有直观意义。

时钟是不必要的。最有可能的是，作者使用了（站点，时钟）对或 Lamport 时间戳作为他们的 UUID，而不符合惯例。一个站点永远不可能创建两个相同的位置，因此永远不需要比较时钟。（假设按顺序从站点接收消息，这对于 Logoot/LSEQ 的其他方面也是必需的。）