Logoot CRDT：在同时编辑同一位置时交错数据的算法？

Question

Logoot CRDT：在同时编辑同一位置时交错数据的算法？

algorithmconcurrencytext-editorconvergencecrdt

12

我想要实现Logoot，以实现最终收敛的P2P文本编辑。但是我遇到了一些问题。我对Logoot的理解是，对象（原始论文中的文本行，但可以是字符或单词）之间的间隔可以由于无限的标识符而被无限地分割。这意味着对象的位置不是像WOOT那样由其邻居确定（这将需要墓碑），而是由沿字符串长度的固定数值点确定。结合唯一的站点标识符，这也为我们提供了一个总顺序，并启用了最终收敛。但是...当在同一位置进行并发编辑时，这不会引起问题吗？如果两个断开的客户端从同一光标位置开始编写新句子，然后合并，它们的句子有很大机会交错。下面是我所说的内容的白板示例：

如您所见，站点B和站点C都按照Logoot的规则划分“I”和“conquered”之间的间隔，给出了在（20，A）和（25，A）位置之间的随机点。但是没有任何东西将这些点相对排序，导致它们在合并时混合在一起。与此同时，基于邻居的算法可以解决这个问题，因为每个对象的因果链是被保留的。

以上只是一个简单的例子，但在更普遍的情况下，想象一下如果两个用户想要在现有的两个句子之间插入不同的句子。如果其中一个用户离线，他们不应该回来看到一堆乱码！显然，为了保持意图，一个句子应该跟随另一个句子。

我在阅读论文时是否漏掉了什么，还是这是Logoot的固有缺陷？

（此外，为什么算法中似乎没有使用记录的时钟值？论文甚至指出，每个对象的标识符在没有时钟的情况下必然是唯一的。）

- Archagon

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- t-mullen · Accepted Answer

你说得对，这是Logoot和LSEQ中的一个真正的异常情况。它是否构成了意图违规取决于你对意图的定义。将连续序列保持连续除非它们被随后的操作分割的定义扩展，会更加直观。

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