怎么做网络棋牌网站,宜兴做网站哪个好,五金设备网站建设,公共设施建设投资公司网站初探富文本之CRDT协同算法
CRDT的英文全称是Conflict-free Replicated Data Type#xff0c;最初是由协同文本编辑和移动计算而发展的#xff0c;现在还被用作在线聊天系统、音频分发平台等等。当前CRDT算法在富文本编辑器领域的协同依旧是典型的场景#xff0c;常用于作为…初探富文本之CRDT协同算法
CRDT的英文全称是Conflict-free Replicated Data Type最初是由协同文本编辑和移动计算而发展的现在还被用作在线聊天系统、音频分发平台等等。当前CRDT算法在富文本编辑器领域的协同依旧是典型的场景常用于作为实现文档协同的底层算法支持多个用户同时编辑文档不会因为用户并发修改导致冲突而导致结果不一致甚至数据丢失的问题。
描述
Conflict-free Replicated Data Type直译过来就是无冲突的复制数据类型从名字可以看出来CRDT的重点在于无冲突复制和数据类型去掉定语的话就可以得到CRDT是一种数据结构也就是说CRDT是通过数据结构来保证最终一致性的。在分布式系统中不同节点之间的数据复制存在一致性问题即强一致性问题CRDT是作为一种理论来指导如何将原有数据结构设计成在数据复制过程中通向最终一致性的一种新的数据结构。假设此时我们拥有多个副本或者操作如果托管副本的计算机之间没有协调此时进行合并的话则可能导致副本之间的不一致这通常是无法解决的当更新存在冲突时要恢复一致性和数据完整性可能需要部分甚至全部更新的删除。由此CRDT指导我们在有多个副本或者操作进行合并或者更新时使得我们的数据能根据一定的规则自动合并、解决冲突最终达到强一致性的效果。回到富文本协同上文档协同编辑同样可以理解为分布式应用的一种而CRDT通过数据结构的设计保证并发操作数据的最终一致性。简单来说CRDT就是可以在网络中的多个终端上复制的数据结构副本可以独立和并行地更新不需要在副本之间进行协调并保证不会有冲突发生从而保证最终各个副本的内容一致。
在讨论具体的协同算法之前我们探究一下为什么要有协同算法如果没有协同算法的话会出现什么问题以及具体会出现问题的场景。那么假如我们有一个在线的文档应用而我们是一个团队我们有可能对同一篇文档进行编辑既然我们会同时编辑那么就有可能产生冲突。假设文档此时的内容为A此时U1和U2两位用户同时在编辑也就是说这两位都是从文档的A状态开始编辑当U1编辑完成之后文档状态是BU1对文档进行了保存此时U2也写完了文档状态是CU2也对文档进行了保存那么此时文档的状态就是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块钱而是每个账户都各自存储了这个数字在这个分布式系统中我们不考虑安全方面的因素我们只需要最终保证每个人的数据都是一致的即可。
假设某个时刻t1A往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同样也并不仅仅应用在在协同领域当前各种分布式系统和应用均开始尝试CRDTredislabs和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 ∪ BB数据同步到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∈Pa≤a。反对称性: ∀a, b∈P若a≤b且b≤a则ab。传递性∀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的值为11B的值为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增加了1B增加了2那么全量同步数据时如果max(1, 2) 2是不行的因为我们实际上想得到的数据是3。以上虽然我们通过max设计的数据结构是符合了交换律结合律和幂等律但是这个设计与我们的目的是相悖的我们想得到的是一个计数器而不是获得客户端的最大值。
那么一种可行的方案是在每个副本上都使用一个数组保留其它所有副本的值本地更新时只操作当前副本在数组中对应项合并只能修改数组中除了当前副本的其他项目并且对数组每一项求max进行合并在查询时将本地所有副本的值求和即为我们想要的计数器Counter。此时我们有A、B两个客户端共同维护一个计数器初始时两个客户端数据都是0那么A维护的数据是[0, 0]B维护的数据是[0, 0]此时A增加了1B增加了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-SetSet 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/uuidRemove(e)将当前节点上的所有e和对应的tag/uuid都删除这样在Remove(e)同时其它节点又有并发Add(e)的情况下e是能够最终保证添加成功此种语义称为Add wins。接下来我们可以看看这种方式是如何满足交换律、结合律和幂等律的在这里的叙述都是要满足因果一致性来表述的首先对于交换律而言由于tag/uuid是全局唯一的无论是Add还是Remove显然都是可以交换的当然前提是满足因果一致性不满足需要阻塞等待同样还有结合律在满足因果一致性的情况下我们是可以随意对于集合进行结合操作的主要是tag/uuid是全局唯一的并不会出现不一致的问题最后是幂等律我们需要保证因为网络不可靠重新发送的包的tag/uuid与重试前的数据相同那么因为该元素已经实际存在我们并不会重复添加因而这个操作是幂等的。其实类似于我们最初写到的Op-based CounterOp是可交换的并且保证了幂等性所以这也是一种合理的CRDT设计。
最后
由于CRDT是处理分布式系统数据同步问题的通用解决方案所以本文并没有局限于在富文本数据结构的设计而是从分布式数据同步的角度来理解CRDT并且穿插着CRDT在富文本领域上的应用从而让我们能够更好地理解这个数据模型。同样本文介绍的内容也只是冰山一角分布式数据的同步一直以来都是个复杂的问题回归到富文本领域上如何保证多人协同的编辑器性能、在CAP理论下如何做取舍策略、如何保证数据的稳定性可恢复可回溯、光标的同步处理、如何处理Undo/Redo等等都是需要深入研究并且设计的。
在富文本领域中当前在线文档的主流方案依旧是OTShareDB作者在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
