背景

在数字时代，Google Docs、Figma、Notion 等实时协作工具已成为我们工作和生活的一部分。我们能够看到同事的光标在屏幕上跳跃，他们的修改近乎瞬时地出现在我们的屏幕上。这背后流畅体验的核心技术之一，就是 CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）。

简单来说，CRDT 是一种“天生乐观”的数据结构。它从数学上保证，当多个用户在不同设备（副本）上独立、并发地修改数据时，即使没有中央服务器的协调，这些修改最终也能以一种确定的、无冲突的方式合并，并让所有副本达到完全一致的状态。

CRDT 之所以能解决实时协作的冲突，关键在于其独特的设计哲学：与其解决冲突，不如从设计上避免冲突。

两大核心原则

CRDT 实现这一目标主要依赖两个核心原则：

• 操作的幂等性 (Idempotent)：重复执行同一个操作，结果与执行一次完全相同。例如，将一个元素添加到一个集合中，无论执行多少次“添加”操作，该元素都只在集合中存在一份。

• 操作的交换律 (Commutative)：操作的执行顺序不影响最终结果。A + B 和 B + A 的结果是一样的。这意味着系统无需关心操作到达的先后顺序，极大简化了分布式系统的设计。

当所有操作都满足这些特性时，无论网络延迟多高、操作顺序多乱，只要所有副本最终都接收到了相同的操作集合，它们就能自行计算出完全一致的最终状态，即“强最终一致性”（Strong Eventual Consistency）。

CRDT 的两大类型与实例解析

CRDT 主要分为两种类型：基于状态的 CRDT (State-based, CvRDT) 和 基于操作的 CRDT (Operation-based, CmRDT)。

• CvRDT：每个副本在本地更新自己的完整状态，然后将整个状态发送给其他副本进行合并。合并函数必须满足交换律、结合律和幂等性。

• CmRDT：每个副本只将引发状态变更的“操作”（Operation）广播出去。这种方式传输的数据量更小，但要求通信层保证操作的可靠传递。

下面通过几个简单的例子，来理解 CRDT 是如何巧妙地避免冲突的。

场景一：共享购物车（集合 CRDT）

想象一下，你和家人正在用一个共享的 App 往购物车里添加商品。

• 2P-Set (Two-Phase Set)：这是最简单的支持“增”和“删”的集合。它内部由两个只能增长的集合（G-Set）组成：一个“添加集”（A）和一个“删除集”（T，也称墓碑集）。

  • 添加商品：将商品ID加入到“添加集” A 中。

  • 删除商品：将商品ID加入到“删除集” T 中。

  • 查看购物车：购物车的最终内容是 A - T（即在添加集中但不在删除集中的所有商品）。

  冲突解决：如果用户 A 添加了“牛奶”，同时用户 B 删除了“牛奶”，会发生什么？

  • A 的操作：A = {牛奶}

  • B 的操作：T = {牛奶}

  • 最终合并后的状态：A = {牛奶}, T = {牛奶}。

  • 购物车内容：{牛奶} - {牛奶} = {}（空）。

    在这种设计下，“删除”操作的优先级更高，一旦一个商品被删除，就不能再被重新添加回来（因为它永远存在于墓碑集中）。

• LWW-Set (Last-Write-Wins Set)：为了解决 2P-Set 不能重新添加的问题，LWW-Set 为每个元素的添加和删除操作都附加一个时间戳。

  • 添加商品：add_set.add({id: "牛奶", timestamp: 10:01})

  • 删除商品：remove_set.add({id: "牛奶", timestamp: 10:02})

  • 查看购物车：一个商品存在于购物车中，当且仅当它在 add_set 中，并且：

    • 它不在 remove_set 中。

    • 或者，它在 remove_set 中的时间戳比在 add_set 中的时间戳要早。

  冲突解决：用户 A 在 10:01 添加“牛奶”，用户 B 在 10:02 删除了“牛奶”，而用户 C 在 10:03 又添加了“牛奶”。

  • 最终合并状态：add_set 中牛奶的时间戳是 10:03，remove_set 中是 10:02。

  • 判断：因为添加的时间戳 (10:03) > 删除的时间戳 (10:02)，所以“牛奶”最终会留在购物车里。这就是“最后写入者获胜”的原则。

场景二：协同编辑文档（序列 CRDT）

协同编辑文本是实时协作中最复杂的场景，因为它不仅要处理内容的增删，还要处理内容的“位置”。如果两个用户同时在同一个位置插入不同的字符，怎么办？

这就是 序列 CRDT (Sequence CRDT) 发挥作用的地方，如 RGA (Replicated Growable Array) 和 Yjs 使用的 YATA 算法。

它们的核心思想是：不使用传统的整数索引（如第 5 个字符），而是为文档中的每个字符（或原子单位）分配一个全局唯一的、不可变的位置标识符 (ID)。

这个 ID 通常由两部分组成：

• 站点ID (Site ID)：每个协作者的唯一标识。

• 逻辑时钟 (Lamport Clock)：一个在当前协作者处单调递增的整数。

冲突解决：同时在同一位置插入

假设文档内容为 "Hi"，用户 A 和用户 B 同时想在 'H' 和 'i' 之间插入内容。

• 初始状态：'H' 的 ID 可能是 (SiteX, 1)，'i' 的 ID 可能是 (SiteX, 2)。

• 用户 A 操作：想插入 "A"。他会生成一个新字符的 ID，这个 ID 必须位于 'H' 和 'i' 的 ID 之间。他广播一个操作：insert('A', after: (SiteX, 1), new_id: (SiteA, 5))。

• 用户 B 操作：想插入 "B"。他也生成一个新字符的 ID：insert('B', after: (SiteX, 1), new_id: (SiteB, 3))。

现在，所有副本都收到了这两个操作。如何决定 "A" 和 "B" 的顺序？

CRDT 会定义一个确定的排序规则。例如，Yjs 的规则是：如果两个新字符都声称在前一个字符之后，那么就比较它们的站点 ID，ID 较大者排在后面。

• 假设 SiteA > SiteB。

• 当 A 的副本收到 B 的操作时，它看到 (SiteB, 3) 和自己的 (SiteA, 5) 都想跟在 (SiteX, 1) 后面。根据规则，B 的站点 ID 更小，所以 B 的内容排在前面。最终顺序是 "HBiA"。

• 当 B 的副本收到 A 的操作时，它也应用同样的规则，得到的结果同样是 "HBiA"。

通过这种方式，即使操作到达顺序不同，所有副本最终都会收敛到完全一致的 HBiA 状态，冲突得以自动解决。删除操作则通过“墓碑”机制实现，即标记一个字符为已删除，而不是真正地从数据结构中移除它。

结论

CRDT 通过放弃强一致性，转而追求最终一致性，并利用精心设计的、满足数学定律的数据结构，从根本上避免了合并冲突。它将冲突解决的逻辑内建于数据类型本身，使得每个副本都能独立、自信地处理本地和远程的修改，最终汇聚成一个统一的、正确的状态。正是这种优雅的设计，才使得我们能够在各种协作软件中享受到如丝般顺滑的实时交互体验。

原理详解

想象一下，你和朋友们在同一份文档上同时编辑，你加了一句话，他删了一个字，另一个人又改了标点。神奇的是，你们看到的文档最终都能保持一致，而且没有谁的修改被“吃掉”或覆盖。这背后，就是CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）在施展“所见即所得”的魔法。

1. 实时协作的“痛点”：为什么会冲突？

在没有CRDT之前，实时协作面临的核心问题是：如何处理并发修改？

• 网络延迟： 你做的修改，需要时间才能传到别人的电脑上。在这段时间里，别人可能也做了修改。

• 并发操作： 两个人同时在文档的同一个位置进行操作（比如你插入，他删除）。

• 最终一致性： 如何保证所有人的文档最终都能变成同一个正确版本？

传统的解决方案，比如“最后写入者胜出”（Last Write Wins），会导致数据丢失；或者需要一个中心服务器来协调所有操作，一旦服务器挂了或者网络断了，就无法工作。

2. CRDT的“魔法”核心：操作的“可交换性”

CRDT的魔法在于它设计了一套特殊的数据结构和操作规则，使得无论操作的顺序如何，最终的结果都是一样的。这就像数学里的加法：1 + 2 + 3 和 3 + 1 + 2 结果都是 6。

CRDT的核心思想是：把每一次修改都看作一个独立的、可合并的“事件”，而不是直接修改最终状态。

想象一下，你不是直接修改文档，而是给文档发送“指令”：

• “在第5个字后面插入‘你好’。”

• “删除第3个字。”

这些指令，无论以什么顺序到达，都能被正确地应用，并且最终文档会达到一个确定的、无冲突的状态。

3. CRDT的“魔法成分”：三大特性

为了实现这种“可交换性”，CRDT需要满足以下三个关键特性：

1. 交换律 (Commutativity)： 两个操作的执行顺序可以互换，结果不变。

   • 例子：你“添加A”，我“添加B”。无论谁先谁后，最终文档里都会有A和B。

2. 结合律 (Associativity)： 多个操作的组合方式可以改变，结果不变。

   • 例子：(添加A + 添加B) + 添加C 和 添加A + (添加B + 添加C) 结果一样。

3. 幂等性 (Idempotence)： 同一个操作执行多次，效果和执行一次一样。

   • 例子：你“删除X”，我收到并执行了。如果我再收到一次“删除X”的指令，它不会产生新的副作用，文档状态不变。

4. CRDT如何解决冲突：两种主要流派

CRDT主要分为两大类，它们实现“无冲突”的方式略有不同：

a. 基于状态的CRDT (State-based CRDTs / CvRDTs)

• 原理： 每个客户端维护一份完整的本地数据状态。当有修改时，客户端会把自己的最新状态（或者状态的摘要）发送给其他客户端。其他客户端收到后，会用一个特殊的“合并”函数，将收到的状态与自己的本地状态进行合并。

• 核心： 合并函数必须满足上面提到的交换律、结合律和幂等性。

• 通俗理解： 就像大家都在画一幅画，你画了一笔，就把你画完的整幅画拍个照发给别人。别人收到后，会把你的画和自己的画“叠加”起来，确保所有笔触都在。

• 优点： 简单粗暴，即使消息丢失，只要最终状态能到达，就能保证一致性。

• 缺点： 传输的数据量可能比较大（因为要传整个状态或其摘要）。

b. 基于操作的CRDT (Operation-based CRDTs / OpCRDTs)

• 原理： 每个客户端只发送自己执行的“操作”本身（比如“在位置X插入字符Y”）。其他客户端收到操作后，直接在自己的本地数据上执行这个操作。

• 核心： 每个操作都必须是“上下文无关”的，或者说，它包含了足够的信息，使得无论在哪个客户端、什么状态下执行，都能产生正确的效果。这通常需要为每个字符或操作赋予唯一的ID和逻辑时间戳。

• 通俗理解： 就像大家都在画画，你画了一笔，不是把整幅画发出去，而是只告诉别人“我在这个位置画了一道红线”。别人收到后，也在自己的画上画一道红线。

• 优点： 传输的数据量小（只传操作指令）。

• 缺点： 对消息传递的可靠性要求更高，通常需要保证所有操作都能到达，并且有时需要保证因果顺序（比如先插入再删除）。

5. 以文本编辑为例：CRDT的魔法如何实现？

想象一个简单的文本编辑器：

1. 每个字符都有唯一ID： 当你输入一个字符“A”时，它不仅仅是“A”，而是“A”加上一个唯一的标识符（比如A_client1_timestamp123）。这个ID是全局唯一的，即使你删除了它，它的ID也可能被保留下来（作为“墓碑”）。

2. 插入操作： 当你在某个位置插入一个字符时，CRDT会记录这个字符的ID，以及它“之前”和“之后”的字符的ID。这样，即使其他客户端在同一位置插入了其他字符，CRDT也能根据这些ID来确定最终的相对顺序。

3. 删除操作： 删除一个字符，并不是真的从内存中抹去它。而是给这个字符打上一个“已删除”的标记（一个“墓碑”）。这样，即使其他客户端在删除操作到达之前，基于这个字符做了其他操作（比如在其后插入），这些操作仍然是有效的。当所有客户端都收到删除标记后，这个字符才会在UI上消失。

4. 合并： 当客户端收到来自其他客户端的操作时，它会根据这些操作的ID和逻辑时间戳，以一种确定的、无冲突的方式，将这些操作应用到自己的本地文档上。由于操作的交换律和幂等性，无论操作到达的顺序如何，所有客户端最终都会收敛到相同的文档状态。

6. CRDT的优势：为什么它是“魔法”？

• 真正的离线协作： 用户可以在没有网络的情况下继续工作，当网络恢复时，所有修改会自动同步合并。

• 乐观UI： 用户自己的修改会立即显示，无需等待服务器确认，提升用户体验。

• 无中心服务器依赖（可选）： CRDT可以实现完全去中心化的P2P协作，减少单点故障。

• 最终一致性： 保证所有副本最终都会收敛到同一个正确状态，且不会丢失数据。

总结

CRDT的“所见即所得”魔法，在于它将传统上难以处理的“冲突”问题，转化为了“可合并”的数学问题。通过设计具有交换律、结合律和幂等性的数据结构和操作，CRDT让分布式系统中的数据复制和同步变得简单而可靠，为实时协作应用带来了前所未有的流畅体验。它不再是简单地“覆盖”或“选择”，而是巧妙地“融合”了所有人的贡献。