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 photo album application might need to sync the order in which photos appear in an album.

协作式点对点应用有时需要在所有 peer 之间对对象序列保持一致的顺序。例如，点对点相册应用可能需要同步照片在相册中的显示顺序。

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. Unlike my original article about this technique, the algorithm presented here uses random offsets to avoid requiring a central server, and works in true peer-to-peer scenarios. Compared to tree-based indexing, fractional indexing is simpler but doesn't prevent interleaving of concurrently-inserted runs, which makes it inappropriate for textual data.

这里介绍的算法是实现此目的的一种方式。它来自一类称为 CRDTs 的算法家族，本文不会详细描述。与 我最初关于此技术的文章 不同，这里介绍的算法使用随机偏移量来避免需要中央服务器，并可在真正的点对点场景中工作。与 基于树的索引 相比，分数索引更简单，但无法防止并发插入序列的交错，因此不适用于文本数据。

The algorithm:

算法：

• Each object is given a fractional position between 0 and 1 (exclusive). The object order is determined by sorting the objects by their positions (using object id as a tie-breaker).

  每个对象被赋予一个介于 0 和 1（不含）之间的分数位置。对象顺序通过按位置排序对象来确定（位置相同时使用对象 id 作为平局决胜）。

• To insert an object between two other objects, set its position to a fraction in between the two other objects' positions. To insert before any other object, substitute 0 for the first object's position. To insert after before any other object, substitute 1 for the second object's position.

  若要在两个对象之间插入一个对象，将其位置设为这两个对象位置之间的一个分数。若要在任何其他对象之前插入，将第一个对象的位置替换为 0。若要在任何其他对象之后插入，将第二个对象的位置替换为 1。

• To prevent two peers from generating the same fraction (with high probability), add a random offset to the end of the fraction during each insert operation.

  为防止两个 peer 以高概率生成相同的分数，在每次插入操作时为分数末尾添加一个随机偏移量。

You can use any conflict-resolution strategy for syncing the fractional positions to other peers. The demo below assigns each write a timesta...