CRDT 协同编辑：如何确定操作时序？

大家好，我是前端西瓜哥。

CRDT 协同编辑中，我们经常会使用 Last-Writer-Win 的策略解决冲突。即对于多个冲突的操作，哪个操作是最后修改的，就应用哪个操作。

于是这里就有一个问题，我们应该基于什么去做判断先后顺序？

服务端时间

开发普通 Web 应用的时候，我们不用考虑客户端状态是否同步，只需维护好服务端的一份数据，晚到达的写操作会覆盖掉旧数据，可以视为基于 请求到达服务器时间戳 的比较。

这在协同编辑的场景中能用吗？

不太行。

这种方案需要一个服务器，所以就无法支持去中心化的 P2P 协同编辑（不经过服务器，用户直接向用户发送数据）。

假设可以提供中心服务，如果有客户端 A 在离线的状态下进行编辑，在很长一段时间后才重连同步。到他再次重连的这段期间，其他客户端可能进行了操作。

最后客户端 A 重连服务器并进行同步，客户端 A 的操作最早，但优先级却最高，覆盖掉了其他客户端的编辑，这并不合理。

客户端时间

既然要考虑离线的情况，那我们转换一下思路，使用客户端时间戳如何？

我们在操作生成的那一刻，把当前客户端时间也加上，这样同步后就能知道操作的先后顺序了。

理论上是可以的，但有 准确性问题：客户端的物理时钟无法同步一致。

尤其是有些客户端的系统时间错得离谱，比如比真实时间晚一分钟或晚好几天。

如果客户端是可管理，比如分布式系统的节点，我们可以通过 NTP 时间同步服务进行时间校准，误差在 100 ms 以内，如果是局域网会小很多。此外还可以使用更高精度的时钟硬件。

当然我们这里讨论的是协同编辑，客户端是不可控的，就不发散思考了。

不同步的客户端时间戳会导致因果错乱的问题。

比如客户端 A 创建一个对象，同步给客户端 B，然后 B 将其删除。这两个操作是不能颠倒过来的。

但在使用客户端时间戳的场景下是可能发生的：在客户端 A 的系统时间比客户端 B 的系统时间晚一些，那创建操作的时间戳就可能会比删除操作晚一点。

客户端的物理时钟不可靠，我们需要另一种时钟：逻辑时钟。

逻辑时钟

逻辑时钟是人为定义的递增序列，只要能表示两个操作的先后顺序即可。

对于协同编辑，我们通常会选择 Lamport 逻辑时钟算法。

对客户端 A，初始化时会有一个全局的逻辑时钟 clockID，通常我们选择从某个数字开始。

客户端 A 的每进行一个操作 operation，clockID 加一，然后保存到对应的 operation 操作对象上：

let clockID = 0;
let sessionID = 3;

const op = {
  id: {
    sessionID: sessionID, 
    clockID: ++clockID,
  }
  // ...
}

这里还要保存当前客户端的唯一 ID，后面再说有什么用。

当要将操作同步给其他客户端 B 时，生成一个专门的 “发送消息操作对象”，带上本地的 clockID。

操作到达客户端 B 后，此时将本地逻辑时钟更新为 clockID（A） 和 clockID（B） 的最大值，然后加一，这里的目的是对齐，确保之后操作的发生时间都大于 clockID（A） 以及本地的 clockID（B）。

接着就是生成专门的 “接收消息操作对象”。

大概如上所示。

上面这些节点的存在偏序关系，即部分有序。

比如客户端 A 创建的递增节点，

A:0 -> A:1 -> A:2 -> A:3

以及客户端 B 创建的递增节点：

B:0 -> B:1 -> B:2 -> B:3 -> B:4

还有同步前节点到同步节点。

A:0 -> A:1 -> A:2 -> B:3 -> B:4

这些节点之间的因果关系是明确的，但对于 A0 和 B0，A1 和 B0 这些无法确认因果关系的节点，我们认为它们是 并发关系。

并发关系的话，可以理解两个平行时空发生的两件事，谁先发生谁后发生并不重要，但我们要 找到一个方式给它们排个序，让偏序变成全序（完全有序），这样才能让所有客户端的最终结果是一致的。

所以对于所有节点，我们这样排序：

clockID 小的先发生，如果 clockID 相同，sessionID 小的先发生。

这里不一定要 sessionID 小的先发生，大的也可以，只要确保比较结果一致且满足传递性。

于是同步后节点的操作顺序是：

至此，操作顺序就确定好了，且符合最终一致性原则。

结尾

我是前端西瓜哥，关注我，学习更多协同编辑知识。