【分布式系统百科】CRDT 理论：从半格代数到强最终一致性

两个用户同时在协作文档的同一段落各自插入了一句话。没有中心服务器协调，两台设备在断网状态下各自完成编辑，重新上线后需要合并。如果简单地用”后写入者胜出”策略，必然丢弃一方的修改；如果走共识协议，断网期间就无法写入。有没有一种数据结构，能让每个副本独立更新，在任意顺序收到对方的更新后自动收敛到同一状态，且不丢失任何修改？

这正是 CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）要解决的问题。CRDT 的理论根基不在分布式系统本身，而在抽象代数中一个朴素的结构——半格（Semilattice）。本文从数学基础出发，严格推导 CRDT 的两种形式化定义及其等价性，最后讨论强最终一致性的精确含义、元数据开销的理论下界，以及 CRDT 与共识协议的本质区别。

一、数学基础：偏序集、半格与最小上界

1.1 偏序集（Poset）

CRDT 的数学基础始于偏序关系。一个偏序集（Partially Ordered Set，Poset）是一个二元组 (S, ≤)，其中 S 是一个集合，≤ 是 S 上的一个二元关系，满足以下三条公理：

• 自反性（Reflexivity）：对任意 a ∈ S，有 a ≤ a。
• 反对称性（Antisymmetry）：对任意 a, b ∈ S，若 a ≤ b 且 b ≤ a，则 a = b。
• 传递性（Transitivity）：对任意 a, b, c ∈ S，若 a ≤ b 且 b ≤ c，则 a ≤ c。

偏序与全序（Total Order）的区别在于：偏序允许两个元素之间”不可比较”。例如在集合的包含关系中，{a} 和 {b} 之间既不满足 {a} ⊆ {b}，也不满足 {b} ⊆ {a}，它们是不可比的。

为什么偏序对 CRDT 如此重要？因为分布式系统中副本状态的演化天然形成偏序：如果副本 A 的状态包含了副本 B 已经看到的所有更新，再加上一些 B 还没收到的更新，那么 B 的状态”小于等于”A 的状态。但两个副本可能各自收到了对方没有的更新，此时它们的状态就是不可比的——这恰好对应并发修改的场景。

1.2 上界与最小上界（LUB / Join）

给定偏序集 (S, ≤) 和子集 X ⊆ S，元素 u ∈ S 是 X 的一个上界（Upper Bound），当且仅当对所有 x ∈ X 都有 x ≤ u。

最小上界（Least Upper Bound，LUB），也称为上确界（Supremum）或连接（Join），记作 ⊔X 或对两个元素的情况记作 a ⊔ b，是满足以下条件的上界：对 X 的任意上界 u，都有 ⊔X ≤ u。直觉上，LUB 是”刚好能覆盖所有输入的最小状态”。

用集合的例子说明：对于 {a, b} 和 {b, c}，它们的上界包括 {a, b, c}、{a, b, c, d} 等所有包含二者的集合，但最小上界恰好是 {a, b, c} = {a, b} ∪ {b, c}。这不是巧合：集合的并运算就是包含偏序下的 join 运算。

1.3 半格（Semilattice）

一个连接半格（Join-Semilattice）是偏序集 (S, ≤)，其中任意两个元素 a, b ∈ S 的最小上界 a ⊔ b 都存在。等价地，可以从代数的角度定义：一个连接半格是一个代数结构 (S, ⊔)，其中二元运算 ⊔ 满足：

• 交换律（Commutativity）：a ⊔ b = b ⊔ a
• 结合律（Associativity）：(a ⊔ b) ⊔ c = a ⊔ (b ⊔ c)
• 幂等律（Idempotency）：a ⊔ a = a

这三条性质称为 ACI 性质。从 ⊔ 可以反过来定义偏序：a ≤ b 当且仅当 a ⊔ b = b。两种定义完全等价。

幂等律是 CRDT 的关键：同一个状态合并两次不会改变结果。这意味着网络层可以重复发送同一份状态更新，接收方多次合并不会出错。交换律意味着合并的顺序无关。结合律意味着可以任意分组合并。三者结合起来保证：无论副本以何种顺序、何种次数收到更新，只要最终收到的更新集合相同，最终状态就相同。

1.4 Go 实现：IntMax 半格

用一个最简单的例子来说明半格的代码表示。整数集合上取 max 运算构成一个连接半格：

package crdt

// IntMaxSemilattice 整数最大值半格。
// 偏序：a ≤ b iff a <= b（普通整数序）。
// Join：max(a, b)。
type IntMaxSemilattice struct {
    Value int
}

// Join 计算两个元素的最小上界。
// 满足 ACI 三条性质：
//   max(a, b) == max(b, a)           交换律
//   max(max(a, b), c) == max(a, max(b, c))  结合律
//   max(a, a) == a                   幂等律
func (s IntMaxSemilattice) Join(other IntMaxSemilattice) IntMaxSemilattice {
    if other.Value > s.Value {
        return IntMaxSemilattice{Value: other.Value}
    }
    return s
}

// Leq 偏序比较：a ≤ b iff join(a, b) == b。
func (s IntMaxSemilattice) Leq(other IntMaxSemilattice) bool {
    return s.Value <= other.Value
}

验证 ACI 性质：max(3, 5) = max(5, 3) = 5（交换）；max(max(1, 3), 5) = max(1, max(3, 5)) = 5（结合）；max(4, 4) = 4（幂等）。这个结构虽然简单，却是 G-Counter 中每个节点计数器的核心。

1.5 更复杂的半格：集合并

集合的并运算是另一个经典半格。幂等集（Grow-only Set，G-Set）直接基于此：

package crdt

// GSet 只增长集合，基于集合并半格。
type GSet struct {
    Elements map[string]bool
}

func NewGSet() *GSet {
    return &GSet{Elements: make(map[string]bool)}
}

func (s *GSet) Add(elem string) {
    s.Elements[elem] = true
}

func (s *GSet) Contains(elem string) bool {
    return s.Elements[elem]
}

// Join 集合并。
// {a, b} ⊔ {b, c} = {a, b, c}
func (s *GSet) Join(other *GSet) *GSet {
    result := NewGSet()
    for k := range s.Elements {
        result.Elements[k] = true
    }
    for k := range other.Elements {
        result.Elements[k] = true
    }
    return result
}

集合并满足 ACI：A ∪ B = B ∪ A；(A ∪ B) ∪ C = A ∪ (B ∪ C)；A ∪ A = A。G-Set 的局限在于元素只能增加不能删除，这正是 2P-Set、OR-Set 等更复杂类型存在的原因，我们将在下一篇文章中详细讨论。

二、State-based CRDT（CvRDT）：状态即半格

2.1 形式化定义

Shapiro 等人在 2011 年的论文中给出了 State-based CRDT 的精确定义。一个 CvRDT（Convergent Replicated Data Type）是一个五元组 (S, s⁰, q, u, m)：

• S：状态的连接半格，配备偏序 ≤ 和 join 运算 ⊔
• s⁰ ∈ S：初始状态，通常是半格的最小元素（bottom）
• q: S → result：查询函数，从状态计算返回值
• u: S → S：更新函数，产生新状态，要求单调递增：u(s) ≥ s（即 s ≤ u(s)）
• m: S × S → S：合并函数，定义为 m(s₁, s₂) = s₁ ⊔ s₂

关键约束是更新的单调性：每次本地更新只能让状态在偏序关系上增大或不变，永远不能”后退”。这保证了一旦某个信息被记录到状态中，后续的更新和合并都不会将其丢弃。

2.2 同步协议

CvRDT 的同步协议直截了当：每个副本定期将自己的完整状态发送给其他副本。接收方执行 merge（即 join）操作，将远端状态与本地状态合并。协议不要求可靠传输——如果一条消息丢失，后续的状态传输自然会包含之前的所有信息，因为状态是单调增长的。

package crdt

// GCounter 增长计数器，经典的 CvRDT。
// 每个节点维护自己的局部计数，全局值 = 所有计数之和。
type GCounter struct {
    Counts map[string]uint64 // nodeID -> count
}

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

// Increment 在指定节点上加 1。
// 单调性：counts[nodeID] 只增不减，因此新状态 ≥ 旧状态。
func (g *GCounter) Increment(nodeID string) {
    g.Counts[nodeID]++
}

// Value 查询全局计数值。
func (g *GCounter) Value() uint64 {
    var sum uint64
    for _, c := range g.Counts {
        sum += c
    }
    return sum
}

// Merge 合并两个 GCounter。
// 对每个 nodeID 取 max，即逐分量的 join。
func (g *GCounter) Merge(other *GCounter) *GCounter {
    result := NewGCounter()
    for k, v := range g.Counts {
        result.Counts[k] = v
    }
    for k, v := range other.Counts {
        if v > result.Counts[k] {
            result.Counts[k] = v
        }
    }
    return result
}

GCounter 的状态空间是从节点 ID 到非负整数的映射，偏序定义为逐分量比较：g₁ ≤ g₂ 当且仅当对每个 nodeID 都有 g₁.Counts[nodeID] ≤ g₂.Counts[nodeID]。join 运算是逐分量取 max。这是一个有限维整数向量的半格，也叫做乘积半格（Product Semilattice）——多个 IntMax 半格的笛卡尔积自然构成半格。

2.3 收敛性证明概要

CvRDT 的收敛性证明基于以下推理链：

引理 1（状态单调性）：设副本 i 在时刻 t₁ 的状态为 s，在时刻 t₂ > t₁ 的状态为 s'，则 s ≤ s'。

证明思路：从 t₁ 到 t₂ 之间，副本 i 经历的操作只有两种——本地更新和远端合并。本地更新满足 u(s) ≥ s（定义要求）。合并是 join 操作，s ⊔ r ≥ s（join 的定义）。由传递性，连续的更新和合并操作保持偏序的单调增长。

引理 2（合并收敛）：设副本 i 状态为 sᵢ，副本 j 状态为 sⱼ。当 i 收到 sⱼ 并执行合并后，新状态 sᵢ' = sᵢ ⊔ sⱼ ≥ sⱼ，即 i 的新状态包含了 j 在发送时的全部信息。

定理（强收敛）：若所有副本最终收到彼此的状态更新（Eventual Delivery），则所有副本最终达到相同的状态。

证明思路：假设在某个时刻之后不再有新的更新操作。由 Eventual Delivery，每个副本最终会收到所有其他副本的状态。对副本集合 {1, 2, ..., n}，设 S_final = s₁ ⊔ s₂ ⊔ ... ⊔ sₙ。由 join 的交换律和结合律，这个值与合并的顺序无关。由幂等律，重复收到同一副本的状态不会改变结果。由单调性，后续不会有状态”回退”。因此所有副本最终收敛到 S_final。

这个证明的优雅之处在于它完全是代数的——不依赖任何时序假设、网络拓扑或消息排序保证。只需要一个极弱的活性条件：消息最终能送达。

2.4 CvRDT 的代价

CvRDT 的主要代价是带宽：每次同步需要传输完整状态。对于 G-Set 这样的结构，随着元素不断加入，状态会持续增长。实践中有两种常见的优化策略：

• Delta-state CRDT（增量状态 CRDT）：只传输自上次同步以来的状态增量（delta），接收方将 delta 与本地状态做 join。delta 本身也必须是半格元素，因此保留了 CvRDT 的所有数学性质。Almeida 等人在 2018 年的论文中形式化了这一方法。
• 状态压缩：定期对状态进行垃圾回收或压缩，例如在 OR-Set 中，当确认某个元素的添加标记已被所有副本看到后，可以移除对应的元数据。这需要额外的因果稳定性（Causal Stability）检测机制。

三、Operation-based CRDT（CmRDT）：可交换的操作

3.1 形式化定义

CmRDT（Commutative Replicated Data Type）从操作而非状态的角度定义复制。一个 CmRDT 是一个六元组 (S, s⁰, q, t, u, P)：

• S：状态空间（不要求是半格）
• s⁰ ∈ S：初始状态
• q: S → result：查询函数
• t: S → op：准备函数（prepare），在源副本上执行，生成一个操作描述
• u: S × op → S：效果函数（effect），在所有副本上执行，将操作应用到本地状态
• P：操作之间的前置条件（precondition），描述操作的合法性

关键要求是效果函数的可交换性：对于任意可并发的操作 op₁ 和 op₂，u(u(s, op₁), op₂) = u(u(s, op₂), op₁)。即并发操作以任意顺序应用，结果相同。

3.2 传递要求

CmRDT 对底层通信层的要求比 CvRDT 更强。具体而言，CmRDT 要求：

• 恰好一次送达（Exactly-once delivery）：每个操作恰好被每个副本接收一次。重复送达可能破坏正确性——例如”加 1”操作如果被执行两次，计数器就多加了 1。
• 因果序送达（Causal order delivery）：如果操作 op₁ 因果先于 op₂（即 op₁ 的效果可能影响了 op₂ 的准备阶段），则所有副本必须先执行 op₁ 再执行 op₂。

这些要求在实践中通常通过可靠因果广播（Reliable Causal Broadcast）协议来实现，例如基于向量时钟的协议。注意，只要求因果序而非全序——并发操作可以以任意顺序到达，正是可交换性保证了结果的一致。

3.3 Op-based GCounter

package crdt

import "fmt"

// OpGCounter 基于操作的增长计数器。
type OpGCounter struct {
    NodeID string
    Counts map[string]uint64
}

// Op 描述一个增量操作。
type IncrementOp struct {
    NodeID string
}

func NewOpGCounter(nodeID string) *OpGCounter {
    return &OpGCounter{
        NodeID: nodeID,
        Counts: make(map[string]uint64),
    }
}

// Prepare 在源副本上生成操作。
func (g *OpGCounter) Prepare() IncrementOp {
    return IncrementOp{NodeID: g.NodeID}
}

// Effect 在所有副本上执行操作效果。
// 两个 IncrementOp 天然可交换：
//   effect(effect(s, inc_A), inc_B) == effect(effect(s, inc_B), inc_A)
// 因为它们修改不同的分量（不同 NodeID），或同一分量的加法本身可交换。
func (g *OpGCounter) Effect(op IncrementOp) {
    g.Counts[op.NodeID]++
}

func (g *OpGCounter) Value() uint64 {
    var sum uint64
    for _, c := range g.Counts {
        sum += c
    }
    return sum
}

func (g *OpGCounter) String() string {
    return fmt.Sprintf("OpGCounter{counts=%v, value=%d}", g.Counts, g.Value())
}

对比 State-based 版本，Op-based 版本在网络上传输的是一个 IncrementOp 结构体（只包含一个 NodeID 字符串），而不是整个 Counts 映射表。当节点数量很多、计数器值很大时，操作的大小远小于完整状态的大小。

3.4 因果交付的实现

因果交付可以用向量时钟（Vector Clock）来实现。每个副本维护一个长度为 n（副本总数）的向量。发送操作时附带当前向量时钟；接收方检查向量时钟是否满足因果条件，不满足则缓存（buffer）该操作等待前序操作到达：

package crdt

// CausalDelivery 基于向量时钟的因果交付层。
type CausalDelivery struct {
    NodeID  int
    N       int               // 副本总数
    VClock  []uint64          // 本地向量时钟
    Buffer  []BufferedMessage // 等待交付的消息
}

type BufferedMessage struct {
    SenderID int
    Clock    []uint64
    Op       interface{}
}

// CanDeliver 检查消息是否满足因果交付条件。
// 条件：msg.Clock[msg.SenderID] == local.VClock[msg.SenderID] + 1
//       且对所有 k != msg.SenderID，msg.Clock[k] <= local.VClock[k]
func (cd *CausalDelivery) CanDeliver(msg BufferedMessage) bool {
    if msg.Clock[msg.SenderID] != cd.VClock[msg.SenderID]+1 {
        return false
    }
    for k := 0; k < cd.N; k++ {
        if k != msg.SenderID && msg.Clock[k] > cd.VClock[k] {
            return false
        }
    }
    return true
}

// OnDeliver 交付消息后更新向量时钟。
func (cd *CausalDelivery) OnDeliver(msg BufferedMessage) {
    cd.VClock[msg.SenderID] = msg.Clock[msg.SenderID]
}

四、State-based 与 Operation-based 的等价性

4.1 等价性定理

Shapiro 等人在 2011 年的论文中证明了一个核心定理：任何 CvRDT 都可以模拟为一个 CmRDT，反之亦然。具体而言：

定理 4.1：设 F 是一个 CvRDT，则存在一个 CmRDT G，使得 F 和 G 在语义上等价（即对相同的操作序列产生相同的查询结果）。反之，设 G 是一个 CmRDT，则存在一个 CvRDT F，使得二者语义等价。

4.2 从 CvRDT 到 CmRDT

给定一个 CvRDT (S, s⁰, q, u, m)，构造等价的 CmRDT：

• 状态空间保持不变为 S
• 准备阶段（prepare）：执行本地更新 u(s)，然后将更新后的完整状态作为操作内容发送
• 效果阶段（effect）：接收到远端状态 s_remote 后，执行 m(s_local, s_remote) = s_local ⊔ s_remote

这个构造下，effect 函数本质上就是 join 操作。join 的交换律直接保证了 effect 的可交换性。幂等律保证了即使重复接收也不会出错（虽然 CmRDT 要求恰好一次送达，但这个特殊构造实际上容忍重复）。

// 从 CvRDT 到 CmRDT 的转换示意：
// 将 state-based GCounter 转为 op-based 形式。
// "操作"就是发送完整状态。

type StateToCmRDTAdapter struct {
    state *GCounter
}

// Prepare 生成操作 = 当前完整状态的快照。
func (a *StateToCmRDTAdapter) Prepare() *GCounter {
    snapshot := NewGCounter()
    for k, v := range a.state.Counts {
        snapshot.Counts[k] = v
    }
    return snapshot
}

// Effect 应用操作 = 将远端状态与本地状态 merge。
func (a *StateToCmRDTAdapter) Effect(remoteState *GCounter) {
    a.state = a.state.Merge(remoteState)
}

4.3 从 CmRDT 到 CvRDT

这个方向的构造更为精妙。给定一个 CmRDT (S, s⁰, q, t, u, P)，构造等价的 CvRDT：

• 新的状态空间 S' 定义为：初始状态 s⁰ 加上从 s⁰ 出发、通过有限次应用 effect 函数可达的所有状态组成的集合。由操作的可交换性，可以将每个可达状态唯一地表示为从 s⁰ 出发应用的操作的多重集合（multiset）。
• 偏序定义为：s₁ ≤ s₂ 当且仅当产生 s₁ 的操作多重集合是产生 s₂ 的操作多重集合的子集。
• Join 运算：s₁ ⊔ s₂ 对应两个操作多重集合的并集所产生的状态。

可交换性保证了无论以何种顺序应用并集中的操作，结果相同。因此 join 运算是良定义的（well-defined）。幂等律、交换律、结合律分别由多重集合并的对应性质保证。

4.4 等价性的实际意义

这个等价性定理的实际意义在于：设计 CRDT 时可以自由选择最方便的形式。如果某种数据类型的 merge 语义更直觉（如 G-Set 的集合并），用 CvRDT 定义更自然。如果操作语义更清晰（如序列的插入操作），用 CmRDT 定义更方便。最终都可以转化为另一种形式。

但两种形式在工程实现上的权衡是显著的：

Delta-state CRDT 试图兼取两者之长：传输增量（接近 op-based 的小消息），但使用 merge 语义（保留 state-based 的容错性）。

五、强最终一致性（SEC）的精确定义

5.1 最终一致性的问题

在讨论 CRDT 的一致性保证之前，需要区分两个容易混淆的概念。

最终一致性（Eventual Consistency，EC）是一个相当弱的保证。非形式地说，它要求”如果不再有新的写入，所有副本最终会达到相同的状态”。这个定义存在两个根本缺陷：

第一，它只在”不再有新写入”的假设下成立，但在实际系统中这几乎不会发生。第二，即使满足条件，它也不保证收敛到哪个状态——不同副本可能采用不同的冲突解决策略（例如”最后写入者胜出”），产生不可预期的结果。用户可能看到自己的写入被默默丢弃，这在语义上是不可接受的。

5.2 SEC 的三条性质

Shapiro 等人定义的强最终一致性（Strong Eventual Consistency，SEC）包含三条性质：

性质 1——最终送达（Eventual Delivery）：如果某个正确的副本（即未发生故障的副本）接收到了一个更新，则所有正确的副本最终都会接收到该更新。

性质 2——强收敛（Strong Convergence）：任意两个已接收相同更新集合的正确副本处于相同的状态。注意这里没有”不再有新写入”的前提条件——只要两个副本已经看到了相同的更新，它们当前的状态就相同，无论将来是否还有新的更新到达。

性质 3——终止性（Termination）：所有更新操作和合并操作在有限步骤内完成。

与 EC 相比，SEC 的关键强化在于性质 2：不再有新更新只是两个副本具有相同更新集合的一个充分条件，而非必要条件。SEC 保证的是一种确定性的收敛——相同的输入一定产生相同的输出，不存在”冲突解决”中的任意选择。

5.3 CRDT 满足 SEC 的证明

定理 5.1：任何正确实现的 CvRDT 在满足最终送达的网络上满足 SEC。

证明概要：

• 终止性：merge 是一个纯函数计算（通常是逐分量 max 或集合并），在有限时间内完成。
• 强收敛：设副本 i 和 j 已接收到相同的更新集合 U = {u₁, u₂, ..., uₖ}。副本 i 的状态是 s⁰ ⊔ u₁(s⁰) ⊔ u₂(...) ⊔ ... ⊔ uₖ(...)。由 join 的交换律和结合律，不论这些 join 运算以何种顺序和分组方式执行，结果相同。因此副本 j 也得到相同的最终状态。
• 最终送达：这是对网络的要求，不是 CRDT 本身的性质。CRDT 正确性的证明假设网络满足此条件。

// 演示 SEC：三个副本并发更新后 merge，无论合并顺序，结果相同。
func demonstrateSEC() {
    a := NewGCounter()
    b := NewGCounter()
    c := NewGCounter()

    // 三个副本并发更新
    a.Increment("node-a")
    a.Increment("node-a")
    b.Increment("node-b")
    c.Increment("node-c")
    c.Increment("node-c")
    c.Increment("node-c")

    // 合并顺序 1：(a ⊔ b) ⊔ c
    r1 := a.Merge(b).Merge(c)

    // 合并顺序 2：a ⊔ (c ⊔ b)
    r2 := a.Merge(c.Merge(b))

    // 合并顺序 3：(c ⊔ a) ⊔ b
    r3 := c.Merge(a).Merge(b)

    // r1 == r2 == r3，Value() 均为 6
    // 强收敛：相同的更新集合 => 相同的状态
    fmt.Println(r1.Value(), r2.Value(), r3.Value()) // 6 6 6
}

5.4 从定理到生产：LUB 存在性的实际含义

前面几节证明了 State-based CRDT 满足 SEC，其核心依赖是半格的 LUB 存在性定理：任意两个状态 a, b ∈ S，其最小上界 a ⊔ b 必然存在且唯一。这条看似抽象的代数性质，在生产环境中有着非常具体的含义。以 G-Counter 为例，将这条定理翻译为工程保证。

场景设定：一个分布式计数器部署在 5 个副本（R1 至 R5）上。每个副本独立接受本地的 Increment 操作，初始状态均为零向量 [0, 0, 0, 0, 0]。经过一段时间的独立操作后，各副本的本地状态分别为：

• R1：[3, 0, 0, 0, 0]（R1 本地自增了 3 次）
• R2：[0, 2, 0, 0, 0]（R2 本地自增了 2 次）
• R3：[0, 0, 4, 0, 0]（R3 本地自增了 4 次）
• R4：[0, 0, 0, 1, 0]（R4 本地自增了 1 次）
• R5：[0, 0, 0, 0, 5]（R5 本地自增了 5 次）

定理映射：G-Counter 的合并运算定义为分量取 max，即 (a ⊔ b)[i] = max(a[i], b[i])。第一节已经证明这个运算满足交换律、结合律和幂等律，因此 (Z≥0^n, ⊔) 构成连接半格，LUB 必然存在。将此定理应用到上述 5 个副本的状态集合 {R1, R2, R3, R4, R5}，它们的 LUB 是分量取 max 的结果：

LUB = [max(3,0,0,0,0), max(0,2,0,0,0), max(0,0,4,0,0), max(0,0,0,1,0), max(0,0,0,0,5)]
    = [3, 2, 4, 1, 5]
Value = 3 + 2 + 4 + 1 + 5 = 15

关键在于：无论消息以何种顺序到达，最终状态都是同一个 LUB。下面用三种截然不同的消息传播路径验证这一点。

• 路径 A（链式传播）：R1 → R2 → R3 → R4 → R5，状态沿链逐步合并。
• 路径 B（星形传播）：所有副本先发送给 R3，R3 再广播给其余副本。
• 路径 C（乱序传播）：R5 先收到 R2，然后 R4 收到 R1 和 R5 的合并结果，最后 R3 收到所有。

sequenceDiagram
    participant R1
    participant R2
    participant R3
    participant R4
    participant R5

    Note over R1: [3,0,0,0,0]
    Note over R2: [0,2,0,0,0]
    Note over R3: [0,0,4,0,0]
    Note over R4: [0,0,0,1,0]
    Note over R5: [0,0,0,0,5]

    rect rgb(220, 235, 250)
    Note over R1,R5: 路径 A：链式传播
    R1->>R2: merge → [3,2,0,0,0]
    R2->>R3: merge → [3,2,4,0,0]
    R3->>R4: merge → [3,2,4,1,0]
    R4->>R5: merge → [3,2,4,1,5]
    end

    rect rgb(235, 250, 220)
    Note over R1,R5: 路径 B：星形传播
    R1->>R3: merge
    R2->>R3: merge
    R4->>R3: merge
    R5->>R3: merge → [3,2,4,1,5]
    R3->>R1: broadcast
    R3->>R2: broadcast
    R3->>R4: broadcast
    R3->>R5: broadcast
    end

    rect rgb(250, 235, 220)
    Note over R1,R5: 路径 C：乱序传播
    R2->>R5: merge → [0,2,0,0,5]
    R1->>R4: merge → [3,0,0,1,0]
    R5->>R4: merge → [3,2,0,1,5]
    R4->>R3: merge → [3,2,4,1,5]
    R3->>R1: broadcast
    R3->>R2: broadcast
    R3->>R5: broadcast
    end

    Note over R1,R5: 三条路径最终状态均为 [3,2,4,1,5]，Value = 15

上图展示了三种完全不同的消息传播路径：链式逐跳转发、以 R3 为中心的星形汇聚，以及无规律的乱序传播。每条路径中各副本收到消息的时间和顺序各不相同，中间状态也截然不同（例如路径 C 中 R5 的中间状态是 [0,2,0,0,5]，而路径 A 中 R5 直到最后一步才参与合并）。然而，由于 LUB 的存在性和唯一性保证了合并运算的交换律与结合律，三条路径最终都收敛到同一状态 [3,2,4,1,5]，计数值均为 15。这就是 LUB 存在性定理在生产中的直接体现：它将”消息可以乱序、重复、延迟到达”从一个需要担心的工程问题，转化为一个已被数学证明无害的性质。

5.5 SEC 与线性一致性的关系

SEC 和线性一致性（Linearizability）位于一致性谱系的两端。线性一致性要求所有操作看起来像是在单个副本上按某个全局顺序执行的，这要求同步协调，在网络分区时不可用（CAP 定理的直接推论）。SEC 完全放弃了操作的全局排序，只要求相同的更新集合产生相同的结果。

这个权衡可以用 CAP 定理来理解：线性一致性选择了 C（Consistency）放弃 A（Availability）；CRDT 选择了 A 和 P（Partition tolerance），放弃了强一致性 C，但通过代数结构保证了一种弱于线性一致性却强于最终一致性的中间地带。

六、更多类型预览：MV-Register 与 RGA

前面的 GCounter 和 GSet 是最简单的 CRDT 类型。实际应用中需要更丰富的语义：寄存器需要支持并发写入，序列需要支持插入和删除。本节简要介绍两个重要类型，详细分析将在下一篇文章展开。

6.1 MV-Register（多值寄存器）

LWW-Register（Last-Writer-Wins Register）使用时间戳来解决并发写入冲突，总是保留时间戳最大的值。这很简单，但丢弃了并发写入中时间戳较小的值。MV-Register（Multi-Value Register，多值寄存器）采取不同策略：保留所有并发值，让应用层决定如何解决冲突。

MV-Register 的核心思想是用向量时钟标记每个写入。当两个写入的向量时钟不可比较（即存在因果并发关系）时，两个值都被保留。当一个写入因果依赖于（“happens-after”）另一个时，新值替换旧值。

package crdt

// MVRegister 多值寄存器。
// 并发写入产生多个值（类似 Amazon Dynamo 的 siblings）。
type MVRegister struct {
    Entries []MVEntry
}

type MVEntry struct {
    Value  interface{}
    VClock map[string]uint64 // 写入时的向量时钟
}

// Write 写入新值，附带因果上下文。
func (r *MVRegister) Write(value interface{}, nodeID string) {
    // 新的向量时钟 = merge所有现有条目的时钟 + 自增
    merged := make(map[string]uint64)
    for _, e := range r.Entries {
        for k, v := range e.VClock {
            if v > merged[k] {
                merged[k] = v
            }
        }
    }
    merged[nodeID]++
    // 新写入替换所有现有条目（它因果地覆盖了所有）
    r.Entries = []MVEntry{{Value: value, VClock: merged}}
}

// Read 返回所有并发值。
func (r *MVRegister) Read() []interface{} {
    var values []interface{}
    for _, e := range r.Entries {
        values = append(values, e.Value)
    }
    return values
}

// Merge 合并两个 MV-Register。
// 保留所有不被因果支配的条目。
func (r *MVRegister) Merge(other *MVRegister) *MVRegister {
    result := &MVRegister{}
    all := append(r.Entries, other.Entries...)
    for i, ei := range all {
        dominated := false
        for j, ej := range all {
            if i != j && vcDominates(ej.VClock, ei.VClock) {
                dominated = true
                break
            }
        }
        if !dominated {
            result.Entries = append(result.Entries, ei)
        }
    }
    return result
}

// vcDominates 检查 a 是否因果支配 b（a > b）。
func vcDominates(a, b map[string]uint64) bool {
    if len(a) == 0 && len(b) == 0 {
        return false
    }
    atLeastOneGreater := false
    for k, bv := range b {
        if a[k] < bv {
            return false
        }
        if a[k] > bv {
            atLeastOneGreater = true
        }
    }
    for k, av := range a {
        if _, exists := b[k]; !exists && av > 0 {
            atLeastOneGreater = true
        }
    }
    return atLeastOneGreater
}

Amazon Dynamo 系统使用的就是类似 MV-Register 的机制（论文中称为”siblings”）。客户端在读取时收到多个并发值，需要自行合并。这种设计将冲突解决的责任推给了应用层，增加了编程复杂度，但不丢失任何信息。

6.2 RGA（Replicated Growable Array）

RGA 是一种用于协作编辑的序列 CRDT。在协作文档编辑中，两个用户可能同时在相邻位置插入字符。RGA 使用时间戳和因果关系来确定并发插入的相对顺序。

RGA 的核心数据结构是一个链表，每个节点包含：

• 内容（字符或文本片段）
• 唯一标识符（通常是 (timestamp, nodeID) 对）
• 逻辑删除标记（tombstone）

插入操作指定”在哪个标识符之后插入”，而非”在第几个位置插入”。这避免了位置偏移问题：当两个用户同时在位置 3 插入时，如果用数组索引，两个插入会冲突。用前驱标识符就不会——两个插入各自指定了自己的前驱，不存在语义冲突。

package crdt

// RGANode RGA 链表节点。
type RGANode struct {
    ID        RGAID       // 唯一标识：(lamport timestamp, nodeID)
    Content   rune        // 字符内容
    Deleted   bool        // 逻辑删除标记（tombstone）
    Next      *RGANode    // 链表后继
}

type RGAID struct {
    Timestamp uint64
    NodeID    string
}

// CompareID 比较两个 RGA ID，用于确定并发插入的顺序。
// 先比 timestamp（大者在前），再比 nodeID（字典序大者在前）。
func CompareID(a, b RGAID) int {
    if a.Timestamp != b.Timestamp {
        if a.Timestamp > b.Timestamp {
            return -1
        }
        return 1
    }
    if a.NodeID > b.NodeID {
        return -1
    }
    if a.NodeID < b.NodeID {
        return 1
    }
    return 0
}

RGA 的完整实现较为复杂，我们将在下一篇文章中详细展开。这里需要指出的关键点是：RGA 的 tombstone 机制（逻辑删除而非物理删除）是必须的，因为删除操作需要可交换——如果物理删除一个节点，后续引用该节点的操作就无法定位了。但 tombstone 会导致元数据永久增长，这正是下一节讨论的元数据开销问题。

七、元数据大小的理论下界

7.1 问题的提出

CRDT 为了实现无冲突合并，需要在状态中维护元数据（Metadata）。GCounter 需要一个长度等于副本数量的向量；OR-Set 需要为每个元素维护唯一标识符集合；RGA 的 tombstone 会无限积累。一个自然的问题是：这些元数据开销是 CRDT 的本质限制，还是可以通过更巧妙的设计来消除？

7.2 Burckhardt 的下界定理

Burckhardt 等人证明了一系列关于 CRDT 元数据大小的下界结果。核心结论是：

对于计数器类型：任何实现 counter 语义的 CRDT，其状态大小至少为 O(n) 位，其中 n 是副本数量。这意味着 GCounter 使用 n 个整数的设计在渐近意义上是最优的。

对于集合类型：实现 add/remove 语义的 CRDT（如 OR-Set），其元数据大小的下界依赖于并发操作的数量。在最坏情况下，一个支持 k 次 add 操作的 OR-Set 需要 O(k) 大小的元数据，即使集合当前只有一个元素。

对于序列类型：支持 insert/delete 的序列 CRDT，tombstone 的数量至少与历史上删除的元素数量成正比。在没有垃圾回收的情况下，元数据大小随操作历史线性增长。

7.3 直觉解释

为什么元数据开销不可避免？回到 CRDT 的核心思想：每个副本独立操作，合并时自动收敛。这意味着每个副本必须在其本地状态中编码足够的信息，使得 merge 函数能够在不知道对方操作历史的情况下产生正确结果。

以 OR-Set 为例：当 add(x) 和 remove(x) 并发时，OR-Set 选择”add 胜出”的语义。为了实现这个语义，每次 add 操作需要给元素附加一个唯一标记（tag），remove 操作只删除当前已知的标记。并发的 add 会产生新的标记，因此不会被并发的 remove 删除。这些标记就是元数据的来源：

package crdt

import "fmt"

// ORSet 观察-删除集合的元数据示意。
type ORSet struct {
    // Elements 从元素映射到其所有活跃标记（unique tags）。
    // 每次 add 生成新标记，remove 只移除已观察到的标记。
    Elements map[string]map[string]bool // element -> {tag -> true}
    Counter  uint64                      // 用于生成唯一标记
    NodeID   string
}

func NewORSet(nodeID string) *ORSet {
    return &ORSet{
        Elements: make(map[string]map[string]bool),
        NodeID:   nodeID,
    }
}

func (s *ORSet) Add(elem string) {
    s.Counter++
    tag := fmt.Sprintf("%s:%d", s.NodeID, s.Counter)
    if s.Elements[elem] == nil {
        s.Elements[elem] = make(map[string]bool)
    }
    s.Elements[elem][tag] = true
}

func (s *ORSet) Remove(elem string) {
    // 只移除当前已观察到的标记。
    // 并发 add 产生的新标记不会被移除。
    delete(s.Elements, elem)
}

func (s *ORSet) Contains(elem string) bool {
    return len(s.Elements[elem]) > 0
}

// Merge OR-Set 的合并。
// 对每个元素，标记集合取并集（G-Set 语义）。
// 但被某一侧 remove 显式移除的标记不保留。
func (s *ORSet) Merge(other *ORSet) *ORSet {
    result := &ORSet{
        Elements: make(map[string]map[string]bool),
        NodeID:   s.NodeID,
        Counter:  s.Counter,
    }
    if other.Counter > result.Counter {
        result.Counter = other.Counter
    }
    // 简化版：取两侧标记的并集
    for elem, tags := range s.Elements {
        if result.Elements[elem] == nil {
            result.Elements[elem] = make(map[string]bool)
        }
        for t := range tags {
            result.Elements[elem][t] = true
        }
    }
    for elem, tags := range other.Elements {
        if result.Elements[elem] == nil {
            result.Elements[elem] = make(map[string]bool)
        }
        for t := range tags {
            result.Elements[elem][t] = true
        }
    }
    return result
}

7.4 垃圾回收：突破下界的实践

理论下界假设的是最坏情况，实践中可以通过垃圾回收（Garbage Collection，GC）来控制元数据增长。GC 的核心思想是：如果能确定某个元数据已经被所有副本观察到（即已经达到因果稳定性），就可以安全地移除它。

因果稳定性的判定通常依赖全局知识（例如一个所有副本都确认的最小向量时钟），这在完全去中心化的环境中代价较高。一种折中方案是使用”纪元”（epoch）机制：定期执行一轮全局同步，确认某个时间点之前的所有操作已被所有副本接收，然后压缩该时间点之前的元数据。

这引出了一个有趣的悖论：CRDT 的设计初衷是避免全局协调，但垃圾回收却需要某种程度的全局协调。实际系统通常接受这个折中——GC 不在关键路径上，可以异步、延迟地执行，不影响 CRDT 的可用性保证。

八、与共识的关系：CRDT 不需要共识

8.1 共识问题的本质

共识（Consensus）要求一组进程对某个值达成一致，满足三个条件：一致性（所有正确进程决定同一个值）、有效性（决定的值必须是某个进程提议的）、终止性（所有正确进程最终做出决定）。FLP 不可能定理证明了在异步系统中，即使只有一个进程可能崩溃，也不存在确定性的共识算法。

实践中，Paxos、Raft 等算法通过引入超时和领导者选举等机制来绕过 FLP 不可能性，但它们在网络分区期间可能无法取得进展（牺牲可用性）。

8.2 CRDT 为何不需要共识

CRDT 的核心洞察在于：如果所有并发操作的合并结果是确定的（由代数结构保证），就不需要各副本对操作的顺序达成一致。换言之，CRDT 通过约束数据类型的语义来消除冲突的可能性，而非通过协调来解决冲突。

这可以从 CAP 定理的角度理解。CAP 定理指出，分布式系统在网络分区时不能同时保证强一致性和可用性。共识算法选择了一致性（CP），在分区时拒绝服务。CRDT 选择了可用性（AP），在分区时继续服务，但只提供 SEC 而非线性一致性。

共识（Paxos/Raft）：
  客户端 → 提议 → 领导者 → 复制到多数派 → 提交 → 回复客户端
  分区时：少数派侧的客户端无法写入（不可用）

CRDT：
  客户端 → 本地更新 → 立即回复客户端 → 异步传播到其他副本
  分区时：所有副本都可以继续读写（始终可用）
  代价：只保证 SEC，不保证线性一致性

8.3 形式化论证

Shapiro 等人的论文中包含了以下形式化结论：

定理 8.1：CvRDT 和 CmRDT 不需要共识即可保证 SEC。具体而言，在异步系统中，只要通信通道满足最终送达（对 CvRDT）或可靠因果广播（对 CmRDT），CRDT 就能保证 SEC。

这个结论的重要性在于：它意味着 CRDT 可以在 FLP 不可能定理的限制之外运作。共识在异步系统中不可能，但 CRDT 不需要共识，因此 CRDT 在异步系统中完全可以正确运行。

8.4 CRDT 不能替代共识的场景

尽管 CRDT 避免了共识的开销，它也有本质的局限性。以下场景仍然需要共识：

全局不变量维护：假设系统中有一个约束”库存不能为负”。两个副本各自检查库存为 1，各自卖出 1 件商品。合并后库存变为 -1，违反了不变量。维护这种跨副本的全局不变量需要在写入前协调，这正是共识的职责。

全局唯一性：例如唯一用户名分配。两个副本可能同时将同一用户名分配给不同用户。CRDT 的合并无法解决这种语义冲突——用户名只能属于一个用户。

全序要求：某些应用需要确定操作的全局顺序（例如银行转账的对账）。CRDT 只保证结果收敛，不保证操作的顺序一致。

// 全局不变量违反的示例：库存计数器。
// 两个副本各自减 1，合并后库存为负。
func inventoryViolation() {
    // 使用 PN-Counter（允许加减的计数器）
    replicaA := map[string]int{"inc": 10, "dec": 0} // 库存 10
    replicaB := map[string]int{"inc": 10, "dec": 0} // 库存 10

    // 副本 A：检查库存 > 0，卖出 10 件
    replicaA["dec"] = 10 // 本地库存 = 10 - 10 = 0

    // 副本 B：同时检查库存 > 0，也卖出 10 件
    replicaB["dec"] = 10 // 本地库存 = 10 - 10 = 0

    // Merge：inc 取 max(10,10)=10，dec 取 max(10,10)=10
    // 结果库存 = 10 - 10 = 0？不对——实际卖出了 20 件！
    // PN-Counter 的 merge 丢失了两个副本各自的递减量。

    // 正确的做法需要使用向量化的 PN-Counter
    // 但即使如此也无法阻止超卖——这需要共识。
}

8.5 混合架构

实际系统通常混合使用 CRDT 和共识。例如：

• Riak：键值存储使用 CRDT 类型（计数器、集合、映射等），集群成员管理使用 Raft 共识。
• AntidoteDB：分区内使用 Paxos 做因果一致性，分区间使用 CRDT 做跨数据中心复制。
• Redis CRDB（Redis Enterprise 的 Active-Active）：使用 CRDT 实现多主复制，配置管理使用 Raft。

这种混合架构的思路是：对不变量要求严格的元数据（如集群拓扑、分片映射）使用共识；对可用性要求高的用户数据使用 CRDT。二者各取所长，在同一系统中共存。

九、总结与展望

本文从偏序集和半格的数学基础出发，严格定义了 CRDT 的两种形式：State-based（CvRDT）和 Operation-based（CmRDT），并详细推导了二者的等价性。我们阐明了强最终一致性（SEC）与传统最终一致性的本质区别：SEC 通过代数结构提供确定性的收敛保证，而非依赖停写假设下的不确定收敛。

CRDT 的理论框架给出了两个深刻的洞察：

第一，代数结构可以替代协调协议。只要数据类型的合并运算满足半格的 ACI 性质，副本之间就不需要任何协调即可保证一致性。这将一致性问题从分布式协议领域转化为抽象代数领域。

第二，这种替代不是免费的。元数据开销的理论下界表明，无冲突合并的能力需要在状态中编码足够的因果信息，这带来了存储和带宽的开销。垃圾回收能够缓解但不能消除这个问题，而且垃圾回收本身需要某种形式的全局协调。

下一篇文章将从理论转向实践，系统地介绍各种 CRDT 类型——G-Counter、PN-Counter、G-Set、2P-Set、OR-Set、LWW-Register、MV-Register、RGA 等——的具体实现、语义选择和工程权衡。

参考文献

1. Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. “A comprehensive study of Convergent and Commutative Replicated Data Types.” INRIA Research Report RR-7506, 2011. https://hal.inria.fr/inria-00555588

2. Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. “Conflict-free Replicated Data Types.” In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2011), pp. 386–400, 2011. https://doi.org/10.1007/978-3-642-24550-3_29

3. Nuno Preguiça. “Conflict-free Replicated Data Types: An Overview.” arXiv preprint arXiv:1806.10254, 2018. https://arxiv.org/abs/1806.10254

4. Sebastian Burckhardt. “Principles of Eventual Consistency.” Foundations and Trends in Programming Languages, 1(1–2):1–150, 2014. https://doi.org/10.1561/2500000011

5. Paulo Sérgio Almeida, Ali Shoker, Carlos Baquero. “Delta State Replicated Data Types.” Journal of Parallel and Distributed Computing, 111:162–173, 2018. https://doi.org/10.1016/j.jpdc.2017.08.003

6. Hyun-Gul Roh, Myeongjae Jeon, Jin-Soo Kim, Joonwon Lee. “Replicated Abstract Data Types: Building Blocks for Collaborative Applications.” Journal of Parallel and Distributed Computing, 71(3):354–368, 2011. https://doi.org/10.1016/j.jpdc.2010.12.006

7. Carlos Baquero, Paulo Sérgio Almeida, Ali Shoker. “Making Operation-based CRDTs Operation-based.” In Proceedings of the 14th IFIP International Conference on Distributed Applications and Interoperable Systems (DAIS 2014), pp. 126–140, 2014. https://doi.org/10.1007/978-3-662-43352-2_11

上一篇：NewSQL 架构拆解 下一篇：CRDT 类型目录