文章插图
我是前端西瓜哥 ， 今天我们来简单入门一下 CRDT 。
CRDT 是什么？CRDT，全称为 conflict-free replicated data type（无冲突复制数据类型），它是一种数据类型，或者说是方案，确保在网络中的不同副本最后数据保持一致的，可以用协同编辑领域 。
CRDT 在 2011 年在论文中被正式提出 ， 虽相比 OT 算法（1989年）起步晚了很长的时间，但实现难度低很多 ， 且出现了高性能的 CRDT 库 Y.js，越来越多产品选择使用 CRDT 来实现协同编辑功能 。
CRDT 有以下特性：
每个客户端可独自操作副本，即支持并发，不需要和其他副本协同沟通 。
这是一种乐观复制（Optimistic replication）的策略 。
各个副本可以独立地在本地编辑 ， 不用把更新提交到服务器，等待服务端返回最新的状态，用这个新状态覆盖掉旧状态 。即可做到离线编辑，本地更新了状态后再同步到服务端 。
算法能够自动地处理不一致的问题 。
一个副本和另一个副本通常是不同的，当其他副本同步过来时，有可能会出现冲突（不一致）的地方 ， 比如两个副本同时删除和新增一个元素 。
这个需要 CRDT 算法使用特定的策略去自动处理，而不是像 git merge 那样去手动处理冲突 。
同一时刻不同副本的状态可能不同，但同步后它们能最终收敛（converge），达到相同的状态（最终一致性） 。
CRDT 的类型CRDT 主要分为两大类型：Operation-based 和 State-based 。
Operation-basedOperation-based CRDTs ， 基于操作的 CRDT 。
副本进行同步时，只会把 新增的本地操作（operation） 发送出去 。
另一个副本拿到这个 operation 会将其应用到自己的状态上 ， operatAIon 需要满足交换律（commutative） 。
交换律，指的是交换运算顺序，最后的结果不变 。比如加法就满足交换律 ， a+b 和 b+a 的结果是相等的 。
operataion 之所以要满足交换律 ， 是因为网络并不可知 。
假设有两个副本 a 和 b 要同步过来给其他副本，你不知道到底谁先到达 。对于一些副本可能是先 a 后 b，另一些可能是先 b 后 a ， 我们需保证在不同顺序下，结果是一致的 。
通常我们是通过 Generator 函数生成新的 opreation ， 发送给其他副本，然后这些副本通过 Effector 函数应用这些副本 。
因为交换律这个特性，Operation-based CRDTs 还有另一个名字 commutative replicated data types（CmRDTs） 。
基于操作的 CRDT 的优点是 ， 传输的数据量较少 。
State-basedState-based CRDTs，基于状态的 CRDT 。
一个副本进行同步时，会将 整个完整的本地状态（state） 发送出去 。另一个副本需要支持将其他副本进行合并（merge）的操作，这个 merge 方法需要满足交换律、分配律，以及幂等性 。
基于状态的 CRDT 的问题是，在文档很大时，需要传输大量的数据，会耗费大量的带宽，且花费时间长 。所有实际生产很少会使用它 。
优点是实现更简单，如果数据量不大，是可以考虑使用的 。
State-based CRDTs 同样也有另一个名字：Convergent Replicated Data Types（CvRDTs） 。Convergent 是收敛的意思 。
一些 CRDTCRDT 做到数据最终一致性，是基于数学上的特性来保证的 。
我们来看几个简单的 CRDT 模型 。
AWSetAWSet（Add-wins set），一种新增优先于删除的集合数据结构 。
假如刚开始的时候，副本 A 和 副本 B 的状态是一致的，有一个 a 在集合中 。
副本 A 删除了 a，然后再新增 a 。
副本 B 删除了 a 。
副本 A 的新增 a 和 副本 B 的删除 a 同时发生 。
此时我们会选择新增，忽略删除，最后两个副本的状态还是 a 在集合中 。
文章插图
为判断两个操作是否是 “同时” 的，我们会附加一个和时序相关的元数据，比如时间戳、版本向量 。
RWSetRWSet（Remove-win set），一种删除优先新增的集合数据结构 。
AWSet 类似，但对于并发的操作，会保留删除，丢弃新增 。
LWWLWW（Last-writer-wins），最后写入者优先 。
所有的操作会有一个时间戳元数据，副本会对比同步操作的时间戳 。
如果大于当前状态时间戳，覆盖掉原来的状态；如果小于当前状态时间戳，则忽略 。
2P-SetTwo-Phase Set 。
推荐阅读
- 37岁刘亦菲拍大片彻底放飞！穿红色上衣半穿半露又纯又欲，火辣的像换了个人
- 李小璐又出事了？这一次娱乐圈竟然集体闭嘴
- 古巨基的“清醒”，彻底扯下了《声生不息》的遮羞布
- 这一次，殴打赵露思扇嘴巴的“公司老板”，如今底裤快被扒光了
- 何捷转业成保安，年薪曝光差距立显，这下，张馨予彻底输了
- 被爆当小三的吉克隽逸，人设算是彻底崩塌了，三观尽毁！
- 一天一个猛料，资本圈杀人不见血，这一次，张颂文还能撑得住吗？
- 这一次，40岁的叶一茜，终是为她的“重男轻女”买了单
- 31岁孙怡彻底放飞了，穿衬衫忘记扣扣子，急忙用手遮挡掩饰尴尬！
- 第一集就上尺度，国民第一初恋，彻底黑化