CRDT: 分数排序

最后更新于

原文:«CRDT: Fractional Indexing» 原网站里还有精美的可视化效果。

CRDT 是一系列解决协作问题的算法,其中一个不可避免的问题就是:如何记录顺序,如何在发生顺序修改时表现正确。假设我们使用一个数组来记录一组数据的话:

var todos = ["hello", "world"];

在同步这个数据时,不可避免地要将这个数组发来发去,当数据量很大时显然不是一个优解。此时先别急着实现 CRDT 链表,我们可以让每个元素多记录一个特殊的数据用来排序,并且用这种方式的网络传输压力很小,下面就来看看。

首先,利用传统的 LWW (last-write-win) 算法,我们可以实现 CRDT Map,但这里面的元素不是有序的。接着,我们给每个元素添加一个字段表示它在数组中的位置。

var todos = {
  "1@1": { text: "hello", position: "?" },
  "1@2": { text: "world", position: "?" },
};

其中左边的 1@1 只是用来标记元素唯一的,它可以通过 client(本地随机id) + clock(自增整数) 的方式生成。右边的 position 是本文即将说明的技巧,有了它就可以轻松实现排序、有序元素间交换等行为。

position 的定义

我们定义 position 是一个从 0 到 1 的数,当出现新的元素要插到某个有序列中时,取其前后元素的 position,折半即可得到新元素的 position。当没有前元素时,认为它是 0,当没有后元素时,认为它是 1。

var todos = {
  "1@1": { text: "hello", position: 0.5 }, // 第一个元素,插入 0 ~ 1 的中间,取 0.5
  "1@2": { text: "world", position: 0.75 }, // 第二个元素,插入 0.5 ~ 1 的中间,取 0.75
};

直接二分取数的话,很快我们就会碰到浮点数的瓶颈:折半失效了!此时可以把它转成字符串,利用大整数的实现思路,实现一个无限精度的小数(或者称之为以 10 的指数为分母的分数)。

var todos = {
  "1@1": { text: "hello", position: "0.5" }, // 5/10
  "1@2": { text: "world", position: "0.75" }, // 75/100
};

冲突处理

上面这个技巧在多人协作时会有一个问题:如果两个人同时在一个位置插入了新节点,岂不是会产生两个一模一样的 position

首先我们肯定不能让排序的结果不对,我们可以用客户端本地生成的随机 id (也就是上面 todos 的 keys) 对这些节点的排序算法做兜底。

其次有一个简单的方法可以避免这种确定性冲突——引入不确定的随机数即可,每次不光是折半产生下标,并且我们故意往后多添加几位随机数。在十进制下,仅仅是多添加三个字节就可以达到 1000 种不同的后缀,而这么多人同时操作同一个有序列表的概率不大。

var todos = {
  "1@1": { text: "hello", position: "0.5123" }, // ~5/10
  "1@2": { text: "world", position: "0.75478" }, // ~75/100
};

当然,如果放宽 CRDT 的限制,引入中心服务器裁决的话,也可以让服务器帮冲突的节点挑选一个新位置。