CRDT: 基于树的索引

Collaborative peer-to-peer applications sometimes need to operate on sequences of objects with a consistent order across all peers. For example, a peer-to-peer rich text editing application might need to sync the order in which blocks of text appear in a document.

协作式点对点应用有时需要在所有节点上保持对象序列的一致顺序。例如，点对点富文本编辑器可能需要同步文档中各文本块的顺序。

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. Compared to fractional indexing, tree-based indexing is more complicated but prevents interleaving of concurrently-inserted runs, which makes it appropriate for textual data. The algorithm presented here is similar to a well-known one called "RGA" but with reordering layered on top.

这里展示的算法只是其中一种实现，它属于 CRDT 家族，本文不再赘述。与 fractional indexing 相比，基于树的索引更复杂，但能防止并发插入序列的交错，因此适合文本数据。本文算法与著名的 "RGA" 类似，但额外支持重排序。

The algorithm:

算法：

• Each object is given a parent pointer which must point to an object that existed at the time the object was created.

  每个对象都有一个父指针，该指针必须指向对象创建时已存在的对象。

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

  插入对象时，把父指针设为插入点紧邻的前一个对象（若在开头则设为 null）。对象顺序通过前序树遍历确定，父节点排在子节点之前。

• To order children within a given parent, have each child store the number of children that the parent had at the original insertion time, then sort the children by these counts in descending order (using the object identifier as a tie-breaker). This way newer objects are sorted before older ones.

  要对某个父节点下的子节点排序，让每个子节点记录父节点在最初插入时的子节点数量，然后按这些计数的降序排序子节点（以对象标识符作为平局决胜）。这样，较新的对象会排在较旧对象之前。

You can use any conflict-resolution strategy for syncing the parent pointers and sorting counters to other peers. The demo below assigns each write a timestamp and uses last-writer-wins to resolve conflicts, with the identif...