本文又名：支撑英雄联盟750万同时在线用户的聊天系统底层的crdt是什么？

CRDT 是什么意思？

CRDT是Conflict-Free Replicated Data Types的缩写，直译的话即“无冲突可复制数据类型”。

CAP定理

分布式系统CAP定理

  • Consistency（一致性，所有节点在同一时间的数据完全一致）
  • Availability（可用性，读写服务一直可用）
  • Partition tolerance（分区容错性，部分节点故障系统仍能提供一致可用的服务）

构建分布式系统时，这三者只可以同时选择两样。

2000年UCB提出假说，2年后由MIT证明。

怎么选？

将问题转化

  • 分区容错性P 是实际运营的分布式系统所必需的，无法保证所有的节点都不出现故障或者下线
  • 因此，目前分布式系统都在一致性C 和 可用性A 中取舍
保证 名称 说明
一致性C CP System 数据落地即一致，但有时会不可用
可用性A AP System 最终一致性，每次访问数据可能不一致
  • CP系统
    • 为了保持一致性，系统可能出现暂时不可用的情况，比如节点之间正在同步数据，这时候进来的读请求就要排队等一会
    • 分区故障发生时，为了保持一致性，系统只能暂停等待分区故障恢复。
    • 适合对一致性要求高，可以在性能（可用性）上做出妥协，比如电商的秒杀功能（有时写，一直读）
  • AP系统
    • 为了保持可用性，在 强一致性, 弱一致性, 最终一致性的一致性等级中，仅保证最终一致性，所谓最终一致性，是指所有节点上的数据合并后得到的结果是一致的
    • 分区故障发生时，为了保证系统可用，放弃一致性。
    • 适合对一致性要求不高，但对性能（可用性）要求高的场景，比如日志系统（有时读，一直写），实时聊天，多人协同编辑
  • CA系统
    • 单机系统

理想的分布式

CP系统的启发

  • Raft等强一致性算法，选举leader统一受理写请求
  • 写请求过多时，不堪重负
  • （集中写，分布读，分布的不够彻底）

理想中的分布式

  • 分布式写请求，极大提高吞吐量
  • 任何节点受理写请求后，通知给系统中所有其他节点更新信息
  • （分布写，分布读，彻底的分布）

该架构的问题

该分布式系统中存有1个变量，count

  1. 到达顺序问题
    • 1号请求A节点count=100，2号请求B节点count=99，最终应该count=99
    • 但count=99先到达C节点，count=100后到达C节点，导致C节点的count=100，产生错误
  2. 幂等问题
    • 假设count=100
    • 1号请求A节点count+=1，以为更新失败了，重新请求count+=1，最终应该count=101
    • 由于+=不满足幂等律，count=102，产生错误

问题解决

如果我们找到一种数据结构，它满足交换、结合、幂等律，那么上述顺序问题，幂等问题将不复存在

  1. 交换律 a∨b = b∨a
  2. 结合律 (a∨b)∨c = a∨(b∨c)
  3. 幂等律 a∨a = a

一个CRDT的简单例子

假设系统中存有count = 100，表示100块钱

  • 1号节点存入10块，在它看来，count=110
  • 2号节点取出10块，在它看来，count=90
  • 3号节点，count=100

这就是最终一致的系统，存在不一致的时刻

1号和2号的更新信息发送给3号节点，3号节点并不知道110和90究竟哪个正确，失败

改变数据结构

不存count最终值，存操作

  • 1号节点存入10块，存count+=10
  • 2号节点取出10块，存count-=10

结果

  • 3号节点收到其他节点的通知时，即可通过count = 100+10-10 = 100，计算出最终正确结果，而且不同节点的到达顺序不影响最终结果，满足交换律和结合律
  • 进一步优化，比如说给每个操作加一个时间戳，包含相同时间戳和操作的通知只处理一次，满足幂等律

此时，同时满足交换律，结合律和幂等律，我们得到了CRDT

CRDT的几种结构

G-Counter(Grow-only Counter)

该数据结构实现了+运算

  • n个node
  • payload是长度为n的数组
  • update函数负责+1
  • merge函数负责合并两个node的payload
  • compare函数负责merge时选择哪个node的P[i]
  • query函数负责计算v值，sum(P[i])

减运算怎么办？

PN-Counter (Positive-Negative Counter)

该数据结构实现了+/-运算

字符串运算怎么办？

G-Set (Grow-only Set)

实现了字符串add()操作

  • merge函数直接取两个set的并集，只能添加不能删除
  • OrbitDB底层基于G-Set，其将常用的数据结构转化成字符串记录在G-Set中，比如说Orbit支持的Key-Value结构本质上也是G-Set实现的

字符串删除怎么办？

2P-Set (Two-Phase Set)

实现了字符串的add()和remove()操作 img-w500

再加一个Set，记录被删除的字符串，query的时候取差集

删了又想加回来怎么办？

LWW-Element-Set (Last-Write-Wins-Element-Set)

与2P-Set很像，add()和remove()操作加时间戳，字符串在add和remove集合中都存在时，究竟是否存在取决于最晚的时间戳

出现相同时间戳怎么办？ 可以设置bias，bias toward add or remove

OR-Set (Observed-Removed Set)

与LWW-Element-Set很像，时间戳替换为唯一标识（tags），query时add tag set 减去 remove tag set，仍然非空，则该数据存在

OrbitDB如何实现在线聊天

OrbitChat
OrbitDB
ipfs-log
ipfs/Pubsub
  • OrbitDB是一个基于ipfs的新型分布式数据库
  • OrbitDB实现log, feed, keyvalue, docs, counter等常用数据结构
  • ipfs-log实现G-Set
  • ipfs的Pubsub目前是实验性功能，实现publish-subscribe发布订阅模式

工业界应用

  • SoundCloud open-sourced Roshi, implemented a LWW-element-set CRDT on top of Redis.
  • Riak is a distributed NoSQL key-value data store based on CRDTs.
  • League of Legends uses the Riak CRDT implementation for its in-game chat system，7.5 million concurrent users and 11,000 messages per second

总结

  • 空间换时间
  • 一个优美的，有特定适用场景的分布式同步算法
  • 并不是银弹

参考

  1. What is CRDT

  2. Defanging Order Theory

  3. Wikipedia