CRDT: 文本缓冲区

Collaboratively editing strings of text is a common desire in peer-to-peer applications. For example, a note-taking app might represent each document as a single collaboratively-edited string of text.

在点对点应用中，协同编辑文本字符串是常见需求。例如，一个笔记应用可能将每个文档表示为一个可协同编辑的文本字符串。

The algorithm presented here is one way to do this. It comes from a family of algorithms called CRDTs, which I will not describe here. It's similar to the approaches taken by popular collaborative text editing libraries such as Yjs and Automerge. Other articles have already been written about these similar approaches (see the references section below), but this article also has a nice interactive visualization of what goes on under the hood.

这里展示的算法只是实现这一目标的一种方式。它来自一个名为 CRDTs 的算法家族，本文不会对其进行详细说明。它与 Yjs 和 Automerge 等流行协同文本编辑库所采用的方法类似。已有其他文章介绍了这些类似方法（见下方 参考文献），但本文还提供了一个不错的交互式可视化，展示其内部运作过程。

The algorithm:

算法：

• Each character is assigned a unique identifier consisting of site (the identifier of the creator) and clock (a site-specific integer that is incremented after every operation) as well as a (possibly null) parent pointer to a previous character.

  每个字符被分配一个唯一标识符，由 site（创建者标识符）和 clock（站点自增整数，每次操作后加 1）组成，并带有一个（可能为 null 的）parent 指针指向前一个字符。

• To insert a character, set its parent pointer to the character immediately before the insertion point at the time of insertion (or to null when inserting at the beginning). The character order is determined by a pre-order tree traversal that places parents before their children. This is tree-based indexing.

  插入字符时，将其 parent 指针指向插入时刻插入点之前紧邻的字符（若在开头插入则指向 null）。字符顺序通过前序树遍历确定，父节点排在子节点之前。这就是 基于树的索引。

• To order characters with the same parent, have each character also store a counter value and sort first by counter (use descending order), then by the site of the character (use arbitrary but consistent order). When inserting before a character with the same parent, use its counter incremented by 1 to be ordered before it. This order is unique because doi...