土法炼钢兴趣小组的算法知识备份

【分布式系统百科】CRDT 类型目录：从计数器到序列的完整图谱

2026-04-13

目录

三个节点同时对同一个购物车执行”添加商品”操作，网络恢复后购物车里应该有几件商品？如果两个用户在协同文档里同时输入文字，合并后的文本是否会出现乱序或丢字？这些问题看似简单，但背后对应的数据结构设计空间却异常庞大。CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）正是为了在无中心协调的环境下回答这类问题而诞生的一族数据结构。

在上一篇中，我们从格（Lattice）和半格（Semi-lattice）出发，推导了 CRDT 收敛的数学基础：只要每个副本的状态空间构成一个 join semi-lattice，且 merge 操作满足交换律、结合律和幂等律，任意两个副本在交换完各自状态后，必然会收敛到相同的值。但理论并没有告诉我们：针对现实中的计数器、集合、文本序列等具体需求，应该怎样设计这些数据结构？每种结构有什么代价和局限？

本文的目标很明确：逐一拆解六大类 CRDT 的具体类型——计数器、寄存器、集合、映射、序列和图，给出每种类型的形式化定义、合并操作、空间复杂度和已知缺陷，最后用 Go 语言实现一个覆盖四种核心类型的 CRDT 库。

CRDT 类型分类

一、计数器（Counters）

计数器是最简单的 CRDT 类型，也是理解整个 CRDT 体系的最佳入口。分布式系统中的计数场景非常普遍：页面浏览量、在线用户数、库存数量、点赞数——这些场景都需要多个节点并发地修改一个数值，并在最终合并时得到正确结果。

G-Counter：只增计数器

G-Counter（Grow-only Counter）是最基础的 CRDT 计数器。它的核心思想是：不维护一个全局的计数值，而是让每个节点维护自己的局部计数值，查询时再把所有节点的值相加。

形式化定义：

设系统中有 n 个节点，节点集合为 {1, 2, ..., n}。G-Counter 的状态是一个长度为 n 的向量 V，其中 V[i] 表示节点 i 累计增加的次数。

merge 操作天然满足三大性质：

  1. 交换律： merge(Va, Vb) = merge(Vb, Va)，因为 max 是对称的
  2. 结合律： merge(Va, merge(Vb, Vc)) = merge(merge(Va, Vb), Vc)
  3. 幂等律： merge(Va, Va) = Va

空间复杂度： O(n)，n 是节点数。每个 G-Counter 需要存储所有节点的局部计数值。这意味着节点数量越多，每个计数器的空间开销越大。如果系统有 1000 个节点，每个计数器就需要存储 1000 个整数。

局限性： G-Counter 只能递增，不能递减。如果你需要表示”用户取消点赞”，G-Counter 无能为力。这直接引出了 PN-Counter。

PN-Counter：正负计数器

PN-Counter（Positive-Negative Counter）用两个 G-Counter 组合实现递减功能：一个 P 计数器记录所有增加操作，一个 N 计数器记录所有减少操作。

形式化定义：

PN-Counter 的状态是一对 G-Counter：(P, N)。

merge((Pa, Na), (Pb, Nb)) = (merge_g(Pa, Pb), merge_g(Na, Nb))

merge 的正确性从 G-Counter 的性质直接继承。由于 P 和 N 各自是独立的 G-Counter，对它们分别执行 merge 后取差值，结果保持一致。

空间复杂度： O(2n) = O(n)。需要存储两个向量，空间是 G-Counter 的两倍。

局限性： PN-Counter 的值域是全体整数，可以无限增长也可以变成负数。在很多业务场景中（库存不能为负、余额不能透支），需要对计数器的值施加上下限约束，这就是 Bounded Counter 要解决的问题。

Bounded Counter：有界计数器

Bounded Counter 在 PN-Counter 的基础上增加了上下限约束。核心难点在于：如何在没有全局协调的情况下保证计数值不越界？

一种典型的实现方式是 配额分配（Quota Allocation）。系统将总配额预先分配到各个节点，每个节点只能在自己的配额范围内进行递减操作。

基本机制：

假设计数器初始值为 K，系统有 n 个节点。将 K 均匀分配到各节点，节点 i 获得配额 quota[i]，且 sum(quota) = K。

配额转让需要节点间通信，这本身就是一种轻量级的协调。但关键区别在于：这种协调只在配额不足时才发生，正常操作路径上不需要任何同步。

已知问题：

  1. 配额分配不均可能导致某些节点频繁借用，增加延迟
  2. 节点崩溃会导致已分配的配额丢失，需要回收机制
  3. 严格的边界保证在异步系统中无法完全实现——如果两个节点同时消耗最后一个单位的配额，短暂的越界是可能发生的

Baquero 等人在 2017 年的论文《Bounded Counter CRDT》中对这类问题给出了更严谨的形式化分析和协议设计。

具体场景：酒店房间预订

以一个酒店预订系统为例，说明 Bounded Counter 的实际运作。假设酒店共有 100 间客房，系统部署了 5 个副本（R1 到 R5），每个副本初始分配 20 个配额。

各副本在本地独立处理预订请求，每接受一个预订就将本地配额减 1。假设某个时段 R3 所在区域的预订需求特别旺盛，R3 很快耗尽了自己的 20 个配额。此时 R3 不能再接受新的预订——即使全局来看可能还有大量空房。R3 需要向其他副本发起配额转让请求。例如，R1 当前还剩余 15 个配额，它可以将其中 10 个转让给 R3。转让完成后，R1 的配额变为 5，R3 的配额变为 10，R3 又可以继续接受预订。

这一过程的关键约束是：所有副本的配额总和在任何时刻都不能超过全局上限 100。配额转让是一种轻量级的点对点协调，只在配额不足时才触发，不影响正常路径上的无同步操作。

flowchart TD
    Total["全局上限: 100 间客房"] --> Distribute["初始配额分配"]
    Distribute --> R1["R1: quota=20"]
    Distribute --> R2["R2: quota=20"]
    Distribute --> R3["R3: quota=20"]
    Distribute --> R4["R4: quota=20"]
    Distribute --> R5["R5: quota=20"]
    R3 --> Decrement["本地预订: quota--"]
    Decrement --> Check{"quota > 0?"}
    Check -->|"是"| Accept["接受预订"]
    Accept --> Decrement
    Check -->|"否"| Exhaust["配额耗尽"]
    Exhaust --> Request["向对等副本请求配额转让"]
    Request --> Transfer["R1 转让 10 个配额给 R3"]
    Transfer --> Resume["R3 恢复服务: quota=10"]

上图展示了 Bounded Counter 的配额分配与转让流程。全局上限被均匀分配到各副本后，每个副本在本地独立消费配额；当某个副本耗尽配额时，通过向对等节点请求转让来补充。这种设计保证了全局不变量（总预订数不超过 100）在绝大多数情况下成立，同时将协调开销推迟到配额不足的边界场景。

二、寄存器（Registers）

寄存器是最基本的读写单元：它存储一个值，支持写入（assign）和读取（value）两种操作。在单机环境中这没什么好讨论的，但在分布式环境中，当两个节点同时对同一个寄存器写入不同的值时，合并逻辑就决定了系统的语义。

LWW-Register：最后写入者胜

LWW-Register（Last-Writer-Wins Register）是最简单粗暴的冲突解决策略：给每次写入附加一个时间戳（Timestamp），合并时保留时间戳最大的那个值。

形式化定义：

LWW-Register 的状态是一个二元组 (value, timestamp)。

merge((v1, t1), (v2, t2)) = (v1, t1) if t1 > t2
                            = (v2, t2) if t2 > t1

如果 t1 = t2 且 v1 != v2，需要额外的 tie-breaking 规则，通常用节点 ID 的字典序来打破平局。

merge 操作的正确性依赖于时间戳的全序性。只要不存在两个不同的写入拥有完全相同的时间戳（通过 tie-breaking 保证），merge 就满足交换律和幂等律。

空间复杂度： O(1)。每个寄存器只存储一个值和一个时间戳。

数据丢失风险： LWW-Register 的根本问题是它会丢弃并发写入。假设节点 A 写入 x = 1，节点 B 同时写入 x = 2，如果 B 的时间戳更大，那么 A 的写入就被永久丢弃了。在某些场景下这是可以接受的（比如传感器数据，只关心最新值），但在另一些场景下这会导致数据丢失（比如用户同时编辑同一个字段）。

时间戳问题： LWW-Register 隐含了一个假设——时间戳能准确反映因果顺序。但在分布式系统中，物理时钟存在漂移，节点 A 的”现在”可能比节点 B 的”刚才”还早。如果两个节点的时钟偏差很大，LWW 的结果可能违反直觉。使用混合逻辑时钟（HLC）可以缓解这个问题，但无法完全消除。

Dynamo、Cassandra 和 Riak 都使用 LWW 作为默认的冲突解决策略。它的优势在于简单和空间高效，代价是可能丢失并发更新。

MV-Register：多值寄存器

MV-Register（Multi-Value Register）采取了与 LWW 完全相反的策略：不丢弃任何并发写入，而是保留所有并发值，让应用层决定如何处理冲突。

形式化定义：

MV-Register 的状态是一个集合 {(value, version_vector)}，每个元素包含一个值和对应的版本向量（Version Vector）。

版本向量 VVa 支配 VVb 当且仅当 VVa 的每个分量都大于等于 VVb 的对应分量，且至少有一个分量严格大于。如果 VVa 和 VVb 互不支配，则对应的值被认为是并发的，都需要保留。

空间复杂度： 最坏情况下 O(n * m)，其中 n 是节点数，m 是并发写入的数量。在高度并发的场景中，保留的值数量可能会快速增长。

实际应用： Riak 在配置为 allow_mult = true 时使用 MV-Register 语义。当读取到多个并发值（Riak 称之为 siblings）时，客户端需要自行决定合并策略。购物车场景就是典型例子——两个客户端同时添加不同的商品，MV-Register 会保留两次添加，客户端合并时取并集即可。

三、集合（Sets）

集合类型的 CRDT 是最丰富也最微妙的类别。核心难题在于”添加-删除”冲突：如果一个节点添加元素 e，同时另一个节点删除元素 e，合并后 e 应该存在还是不存在？不同的集合类型对这个问题给出了不同的回答。

G-Set：只增集合

G-Set（Grow-only Set）是最简单的集合 CRDT：只允许添加元素，不允许删除。

形式化定义：

G-Set 的状态就是一个普通集合 S。

集合并运算天然满足交换律、结合律和幂等律，因此 G-Set 是一个合法的 CvRDT。

空间复杂度： O(m)，m 是已添加的元素总数。由于不能删除，集合只会单调增长。

局限性： 无法删除元素。一旦某个元素被添加，它就永远存在于集合中。在很多实际场景中，这种限制太过严格。

2P-Set：两阶段集合

2P-Set（Two-Phase Set）通过引入一个”墓碑集合（Tombstone Set）“来支持删除，但删除是不可逆的——一旦删除就不能再重新添加。

形式化定义：

2P-Set 的状态是一对 G-Set：(A, R)，其中 A 是添加集合，R 是删除集合（墓碑集合）。

空间复杂度： O(m)，m 是曾经添加过的元素总数。注意，即使元素被删除，它仍然占据空间（存在于 A 和 R 两个集合中）。墓碑永远不会被回收。

局限性： 元素一旦删除就不能再添加回来。假设用户把商品从购物车里移除，后来又想加回去——2P-Set 做不到。这在大多数实际应用中是不可接受的。

OR-Set：观察删除集合

OR-Set（Observed-Remove Set）是 CRDT 集合类型中最实用的一种，它通过为每次 add 操作分配一个全局唯一的标签（Tag）来解决添加-删除冲突。

核心思想： 删除操作不是删除”元素”，而是删除”当前观察到的所有标签”。如果在删除发生的同时，另一个节点添加了同一个元素（生成了新标签），这个新标签不在删除的范围内，因此元素会保留下来。这就是”添加优先于并发删除”的语义。

形式化定义：

OR-Set 的状态是一个集合 S，其中每个元素是一个三元组 (element, unique_tag, node_id)。

merge 操作的关键在于正确处理”一个节点添加、另一个节点删除”的并发情况。Shapiro 等人在 2011 年的论文中给出的 merge 语义是：

merge(Sa, Sb) = (Sa ∩ Sb) ∪ (Sa \ causal_past(Sb)) ∪ (Sb \ causal_past(Sa))

直觉上理解：保留双方都有的标签，以及各自新增的标签（对方没有见过、因此不可能删除的标签）。

空间复杂度： O(m * k)，其中 m 是当前元素数量，k 是每个元素的平均标签数量。频繁添加同一个元素会积累大量标签。

已知问题： 标签积累（Tag Accumulation）。如果元素 e 被反复添加 1000 次，即使只保留最新的一次，OR-Set 可能仍然存储着大量历史标签。实际实现需要定期进行垃圾回收（GC），清理不再需要的旧标签。

Bieniusa 等人在 2012 年的论文《An Optimized Conflict-free Replicated Set》中对 OR-Set 进行了详细分析，并提出了优化方案。

下面通过一个时序图来展示 OR-Set 在并发添加与删除时的合并行为：

sequenceDiagram
    participant A as 副本 A
    participant B as 副本 B

    Note over A,B: 初始状态: OR-Set 为空

    A->>A: add(x), 分配唯一标签 t1
    Note right of A: 状态: {(x, t1)}

    B->>B: add(x), 分配唯一标签 t2
    Note left of B: 状态: {(x, t2)}

    B->>B: remove(x), 移除本地所有 x 的标签
    Note left of B: 状态: {} (t2 被删除)

    A->>B: 同步状态 {(x, t1)}
    B->>A: 同步状态 {}

    Note over A,B: 合并结果: {(x, t1)}
    Note over A,B: x 存活! 因为 t1 从未被任何 remove 观察到

该时序图清晰地展示了 OR-Set “添加胜出”语义的根本机制。副本 B 执行 remove(x) 时，只能删除它当时已知的标签 t2；而副本 A 并发分配的标签 t1 对 B 不可见，因此不受该删除操作的影响。合并后 t1 依然存在，元素 x 在最终状态中存活。这正是 OR-Set 使用唯一标签而非简单布尔标记的原因——标签的唯一性使得系统能够精确区分”已被观察到并删除”与”尚未被观察到”的添加操作。

AWSet：添加胜出集合

AWSet（Add-Wins Set）是 OR-Set 的优化变体。它的语义与 OR-Set 相同——并发的添加和删除冲突时，添加胜出——但实现上更紧凑。

核心改进： AWSet 不再为每次 add 分配独立的唯一标签，而是使用版本向量（或点版本向量，Dotted Version Vector）来追踪因果关系。每个元素只需要存储一个因果上下文（Causal Context），而不是一堆独立标签。

形式化定义：

AWSet 的状态是 (S, cc)，其中 S 是元素集合，每个元素关联一个”点”（dot），cc 是因果上下文（Causal Context）。

空间优势： AWSet 的空间复杂度为 O(m + n)，其中 m 是当前元素数，n 是节点数。相比 OR-Set 的 O(m * k)，在元素被频繁添加删除的场景下，AWSet 显著节省空间。

Almeida 等人在 2018 年的论文《Delta State Replicated Data Types》中进一步将 AWSet 与 delta-CRDT 结合，实现了增量同步，只传输状态变化的部分，大幅降低了网络带宽消耗。

四、映射（Maps）

映射（Map）是键值对的集合，在分布式系统中对应字典、哈希表等数据结构。CRDT 映射的难点在于：键值对中的”值”本身可能是另一个 CRDT，这导致了嵌套和递归组合的问题。

OR-Map：键值对的 CRDT

OR-Map 将 OR-Set 的思想应用到键值对上。键的添加和删除遵循 OR-Set 的语义（添加优先于并发删除），值的合并则委托给值类型自身的 merge 函数。

形式化定义：

OR-Map 的状态是 {(key, tag, value_crdt)}，其中 key 是键名，tag 是唯一标签（来自 OR-Set 的机制），value_crdt 是值对应的 CRDT 实例。

示例场景： 假设 OR-Map 用于存储用户配置，键是配置项名称，值是 LWW-Register。节点 A 更新 theme = "dark"，节点 B 同时删除 theme 键。按 OR-Map 语义，添加胜出，theme 键会保留下来。同时，如果两个节点都更新了 theme 的值，值的合并遵循 LWW-Register 的时间戳规则。

嵌套 CRDT：CRDT 的组合与嵌套

CRDT 的一个强大特性是可组合性（Composability）：如果类型 A 和类型 B 各自是合法的 CRDT，那么在一定条件下，它们的组合也是合法的 CRDT。

嵌套规则：

  1. 值嵌套： OR-Map 的值可以是任意 CRDT 类型——G-Counter、PN-Counter、LWW-Register、OR-Set，甚至另一个 OR-Map。只要每层的 merge 函数各自满足 CRDT 的性质，整体的 merge 就自动满足。

  2. 递归嵌套： OR-Map 的值可以是 OR-Map，形成树状结构。这在实际应用中非常有用：JSON 文档本质上就是嵌套的映射和数组。Automerge 库就利用这个原理实现了分布式 JSON 文档。

  3. 组合的限制： 嵌套并非完全自由。当删除一个键时，对应值中的所有状态都会被清除，即使并发操作修改了该值的内部状态。这种语义是否符合应用需求，需要具体分析。

实际系统中的使用：

Riak 的 CRDT Maps 支持嵌套组合。一个 Map 的值可以是 Counter、Set、Register、Flag 或另一个 Map。Riak 在 2.0 版本引入了这套 CRDT 类型系统，文档中称之为 “Riak Data Types”。

Automerge 库将 JSON 文档建模为嵌套的 CRDT Map + CRDT List，每个字段对应一个 LWW-Register 或 MV-Register，每个数组对应一个 CRDT 序列。这种嵌套组合使得整个 JSON 文档成为一个单一的 CRDT，支持离线编辑和自动合并。

五、序列（Sequences）

序列类型的 CRDT 是六大类中复杂度最高的一类，也是实现协同编辑（Collaborative Editing）的核心数据结构。与集合不同，序列中的元素是有序的，而且两个并发插入的相对顺序必须在所有副本上保持一致。

核心挑战在于：如何为序列中的每个位置分配一个标识符（Position Identifier），使得并发插入能被确定性地排序，且不依赖中心节点？

RGA：可复制增长数组

RGA（Replicated Growable Array）由 Roh 等人在 2011 年发表的论文《Replicated abstract data types: Building blocks for collaborative applications》中提出。它是一种基于链表或树结构的序列 CRDT。

核心思想： RGA 将序列建模为一棵有序树。每次插入操作指定”在某个现有元素之后插入”。元素的标识符由 (timestamp, node_id) 组成，用于在多个并发插入到同一位置时确定排列顺序。

操作定义：

因果排序的保证： RGA 使用 Lamport 时间戳确保因果关系得到尊重。如果插入 A 因果先于插入 B（即 B 的操作者已经看到了 A），则 A 的时间戳必然小于 B 的时间戳。并发的插入（互相看不到对方）通过 node_id 打破平局。

空间复杂度： O(m)，m 是所有曾经插入过的元素数量（包括已删除的墓碑）。墓碑不能立即回收，因为远端节点可能还持有指向该墓碑的引用。

墓碑回收： 这是 RGA 在工程实践中的主要难题。只有当所有节点都确认已经看到了某个删除操作后，对应的墓碑才能安全回收。这需要额外的元数据同步机制，通常通过版本向量或因果稳定性（Causal Stability）协议实现。

LSEQ：对数空间标识符

LSEQ 由 Nedelec 等人在 2013 年提出，旨在解决序列 CRDT 中标识符空间增长过快的问题。

问题背景： 在基于标识符的序列 CRDT 中，每个元素需要一个全局唯一且可排序的标识符。如果两个元素的标识符分别是 1 和 2，在它们之间插入一个新元素就需要选择一个介于 1 和 2 之间的标识符，比如 1.5。反复在相邻元素之间插入，标识符的位数会不断增长。

LSEQ 的策略： 使用可变深度的树结构作为标识符空间，在每层随机选择分配策略（boundary+ 或 boundary-）。boundary+ 在区间的开头附近分配新标识符，boundary- 在区间的末尾附近分配。通过随机选择策略，LSEQ 在数学期望上将标识符长度控制在 O(log n)，其中 n 是序列中的元素数量。

局限性： LSEQ 的对数保证是概率性的，最坏情况下标识符长度仍可能退化为线性。此外，LSEQ 在某些特定的编辑模式下（如始终在同一位置插入）可能产生交错异常。

Logoot：稠密标识符空间

Logoot 由 Weiss 等人在 2009 年提出，是最早的基于稠密标识符的序列 CRDT 之一。

核心思想： Logoot 在每对相邻元素之间维护一个”稠密”的标识符空间。标识符是一个多层的元组 [(position, site_id, clock)]，每层的 position 是该层空间中的一个整数。通过增加层数，标识符空间可以无限细分。

插入算法：

  1. 给定左邻居的标识符 id_left 和右邻居的标识符 id_right
  2. 在 id_left 和 id_right 之间随机选择一个新标识符
  3. 如果同层空间不足，增加一层

空间复杂度： 标识符长度在最坏情况下为 O(n)，其中 n 是插入次数。顺序插入（如从左到右连续打字）会导致标识符快速增长，因为每次插入都在区间末尾，可用空间越来越小。

YATA：Yjs 使用的算法

YATA（Yet Another Transformation Approach）是 Yjs 库的作者 Kevin Jahns 在 2016 年提出的序列 CRDT 算法。Yjs 是目前最活跃的协同编辑 CRDT 库之一，被 Notion、JupyterLab 等产品采用。

核心思想： YATA 不使用稠密标识符，而是采用链表结构，每个元素记录其左邻居（origin）和右邻居。当并发插入发生时，YATA 使用以下约束来确定排序：

  1. 左起源约束（Left Origin）： 新元素的 origin 字段指向它插入时的左邻居
  2. 右邻居约束（Right Neighbor）： 新元素同时记录插入时的右邻居
  3. 冲突排序规则： 当多个元素拥有相同的 origin 时，按创建者 ID 降序排列

与 RGA 的区别： RGA 只记录父节点（插入位置的前一个元素），YATA 同时记录左右两个邻居。这额外的信息使得 YATA 在某些并发场景下能更好地保持用户意图。

性能特性： YATA 的插入和合并操作在平均情况下是 O(1)（因为链表结构），但在最坏情况下（大量并发插入到同一位置）退化为 O(n)。Yjs 的实际性能测试表明，在典型的文本编辑场景中，YATA 比基于标识符的方案（如 Logoot、LSEQ）更高效，因为它不需要维护和比较长标识符。

Jahns 在论文中报告，Yjs 可以在数百毫秒内合并数十万次操作的历史记录。

交错异常（Interleaving Anomaly）

交错异常是所有序列 CRDT 都可能面临的一个微妙问题。

场景描述： 用户 A 在位置 p 处插入字符串 “abc”（三次连续插入），用户 B 同时在相同位置 p 处插入字符串 “xyz”。理想情况下，合并后的结果应该是 “abcxyz” 或 “xyzabc”——两个字符串各自保持完整。但某些序列 CRDT 可能产生 “axbycz” 这样的交错结果，破坏了用户的输入意图。

原因分析： 交错异常的根源在于序列 CRDT 对并发插入的排序是逐字符进行的，而不是逐”操作批次”进行的。如果排序规则让 A 和 B 的字符交替排列，就会产生交错。

受影响的算法：

Kleppmann 等人在 2019 年的论文《Interleaving anomalies in collaborative text editors》中系统性地分析了这个问题，并提出了检测和修复交错异常的方法。

六、图（Graphs）

图是最复杂的 CRDT 类型之一。与集合不同，图需要维护顶点和边之间的一致性约束：边不能悬空（即边的两个端点都必须存在于顶点集合中）。这个不变量在并发操作下很容易被破坏——一个节点添加了一条边 (u, v)，而另一个节点同时删除了顶点 u。

Add-only DAG：只增有向无环图

Add-only DAG 是最简单的图 CRDT：只允许添加顶点和边，不允许删除。

形式化定义：

状态是 (V, E)，其中 V 是顶点的 G-Set，E 是边的 G-Set。

由于只允许添加，边的端点不会被删除，因此不存在悬空边的问题。但这也意味着图只会单调增长，无法移除顶点或边。

Add-only DAG 的典型应用场景是 Git 的提交历史——每个提交是一个顶点，父提交关系构成有向边。Git 的提交图本身就是一个 CRDT：不同的仓库可以独立地添加提交，合并时取并集即可。

2P2P-Graph：两阶段顶点-边图

2P2P-Graph 使用两个 2P-Set 分别管理顶点和边，支持添加和删除操作。

形式化定义：

状态是 (VA, VR, EA, ER)，VA 是已添加的顶点集合，VR 是已删除的顶点集合，EA 是已添加的边集合，ER 是已删除的边集合（都是 2P-Set 的组成部分）。

并发问题： 2P2P-Graph 继承了 2P-Set 的限制——删除后的顶点或边不可重新添加。更棘手的是并发场景：节点 A 删除了顶点 v，同时节点 B 添加了以 v 为端点的边 (v, w)。合并后 v 被删除，但边 (v, w) 被添加，产生了悬空边。

解决方案： 在查询时（lookup）过滤掉端点不存在的边。这保证了对外暴露的视图始终满足图的不变量，但代价是存储中可能存在无效边。

Shapiro 等人在 2011 年的综合论文中讨论了更多图 CRDT 的变体，包括使用 OR-Set 管理顶点和边的 OR-Graph，它允许重新添加已删除的顶点和边。

七、Go 实现

以下是一个覆盖 G-Counter、PN-Counter、LWW-Register 和 OR-Set 四种核心类型的 Go CRDT 库实现。代码可直接编译运行。

package main

import (
    "fmt"
    "time"
)

// ---------- G-Counter ----------

// GCounter 只增计数器，每个节点维护自己的局部计数值。
type GCounter struct {
    counts map[string]uint64
}

func NewGCounter() *GCounter {
    return &GCounter{counts: make(map[string]uint64)}
}

func (g *GCounter) Increment(nodeID string) {
    g.counts[nodeID]++
}

func (g *GCounter) Value() uint64 {
    var sum uint64
    for _, v := range g.counts {
        sum += v
    }
    return sum
}

func (g *GCounter) Merge(other *GCounter) {
    for nodeID, val := range other.counts {
        if val > g.counts[nodeID] {
            g.counts[nodeID] = val
        }
    }
}

// ---------- PN-Counter ----------

// PNCounter 正负计数器，用两个 GCounter 分别记录增减。
type PNCounter struct {
    P *GCounter
    N *GCounter
}

func NewPNCounter() *PNCounter {
    return &PNCounter{
        P: NewGCounter(),
        N: NewGCounter(),
    }
}

func (pn *PNCounter) Increment(nodeID string) {
    pn.P.Increment(nodeID)
}

func (pn *PNCounter) Decrement(nodeID string) {
    pn.N.Increment(nodeID)
}

func (pn *PNCounter) Value() int64 {
    return int64(pn.P.Value()) - int64(pn.N.Value())
}

func (pn *PNCounter) Merge(other *PNCounter) {
    pn.P.Merge(other.P)
    pn.N.Merge(other.N)
}

// ---------- LWW-Register ----------

// LWWRegister 最后写入者胜寄存器，用时间戳仲裁并发写入。
type LWWRegister struct {
    value     interface{}
    timestamp time.Time
    nodeID    string
}

func NewLWWRegister() *LWWRegister {
    return &LWWRegister{}
}

func (r *LWWRegister) Assign(value interface{}, nodeID string) {
    r.value = value
    r.timestamp = time.Now()
    r.nodeID = nodeID
}

func (r *LWWRegister) AssignWithTimestamp(value interface{}, ts time.Time, nodeID string) {
    r.value = value
    r.timestamp = ts
    r.nodeID = nodeID
}

func (r *LWWRegister) Value() interface{} {
    return r.value
}

func (r *LWWRegister) Merge(other *LWWRegister) {
    if other.timestamp.After(r.timestamp) {
        r.value = other.value
        r.timestamp = other.timestamp
        r.nodeID = other.nodeID
    } else if other.timestamp.Equal(r.timestamp) && other.nodeID > r.nodeID {
        // 时间戳相同时，用节点 ID 字典序打破平局
        r.value = other.value
        r.timestamp = other.timestamp
        r.nodeID = other.nodeID
    }
}

// ---------- OR-Set ----------

// orEntry OR-Set 中的条目，包含元素值和唯一标签。
type orEntry struct {
    Value interface{}
    Tag   string
}

// ORSet 观察删除集合，用唯一标签解决添加-删除冲突。
type ORSet struct {
    entries map[string]orEntry // tag -> entry
    tagSeq  uint64
    nodeID  string
}

func NewORSet(nodeID string) *ORSet {
    return &ORSet{
        entries: make(map[string]orEntry),
        nodeID:  nodeID,
    }
}

func (s *ORSet) generateTag() string {
    s.tagSeq++
    return fmt.Sprintf("%s:%d", s.nodeID, s.tagSeq)
}

func (s *ORSet) Add(value interface{}) {
    // 先移除该元素所有旧标签，再用新标签添加
    for tag, entry := range s.entries {
        if entry.Value == value {
            delete(s.entries, tag)
        }
    }
    tag := s.generateTag()
    s.entries[tag] = orEntry{Value: value, Tag: tag}
}

func (s *ORSet) Remove(value interface{}) {
    // 移除当前观察到的所有关于该元素的标签
    for tag, entry := range s.entries {
        if entry.Value == value {
            delete(s.entries, tag)
        }
    }
}

func (s *ORSet) Lookup(value interface{}) bool {
    for _, entry := range s.entries {
        if entry.Value == value {
            return true
        }
    }
    return false
}

func (s *ORSet) Elements() []interface{} {
    seen := make(map[interface{}]bool)
    var result []interface{}
    for _, entry := range s.entries {
        if !seen[entry.Value] {
            seen[entry.Value] = true
            result = append(result, entry.Value)
        }
    }
    return result
}

// Merge 合并两个 OR-Set。
// 简化实现：取两个集合的标签并集。
// 完整实现需要因果上下文来区分"对方删除了"和"对方从未见过"。
// 此处为演示目的，采用标签并集策略。
func (s *ORSet) Merge(other *ORSet) {
    for tag, entry := range other.entries {
        if _, exists := s.entries[tag]; !exists {
            s.entries[tag] = entry
        }
    }
}

// ---------- 演示 ----------

func main() {
    fmt.Println("===== G-Counter =====")
    gc1 := NewGCounter()
    gc2 := NewGCounter()

    gc1.Increment("node-a")
    gc1.Increment("node-a")
    gc1.Increment("node-a")
    gc2.Increment("node-b")
    gc2.Increment("node-b")

    fmt.Printf("gc1 合并前: %d\n", gc1.Value()) // 3
    fmt.Printf("gc2 合并前: %d\n", gc2.Value()) // 2

    gc1.Merge(gc2)
    fmt.Printf("gc1 合并后: %d\n", gc1.Value()) // 5

    fmt.Println("\n===== PN-Counter =====")
    pn1 := NewPNCounter()
    pn2 := NewPNCounter()

    pn1.Increment("node-a")
    pn1.Increment("node-a")
    pn1.Increment("node-a")
    pn1.Decrement("node-a")
    pn2.Increment("node-b")
    pn2.Decrement("node-b")
    pn2.Decrement("node-b")

    fmt.Printf("pn1 合并前: %d\n", pn1.Value()) // 2
    fmt.Printf("pn2 合并前: %d\n", pn2.Value()) // -1

    pn1.Merge(pn2)
    fmt.Printf("pn1 合并后: %d\n", pn1.Value()) // 1

    fmt.Println("\n===== LWW-Register =====")
    reg1 := NewLWWRegister()
    reg2 := NewLWWRegister()

    t1 := time.Date(2026, 4, 13, 10, 0, 0, 0, time.UTC)
    t2 := time.Date(2026, 4, 13, 10, 0, 1, 0, time.UTC)

    reg1.AssignWithTimestamp("value-from-A", t1, "node-a")
    reg2.AssignWithTimestamp("value-from-B", t2, "node-b")

    fmt.Printf("reg1 合并前: %v (ts=%v)\n", reg1.Value(), reg1.timestamp)
    fmt.Printf("reg2 合并前: %v (ts=%v)\n", reg2.Value(), reg2.timestamp)

    reg1.Merge(reg2)
    fmt.Printf("reg1 合并后: %v (B 的时间戳更大，B 胜出)\n", reg1.Value())

    fmt.Println("\n===== OR-Set =====")
    os1 := NewORSet("node-a")
    os2 := NewORSet("node-b")

    os1.Add("apple")
    os1.Add("banana")
    os2.Add("banana")
    os2.Add("cherry")

    fmt.Printf("os1 合并前: %v\n", os1.Elements())
    fmt.Printf("os2 合并前: %v\n", os2.Elements())

    os1.Merge(os2)
    fmt.Printf("os1 合并后: %v\n", os1.Elements())
    fmt.Printf("os1 包含 apple: %v\n", os1.Lookup("apple"))
    fmt.Printf("os1 包含 cherry: %v\n", os1.Lookup("cherry"))

    // 演示删除语义
    os1.Remove("banana")
    fmt.Printf("os1 删除 banana 后: %v\n", os1.Elements())

    fmt.Println("\n===== 并发添加-删除演示 =====")
    setA := NewORSet("node-a")
    setB := NewORSet("node-b")

    // 两个节点各自独立添加 "x"
    setA.Add("x")
    setB.Add("x")

    // 节点 A 删除 "x"（只删除自己观察到的标签）
    setA.Remove("x")
    fmt.Printf("setA 删除 x 后: %v\n", setA.Elements()) // []

    // 合并后，节点 B 的 "x" 标签被保留（添加胜出于并发删除）
    setA.Merge(setB)
    fmt.Printf("setA 合并 setB 后: %v (B 的添加胜出)\n", setA.Elements()) // [x]
}

这段代码的几个关键设计决策：

  1. GCounter 使用 map[string]uint64 而不是固定长度数组，使得节点集合可以动态扩展，不需要预先知道节点总数。代价是 map 的查询开销比数组高。

  2. PNCounter 直接组合两个 GCounter，这是组合模式（Composition Pattern）的典型体现：复杂的 CRDT 由简单的 CRDT 组合而成。

  3. LWWRegister 的 tie-breaking 使用节点 ID 的字典序。这保证了即使两个节点的时间戳完全相同，merge 结果也是确定性的。

  4. ORSet 的 Merge 是简化版本，采用标签并集策略。完整的 OR-Set merge 需要维护因果上下文（Causal Context），记录每个节点已知的最大标签序号，从而区分”对方已经看到并删除了这个标签”和”对方从未见过这个标签”。在生产环境中，建议参考 Shapiro 等人 2011 年论文中的完整算法，或使用 Almeida 等人 2018 年提出的 delta-CRDT 版本。

八、类型选择与工程考量

不同的 CRDT 类型在空间复杂度、语义表达力和实现复杂度之间有着显著的权衡。以下从工程角度总结关键的选型依据。

空间复杂度对比

类型 空间复杂度 主要空间消耗来源
G-Counter O(n) 节点数 n
PN-Counter O(n) 节点数 n（两个向量）
LWW-Register O(1) 单个值 + 时间戳
MV-Register O(n * m) 节点数 n，并发写入数 m
G-Set O(m) 元素数 m，单调增长
2P-Set O(m) 元素数 m，含墓碑
OR-Set O(m * k) 元素数 m，标签数 k
AWSet O(m + n) 元素数 m，节点数 n
RGA O(m) 元素数 m，含墓碑
OR-Map O(m * k) 键数 m，每键标签数 k

n 为节点数，m 为元素（或操作）数量，k 为每元素的标签累积量。

语义选型指南

计数场景： 如果只需要递增，用 G-Counter；需要递减，用 PN-Counter；有边界约束（如库存不可为负），考虑 Bounded Counter 或在应用层做校验。

单值读写： 如果可以接受”最后写入者胜”的丢失风险，用 LWW-Register（简单、空间小）；如果需要保留所有并发值让应用层决策，用 MV-Register。

集合操作： G-Set 过于受限，2P-Set 不可重加，实际系统中几乎都用 OR-Set 或 AWSet。如果空间敏感且节点数不多，AWSet 更优。Riak 的 CRDT Sets 内部实现是 AWSet 的变体。

键值存储： OR-Map 是默认选择。值类型根据业务需求选择对应的 CRDT（Counter、Register、Set 等）。

协同文本编辑： RGA 实现较简单但墓碑回收困难；YATA 在实践中性能最好（Yjs 已验证），且较好地避免了交错异常；Logoot 和 LSEQ 的标识符增长问题在长期运行的文档中可能成为瓶颈。

图结构： 大多数实际应用使用 Add-only DAG（如版本控制系统的提交图）。需要删除能力时，2P2P-Graph 或基于 OR-Set 的变体可以考虑，但需要处理悬空边的边界情况。

墓碑与垃圾回收

几乎所有支持删除操作的 CRDT 都面临墓碑（Tombstone）累积的问题。元素被删除后，其元数据（标签、版本向量、墓碑标记）不能立即清除，因为可能存在尚未同步的远端节点。

常见的垃圾回收策略：

  1. 因果稳定性（Causal Stability）： 当所有节点都确认已经看到某个删除操作后，对应的墓碑可以安全回收。这需要额外的同步机制来追踪全局的最小版本向量。

  2. 定期全量同步（Periodic Full Sync）： 节点之间定期交换完整状态，同步完成后双方可以清理已达成共识的墓碑。Riak 使用基于 Merkle Tree 的 Active Anti-Entropy 来实现。

  3. 有限窗口（Bounded Window）： 设定一个时间窗口，超过窗口期的墓碑强制回收。离线时间超过窗口期的节点需要全量重同步。这是一种工程妥协，在大多数实际系统中被采用。

为什么墓碑会无限增长？

以一个使用 OR-Set 的协同编辑系统为例。假设一份共享购物清单在 3 个副本之间同步，用户每天添加和删除约 50 个条目。每次删除操作会产生一条墓碑记录。如果系统不做任何垃圾回收，一年后墓碑数量将达到约 54,750 条（365 天 x 50 条 x 3 副本，考虑去重后约为此量级）。而实际存活的元素可能只有几十个。墓碑所占用的存储和在合并时需要遍历的开销远远超过有效数据本身。更严重的是，墓碑在合并操作中不能被跳过——每次 merge 都必须检查墓碑集合以确保删除语义的正确性。随着墓碑的积累，merge 的时间复杂度线性增长，系统性能逐步退化。

因果稳定性的精确条件

一条墓碑可以被安全回收，当且仅当系统中所有副本都已经观察到了产生该墓碑的删除操作。形式化地说，设删除操作 d 发生在副本 i 的逻辑时钟 t_i 处，当所有副本 j 的已知向量时钟 V_j 满足 V_j[i] >= t_i 时，操作 d 达到因果稳定（Causally Stable）。此时即使有延迟的副本最终上线同步，它看到的状态也已经包含了该删除操作的效果，因此对应的墓碑可以安全移除。

实现因果稳定性检测需要维护一个全局最小向量时钟（Global Minimum Vector Clock），即所有副本向量时钟的逐分量取最小值。只有时间戳被该全局最小向量时钟”支配”的墓碑才满足回收条件。这意味着系统中最慢的副本决定了回收的速度——任何长期离线的副本都会阻止所有墓碑的回收。

裁剪协议（Prune Protocol）

为了解决因果稳定性检测在实际系统中过于保守的问题，一些系统采用了主动裁剪协议。裁剪协议的核心思想是：发起裁剪的节点先广播一个”裁剪屏障”（Prune Barrier），要求所有副本在屏障时间点之前完成状态同步。一旦所有副本确认（通过 ACK）已同步到屏障点，发起者就可以安全地删除屏障之前的所有墓碑。如果某个副本长期不响应，系统可以选择将其标记为”已脱离”（Retired），不再等待其确认，但该副本重新上线后必须执行全量状态重建而非增量同步。

stateDiagram-v2
    [*] --> Active: 元素被添加
    Active --> Tombstoned: 执行删除操作
    Tombstoned --> GCEligible: 达到因果稳定\n(所有副本已确认)
    GCEligible --> Pruned: 裁剪协议执行\n回收元数据
    Pruned --> [*]

    Tombstoned --> Tombstoned: 等待远端副本同步
    GCEligible --> GCEligible: 等待裁剪屏障确认

上图描述了墓碑从产生到最终被回收的完整生命周期。元素被删除后进入墓碑状态，此时元数据必须保留以确保与尚未同步的副本合并时语义正确。当所有副本都确认已观察到该删除操作后，墓碑达到因果稳定，进入可回收状态。最终通过裁剪协议的屏障确认机制，墓碑的元数据被安全清除，释放存储空间。在每个中间阶段，墓碑可能因等待远端同步或屏障确认而停留较长时间，这也是墓碑回收在实践中面临的主要挑战。

CvRDT 与 CmRDT 的实现选择

CRDT 有两种等价的实现形式：

基于状态的 CvRDT（Convergent Replicated Data Type）： 节点之间传输完整状态，接收方用 merge 函数合并。优点是实现简单，对网络层的要求低（只需要最终可达，不需要因果有序）；缺点是带宽消耗大，每次同步都传输完整状态。

基于操作的 CmRDT（Commutative Replicated Data Type）： 节点之间传输操作（如 “increment”、“add(x)”），接收方重放操作。优点是带宽小（只传输变化量）；缺点是要求底层通信层提供因果有序的可靠广播（Causal Order Reliable Broadcast），实现复杂度更高。

Shapiro 等人在 2011 年的论文中证明了 CvRDT 和 CmRDT 在表达能力上是等价的：任何 CvRDT 都可以转换为对应的 CmRDT，反之亦然。

实际系统中的选择：

delta-CRDT 是一种折中方案：不传输完整状态，也不传输单个操作，而是传输自上次同步以来的状态增量（delta）。Almeida 等人在 2018 年的论文中给出了系统性的 delta-CRDT 框架，Riak 2.2 和 AntidoteDB 都采用了这种方式。

参考文献

  1. Shapiro, M., Preguiça, N., Baquero, C., & Zawirski, M. (2011). “A comprehensive study of Convergent and Commutative Replicated Data Types.” INRIA Technical Report RR-7506. https://hal.inria.fr/inria-00555588

  2. Bieniusa, A., Zawirski, M., Preguiça, N., Shapiro, M., Baquero, C., Balegas, V., & Duarte, S. (2012). “An Optimized Conflict-free Replicated Set.” arXiv:1210.3368. https://arxiv.org/abs/1210.3368

  3. Roh, H. G., Jeon, M., Kim, J. S., & Lee, J. (2011). “Replicated abstract data types: Building blocks for collaborative applications.” Journal of Parallel and Distributed Computing, 71(3), 354-368. https://doi.org/10.1016/j.jpdc.2010.12.006

  4. Almeida, P. S., Shoker, A., & Baquero, C. (2018). “Delta State Replicated Data Types.” Journal of Parallel and Distributed Computing, 111, 162-173. https://doi.org/10.1016/j.jpdc.2017.08.003

  5. Nedelec, B., Molli, P., Mostefaoui, A., & Desmontils, E. (2013). “LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing.” ACM DocEng 2013. https://doi.org/10.1145/2494266.2494278

  6. Weiss, S., Urso, P., & Molli, P. (2009). “Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks.” ICDCS 2009. https://doi.org/10.1109/ICDCS.2009.75

  7. Jahns, K. (2016). “YATA: Yet Another Transformation Approach.” Technical Report, RWTH Aachen University.

  8. Kleppmann, M., Gomes, V. B. F., Mulligan, D. P., & Beresford, A. R. (2019). “Interleaving anomalies in collaborative text editors.” PaPoC 2019. https://doi.org/10.1145/3301419.3323972

  9. Baquero, C., Almeida, P. S., & Lerche, C. (2017). “The problem with embedded CRDT counters and a solution.” PaPoC 2017. https://doi.org/10.1145/3064889.3064893

上一篇：CRDT 理论 下一篇：CRDT 在协同编辑中的应用

By .