冲突自由复制数据类型 (CRDT)

Source: Dev.to

请提供您希望翻译的完整文本（除代码块和 URL 之外的内容），我将把它翻译成简体中文并保持原有的格式、Markdown 语法和技术术语不变。谢谢！

背景

现代分布式系统经常在多台机器、多个地区或用户设备之间复制数据。复制是一种根本的设计选择，能够提升系统行为和用户体验。

为什么复制很重要

• 高可用性 – 即使部分节点故障，系统仍能继续工作
• 低延迟 – 用户可以与就近的副本交互
• 离线支持 – 设备在断网时仍能运行
• 容错性 – 冗余防止数据丢失

核心问题

当多个副本同时修改同一数据时会发生什么？

在分布式环境中，并发更新 不是 边缘情况——它们是常态。

真实世界的条件

• 节点维护数据的独立副本
• 网络分区和断连会发生
• 更新可能在同一时间发生
• 消息可能被延迟或乱序

如果设计不够谨慎，这些现实会导致：

• 更新之间的冲突
• 更新丢失
• 副本分歧
• 系统状态不一致

经典的基于协调的解决方案

• 锁
• 基于 Leader 的系统
• 共识协议（例如 Paxos、Raft）

虽然有效，但协调会带来权衡：

• 延迟增加
• 故障期间可用性降低
• 系统复杂度提升

正确性得以保留，但性能和弹性可能受到影响。

冲突自由复制数据类型（CRDT）

CRDT 采用一种根本不同的方法。它们不是通过协调来 防止 冲突，而是 设计 成：

• 预期会出现并发更新
• 冲突在数学上不可能出现或会自动解决
• 副本始终收敛到相同状态

这使系统能够保持：

• 高可用
• 低延迟
• 分区容错

CRDT 将负担从运行时协调转移到 数据结构设计 上。

什么是 CRDT？

冲突自由复制数据类型（CRDT） 是一种专为分布式系统设计的数据结构，在该系统中多个副本可以独立更新数据。

CRDT 能保证：

1. 副本可以独立更新数据。
2. 副本可以在 无需 协调的情况下安全合并。
3. 冲突 不会 发生（设计如此）。
4. 所有副本最终会收敛到相同的状态。
5. 不需要中心协调者或锁机制。

CRDT 通过确定性的合并规则提供 强最终一致性。

核心合并属性

CRDT 的合并操作满足三个关键的代数属性：

正因为具备这些属性，副本无论在以下情况下都能收敛：

• 消息延迟
• 网络分区
• 重复更新
• 无序投递

两大 CRDT 家族

1. 基于状态的（又称 Convergent）CRDT

• 工作原理

  1. 每个副本独立更新其 本地状态。
  2. 副本定期 共享完整状态 给其他副本。
  3. 确定性的 合并函数 将收到的状态与本地状态合并。

• 关键特性

  • 易于推理
  • 天然抵抗消息重复
  • 在不可靠网络下仍然健壮
  • 缺点： 由于全状态传输，消息体积较大

2. 基于操作的（又称 Commutative）CRDT

• 工作原理

  1. 副本生成 操作（添加、删除、插入，…）。
  2. 操作 广播 给其他副本。
  3. 操作被设计为 可交换，顺序无关紧要。

• 关键特性

  • 更节省带宽（消息更小）
  • 单条消息体积更低
  • 需要 可靠投递 假设（或因果广播）
  • 设计上更复杂，需要正确实现

简单计数器示例（基于状态）

假设两个副本从相同的值开始：

Value = 0

两者都离线并独立更新：

合并规则： 对每个副本槽位取 最大值。

Merged result = { A: 1, B: 1 } → Value = 2

即使没有协调，也不会丢失更新。

PN‑计数器（支持减法）

PN‑计数器维护两个内部 G‑计数器：

• P – 计数增量（正向）
• N – 计数减量（负向）

value = P − N

这在允许两种操作的同时保持收敛性。

文本编辑示例（基于操作）

初始文本

Hello World

两个用户在同一逻辑位置并发编辑：

如果编辑仅依赖数值索引（6），则到达的顺序决定最终字符串，可能会相互覆盖并导致分歧。

基于 CRDT 的方法

• 每个字符都会获得一个 唯一标识符（例如，副本 ID + 计数器 的元组）。
• 插入操作是 相对于标识符 表达的，而不是相对于绝对索引。
• 并发插入在设计上会被保留下来。

可能的合并结果（确定性平局决策器决定顺序）：

• Hello vikasnannu World
• Hello nannuvikas World

所有副本对最终文本达成一致。

CRDT 目录

要点

• CRDT 消除了运行时协调的需求，因为它们将冲突解决逻辑嵌入到数据类型本身。
• 它们提供 强最终一致性：所有副本在看到相同的一组更新后会收敛到相同的状态。
• 在 状态基 与 操作基 CRDT 之间的选择取决于带宽、可靠性以及设计复杂性等因素。
• 丰富的 CRDT 生态系统（寄存器、计数器、集合、映射等）使得在各种应用领域实现安全复制成为可能。

模型

• Sequences 维护有序集合，对协作编辑至关重要。

使用案例

• 文本编辑器
• 实时协作工具
• 有序共享日志

删除 vs. 插入

• 在分布式系统中，删除在根本上比插入更困难。
• 一种常见的 CRDT 技术是使用 tombstones：
  • 元素被标记为已删除，而不是直接移除。
  • 元数据被保留，以实现正确的合并。

权衡

• 增加的存储/元数据开销
• 保证收敛性和正确性

CRDT‑基系统的安全属性

• 不会丢失更新
• 无需手动冲突解决
• 副本之间最终收敛
• 在故障情况下保持高可用性
• 设计上容忍分区
• 不需要锁、领导者或协调

为什么 CRDT 很强大

• 自然地与分布式环境对齐：
  • 允许独立的副本更新
  • 在离线条件下仍能正确运行
  • 消除复杂的冲突‑解决逻辑
  • 在各地区高效扩展
  • 减少协调开销

Practical Challenges (Limitations)

• Metadata growth over time → memory and storage overhead
• Non‑intuitive ordering behavior
• Difficulty enforcing strict invariants

不适用于以下系统需求

• 强一致性保证
• 全局排序约束
• 复杂的事务不变式（例如，银行系统、金融账本、严格序列化的工作流）

对比设计哲学

强一致性系统

• 使用共识协议
• 强制全局排序
• 提供即时一致性
• 通常会导致更高的延迟

基于 CRDT 的系统

• 避免协调
• 接受最终一致性
• 优先考虑可用性和延迟

正确的选择完全取决于应用需求。

当 CRDT 最适用的情况

• 并发更新很常见
• 预期会有离线操作
• 低延迟至关重要
• 可接受最终一致性

示例领域

• 协作编辑器
• 离线优先的应用
• 分布式计数器
• 边缘 / 多设备系统
• 共享状态的应用

对 CRDT 的推理

• 副本永不争夺更新。
• CRDT 通过设计防止冲突；每个更新的结构都保证合并始终是确定且安全的。

结论

CRDT 代表了分布式系统设计的一种优雅转变：

与其对每一次更新进行协调，不如让副本独立演化，同时仍然保证收敛。

它们在现代系统中尤为有价值，因为：

• 离线使用是常态
• 延迟直接影响用户体验
• 全局协调成本高

如果恰当地使用，CRDT 能显著简化分布式数据管理，同时提升系统弹性。