如何使用CRDT实现一个简单的多人文本协同应用

这篇博客将简要介绍CRDTs（Conflict-free Replicated Data Types）的基本概念以及从开发者的角度着重介绍简单的 CRDTs 的实现流程与细节（基于RGA 算法），并且基于这些知识点实现一个 rust+wasm 的简单 web 文本协作 demo。

实现思路参考了 crdt-edit1

什么是 CRDTs

对于 CRDTs 可以优先通过看[CRDT 简介]2、[CRDT 原理]3这些文章了解。

CRDTs 是近些年开始备受关注的一种用来处理分布式系统上的协同可用性的数据结构。它在可用性与分区容错性的基础上，不提供完美的一致性而是提供强最终一致性。下面的例子可以帮助我们理解什么是强最终一致性。

比如当前有Alice和Bob两个同学在各自的电脑上共同编辑同一份文档，Alice 写入了Hello CRDT，Bob 写入了Hello crdt。

Loading graph...

    flowchart TB
    subgraph Bob
    id2[Hello crdt];
    end;
    subgraph Alice
    id1[Hello CRDT];
    end;

但在此时 Alice 其实并没有办法知晓 Bob 可能在同一时刻也写入了Hello crdt的文本，并不像真正本地那样，完全意义上的在编辑同一份文件（一致性）。

只有当他们进行了一次同步通信后，Alice 或者 Bob 才会知晓对方编辑了什么。crdt 所提供的 强最终一致性 意义并不是让多人协同真正地像大家就在同一页纸上写字一样，而是大家可以各自地编辑自己的内容，尽管在多次同步的过程中会产生冲突，但 crdt 可以保证所有的消息都被接收后，最终的内容将会是多方一致的，哪怕可能最终冲突解决后的版本并不是真正所期待的结果。

Loading graph...

  flowchart TB
    subgraph Editor
    id1-->id3
    id2-->id4
    direction TB %% 子图1方向
        subgraph Alice
            direction TB
            id1[Hello CRDT];
            id1---id4((多次同步));
        end
        subgraph Bob
            direction TB
            id2[Hello crdt];
            id2---id3((多次同步));
        end

    end

    subgraph Result
    direction TB %% 子图2方向
    idn[结果]
    idn--?---id5[Hello crdt];
    idn--?---id6[Hello CRDTHellocrdt];
    idn--?---id7[Hello CRDTcrdt];
    end

  %% 主图
  id3-->idn
  id4-->idn

对于 Alice 和 Bob 的例子，在输入Hello CRDT和Hello crdt时可能进行了多次的同步操作，最终展现在 Alice 和 Bob 眼前的文本根据不同的 crdt 算法和冲突解决策略可能变得不同。也许是Hello crdt、Hello CRDTHellocrdt或Hello CRDTcrdt等等都有可能，但是最终在 Alice 和 Bob 眼前的结果将会是完全一致的其中一种结果。

CRDTs 的简单实现

我们就以多人的文本内容协作作为场景来尝试实现一个基于 op 的 crdt 的编辑器。下面是编辑器 demo 的效果展示。分别有Client1和Client2两个客户端在共同编辑一份文档。 Final Text的文本区域展示的当前同步后的结果。Client1和Client2也可以点击按钮表示进行同步。

首先我们需要确定这样一个简单的编辑器，用户会有哪些操作(op)。思考一下，非常简单地就可以得出一共有两种操作：

分布式中的顺序

那么我们还是回到 Alice 和 Bob 的例子，我们提供了第一版的编辑器给他们，但是由于我们技术还未成熟，要求他们只能插入内容还不能删除。Alice 和 Bob 同意参与到我们的迭代测试中去。他们还是分别一次输入了 Hello CRDT和Hello crdt。这时他们发起了同步。

Loading graph...

  flowchart TB
    subgraph Editor
    id1-->id3
    id2-->id4
    direction TB %% 子图1方向
        subgraph Alice
            direction TB
            id1[Hello CRDT];
            id1---id4((同步));
            id4-->AliceText[Hello CRDTHello crdt]
        end
        subgraph Bob
            direction TB
            id2[Hello crdt];
            id2---id3((同步));
            id3-->BobText[Hello crdtHello CRDT]
        end

    end

Alice 给 Bob 打了个电话，发现自己的屏幕上结果是Hello CRDTHello crdt而 Bob 的屏幕上结果是Hello crdtHello CRDT。怎么会这样？他们把测试结果反馈给了我们。

原来我们第一版系统都把新接收到的插入操作当作了后发生的事情，Alice 的编辑器把 Bob 的内容加在了后面，Bob 的编辑器也是如此。这和我们一开始所强调的强最终一致性可不符。我们希望无论事件被怎样创建和接收，只要操作集合是一致的，那么最终结果应该一样。

既然已经知道了问题所在，那么就没什么问题了。我们只需要让每个用户之间有一个固定的顺序就可以了，可以为每一个编辑器客户端分配一个Client ID，以ID的大小顺序来作为操作的顺序。我们很快发布了 v2.0 版本，让客户端 ID 越大认为操作越先发生，并且分配

提供给了 Alice 和 Bob 帮忙测试使用。

Loading graph...

  flowchart TB
    subgraph Editor
    id1-->id3
    id2-->id4
    direction TB %% 子图1方向
        subgraph Alice
            direction TB
            id1[Hello CRDT];
            id1---id4((同步));
            id4-->AliceText[Hello crdtHello CRDT]
        end
        subgraph Bob
            direction TB
            id2[Hello crdt];
            id2---id3((同步));
            id3-->BobText[Hello crdtHello CRDT]
        end

    end

这回没有问题了，Alice 和 Bob 的编辑器上显示的都是Hello crdtHello CRDT文本。

但随着进一步使用，Alice 和 Bob 又发现问题了。这次

然后他们进行了同步，这次每个人都发送了两个插入操作。

Loading graph...

  flowchart TB
    subgraph Editor
    one-->sy2
    two-->sy2
    three-->sy1
    four-->sy1
    direction TB %% 子图1方向
        subgraph Bob
            direction TB
            one[one ];
            one-->two;
            two---sy1((同步))
            sy1-->BobText[one two fourthree ]
        end

        subgraph Alice
            direction TB
            three[three ];
            three-->four;
            four---sy2((同步));
            sy2-->AliceText[one two three four]
        end

    end

现在 Bob 的屏幕上显示的是one two fourthree 而 Alice 屏幕上显示的却是one two three four，正常来说one two three four才是他们想要的结果。

我们发现 Alice 向 Bob 同步的内容发生了顺序的改变，有着分布式经验的我们立刻想到，可能是网络延迟的原因，导致 Alice 的第二个操作早于第一个操作被 Bob 的客户端接收到造成了顺序的不一致。

既然已经知道了问题所在，那么就没什么问题了。我们可以新增一个逻辑时间戳，也就是Lamport Timestamp

Lamport Timestamp 的算法很简单4

  • 每个进程维护一个counter
  • 本地每发生一个事件就将counter + 1，并将事件的时间戳设置为counter值
  • 每当进程发送一个消息，就将本地counter + 1，并将最新的counter值附带在消息上
  • 当进程收到消息后，让自己的counter = max(counter, message.counter) + 1

我们在原有的ClientId基础上进行了扩展，构建了一个EventId，其中包括了ClientId和Lamport Timestamp两部分，这样事件的发生顺序就可以与接收到的顺序无关了。

我们抓紧更新了 v3.0 版本的编辑器给到 Alice 和 Bob，心想肯定没问题了。

只确定逻辑顺序就够了吗

Alice 和 Bob 拿到 v3.0 的编辑器那肯定先尝试了一下刚刚失败的例子

Loading graph...

  flowchart TB
    subgraph Editor
    one-->sy2
    two-->sy2
    three-->sy1
    four-->sy1
    direction TB %% 子图1方向
        subgraph Bob
            direction TB
            one[one ];
            one-->two;
            two---sy1((同步))
            sy1-->BobText[one two three four]
        end

        subgraph Alice
            direction TB
            three[three ];
            three-->four;
            four---sy2((同步));
            sy2-->AliceText[one two three four]
        end

    end

果然更新后就没问题了。但 Bob 这回想着也不能一直只在后面加字符，于是 Bob 在编辑器的最前面插入了zero ，并且同步给了 Alice。发现同步之后结果怎么又不一样了。Alice 的结果是one two three fourzero ，Bob 输入的zero 怎么在后面啊？

Loading graph...

  flowchart TB
    subgraph Editor
    one-->sy2
    two-->sy2
    three-->sy1
    four-->sy1
    zero-->sy3
    direction TB %% 子图1方向
        subgraph Bob
            direction TB
            one[one ];
            one-->two;
            two---sy1((同步))
            sy1-->zero["zero (insert at 0 position)"]
            zero-->BobText[zero one two three four]
        end

        subgraph Alice
            direction TB
            three[three ];
            three-->four;
            four---sy2((同步));
            sy2---sy3((同步))
            sy3-->AliceText["one two three fourzero "]
        end

    end

Alice 和 Bob 开始不耐烦了起来，你们这个编辑器到底行不行？我们听到这个消息，赶快赶过来了解情况。

之前我们给每个插入操作分配了一个EventId，能够确定所有的插入操作的发生顺序。但是我们没有想到操作的顺序在文本这个场景下不能代表操作的位置。我们觉得不能再这样遇到什么问题解决什么问题了，需要好好想清楚编辑器这个问题，包括一直没被考虑的删除操作。

目前我们一共面临下面几个问题：

面临的问题还有些抽象，我们先通过一部分的例子来模拟一下吧。

Loading graph...

flowchart LR

blank[空白]-->ia[在编辑器中插入a]-->ib[在a后面输入b]-->ic[在b后面输入c]-->db[删除字符b]-->id[在a的后面插入d]
blank[空白]-->a-->ab-->abc-->ac-->adc

看到上面的图，我们的思路就清晰了很多。文本编辑里面最小操作的单位肯定是**字符**这点毋庸置疑了。至于确定位置这点，我们观察图中第一排的全部操作描述

那么位置就完全可以通过当前文本内容，看接下来要插入或者删除的字符是基于目前文本的哪个字符做的操作就可以确定了。这样不同的字符之间好像就有了依赖关系，那数据结构是不是可以使用树形结构了？

我们突然感觉灵感来了。

文本编辑好像就是棵树

如果我们把初始空文本当作树的根节点（root）的话，那么插入字符a就是a是root的子节点。在a后面插入b，那b就是a的子节点。我们把上面的示例画一下：

Loading graph...

flowchart LR
1-->2
2-->3
3--删除?-->4
4--顺序?-->5
    subgraph 1
    direction TB
    root-->a-->b
    end

    subgraph 2
    direction TB
    root2[root]-->a2[a]-->b2[b]-->c2[c]
    end

    subgraph 3
    direction TB
    root3[root]-->a3[a]-->b3["b(删除)"]-->c3[c]
    end

    subgraph 4
    direction TB
    root4[root]-->a4[a]-->c4[c]
    end

    subgraph 5
    direction TB
    root5[root]-->a5[a]-->c5[c]
    a5-->d5[d]
    end

把输入字符的过程可视化之后，我们看到过程 1 和 2 好像都没什么问题，全部都是在按顺序插入字符，前一个字符作为后一个字符的父节点，从根节点遍历下来就能还原原始文档。但是接下来我们好像遇到两个不是太明朗的操作。

这回实在不好意思再请 Alice 和 Bob 帮我们找问题了，就我和你来自己先多测测吧。第一个问题看起来还算简单

Loading graph...

flowchart LR
t1-.-g1
t2-.-g2
t3-.-g3
t4-.-g4


subgraph tree[Tree]
direction LR
    g1-->g2
    g2-->g3
    g3-->g4

    subgraph g1["insert a at 0"]
    direction TB
    a1[a]
    end

    subgraph g2[insert b after a]
    direction TB
    a2[a]-->b2[b]
    end

    subgraph g3[insert c after a]
    direction TB
    a3-->c3[c]
    a3[a]-->b3[b]
    end

    subgraph g4[insert d after a]
    direction TB
    a4-->d4[d]
    a4-->c4[c]
    a4[a]-->b4[b]
    end
end

subgraph text[Text]
direction LR

t1[a]-->t2[ab]-->t3[acb]-->t4[adcb]
end

我们不断模拟向a后面加入文本，结果都是越后面加入的字符，越显示在前面。在前面测试分布式同步的时候我们已经可以通过EventId全局地确定顺序了，那么全部子节点的顺序就可以通过EventId进行排序，越新的EventId将在子节点中越早被遍历。

删除了字符，它就不存在了吗？

接着我们模拟了几次协作时删除字符的情况，比如这次我先输入了ab你输入了c，之后我们进行了一次同步，我们的结果最后都是abc。

你可能会有疑问，为什么是abc，而不是cab？

这里我们使用假设

  • 你的ClientId是1
  • 我的ClientId是2
  • ClientId越大 crdt 认为越先发生

我们详细看一下abc的合并过程，现在我收到了全部的 crdts 的 op：

  1. 根节点插入 a EventId(counter: 0, client_id: 2)
  2. a 节点插入 b EventId(counter: 1, client_id: 2)
  3. 根节点插入 c EventId(counter: 0, client_id: 1)

根据刚刚的结论，op1 和 op3 都是counter为 0 的 op，但是 op1 的ClientId更大，在假设前提下会被认为优先发生。那么整个 op 顺序就会变成 132，即结果的abc。

紧接着我删除了b，而你在b的后面输入了d，然后我们都发起了同步请求。

Loading graph...

flowchart TB
    subgraph Editor
    direction TB %% 子图1方向
    b--->sy1
    c-->sy2
    d-->sy4
    db2-->sy3
    sy3-->rf["??????"]
    sy4-->rf
        subgraph 我
            direction TB
            a["insert a at 0\n a"]-->b["insert b after a\n ab"]-->sy2((同步))-->r2["同步后\n abc"]-->db2["delete b\n ac"]-->sy4((同步))
        end

        subgraph 你
            direction TB
            c["insert c at 0\n c"]-->sy1((同步))-->r1["同步后\n abc"]-->d["insert d after b\n abdc"]-->sy3((同步));
        end

    end

现在好像遇到了问题，我都已经把b删掉了，那么该怎么同步你要把d插入在b后面的操作呢？

我静静地整理了一下思路，我删除了b，但于此同时的你或者其他人仍可能在b后面输入一些字符，这也就是b仍可能是其他子树的父节点。其他节点仍然可能会依赖于它。所以我们在删除操作时不可能将真正的树节点删除。

再来想想文本展示时，就是一个树的遍历过程。只要不在编辑器上显示这个字符那么使用编辑器的用户就完全可以认为这个字符被删除了。所以我们只需要给每个节点增加一个标志，表示这个节点是不是被删除就可以了。

上面提到的为了保留树的完整结构，不删除节点，而是添加标志的方式就是一种墓碑机制

现在我们编辑器的结果就都会是adc，满足 crdts 所要求的强最终一致性。我们来遍历一遍刚刚所形成的文本树：

Loading graph...

flowchart LR
t1-.-g1
t2-.-g2
t3-.-g3
t4-.-g4
t5-.-g5


subgraph tree[Tree]
direction LR
    g1-->g2
    g2-->g3
    g3-->g4
    g4-->g5

    subgraph g1["insert a at 0"]
    direction TB
    root1[root]-->a1[a]
    end

    subgraph g2[insert b after a]
    direction TB
    root2[root]-->a2[a]-->b2[b]
    end

    subgraph g3[insert c at 0]
    direction TB
    root3[root]-->a3[a]-->b3[b]
    root3-->c3[c]
    end

    subgraph g4[delete b]
    direction TB
    root4[root]-->a4[a]-->b4["b (deteled)"]
    root4-->c4[c]
    end

    subgraph g5[insert d after b]
    direction TB
    root5[root]-->a5[a]-->b5["b (deteled)"]-->d5[d]
    root5-->c5[c]
    end
end

subgraph text[Text]
direction LR

t1[a]-->t2[ab]-->t3[abc]-->t4[ac]-->t5[adc]
end

参考资料

Footnotes

  1. https://github.com/wangdashuaihenshuai/crdt-edit ↩

  2. CRDT 简介 ↩

  3. A CRDT Primer Part I: Defanging Order Theory ↩

  4. 如何设计 CRDT 算法-Zxch3n ↩