CRDT无冲突复制数据类型深度解析：从数据类型设计到分布式系统的工程实践

引言：无需协调也能一致的复制数据模型

在分布式系统中，"多个副本上的操作能够无协调地并发执行，且最终收敛到一致的状态"——这就是Conflict-free Replicated Data Type（CRDT）所攻克的核心问题。与Paxos/Raft需要多数节点通信才能写入不同，CRDT允许任何副本独立接收操作，写入延迟降至本地IO级别。应用场景包括：实时协作编辑器（Google Docs）、多数据中心复制（Redis Enterprise Active-Active）、移动离线优先应用。

一、理论基础：半格代数

CRDT的数学基础是Join-Semilattice——偏序集合中唯一最小上界（join，记为⊔）。该运算满足：幂等性（a⊔a=a）允许操作重放安全；交换律（a⊔b=b⊔a）允许合并操作以任意顺序到达；结合律（(a⊔b)⊔c=a⊔b⊔c）允许分组合并。状态基CRDT（State-based/CvRDT）要求状态构成单调递增半格，每个状态转移使状态沿偏序向上移动，副本间通过周期性交换状态或delta状态实现同步。操作基CRDT（Op-based/CmRDT）传输操作本身，传输需满足因果一致性。实践中两者常结合：高频操作使用op-based传播，周期性地使用state-based全量对比修复。

二、核心数据类型

G-Counter（Grow-only Counter）：每个副本维护向量P[i]，本地递增P[self]++，合并时各分量取max，最终sum(P)。PN-Counter支持增减：由P（递增）和N（递减）两个G-Counter组合，实际值sum(P)-sum(N)。LWW-Register（Last-Writer-Wins）：保留最大时间戳的写入，使用混合逻辑时钟（HLC）解决时钟漂移。OR-Set（Observed-Remove Set）：每个元素关联唯一tag，添加产生新tag，删除将观察到的tags标记移除，解决重添加问题。

三、序列CRDT：协同编辑核心

RGA（Replicated Growable Array）为每个节点分配逻辑时间戳，insert指定父节点，delete标记逻辑删除保留因果关系。Yjs使用Yet Another Transformation Approach：每个节点有origin、rightOrigin和唯一ID，冲突时使用确定性规则统一排序。Yjs通过State Vector编码仅存增量（减少初始同步带宽90%+），通过Offline Support写入IndexedDB保证断网时的操作历史，是当前性能最好的CRDT实现。OT需要中央服务器协调无法P2P去中心化；CRDT天然去中心化，更适合端到端加密和P2P场景。

四、生产实践与选型

选型判断：CRDT适合"本地优先写入、容忍临时不一致、操作可交换"的场景——计数器、集合、文档协作。CRDT不适合需要线性一致性（银行转账、库存扣减）的场景。混合架构是常见方案：核心数据用Raft保证强一致，协作数据用CRDT保证AP（可用性+分区容忍）。Tombstone积累是CRDT主要工程挑战：协同文档定期snapshot全量状态重置tombstone；分布式数据库使用max-tombstone-ratio动态清理；移动应用以水mark为界剪枝历史。前沿方向：组合CRDT（多操作原子性）、Privacy-Preserving CRDT（端到端加密场景）、Reproducible CRDT（formal verification）。