# 初探富文本之CRDT协同算法
`CRDT`的英文全称是`Conflict-free Replicated Data Type`，最初是由协同文本编辑和移动计算而发展的，现在还被用作在线聊天系统、音频分发平台等等。当前`CRDT`算法在富文本编辑器领域的协同依旧是典型的场景，常用于作为实现文档协同的底层算法，支持多个用户同时编辑文档，不会因为用户并发修改导致冲突，而导致结果不一致甚至数据丢失的问题。

<details>
<summary><strong>初探富文本编辑器系列相关文章</strong></summary>

* [初探富文本编辑器#1-富文本概述](./初探富文本之富文本概述.md)
* [初探富文本编辑器#2-编辑器引擎](./初探富文本之编辑器引擎.md)
* [初探富文本编辑器#3-OT 协同算法](./初探富文本之OT协同算法.md)
* [初探富文本编辑器#4-OT 协同实例](./初探富文本之OT协同实例.md)
* [初探富文本编辑器#5-CRDT 协同算法](./初探富文本之CRDT协同算法.md)
* [初探富文本编辑器#6-CRDT 协同实例](./初探富文本之CRDT协同实例.md)
* [初探富文本编辑器#7-React 实时预览](./初探富文本之React实时预览.md)
* [初探富文本编辑器#8-文档 diff 算法](./初探富文本之文档diff算法.md)
* [初探富文本编辑器#9-在线文档交付](./初探富文本之在线文档交付.md)
* [初探富文本编辑器#10-划词评论能力](./初探富文本之划词评论能力.md)
* [初探富文本编辑器#11-文档虚拟滚动](./初探富文本之文档虚拟滚动.md)
* [初探富文本编辑器#12-搜索替换算法](./初探富文本之搜索替换算法.md)
* [初探富文本编辑器#13-序列化与反序列化](./初探富文本之序列化与反序列化.md)

</details>

## 概述
`Conflict-free Replicated Data Type`直译过来就是无冲突的复制数据类型，从名字可以看出来，`CRDT`的重点在于无冲突复制和数据类型，去掉定语的话就可以得到`CRDT`是一种数据结构，也就是说`CRDT`是通过数据结构来保证最终一致性的。在分布式系统中，不同节点之间的数据复制存在一致性问题即强一致性问题，`CRDT`是作为一种理论来指导如何将原有数据结构设计成在数据复制过程中通向最终一致性的一种新的数据结构。假设此时我们拥有多个副本或者操作，如果托管副本的计算机之间没有协调，此时进行合并的话则可能导致副本之间的不一致，这通常是无法解决的，当更新存在冲突时，要恢复一致性和数据完整性，可能需要部分甚至全部更新的删除。

由此`CRDT`指导我们在有多个副本或者操作进行合并或者更新时，使得我们的数据能根据一定的规则自动合并、解决冲突，最终达到强一致性的效果。回到富文本协同上，文档协同编辑同样可以理解为分布式应用的一种，而`CRDT`通过数据结构的设计保证并发操作数据的最终一致性。简单来说，`CRDT`就是可以在网络中的多个终端上复制的数据结构，副本可以独立和并行地更新，不需要在副本之间进行协调，并保证不会有冲突发生，从而保证最终各个副本的内容一致。

在讨论具体的协同算法之前，我们探究一下为什么要有协同算法，如果没有协同算法的话会出现什么问题，以及具体会出现问题的场景。那么假如我们有一个在线的文档应用，而我们是一个团队，我们有可能对同一篇文档进行编辑，既然我们会同时编辑，那么就有可能产生冲突。假设文档此时的内容为`A`，此时`U1`和`U2`两位用户同时在编辑，也就是说这两位都是从文档的`A`状态开始编辑，当`U1`编辑完成之后，文档状态是`B`，`U1`对文档进行了保存，此时`U2`也写完了，文档状态是`C`，`U2`也对文档进行了保存，那么此时文档的状态就是`C`了，由`U1`编写的`A -> B`状态的内容修改便丢失了，为了解决这样的问题，通常有以下几个方案：

### 乐观锁
乐观锁，主要就是一种对比于悲观锁的说法，因为乐观锁的操作过程中其实没有没有任何锁的参与，严格的说乐观锁不能称之为锁。乐观锁总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，可能需要在更新的时候会判断一下在此期间别人有没有去更新这个数据提示一下，或者干脆不会给予任何的提示信息。

那么具体到文档编辑上边，我们可以乐观地认为永远不会有两个人同时编辑同一篇文档，现实中也可能有这种情况，比如团队中每个人只负责几篇文档，其他人不需要也没有权限去编辑自己负责之外的文档。那么基于这种要求，我们可以乐观地认为永远不会出现冲突的问题，那么自然也就不需要对文档的管理做任何限制了，只需要完整地提供编辑能力即可。

### 悲观锁
悲观锁，顾名思义是基于一种以悲观的态度类来防止一切数据冲突的方式，其以一种预防的姿态在修改数据之前把数据锁住，然后再对数据进行读写。在其释放锁之前其他的任何人都不能对数据进行操作，直到前面一个人把锁释放后下一个人才可对数据进行加锁，继而才可以对数据进行操作，通过这种方式可以完全保证数据的独占性和正确性。

那么具体到文档编辑上边，我们可以对同一篇文档的编辑操作权限进行加锁，这样就可以保证同一时间只有一个人可以对文档进行编辑，其他人只能等待。直到前面的人把文档编辑完成并且释放锁之后，下一个人才可以对文档进行编辑，当然也可以开一个口子允许强行抢占并且将被抢占者的现场存储下来，相当于将一个并发操作压成了线性操作，这样就可以通过独占的方式保证文档的正确性，避免文档的内容冲突与丢失。

### 自动合并
自动合并，文档内容自动合并以及冲突处理的方式也是一个可行的方案，类似于`Git`的版本管理思想，可以对提交的内容进行`diff`差异对比、`merge`合并等操作，也可以在出现无法解决的冲突时出现时交给用户主动处理，`GitBook`是采用这种方式解决冲突问题的。

### 协同编辑
协同编辑，可以支持多个用户同时编辑文档，不会因为用户并发修改导致冲突，而导致结果不一致甚至数据丢失的问题。协同编辑重点在于协同算法，主要有`Operational Transformation(OT)`与`Conflict-free Replicated DATA Type(CRDT)`两种协同算法。协同算法不需要是正确的，其只需要保持一致，并且需要努力保持你的意图，就是说协同算法最主要的目的是在尽可能保持用户的意图的情况下提供最终的一致性，重点在于提供最终一致性而不是保持用户的意图。当前石墨文档、腾讯文档、飞书文档、`Google Docs`都是基于`OT`协同算法的，`Atom`编辑器使用的是`CRDT`协同算法。

## CRDT协同算法
`Conflict-free Replicated DATA Type(CRDT)`协同算法的核心思想不在于解决冲突，而在于构造一种数据结构来避免冲突，避免了冲突就可以直接进行合并，最终得到文档内容。`CRDT`协同算法的目的是在尽可能保持用户意图的情况下，保持文档的最终一致性。举个例子，当`A`和`B`同时在文档的`L`处插入了不同的字符，那么谁插入的字符在前协同算法并不关心，其只需要尽可能地根据一定策略例如时间戳来判断究竟是谁的字符在前，但是最终计算出的结果即究竟谁的字符在前并不影响协同算法。

其关心的重点在于经过协同算法将用户产生的`Op`调度之后，在每个人面前呈现的文档内容是绝对一致的，这就是保持文档的最终一致性。从功能的角度上说，协同算法保证的是在多人同时在线编辑的情况下，由于每个人提交的内容是不一样的，就需要通过协同算法的调度，使得每个用户最终都能看到一样的内容。实际上在线文档本身就是一个数据一致性要求很强的项目，所以无论是使用`CRDT`算法还是`OT`算法来实现协同，保证最终一致性就是必须要考虑的基本内容。

由于`CRDT`设计上可以完成对于各个副本的合并与更新而不会产生冲突，那么经由`CRDT`实现的算法就可以直接在客户端之间互相传递，相互同步至最终一致性的状态，也就是各个用户之间可以直接`P2P`进行数据合并而不需要中央服务器进行调度。由此`CRDT`可以很好地支持去中心化的应用，即使没有中心化服务器各端之间也能完成同步。

谈到了最终一致性和分布式系统，那么就不得不提到`CAP`理论，`CAP`理论指出在一个分布式系统中，最多只能同时满足`Consistency`(一致性)、`Availability`(可用性)和`Partition Tolerance`(分区容错性)中的两项。

* 一致性`Consistency`: 对于客户端的每次读操作，要么读到的是最新的数据，要么读取失败。换句话说，一致性是站在分布式系统的角度，对访问本系统的客户端的一种承诺：要么我给你返回一个错误，要么我给你返回绝对一致的最新数据，不难看出，其强调的是数据正确。
* 可用性`Availability`: 任何客户端的请求都能得到响应数据，不会出现响应错误。换句话说，可用性是站在分布式系统的角度，对访问本系统的客户的另一种承诺：我一定会给你返回数据，不会给你返回错误，但不保证数据最新，强调的是不出现响应错误。
* 分区容错性`Partition tolerance`:由于分布式系统通过网络进行通信，网络是不可靠的。当任意数量的消息丢失或延迟到达时，系统仍会继续提供服务，不会挂掉。换句话说，分区容忍性是站在分布式系统的角度，对访问本系统的客户端的再一种承诺：我会一直运行，不管我的内部出现何种数据同步问题，强调的是不挂掉。

对于一个分布式系统而言，`P`是前提，必须保证，因为只要有网络交互就一定会有延迟和数据丢失，这种状况我们必须接受，必须保证系统不能挂掉，所以只剩下`C`、`A`可以选择，要么保证数据一致性即数据绝对正确，要么保证可用性即保证响应不出错。首先我们要理解一下为什么`P`是前提，这里的场景是分布式系统，网络是不可靠的，一定会存在网络延迟与丢失等问题，如果不允许存在网络分区也就是说网络是一直保证运行正常的，那么显然每次写入数据都可以进行同步，自然一致性和可用性显然得到了保障，但这也不是分布式系统了。

我们来举个例子，在网络发生问题时，为什么需要在`C`和`A`之间进行选择，假设在分布式系统中存在`100`个节点，但由于故障，使得网络发生了分区，其中有一半的节点无法向另外一半节点通信，于是系统被分割为`A`区与`B`区。在网络分区的情况下，客户端发送请求尝试来对`A`区一个节点进行数据写入，由于`AB`区网络不通，这时候无法同步写入信息给到`B`区节点。在这种场景下，究竟允不允许当前客户端进行数据写入呢。

* 如果允许客户端数据写入，那么当前节点的可用性得到了保证，但是由于网络分区，所以网络不可触达，数据无法同步。因此此时是无法满足一致性，也就是分布式系统中，同时访问两个节点，可能会返回不同数据。
* 如果不允许客户端数据写入，那么当前节点的一致性得到了保证，所有节点数据都是一致的，但是由于数据都无法写入，这时系统显然是不可用的，需要阻塞等待，直到网络连接恢复，也就是可用性无法满足。

实际上`CAP`特性三选二的描述其实具有误导性，从上边的例子中也可以看出，不是在所有时候都只能选择两个特性，在不存在网络失败的情况下即分布式系统正常运行时，`C`和`A`能够同时保证，只有当网络发生分区或失败时，才会在`C`和`A`之间做出选择，但是谁也无法保证任何时刻网络都是畅通无阻的，所以必须要处理在这种情况下的策略，以此来取得`C`和`A`的权衡。作者`Eric Brewer`在`2012`年也发表论文解释了`CAP`实际上只是禁止了设计空间存在分区时的完美可用性和一致性。而实际上在`C`和`A`之间的权衡的设计非常灵活，`CRDT`就是一个很好的例子。`CRDT`算法正是在满足`Partition Tolerance`(分区容错性)的前提下，尽可能地保证`Consistency`(一致性)和`Availability`(可用性)，同样`OT`协同算法也是一样通过保证最终一致性来完成这个权衡的。

在协同编辑的场景下，我们似乎能够同时满足了`CAP`的三个场景限制，假设在网络差的情况下，两个客户端同时提交，虽然暂时一致性无法满足，本地客户端会看到不同的内容，但网络恢复后，通过协同算法数据也能保持一致，这不是既满足了一致性又满足了可用性。这个想法是对的，只是这里我们保证的一致性不等于`CAP`理论的一致性，`CAP`理论是假设在没有网络延迟的情况下的强一致性，也就是数据时刻都是一致的，而协同编辑的场景的一致性则是最终一致性。前文也提到过，在`C`和`A`之间的权衡的设计非常灵活，既然无法做到强一致性`Strong consistency`，那么应用可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性`Eventual consistency`，这个就又需要说到`BASE`理论了。

* `BA`: `Basically Avaliable`，基本可用，允许损失部分可用性，允许牺牲响应时间、降级系统功能等操作。
* `S`: `Soft State`，软状态，允许存在数据中间状态，不要求强一致性，并不影响整体可用性，允许副本之间的数据同步延迟。
* `E`: `Eventually consistency`，最终一致性，所有的副本，在最终都能达到数据一致的状态，但不要求实时的强一致性。

在`BASE`理论中，我们可以看到协同编辑文档的场景中，虽然`CAP`的强一致性无法满足，但通过灵活地设计`C`和`A`，损失部分可用性，允许暂时的客户端不一致情况，通过协同编辑冲突算法，可以解决数据不一致问题，达到了最终的数据一致性。实际上在分布式理论上又有很多研究，有着强一致性、弱一致性、顺序一致性、最终一致性、因果一致性等，而最终一致性也有读写一致性、写读一致性、单调读一致性、单调写一致性等划分，在这里就不再赘述了。

之后我们再简单举一个例子，看看应该如何去实现最终一致的分布式系统。假设我们当前有一个账户是`T`，初始时这个账户有`100`块钱，用户可以通过系统里面好几个节点，例如`A`、`B`、`C`，访问`T`这个账户，并且可以在任何时刻都对`T`进行操作。注意此时我们并没有中央服务器来保存这`100`块钱，而是每个账户都各自存储了这个数字，在这个分布式系统中我们不考虑安全方面的因素，我们只需要最终保证每个人的数据都是一致的即可。

假设某个时刻`t1`，`A`往`T`中存了`10`块钱，`B`则向`T`中取了`10`块钱，`C`则在接下来的一个时刻查询`T`有多少钱，这几个操作都是同时发生的。那么，我们的分布式系统会保证这三个操作都能完成，于是在本地:

* 在`A`系统看来，`T`有`110`块钱。
* 在`B`系统看来，`T`有`90`块钱；
* 在`C`系统看来，`T`有`100`块钱。

在这个时刻`t1`，这三者都是对的，因为我们可以在最终一致性系统中，存在不一致的时刻，那么经过一段时间之后，假设是`t2`，我们需要使得`A`、`B`和`C`系统看来，`T`都有`100`块钱，即保证最终一致。那么这中间肯定需要做一些操作，即`A`、`B`和`C`系统之间交换一些必要的信息数据。那么现在麻烦来了，我们需要如何进行数据交换，如果在各节点我们只是存了`T`的余额，例如用一个整数变量，这样显然是不行的，因为当`A`系统和`B`系统的数据传输到`C`系统时，`C`无法分辨`A`或者`B`系统的结果到底谁对。那么重点来了，我们应该如何处理这个问题，最简单的处理方案，加入额外的数据，通过额外的数据来保证合并的正确，这也就是`CRDT`的重点。

那么在这个例子里面，我们可以这样设计，每个系统存储的不是一个最终数值，而是一系列包含了时刻与余额的记录，假设我们的系统是从`t0`时刻开始的，那么在我们的例子里面，`t1`时刻存储的数据如下所示:

* `A`系统存储的是`(t0, 100)`、`(t1, 110)`。
* `B`系统存储的是`(t0, 100)`、`(t1, 90)`。
* `C`系统存储的是`(t0, 100)`、`(t1, 100)`。

那么在`t2`时刻，我们进行了数据传输，对于`C`而言收到了`A t0->t1 +10`的操作，收到了`B t0->t1 -10`的操作，由此`C`在`t2`时刻依旧是`100`；而对于`A`而言，收到了`B t0->t1 -10`的操作，`C`没有更新操作所以不需要同步；对于`B`而言收到了`A t0->t1 +10`的操作，`C`没有更新操作所以不需要同步。最终`A`、`B`、`C`三者得到了一致的数据总和表示`100`，由此得到了最终一致性。当然这个例子足够简单，答案也足够的粗糙，而且在实际的应用中，我们必须要考虑更多的数据类型和应用场景，于是设计一个能够保持最终一致性的数据结构，就会变成一件很难的事情。由此才需要围绕着`CRDT`的理论进行分布式系统的设计，从而减少我们的对于分布式协同设计的心智负担。

回到协同，在了解`CRDT`协同算法之前，我们也可以了解一下`CRDT`协同算法与`OT`协同算法的主要区别。首先`CRDT`与`OT`都提供了最终一致性，这也是协同编辑的最终目标，但是这两种方案达成这一目标的方式不一样：

* `CRDT`无冲突复制数据类型是通过数据结构来做到这一点，`CRDT`有两种实现方式，基于状态的`CvRDT`收敛复制数据类型和基于操作的`CmRDT`可交换复制数据类型。`CvRDT`是将各个副本进行合并，进行多少次合并或以何种顺序进行合并并不重要，所有副本都会收敛。`CmRDT`则具有可交换的操作，因此无需转换操作即可正确应用这些操作。
* `CRDT`更适合分布式系统，可以不需要中央服务器。
* `CRDT`通过数据结构保证了编辑的无冲突，增加了空间复杂度。
* `OT`操作转换则是通过操作`Operation`转换`Transformation`来做到这一点，终端所进行的操作`O`通过网络传输，其他终端在收到操作`O`后需要进行转换`T`，之后才可以应用到文档上，最基础的`OT`是通过转换索引位置以确保收敛。
* `OT`通常必须要有中央服务器进行协同调度。
* `OT`通过算法处理编辑冲突的问题，增加了时间复杂度。

### 基本原理
在上边我们讨论到了`CAP`定理，我们需要在一致性与可用性之间做出取舍，能够达到最终一致性而暂时地损失部分可用性是完全可以接受的，不过无论如何在实际情况中设计这样一个分布式系统还是非常复杂的，而`CRDT`就是是这样一个通向最终一致性的理论，可以指导我们去正确地设计一个高可用的分布式系统。`CRDT`同样也并不仅仅应用在在协同领域，当前各种分布式系统和应用均开始尝试`CRDT`，`redislabs`和`riak`已经实现多种数据结构，微软的`CosmosDB`也在`azure`上使用`CRDT`作为多活一致性的解决方案。

那么`CRDT`究竟代表了什么，其是如何做到合并时不会出现冲突的。在分布式系统中复制有两种实现途径，一种是在主节点和从节点之间复制全量状态，还有一种是就是复制操作本身。简单解释一下，全量复制状态类似于我们把当前正在编写的整个文档都复制出来同步到其他客户端，而复制操作本身类似于我们只把当前编辑时造成的`Op`复制出来同步到其他客户端。

那么如果是复制状态，也就是全量复制，就需要有一些状态收敛规则，因此我们就可以创建`Convergent Replicated Data Types`，也就是`CvRDT`基于状态的收敛复制数据类型，也被称为`State-based CRDT`。而如果是复制操作，那么这个操作就需要被设计为`Commutative`可交换的，而并不需要进行操作变换，由此可以创建`Commutative Replicated Data Types`，也就是`CmRDT`可交换复制数据类型，也被称为`Op-based CRDT`。在这两种情况下，目标都是通过确保操作彼此不会冲突独立发生从而为了避免协调，所以可以总称为`Conflict-free Replicated Data Type`，也就是`CRDT`。

#### State-Based CRDT
基于状态的`CRDT`，名字听着很吓人，实际上突然理解起来也挺吓人，但是拆开看就没有那么难以理解了。`State-based CRDT`的结点和结点传输的是状态，存在一个算子`Merge: (SA, SB) => SC`, 收到传输的状态就和自己存储的状态`Merge`，这个算子必须满足交换律、结合律和幂等律，所以如果用抽象代数的角度形容地话，其使整个状态系统形成了一个半格。所以最终只要能接受到其他所有节点的新状态，那么永远能保证系统最终会收敛，由此并不会发生冲突。这样也去除了对于`CmRDT`的底层通讯机制依赖，但是因为传递的是状态，所以最后传输可能有点大，当然也是存在优化策略的。

上边这段话可能有些难以理解，我们慢慢拆开来研究一下，首先我们看下算子`Merge: (SA, SB) => SC`，这也就是说我们同步状态的内容是需要合并的，这也就是我们做`State-based CRDT`的目的，即收到传输的状态就和自己存储的状态`Merge`。接下来就是我们这个算子需要保证的条件了，先来回顾一下交换律、结合律和幂等律:

* 交换律: `A ∪ B = B ∪ A`。
* 结合律: `(A ∪ B) ∪ C = A U (B U C)`。
* 幂等律: `A U A = A`。

看到这三个公式我们就可以比较容易地理解这个为什么这个算子需要满足这三律了，我们首先需要关注的一点是网络是不可靠的，而分布式的系统必须要依赖于网络进行数据传输，由此我们来看下为什么需要保证这三个公式:
* 交换律，假设我们有`A`、`B`两位用户相互进行数据传输，`A`数据同步到`B`就是`A ∪ B`，`B`数据同步到`A`就是`B U A`，那么在需要保证最终一致性的前提下则必须保证交换律进而能够保证正确地进行数据合并，即应用顺序无关紧要。
* 结合律，假设我们有`A`、`B`、`C`、`D`、`E`五位用户相互进行数据传输，此时`A`、`B`、`C`对数据进行了改动，对于`D`、`E`而言就需要从其他三个客户端进行数据同步，由于存在网络延迟，无法哪个客户端的位置先行到达，也就是`D`的合并顺序可能是`A B C`，而`E`的合并顺序可能是`B C A`，所以需要满足结合律才能够保证正确进行数据合并，即分组无关紧要。
* 幂等律，假设我们有`A`、`B`两位用户相互进行数据传输，当`A`用户进行改动后将副本进行了网络传输，但是久久没有得到`ACK`确认，那么此时可能会有一个超时重传的机制，我们又将`A`发送了出去，但是巧合的是刚才那个包并没有丢失，只是传递比较慢，而新的`A`包由于选择了其他的路由线路也没有丢失，此时两个相同的`A`包同时到达了`B`，由于`B`未发生修改，`B`合并了第一个`A`之后相当于内容与`A`相同，此时再合并第二个`A`就需要保证幂等性从而保证能够正确进行数据合并，即重复无关紧要。

可以看出其实满足上边三个公式都是由于网络的不可靠，而我们为了保证最终一致性从而需要对数据结构进行设计。此外需要注意的是如果我们能够保证`Exactly once`的语义，则幂等律条件是可以放宽的，举个例子加法本身满足交换律结合律但不幂等，假如此时我们能够保证加法操作只复制一次，其结果还是最终一致的。实际上保证了上述三个定理，我们在分布式系统同步数据的时候就可以无需考虑合并的顺序以及多次合并的问题了，且能够保证最终一致性。

下边再看一下半格的概念，在了解半格之前我们需要探讨一下偏序集的概念，实际上了解了半格之后，我们就可以大概理解`CRDT`如何做到合并不会出现冲突的问题了。设`P`是集合，`P`上的二元关系`≤`满足以下三个条件，则称`≤`是`P`上的偏序关系或部分序关系。

* 自反性: `∀a∈P`，`a≤a`。
* 反对称性: `∀a, b∈P`，若`a≤b`且`b≤a`，则`a=b`。
* 传递性：`∀a, b, c∈P`，若`a≤b`且`b≤c`，则`a≤c`。

需要注意的是这里的`≤`不必是指一般数学意义上的小于或等于，我们通常认为其意义是`x`排在`y`前面`x precedes y`，也就是说这个偏序关系不一定是比大小，也并不要求集合元素之间是数字，关键要如何定义这个二元关系，只要要满足上述三条性质，即是偏序关系。可能有些抽象哈，我们举个例子，自然数的集合配备了它的自然次序即小于等于关系，那么这个偏序是全序。我们同样也可以定义一个关系`≤`为子集，也就是说我们可以通过子集来比较集合，从而构造一个偏序关系，下面这个例子中就可以由子集偏序关系看出`{} ≤ {x} {x} ≤ {x, y} {x, y} ≤ {x, y, z} ...`。

```
         {x, y, z}
{x, y}    {x, z}    {y, z}
  {x}       {y}       {z}
             {}
```

接下来我们再看一下格相关的概念。格是一个偏序集，具有不同的顶部(最小上界)和不同的底部(最大下界)。半格同样也是一个偏序集，且每个非空集合都有上确界或者下确界，而上确界被称为`Least upper bound`即`LUB`。也就是说半格相较于格来说，只有一个不同的顶部或底部，所以是在名字上也可以看出是叫做半个格。连接半格是具有不同顶部(最小上界)的半格，而相交半格是具有不同底部(最大下界)的半格。任何表示为半格的数据类型都可以实现为保证收敛的数据结构。例如，计算一组值的`Max()`将始终返回相同的结果，无论接收值的顺序如何，只要最终接收到所有值，因为`Max()`操作是保证了交换律、结合律和幂等律的。依旧拿上边的这个集合例子来说，我们此时改变了定义，在这里有两种格子，对于集合是定义了`Union(items)`格子，对于数据是定义了`Max(value)`格子，对于两个半格而言，我们保证了一个最大上界，在例子中我们三个集合的最终一致性数据为`{x, y, z} 3`。

```
         {x, y, z}                 3   
{x, y}    {x, z}    {y, z}    2    3    3
  {x}       {y}       {z}     1    2    3
             {}                   null
```

在经历了半格、偏序集之后，似乎我们最终又回到了交换律、结合律和幂等律，实际上我们在半格中也提到了，只要我们能够定义一个有意义的最小上界`LUB`函数，我们就能创建`CRDT`。如果上边的`Max(x, y)`不是很直观的话，我们在本文数据结构一节中会有更多的数据结构示例来解释这个问题。或许在富文本的数据结构中并没有`Max(x, y)`这么简单地能够满足半格条件的实现方法，但是别忘了我们可以为数据附加额外的信息，在我们前边提到了`CRDT`是通过数据结构保证了编辑的无冲突，从而增加了空间复杂度，而数据结构的设计很重要的一点就是携带其他的信息，例如时间戳、逻辑时间戳、用户唯一`id`等等，通过附带元信息的方式是让其更新保持单调，从而能够构建一个带有最小上界偏序关系的半格。

#### Op-Based CRDT
基于操作的`CRDT`，实际上类似于上边的`State-based CRDT`，只不过我们操作的对象变成了操作`Op`的复制与同步。那么同样对于操作，我们也需要为其设计为符合交换律、结合律与幂等律的，因为即使传输的对象从状态转换到了操作，也是需要经过网络进行传输的，那么就不可避免地出现了上述分布式系统必须要解决的问题，所以传输的操作也是需要经过设计的，而使用`Op-based CRDT`能够获得的明显提升是同步过程中需要传输的数据显著降低。

那么当前客户端的更新操作本身满足以上三律，那么复制过后的操作同步到其他客户端的时候仅需要对传输过来的操作进行回放即可，最简单的例子是集合求并集。如果本地的客户端操作无法满足上述的条件，则可以考虑将元信息附加到操作`Op`上从而满足三律条件。同样的，如果我们能够保证`Exactly once`的语义，则幂等律条件是可以放宽的。如果依旧无法满足的话，则可以考虑同步副本数据即`State-based CRDT`，同时附带额外元信息，通过元信息让本地更新与其他客户端合并操作具备以上三律。有趣的是，使用基于操作的方式总是能够模拟基于状态的方式。

由于这里操作的对象是`Op`，我们重新表示一下在快照的基础上满足于交换律、结合律与幂等律的方式，类似于`OT`的表示，我们需要定义一些概念，`snapshot`是当前文档的内容，`apply(snapshot, op)`是在`snapshot`的基础上应用`Op`从而更新文档，那么三律的表示如下:

* 交换律: `apply(apply(snapshot, A), B) = apply(apply(snapshot, B), A)`。
* 结合律: `apply(apply(apply(snapshot, A), B), C)= apply(apply(apply(snapshot, B), C), A)`。
* 幂等律: `apply(apply(snapshot, A), A) = apply(snapshot, A))`。

在`Op-based CRDT`的设计中，我们还需要考虑到因果一致性，我们需要在`apply`之前对快照进行检查，保证`Op`所依赖的因果顺序成立，例如删除`x`节点的操作依赖于`x`节点被创建的操作，否则就无法应用该操作，在不满足条件的情况下需要阻塞延迟，这也意味着我们有责任保证每个操作的前置状态都是能够得到满足的。也就是说我们需要保证每个操作的前置条件都能通过按因果顺序应用得到满足，从而所有更新函数都会终止。最终各个客户端的副本之间通过传递彼此缺失的`Op`，并进行`apply`操作来达到最终一致性。

同样的，即使是同步`Op`，我们也可以通过保证一个偏序关系来保证三律的实现，我们可以根据每个`Op`在副本上的执行顺序来确定偏序关系，也就是说我们此时附加的元信息是时间戳或者是逻辑时间戳。

* 如果一个`OpA`在副本上先于`OpB`执行，那么`A < B`。
* 如果既没有`A < B`也没有`B < A`，那么我们就称`A`和`B`是并行的操作。

由此在`Op-based CRDT`的设计中，我们需要设计使得`Op`满足交换律、结合律与幂等律，并且需要保证每个操作的前置条件都能通过按因果顺序应用得到满足，从而所有更新函数都会终止，从而得到满足`Op-based CRDT`的数据结构。实际上，在形式上`Op-based CRDT`和`State-based CRDT`是可以互相转换的，所以在`Op-based CRDT`这一节当中大部分需要了解的内容在`State-based CRDT`一节中都有体现。在`State-based CRDT`这一节的最后我们提到了在富文本中通过附加元信息的方式来满足`CRDT`的条件，同样我们也可以将元信息附加到`Op`上来满足条件，简单一点的话，我们如果为富文本的每一个字都赋予了唯一的`id`，再配合上逻辑时间戳，我们就能精确地知道该如何将`Op`应用到文档的位置，从而就不需要进行操作变换转换索引了。当然这个实现非常非常粗糙，如果想深入涉及一下的话，可以看看`YATA`算法与`Yjs`，在`Yjs`中，大部分操作都是基于`Op-based CRDT`设计实现的，只有处理删除操作的时候是类似于`State-based CRDT`的实现。

### 数据结构
下面是一些典型的`CRDT`数据结构的例子，可以帮助我们理解`CRDT`的设计思想，要注意的是我们在此处的例子是没有中央服务器调度以及数据存储的的，数据都是在各个客户端之间进行同步。

#### Op-Based Counter
`Op-based Counter`表示了一个整数计数器，假设此时我们有`A`、`B`两个客户端共同维护一个计数器，也就是说我们两个客户端都存储了一个整数，假设当前值为`10`，那么此时`A`进行了`increment`操作，`B`进行了`decrement`操作，那么我们就可以暂时地得到`A`的值为`11`，`B`的值为`9`，之后便要进行数据同步，以便使得`A`和`B`得到最终一致性的`10`这个值，那么我们就可以在网络中同步`A`的`increment`操作，`B`的`decrement`操作，这样就能够使得`A`和`B`的值都变为`10`。

看起来这个操作是很容易实现的，那便是因为加法天然满足交换律和结合律，减法也同样可以看作是加法，只不过是加一个负值，那么在这个例子中需要注意的点是加法不幂等，所以同步过程中需要保证不丢不重。

#### Grow-Only Counter
`State-based Counter`在组织形式并非那么的显而易见，在这一小节我们先从`Grow-only Counter`看起，也就是只增的计数器。首先明确的概念是我们此时是将数据全量同步的`CRDT`实现，由于同步的是全量，如果每个副本单独进行累加，在进行合并的时候无法知道每个副本具体累加了多少，也不能简单的取一个`max`作为最终结果。例如此时我们有`A`、`B`两个客户端共同维护一个计数器，初始时两个客户端数据都是`0`，此时`A`增加了`1`，`B`增加了`2`，那么全量同步数据时如果`max(1, 2) = 2`是不行的，因为我们实际上想得到的数据是`3`。以上，虽然我们通过`max`设计的数据结构是符合了交换律结合律和幂等律，但是这个设计与我们的目的是相悖的，我们想得到的是一个计数器，而不是获得客户端的最大值。

那么一种可行的方案是在每个副本上都使用一个数组保留其它所有副本的值，本地更新时只操作当前副本在数组中对应项，合并只能修改数组中除了当前副本的其他项目，并且对数组每一项求`max`进行合并，在查询时将本地所有副本的值求和，即为我们想要的计数器`Counter`。此时我们有`A`、`B`两个客户端共同维护一个计数器，初始时两个客户端数据都是`0`，那么`A`维护的数据是`[0, 0]`，`B`维护的数据是`[0, 0]`，此时`A`增加了`1`，`B`增加了`2`，那么`A`就变成了`[1, 0]`，`B`变成了`[0, 2]`，当数据同步之后，`A`即为`[1, 2]`，`B`为`[1, 2]`，这样两个客户端的数据就是一致的了，最终的计数为`3`。

在上述的方式中，对数组每一项求`max`进行合并就是我们维持交换律结合律和幂等律的方式。由于网络的不可靠，我们不能保证数据包都能够正常同步，假如历史遗留了一个`[1, 1]`的包在网络中刚到达某一个客户端，而此时客户端的值已经达到了`[6, 10]`，那么这个包一定是要被舍弃的，否则就不能达到我们需要保证的三律，由此我们维护了一个偏序关系，当然了自然数实际上是全序关系。当然我们也可以为数据附带一个时间戳，或者逻辑时间戳，这也是可实现的方式，因为同样符合我们前边论述的，通过附加元信息的方式来达到三律。

#### Positive-Negative Counter
在上述的`Grow-only Counter`的最后，我们举了个假如历史遗留了一个`[1, 1]`的包在网络中刚到达某一个客户端，而此时客户端的值已经达到了`[6, 10]`，那么这个包一定是要被舍弃的，否则就不能达到我们需要保证的三律的例子。其实也能够看出来，这个例子维护的是一个仅增的数据结构，如果加的是一个负数，或者直接叫做减法的话，那么上述的这个系统就是无效的。

由此带有`Decrement`的`State-based CRDT`也并非像`G-Counter`那样显而易见，带有减法之后，不能满足更新时时单调的偏序关系，所以在这里一种可行的方式是构造两个`G-Counter`，一个存放`Increment`的累加值，一个存放`Decrement`的累加值，通过两组带有偏序关系的`CRDT`来达到我们维持三律的目的。

#### Grow-Only Set
`Grow-only Set`表示的是一个仅增的集合，`Set`的`Add`操作本质上是求并，天然满足交换律、结合律和幂等律, 可以很简单地使用`Op-based CRDT`，此时也不需要与上述的`Op-based Counter`一样需要保证不丢不重，因为集合求并集是幂等的，当然也可以使用`State-based CRDT`进行全量的数据求并集，此时每个客户端的副本也只需要保存一份集合即可。

#### Two-Phase Set
在`Two-Phase Set`中，我们考虑到了删除操作，实现思路上和`PN-Counter`一致，使用两个`G-Set`，`Set A`只负责添加，对于从`Set A`中`remove`的元素不做实际删除，只是复制到`Set R`中，在查询时如果元素在`Set A`且不在`Set R`中，则表示该元素存在。实际上`2P-Set`十分不实用，一方面已经被删除的元素不能再次被添加，因为集合必须保持只增的偏序关系，一方面删除的元素还会保留在原`Set`中，占用大量空间。

#### Last-Write-Wins-Element Set
在`Last-Write-Wins-Element Set`中为了解决删除元素不能再次添加的问题，可以考虑给`2P-Set`中`A`和`R`的每个元素加一个更新时间戳，其它操作保持不变，那么在查询的时候就需要判断该元素是否存在，即如果一个元素在添加集`A`中，并且不在删除集`R`中，或者在删除集`R`中但时间戳早于添加集`A`中的最新时间戳，那么就认为该元素存在。另一个更优化的实现是不要`R`集合，而`A`集合中每一个元素除了维护一个更新时间戳之外，还有一个删除标志位，这也可以看出实际上通过附加元信息的方式可以有很多实现，只要能够满足交换律、结合律和幂等律即可。

#### Observed-Remove Set
`Observed-Remove Set`类似于`LWW-Element-Set`的实现，但使用唯一标签`tag/uuid`而不是时间戳，我们同样需要维护一个增加集`Set A`与删除集`Set R`。在添加元素时生成一个新的唯一标记`tag/uuid`，在删除的时候就将该元素与`tag`复制到删除集`Set R`中，查询时如果元素在`Set A`中且不在`Set R`中，元素才存在于集合当中，因为我们生成了全局唯一的`tag`，所以并不需要比较时间戳，这样就可以保证删除元素后可以再次添加，这可以看作是`State-based CRDT`的实现。

还有一种满足`Op-based CRDT`的设计，核心思想是每次`Add(e)`的时候都为元素`e`加一个唯一的`tag/uuid`，`Remove(e)`将当前节点上的所有`e`和对应的`tag/uuid`都删除，这样在`Remove(e)`同时其它节点又有并发`Add(e)`的情况下`e`是能够最终保证添加成功，此种语义称为`Add wins`。

接下来我们可以看看这种方式是如何满足交换律、结合律和幂等律的，在这里的叙述都是要满足因果一致性来表述的，首先对于交换律而言，由于`tag/uuid`是全局唯一的，无论是`Add`还是`Remove`显然都是可以交换的，当然前提是满足因果一致性，不满足需要阻塞等待；同样还有结合律，在满足因果一致性的情况下我们是可以随意对于集合进行结合操作的，主要是`tag/uuid`是全局唯一的，并不会出现不一致的问题；最后是幂等律，我们需要保证因为网络不可靠重新发送的包的`tag/uuid`与重试前的数据相同，那么因为该元素已经实际存在，我们并不会重复添加，因而这个操作是幂等的。其实类似于我们最初写到的`Op-based Counter`，`Op`是可交换的，并且保证了幂等性，所以这也是一种合理的`CRDT`设计。

## 总结
由于`CRDT`是处理分布式系统数据同步问题的通用解决方案，所以本文并没有局限于在富文本数据结构的设计，而是从分布式数据同步的角度来理解`CRDT`，并且穿插着`CRDT`在富文本领域上的应用，从而让我们能够更好地理解这个数据模型。同样，本文介绍的内容也只是冰山一角，分布式数据的同步一直以来都是个复杂的问题，回归到富文本领域上，如何保证多人协同的编辑器性能、在`CAP`理论下如何做取舍策略、如何保证数据的稳定性可恢复可回溯、光标的同步处理、如何处理`Undo/Redo`等等，都是需要深入研究并且设计的。

在富文本领域中，当前在线文档的主流方案依旧是`OT`，`ShareDB`作者在`2020`年`9`月的文章`CRDTs are the future`中，说明了`CRDT`和`OT`的取舍问题，`OT`最大的问题就是必须依赖中央服务器，那在所有设备之间无缝共享数据就必须依赖于服务器调度数据，而通过`CRDT`来实现就能够做到无需中央服务器来实现数据同步，可能`CRDT`是未来解决一致性问题的一个有力手段。与`OT`一样，在`CRDT`的领域也有很多开源的实现，通过应用`CRDT`基础库为应用带来了奇妙的可能，只需要一个`API`与`Backbone`几乎一样简单的数据`Model`层，应用就能自然地获得对多人协作场景下并发更新的支持，在这里推荐两个`CRDT`实现，`automerge https://github.com/automerge/automerge/`与`yjs https://github.com/yjs/yjs`。

## 每日一题

- <https://github.com/WindRunnerMax/EveryDay>

## 参考

- <https://zhuanlan.zhihu.com/p/50990721>
- <https://zhuanlan.zhihu.com/p/424467723>
- <https://zhuanlan.zhihu.com/p/452980520>
- <https://zhuanlan.zhihu.com/p/510797688>
- <https://zhuanlan.zhihu.com/p/425265438>
- <http://www.alloyteam.com/2020/01/14221/>
- <https://www.jdon.com/artichect/crdt.html>
- <https://www.zhihu.com/question/507425610>
- <https://juejin.cn/post/6844903672032264199>
- <https://juejin.cn/post/7049939780477386759>
- <https://josephg.com/blog/crdts-are-the-future/>
- <https://www.zxch3n.com/crdt-intro/design-crdt/>
- <https://my.oschina.net/fileoptions/blog/1819610>
- <https://hal.inria.fr/file/index/docid/555588/filename/techreport.pdf>