无冲突复制数据类型

破除误解：无冲突不是没有并发，更不是替代共识#

「无冲突」容易被读成「不会有并发更新」。恰恰相反：CRDT 假定并发是常态。它保证的是合并函数不会因为到达次序而分叉出不可调和的状态，不是保证业务语义符合你的直觉。两个副本同时把库存减一，G-Counter 式的求和会变成减二；若业务要的是「只准卖一份」，那是线性化库存，需要协调或至少一次原子校验。CRDT 解决的是会合，不是库存会计。

第二个误解是：有了 CRDT 就不需要共识。共识（Paxos、Raft）提供全序与线性化。当你需要全局唯一的序号、唯一领导者、一次选举一个值，仍要共识。CRDT 覆盖的是单调、可交换的更新：计数器只增、集合只加、序列用稠密标识插入。CALM 定理（Consistency as Logical Monotonicity）把这条界说成逻辑：单调查询在最终一致的数据上也能给出正确结果；非单调查询（如「还没有」）必须协调。CRDT 是 CALM 在数据类型上的工程对应物，不是共识的坟墓。见 分布式共识算法。

第三个误解来自产品文案。把任意 JSON 同步都叫做 CRDT，会把 OT、中心化操作日志、以及「有一台服务器做合并」混在一起。真正的 CRDT 必须指明：状态型还是操作型、半格是什么、删除如何避免复活。没有这些，只是同步。

两种形态：状态型半格与操作型广播#

状态型 CRDT（CvRDT）把本地状态做成一个半格（join-semilattice）。副本之间发送完整状态或增量，合并函数 $\sqcup$ 必须幂等、交换、结合。收到任何副本的状态，与本地做 join，得到上确界。因果送达不是必须的，因为 join 自己消化乱序与重复。代价是状态可能变大：墓碑、向量、元数据会留下。

操作型 CRDT（CmRDT）广播更新操作。操作必须在「恰好一次、因果有序」的可靠广播下可交换（或设计成对并发可交换）。实现更轻，但对通道要求更高：丢失一条增量，会合就停。实务里常用混合：本地把操作压成状态增量再发，既保留半格证明，又避免每次送整棵树。

夏皮罗等人的目录给出一组可组合的原子：G-Counter、PN-Counter、G-Set、2P-Set、OR-Set、LWW-Register、LWW-Set，以及序列上的 RGA。后续的 JSON CRDT、无墓碑压缩、delta-CRDT，都是在同一半格叙事上减元数据。

计数器、集合与序列：三个标准例子#

G-Counter（只增计数器）最干净。每个副本 $i$ 只在自己的槽位上加。状态是向量 $v$，合并取逐分量最大。查询是各分量之和。它显然是半格：分量的 $\max$ 是上确界。PN-Counter 用一对 G-Counter 表示正负，才能减。没有「先减后加」的全局时间，只有两份只增历史。

OR-Set（Observed-Remove Set）针对「加和删并发」的经典坑。朴素 2P-Set 里，删过的元素不能再加入。OR-Set 给每次添加一个唯一标签（常是副本标识加序号），删除只移除自己观察到的那些标签。并发的「加」与「删」时，未观察到的添加会留下，元素还在——「添加获胜」是被规定的会合语义，不是bug。墓碑（已删标签）必须保留足够久，否则迟到的添加会让元素复活。这是 CRDT 用空间换会合确定性的典型账单。

RGA（Replicated Growable Array，Roh 等人 2011 前后）给序列编辑。每个字符（或原子）带一个标识，标识在副本间用点号或混合逻辑钟生成，全序扩展因果序。插入挂在某个已有标识之后；删除打墓碑。并发在同一位置插入时，用标识次序打破平局，避免 OT 那种对操作变换函数的逐条证明。代价仍是墓碑与标识体积。树结构日志（RGATreeSplit）、YATA、Fugue、以及后来的无墓碑序列 CRDT，都在打同一场仗：让文本的并发插入可交换，且空间不随删除历史线性膨胀。

Automerge、Figma 风格与工程现实#

Automerge 把 JSON 文档做成 CRDT：map、list、文本各自用一套会合规则，历史可回放。它让「分支、合并、离线」看起来像 Git，但合并是自动半格，而不是三路文本合并。Git 的合并可以冲突停止；CRDT 的合并必须给出一个值。产品若需要「让人看冲突」，要在半格之上另做意图层。

Figma 公开过其多人协同的设计：并不是把整份文件当成一个学术目录里的现成 CRDT，而是把画布对象的属性做成可独立会合的寄存器与列表，并在需要全序的地方保留中心化排序。这是工业界的典型折中：能半格的字段半格，必须全序的字段走中心或共识。把「Figma 用了 CRDT」理解成「整个产品没有协调」，会过度阅读。正确的句子是：协同编辑的许多字段满足单调更新，于是可以避免为每一次拖拽开一轮 Raft。

Delta-CRDT（Almedia 等）只发送自上次确认以来的增量，减轻状态型广播的带宽。无墓碑方案用压缩、过期和因果稳定性证明「不会再有迟到的添加」，才能丢掉删除记录。没有稳定性证明就删墓碑，等于重新引入复活。工程上的 CRDT 失败，多半不是半格证错，而是元数据协议与成员变更没写完。

CALM 与共识的边界#

赫勒斯坦与 Alvaro 的 CALM 说：一个分布式程序若其规范是逻辑单调的，则不需要额外协调就能在最终一致的输入上得到正确输出。集合的并、计数器的和、可达性，是单调的；「尚未收到」「恰好一次」「全局第 $k$ 名」，不是。CRDT 把单调更新封装成数据类型，让程序员少写协调。非单调出现时，必须引入屏障、事务或共识。

因此 CRDT 与共识是互补。成员资格、一次性选举、跨分片的原子提交，仍落在共识一侧。CRDT 内部的唯一标识生成，往往假设副本标识唯一——而这唯一性本身可能来自配置服务，也就是轻量共识。宣称「我们用 CRDT 所以没有单点」，要检查标识、成员和删除稳定性从哪来。

与线性化寄存器相比：LWW-Register 是 CRDT，它用时间戳（或逻辑钟）做 join，并发时丢掉其中一个值。它会合，但不保护「读到最新写入」。需要线性化时，应使用共识复制的寄存器，而不是给 LWW 加上更炫的名字。

操作变换为何被半格替代#

协同编辑的上一代标准是操作变换：把针对同一文档状态的插入、删除改写成对「已经应用过其他操作的状态」仍有意义的操作。OT 的正确性依赖一组变换函数满足交换与结合的代数恒等式（常被写成 TP1/TP2）。实践中每增加一种操作——加粗、表格、嵌套列表——都要重做这组恒等式，遗漏一条就会在特定交错下分叉。CRDT 把文档状态本身做成可 join 的对象，操作只负责推进半格，不再对「对方刚做了什么」做即时改写。RGA、WOOT、Logoot、LSEQ 都是序列上的这一思路：用标识而不是用整数下标，避免「删除第 5 个字符」在并发下指向不同字节。

Logoot 与 LSEQ 用稠密全序（有理数或变长数字串）在两字符之间插入新标识，避免 RGA 那样把已删字符长期留作锚点。它们仍是 CRDT：并发插入的标识可比较，join 是按标识排序。代价是标识长度可能随反复「在缝里再插缝」而增长，需要间歇重编号。RGA 的墓碑与 Logoot 的变长标识是同一空间账单的两种付法。Automerge 的文本层采用类似标识序列的变体，JSON 的 map 则用每键一个 LWW 或每键一个子 CRDT。组合规则必须写明：对同一键的并发赋值，是 LWW 还是「变成冲突值列表」。Automerge 选择可追踪的冲突对象，而不是静默 LWW，为的是让应用层决定意图。这已经超出纯半格——半格保证会合到某一状态，应用层决定那一状态是否展示为冲突。

成员、纪元与增量#

CRDT 论文常假设固定的副本集合。真实系统有节点加入、退出、崩溃后换磁盘。副本标识若被重用，OR-Set 的标签会撞车，删除可能删错一次添加。成员变更协议因此不是外围：它给每个纪元一套标识，并在纪元切换时把旧墓碑压缩进快照。delta-CRDT 只发送「自对方上次确认以来我半格里新的部分」，确认本身是因果上的进度向量。进度向量的维度又随成员数增长，于是又要有成员垃圾回收。这条链说明：无冲突合并把协调从「每次写入」推迟到「成员与垃圾」，并没有把协调从系统里蒸发。

部分复制把问题再推进一步。只同步文档的一棵子树时，缺失的祖先标识可能让序列 CRDT 无法放置新节点。Merkle 树可以比较哪些子半格不同，但不能凭空补上没收到的锚点。产品要么禁止在未物化的子树上编辑，要么把锚点做成可从内容哈希重建的结构。Figma 风格的「对象标识全局唯一、属性独立会合」绕开了文本序列的锚点问题，却把「对象创建」的唯一性重新交给标识生成。设计选择是数据类型形状，不是一句「我们是 CRDT」。

因果序与日历时间必须分开。混合逻辑钟可以给 LWW 一个近似的「谁更晚」，但它不是半格的替代：时钟回拨、分区两侧各自前进，仍可能让后发生的写入带上更小的戳。状态型 CRDT 用 join 消化乱序，不依赖谁的钟快。操作型 CRDT 若用 Lamport 时戳当唯一序，并发操作会被强行排成全序，于是退化成「用时钟做共识」。正确的操作型设计是：并发操作必须真正可交换，时钟只用来生成唯一标识，不用来当全局裁判。日历时间进半格之日，就是会合语义变成「最后写入获胜」并接受丢更新之日。混合逻辑钟可以作为唯一标识的来源，只要比较规则仍是「并发则保留双方、用标识打破平局」，而不是「较大的戳覆盖」。OR-Set 的标签通常正是副本加计数器，并不读取墙钟。墙钟一旦进入比较器，半格证明就要把时钟单调性写进假设，而真实时钟不提供这条假设。标识生成用计数器即可，不必借用物理时间来伪装全序。半格要的是可交换的 join，不是一张全序时间表。用墙钟排序并发更新，等于把 CRDT 退回最后写入获胜，并重新引入丢更新与虚假冲突。

代价与争议#

元数据是第一代价。OR-Set 的标签、RGA 的墓碑、向量钟的维度，都随副本数和操作历史增长。压缩需要因果稳定或纪元，而稳定性又需要某种对「不会再有更早消息」的判断——这常常悄悄把协调从合并函数搬到成员协议。

语义是第二代价。会合语义由半格规定，不一定等于用户意图。购物车里「删一件」与「加一件」并发，OR-Set 的添加获胜可能让已删商品回来。要「删除获胜」就要换半格，于是另一种意图被牺牲。没有一种集合 CRDT 同时满足所有自然语言里的「加」「删」。

证明与实现的缝是第三代价。论文中的可靠因果广播，在真实 UDP、NAT、部分复制、只同步子文档时并不免费。部分复制下，半格的全局上确界可能根本不在任何一台机器上。研究线（如 Merkle-CRDT、局部 join）仍在追赶产品里「只同步一棵子树」的需求。

日历与在线协同还暴露第四代价：意图保存（intention preservation）与会合并不自动相同。操作变换（OT）走另一条路，要在并发编辑上保持用户意图，证明更碎。CRDT 用半格换掉 OT 的变换函数，换来的是元数据与「哪种并发胜出」必须预先写进类型。产品选 CRDT，不是因为它没有代价，是因为会合证明更好写、对等同步更好做。

跨域连接#

• 范畴论：状态型 CRDT 的合并是 join-半格上的上确界，也就是一个幂等交换幺半群。把数据类型看成对象、把 join 看成态射的合成，收敛就是任意有限更新集都有上确界。范畴语言在这里不是装饰：它解释为什么组合若干 CRDT 仍是 CRDT——因为半格的积仍是半格，而不是因为实现碰巧没撞车。
• 组合学：OR-Set 的标签、RGA 的稠密标识，都是在给并发操作分配可全序扩展的偏序编码。标识空间必须可插、可比较、且几乎不碰撞。序列 CRDT 的正确性，很大一部分是组合设计而不是网络协议：平局如何打破，决定了「同一位置的两次插入」会合后的唯一结果。
• 证明：CRDT 论文的核心证明是：半格性质 ⇒ 强最终一致性（在公平送达下）。证明依赖的是代数恒等式，而不是「最终会选出领导者」。阅读时要核对假设：操作型还要求因果广播；丢掉这条假设，交换律不足以推出会合。证明停在哪个通道模型，实现就必须提供哪个通道。
• 信息哲学：CRDT 把「何为同一份文档」从中心时间线改写成「所有副本 join 之后的上确界」。知识不再是某台机器上的当前值，而是半格里尚未完全会合的一组观察。这逼问：在分区期间，是否存在「真状态」，还是只有各副本的局部上界。CALM 给出计算侧的回答——对单调问题，真值就是最终的上确界；对非单调问题，没有协调就没有全局事实。

参考文献#

• Shapiro, M., Preguiça, N., Baquero, C. & Zawirski, M. "Conflict-Free Replicated Data Types." SSS, 2011; INRIA Research Report RR-7687, 2011.
• Shapiro, M. et al. "A Comprehensive Study of Convergent and Commutative Replicated Data Types." INRIA RR-7506, 2011.
• Roh, H.-G., Jeon, M., Kim, J.-S. & Lee, J. "Replicated Abstract Data Types: Building Blocks for Collaborative Applications." Journal of Parallel and Distributed Computing 71(3):354–368, 2011.
• Hellerstein, J. M. & Alvaro, P. "Keeping CALM: When Distributed Consistency is Easy." Communications of the ACM 63(9):50–59, 2020.
• Almeida, P. S., Shoker, A. & Baquero, C. "Delta State Replicated Data Types." Journal of Parallel and Distributed Computing 111:162–173, 2018.

延伸阅读#

• Preguiça, N. "Conflict-Free Replicated Data Types: An Overview." arXiv:1806.10254, 2018.
• Kleppmann, M. Designing Data-Intensive Applications. O'Reilly, 2017. 第五章（复制）中关于 CRDT 与多主复制的讨论。