本文介绍了一种用于协同编辑文本的CRDT算法，适用于点对点应用如笔记软件。该算法为每个字符分配唯一标识符，包括创建者标识符和操作计数器，并通过父指针确定字符顺序。插入字符时，父指针指向插入点前的字符，确保字符顺序一致。文章还提供了交互式可视化，帮助理解算法内部机制。

CRDT文本缓冲区算法解析

在点对点应用中，协同编辑文本字符串是一个常见的需求。例如，笔记应用可能将每个文档表示为可协同编辑的文本字符串。本文介绍了一种实现这一目标的方法，该算法属于CRDT（无冲突复制数据类型）家族，与Yjs和Automerge等流行的协同文本编辑库采用的方法类似。

算法核心：

1. 字符标识：每个字符都有一个唯一的标识符，包括site（创建者标识符）和clock（每次操作后递增的站点特定整数），以及一个可能为空的parent指针，指向前一个字符。

2. 插入字符：插入字符时，将其parent指针设置为插入点前的字符（或在开头插入时为null）。字符顺序通过前序遍历树来确定，父节点先于子节点。这被称为基于树的索引。

3. 排序字符：对于具有相同父节点的字符，每个字符还存储一个counter值，首先按counter降序排序，然后按字符的site排序。在具有相同父节点的字符前插入时，使用其counter加1的值进行排序。

4. 删除字符：删除字符时，将其标识符放入删除集合中。这意味着删除的字符会永久保留，这在CRDT文献中被称为“墓碑”。删除的字符值可以被遗忘，但必须记住其位置，以便正确排序使用已删除字符作为父节点的传入更改。

优化措施：

1. 合并插入：来自同一站点的连续插入可以合并为内存中的单个块，例如粘贴大段文本与插入单个字符使用相同数量的元数据。

2. 连续存储：这些内存块可以连续存储在单个预排序的数组中，插入新块只需在正确位置插入到数组中。

3. 范围删除：删除集合可以使用基于范围的表示法更高效地表示，具有相同site和连续clock值的删除可以用单个范围表示。

优缺点：

优点： - 内存使用：跟踪协同编辑的元数据开销合理，且可能压缩良好。 - 性能：使用二叉树或二分查找数组，大多数查询和更新操作可以在O(log n)时间内完成。

缺点： - 复杂性：拆分和合并的逻辑复杂，难以正确实现，模糊测试可能是必要的。 - 只增不删：删除数据不会减少元数据的大小，解决这一问题非常具有挑战性。

参考资料： - Josephg的博客：讨论了如何高效实现基于文本的CRDT。 - Archagon的博客：深入探讨了基于树的索引。 - Bartosz Sypytkowski的博客：详细介绍了Yjs的内部结构。 - Ink & Switch的Peritext：讨论了在协同环境中处理富文本的算法。

评论1（作者：josephg）主要讨论了RGA（Replicated Growable Array）算法的优缺点，并推荐了FugueMax作为改进方案。

主要观点和论据：

1. RGA的优点：RGA是一种在实践中表现良好的列表和文本CRDT（冲突自由复制数据类型），曾被Automerge用于文本编辑。

   • "This is a pretty good description of RGA (Replicated Growable Array). Which is a list & text CRDT that works pretty well in practice."
   • "RGA是一种在实践中表现良好的列表和文本CRDT。"

2. RGA的缺点：RGA在反向插入时存在交错问题，导致插入顺序不可预测。

   • "It has interleaving problems if you insert items backwards."
   • "RGA在反向插入时存在交错问题。"

3. FugueMax的改进：FugueMax通过使用“右父指针”解决了RGA的交错问题，且实现简单。

   • "This problem is fixed by FugueMax, described in 'The Art of the Fugue' paper."
   • "FugueMax通过使用‘右父指针’解决了RGA的交错问题。"

4. 实现建议：作者建议从FugueMax开始实现文本CRDT，并提供了简单的参考实现。

   • "If you're thinking of implementing a text CRDT, I recommend starting there."
   • "作者建议从FugueMax开始实现文本CRDT。"

总结：评论1认为RGA虽然有效，但在特定情况下存在缺陷，而FugueMax提供了更优的解决方案，且实现简单。