鲁班 - 系统设计大全

25.6 CRDT (计数 / 集合 / 寄存器)

一句话

CRDT 让 “任意顺序、重复应用 的结果都一样”：状态型靠 merge 满足交换/结合/幂等，操作型靠因果投递——代价是它只能表达可合并的结构，表达不了 “余额不能为负” 这种约束。

两大类

类型 做法 要求
状态型（CvRDT） 各副本合并状态，merge 满足交换/结合/幂等 状态要能定义成一个 “只增不减” 的偏序集
操作型（CmRDT） 广播操作，按因果序应用 需要可靠、因果有序的投递

四个常用结构

结构 语义 合并方式 局限
G-Counter 只增计数 各副本向量逐项取 max 再求和 不能减
PN-Counter 可增可减 增/减两个 G-Counter 相减 元数据翻倍
2P-Set 只增删一次 存在集 + 墓碑集，删除优先 不能重复添加
OR-Set 可反复增删 每个元素带唯一 tag，删除只删自己见过的 tag 元数据随操作增长
LWW-Register 单值覆盖 时间戳大者胜 依赖时钟（见 23.1 物理时钟与漂移）
MV-Register 单值冲突保留 保留并发写入的多个值，交给应用/用户选 需要冲突解决界面

为什么 “合并” 能保证收敛

状态型 CRDT 的 merge 是一个 join（上确界）：交换律保证 “谁先谁后不影响”，结合律保证 “分批合并等价于一次合并”，幂等保证 “重复收到同一状态不变”。三者合起来，任意网络乱序与重传最终都收敛到同一状态。

表达不了什么

约束 为什么 CRDT 做不到
余额 ≥ 0 并发扣减可能各自合法、合并后为负
唯一用户名 需要全局仲裁，不是可合并结构
库存不超卖 同上，需要 “拒绝” 而不是 “合并”
有序唯一编号 需要全局定序（见 21.x 共识）

这类 “必须拒绝” 的约束，只能靠中心化仲裁（共识/锁）或事后对账。

实测：合并顺序与重复合并都不改变结果

本机 Python 3.14 实测：

结构 操作 结果
G-Counter（3 副本，各 +1、+10、+2） 枚举全部 6 种合并顺序 结果集合 = {36}（唯一）
OR-Set（A 加 x、y；B 加 x 并删 A 的 tag） a∪b 与 b∪a 都是 ['x','y']（一致）
OR-Set (a∪b)∪b（重复合并） 仍为 ['x','y']（幂等）

这三条正是状态型 CRDT 的三个数学性质：交换律（顺序无关）、结合律（分批合并等价）、幂等（重复合并不变）。缺任何一个，网络重传或乱序就会让副本发散。

class GCounter:
    def merge(self, o):                 # 逐副本取 max，满足交换/结合/幂等
        return GCounter.from_v([max(a, b) for a, b in zip(self.v, o.v)])
    def value(self): return sum(self.v) # 求和得到全局计数（只增）

class ORSet:
    def merge(self, o):                 # 每个元素取 tag 并集
        r = ORSet()
        for e in set(self.elems) | set(o.elems):
            r.elems[e] = self.elems.get(e, set()) | o.elems.get(e, set())
        return r

反模式

反模式 后果
用 CRDT 做金额账务 合并出负数，无法对账
元数据不设上限 OR-Set 的 tag 无限增长，内存爆
操作型 CRDT 不保因果序 收敛到错误状态
认为 “最终一致 = 马上一致” 用户看到回跳，体验差

三条铁律

🔑 CRDT 解决 “可合并的冲突”；需要拒绝的约束必须中心化。

🔑 元数据会膨胀：删除/添加都要留 “墓碑/tag”，要设计清理策略。

🔑 能收敛 ≠ 业务正确：合并后的值仍需满足业务语义。

自检

Q1 为什么 G-Counter 只需 “逐副本取 max 再求和”？

▸ 答案：因为每个副本只增不减，其计数值单调递增；合并时取每个副本的 max 就能得到 “每个副本贡献的最大值”，求和即全局总数。这个过程满足交换/结合/幂等，所以任意顺序合并结果一致。

Q2 2P-Set 为什么 “删了就不能再加”？

▸ 答案：因为它用 “墓碑集” 记录删除，且墓碑只增不减。元素一旦进墓碑，就永远处于 “已删” 状态；要支持重复添加，必须用 OR-Set（每个添加带唯一 tag，删除只移除已见的 tag）。

Q3 OR-Set 的元数据为什么会膨胀？

▸ 答案：因为每次添加都会生成唯一 tag 并随元素保存，删除只删除 “本地见过的 tag”。并发添加/删除越多，残留 tag 越多；需要垃圾回收（基于因果稳定时间）来控制。

Q4 购物车用哪种 CRDT 合适？

▸ 答案：OR-Set：并发添加与删除都能正确合并（“加回来” 与 “删掉” 不会互相覆盖错误）。但 “同一商品改数量” 需要额外语义（用 PN-Counter 或 LWW per item），否则会出现 “两次 +1 合并成 1” 的错误。

Q5 什么时候该放弃 CRDT 改用中心化？

▸ 答案：当约束是 “必须拒绝” 而非 “可以合并” 时：库存、余额、唯一键、限额。这类场景需要全局仲裁点（数据库行锁/共识/专用服务）；硬套 CRDT 只会把 “不一致” 推迟到对账时爆发。

Q7 OR-Set 删掉 “自己没见过的 tag” 会发生什么？

▸ 答案：删不掉（在并发合并后元素又回来）——这正是 OR-Set 的语义（add-wins）。如果要 “删了就永远不回来”，得用 2P-Set（墓碑）或给删除加更高优先级，代价是 “删后不能再加”。所以 “并发增删” 的语义必须先和产品确认，不能由实现随便定。

关联