CRDT：无冲突复制数据类型

可视化演示

分布式一致性中的CRDT（Conflict-free Replicated Data Type）。你将学习CR... 切换模式查看不同维度。

分布式协作困境

老王、老李和老张三兄弟各拿一份手工抄写的购物清单。老王写上“鸡蛋”，老李补上“牛奶”，老张写下“酱油”。傍晚三人在客厅对清单，最怕看到这样的局面：老李觉得“鸡蛋”是自己上次划掉的旧项，于是把它抹掉。谁也没错，但老王想买的鸡蛋就这样没了。这个场景和分布式系统遇到的困境一模一样：同一份数据被复制到很多台机器上，每台机器都会收到用户的修改，可机器之间的网络可能延迟、断开，甚至消息反复重发。

在分布式系统里，那份“购物清单”就是数据副本。多台机器同时接受用户写入，叫做“多副本并发写”；机器之间无法实时互通，叫“网络分区”；两边对同一位置写出不同值，就产生了“写写冲突”。最粗暴的解决办法是“最后写入覆盖”：谁的时间戳晚，就以谁为准。可这等于让老李用橡皮擦掉老王的字，另一部分用户的意图被悄悄丢弃。如果系统要求所有副本先协商一致再回复用户，分区期间服务就会不可用——用户体验从“偶尔丢字”变成“直接罢工”。

所以工程师开始思考：是否存在一种数据结构，让并发修改不依赖协商也能安全合并？合并时既不丢字，也不重复计数？这种数据结构要天生具备“宽容”：无论修改按什么顺序到达，最终所有副本都收敛到同一份清单。这就是 CRDT 的出发点。它不解决网络分区本身，而是解决“分区之后，副本重新连通时如何优雅地拼数据”。

三兄弟最后约定：谁都不许擦掉别人新写的那一行，只允许往清单上补充新字。于是这张清单变成了一块无限大的黑板，所有补充最终都会被看到。CRDT 正是用类似的约定，让冲突从源头消失。

最终一致性

三兄弟白天各自采购，晚上合并清单。他们并不要求“下午三点整所有清单必须一模一样”，只要求“晚上大家坐下来交换之后，最终一样”。这种目标叫做最终一致性。在分布式系统中，CAP 定理告诉我们：网络发生分区时，系统必须在“线性一致”和“可用”之间二选一。线性一致要求读操作必须返回最新已确认的写入，这需要等待所有节点回应；一旦网络分区，等待就意味着超时，系统就不可用。

大部分互联网产品选择优先保证可用性（AP），接受“暂时不一致，最终收敛”。CRDT 正是 AP 路线上的利器：每个节点独立处理本地写请求，不同步时也不阻塞；当网络恢复，节点之间用合并操作把状态拼起来，所有副本向同一个终态收敛。CRDT 并不承诺“多快收敛”，它只保证“如果消息足够多次重试、传播最终完成，那么收敛一定会发生”。

三兄弟不需要每时每刻知道对方买了什么，只要最终对清单达成共识，今晚的菜就能备齐。最终一致性不是“妥协”，而是分布式系统在可用性约束下的明智契约。

CRDT 核心思想

三兄弟的约定之所以有效，是因为“补充新字”这个操作遵循三条朴素的规则：先补后补都一样、几个人分头补最后合起来也一样、同一句话誊写两遍不会让东西变成两份。这三条规则在数学上分别叫交换律、结合律、幂等律，它们构成了 CRDT 的灵魂。一个合并操作如果同时满足这三条性质，无论消息以什么顺序、什么分组、重复多少次到达，最终结果都一样。

这三条性质让 CRDT 拥有了一个宝贵能力：不需要中央协调器。每个节点只要把自己看到的最新状态丢给邻居，邻居合并后再传给下一个，整个网络就能收敛到一致。回到购物清单的比喻：三兄弟不需要请一个裁判坐在中间指挥“谁先写谁后写”，只要人人遵守“只补不删”的规则，黑板上迟早会有所有条目。

计数器集群

购物清单解决“记了什么”，计数器要解决“记了多少”。假设三兄弟合用一个家庭账本，记录买菜的笔数。老王买了三样，老李买了五样，两人在各自的账本上写下一个总数。合并时如果直接相加，3 加 5 等于 8，看起来没问题；但如果老王又买了两样，账本从 3 变成 5，老李的账本也从 5 变成 8，两份账本都带着历史总额，再合并就会把老李买过的 5 样重复计算。问题出在“总数”不是单调的局部记录，它包含了别人的贡献。

G-Counter（增长计数器）的解法是：每个节点只维护属于自己的那一个“小隔间”计数，别人不能往你的隔间里写。合并时，对每个隔间取最大值，而不是对总数求和。这样 A 的隔间永远是 A 自己加过的次数，B 的隔间永远是 B 自己加过的次数，总值就是所有隔间之和。

G-Counter 只能加不能减，一旦要扣账就麻烦了。PN-Counter（正负计数器）想了个巧妙的办法：准备两本账本，一本只记买入（P 计数器），一本只记退货（N 计数器）。买入一本用 G-Counter 单调递增，退货一本也用 G-Counter 单调递增，最终余额等于 P 的总值减去 N 的总值。退货不是“擦掉一笔买入”，而是在另一本账本上“加一笔退货”，两本账本都只增不减，因此合并依旧无冲突。这就像三兄弟约定：想退掉鸡蛋，不是把鸡蛋从清单上擦掉，而是另外写一行“鸡蛋 -1”；晚上合并时，把加的总数和减的总数分别加起来，差值就是最终答案。

集合与映射

现在购物清单需要支持“删除”。老王写了鸡蛋，后来发现自己记错了，想把鸡蛋划掉；可同时老李又往清单上补了一行鸡蛋。划掉还是保留？如果直接擦除，老李的补写可能被误伤。OR-Set（观察删除集合）用了一个聪明的办法：每个元素不是一个孤零零的字符串，而是一个带着唯一标签的个体，例如“鸡蛋#老王-3”。删除的时候，只删除自己当前看到的那几个标签；如果别人并发添加了新的“鸡蛋”标签，那个标签是不受删除影响的。

合并 OR-Set 时，集合取并集。A 删掉“鸡蛋#A-1”，B 添加“鸡蛋#B-1”，合并结果是两个标签都在。A 再删一次只能删掉自己见过的标签，删不掉 B 刚创建的标签。这样“删了又加”的需求被正确表达为“旧标签已删，新标签仍在”。这种机制称为“墓碑删除”：被删掉的标签不会消失，而是留在集合里当墓碑，防止别人又把它合并回来。代价是状态会不断增长，墓碑越来越多，工程上需要周期性清理。

LWW-Map（最后写入获胜映射）是另一种思路：每个键值对都附带一个时钟值，合并时谁的时钟大就保留谁。它本质上是“按键粒度的最后写入覆盖”，不会出现整个文档被一份旧版本覆盖的悲剧。这里的关键是时钟不能用普通的墙上时间，因为各机器时钟可能漂移；实践中常用 Lamport 时钟维护偏序关系。

回到购物清单：OR-Set 是“划掉我见过的那一行字，别人新写的同一物品仍保留”；LWW-Map 是“同一栏里谁最后写就听谁的”。没有哪种绝对更好，只有哪种更贴合业务语义。

合并传播协议

三兄弟的清单要如何汇聚到一起？可能是老王直接拿着自己的清单去老李家，也可能由老张当中间人传递。传播路径五花八门，但最终清单必须一致。CRDT 的传播协议主要分两类。第一类是状态合并：每隔一段时间，节点把自己的完整状态发给邻居，邻居执行 merge 后再继续传播。这种模式实现简单，不怕消息丢失——丢了就等下一次全量状态，反正 merge 是幂等的。缺点也明显：状态可能很大，尤其 OR-Set 攒了一堆墓碑时。

第二类是操作传播：节点只广播“我做了哪个操作”，比如“在集合里添加标签 X”。操作日志更节省带宽，但依赖可靠传输，如果一条操作丢失，后续合并就会缺项。两种模式都必须遵守同一条底线：合并规则要满足交换律、结合律、幂等律，否则传播顺序一变，结果就变。

要理解什么叫“顺序变了也没关系”，需要引入因果序的概念。如果事件 \(a\) 发生在事件 \(b\) 之前，我们记为 \(a \prec b\)；同一进程内先发生的事件、或通过消息传递被对方感知到的事件，就构成这种偏序关系。两个互不可见的事件是并发的，CRDT 必须让并发事件也能确定性地合并。

购物清单的传播也一样：老张收到老王的清单后加上了自己的条目，这个过程就形成了因果链；而老李在自己本子上写酱油，与老王写鸡蛋互不知晓，两者并发，合并时谁先谁后无所谓。因果序帮我们判断“哪些操作必须保持顺序，哪些顺序可以自由调整”，这正是 CRDT 合并正确性的根基。

工程实施取舍

终于到了把 CRDT 放进真实系统的时刻。选型第一条：业务能否容忍最终一致？如果能，CRDT 是很好的答案；如果必须线性一致，比如转账交易，那应该考虑 Raft 这类强一致协议，而不是强行套用 CRDT。第二条：数据形态是什么？计数类选 PN-Counter，集合类选 OR-Set，键值配置类选 LWW-Map，复杂文档可以组合多个 CRDT。第三条：状态合并还是操作传播？状态合并抗消息丢失、实现简单，但状态会无限膨胀；操作传播省带宽，但要求可靠通道。

工程上还需要关注状态大小。以 G-Counter 为例，每个节点都要在状态向量里占一个分量，节点数越多，状态越大。若节点数为 \(n\)，每次合并都要遍历整个向量，因此合并代价也是 \(O(n)\)。

典型落地方案里，CRDT 已经活跃在在线协作文档中：每个人在本地维护一份文档片段，光标移动、字符插入都作为操作广播，断网重连后与其他人的片段合并；在视频观看量统计中，边缘节点用 PN-Counter 各自累加，定期汇总；在多端购物车场景中，OR-Set 让手机和电脑上的增删操作合并成一台购物车。选对模型，CRDT 就像一张永远不吵架的购物清单；选错模型，再精妙的合并也会变回一场混乱。

AI 应用场景

Python 演示

class GCounter:    def __init__(self, node_id):        self.node_id = node_id        self.counts = {}     def increment(self, delta=1):        self.counts[self.node_id] = self.counts.get(self.node_id, 0) + delta     def value(self):        return sum(self.counts.values())     def merge(self, other):        merged = GCounter(self.node_id)        for key in set(self.counts) | set(other.counts):            merged.counts[key] = max(self.counts.get(key, 0), other.counts.get(key, 0))        return merged  class PNCounter:    def __init__(self, node_id):        self.p = GCounter(node_id)        self.n = GCounter(node_id)     def increment(self, delta=1):        self.p.increment(delta)     def decrement(self, delta=1):        self.n.increment(delta)     def value(self):        return self.p.value() - self.n.value()     def merge(self, other):        result = PNCounter(self.p.node_id)        result.p = self.p.merge(other.p)        result.n = self.n.merge(other.n)        return result  def main():    a = GCounter('A')    b = GCounter('B')    a.increment(3)    b.increment(5)    a_merged = a.merge(b)    b_merged = b.merge(a)    assert a_merged.value() == b_merged.value() == 8    assert a_merged.merge(b_merged).value() == 8    print("G-Counter 合并结果:", a_merged.value())     pa = PNCounter('A')    pb = PNCounter('B')    pa.increment(3)    pb.increment(5)    pb.decrement(2)    merged_pn = pa.merge(pb)    assert merged_pn.value() == 6    print("PN-Counter 合并结果:", merged_pn.value())  if __name__ == '__main__':    main()

1. self.counts = {}每个节点的状态是一个字典，键是节点编号，值是该节点的本地累计值，相当于“专属隔间”。
2. self.counts.get(self.node_id, 0) + delta只更新自己的隔间，避免把别人的贡献算到自己头上。
3. set(self.counts) | set(other.counts)取两个状态字典的键并集，保证合并时不会漏掉任何一个节点。
4. max(self.counts.get(key, 0), other.counts.get(key, 0))逐位取最大值，这是 G-Counter 合并的核心，也是幂等性的来源。
5. self.p.value() - self.n.value()PN-Counter 的最终值等于买入账本减去退货账本，两本账本都是 G-Counter。
6. assert a_merged.merge(b_merged).value() == 8同一状态合并两遍结果不变，验证幂等性质。

常见误区

面试题