无声立约者：CRDT 与”不争而胜”的分布式同步哲学

上篇：寓言——千岛贡品账本

一、南海千岛

南海上，散落着数百座小岛。

每座岛屿都归属于同一个王国，每年定期缴纳贡品。王国的财务大臣为了管理这浩瀚的贡品账目，在每一座岛上都存放了一本《贡品总录》——厚重的羊皮本，记录着所有岛屿缴纳的货物清单。

起初，每有新的贡品记录，各岛都要派飞鸽向王都汇报，由王都下令统一更新所有岛的账本。这套制度在风平浪静的年月运转良好。

但问题来了。

台风季节，飞鸽十日不至。南方诸岛的贡品送到了，北方诸岛却还不知道。而与此同时，北方诸岛也在更新本地账本，记录着自己收到的货物。当台风过去，双方的账本都已面目全非，且互相矛盾：

南方账本写着：”蜂蜜十缸，已入库。玉器五箱，待运。”
北方账本写着：”蜂蜜十缸，已运走。玉器五箱，未收到。”

同一批货物，两份账本给出了截然不同的状态。

财务大臣绝望了。台风一过，他必须从南北各岛的账本中拼凑出”真实”的贡品状态。可哪个版本才是对的？如果南方说”已入库”，北方说”已运走”——也许两件事都发生过，只是时间先后不同。但账本上没有时间戳，没有顺序，只有”最终状态”。

他陷入了无解的困境。

二、两种解法，两种哲学

困境持续了三年。

第一位顾问——来自北方的法学家——提出了“强制共识”方案：

规定全国所有账本的修改，必须先向王都申请许可，得到至少半数岛屿的认可，方可生效。任何未经许可的修改，一律视为无效。

台风来了？那就停止一切账本更新，等通讯恢复。

这个方案听起来合理，实则代价惨重。台风一来，所有贸易停摆。岛屿不能记录新的贡品，商人不能确认收货，一切都在等待一个不知何时到来的”共识”。整个王国经济陷入停滞。

第二位顾问——一位年迈的数学隐士，来自算学门派——提出了截然不同的方案。他既不要求所有人都停下来等待，也不要求所有人实时同步。

他说：

“问题不在于通讯不稳定，问题在于账本的记录方式本身存在歧义。若我们重新设计账本的格式，使得任意两份账本的合并，其结果都唯一且无争议——那么台风来不来，都无所谓。”

这位隐士拿出了他设计的新账本格式。

三、隐士的账本

新账本有几条奇特的规则：

规则一：只增不减。

每座岛的账本都有一列叫”已收蜂蜜”，这个数字只能增加，绝不能减少。如果要记录”蜂蜜运走了”，不是修改这个数字，而是在另一列”已运走蜂蜜”中增加相应数量。

“入库”和”运走”是两条独立的记录轨道，永远单调递增，永不相互覆盖。

规则二：合并取最大。

当两座岛的账本合并时，每个数字取两份账本中的最大值：

南方账本：已收蜂蜜 = 10，已运走蜂蜜 = 0
北方账本：已收蜂蜜 = 10，已运走蜂蜜 = 10

合并结果：已收蜂蜜 = max(10, 10) = 10，已运走蜂蜜 = max(0, 10) = 10

净余 = 已收 - 已运走 = 0。

两份账本，一合并，矛盾消失了。没有人需要”仲裁”，数学自动给出了唯一的答案。

规则三：合并的结果与顺序无关。

无论先合并南北，还是先合并东西，再与其他岛合并，最终结果永远相同。不存在”谁先合并”的问题，不存在”谁的版本优先”的问题。

老隐士把这套账本叫做“无声立约”——因为它不需要任何明确的协商，数据结构本身就是一份永恒的契约，保证了所有参与者最终达成共识。

四、”不争”的哲学

隐士离开时，留下了一句话：

“争者，皆因设计不善。若设计之初便令冲突无从发生，天下何须争锋？”

这句话让财务大臣想起了一段古语：

“夫唯不争，故天下莫能与之争。”

强制共识的方案，是以”争”止争——用权威、投票、强制停顿来解决冲突。它有效，但代价是可用性：系统在分区时必须停止工作。

隐士的方案，是以”设计”消争——把账本的格式设计成天然可合并的结构，冲突从根源上就不存在了。系统在分区时可以继续工作，重新连接后自动收敛。

这，正是CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）的哲学内核。

五、现代世界里的账本战争

你现在打开手机，用某个协同文档软件，和同事同时编辑同一份文件。你们可能都在没有网络的地铁里，各自修改着同一段落。当网络恢复，两份修改如何合并？

你在离线地图里标记了一个餐厅，你的朋友也在同一份地图里标记了同一个地点（名字略有不同）。同步时，哪个版本算数？

你在一个多人协作的 Todo App 里完成了一项任务，你的队友删除了同一项任务。谁的操作优先？

这些问题，都是那座南海千岛上账本战争的现代版本。

而 CRDT，就是那位年迈隐士留下的答案。

下篇：掰开揉碎——CRDT 的工程心法

一、从定义出发

CRDT，全称 Conflict-free Replicated Data Type，直译为”无冲突复制数据类型”。

它是一类特殊设计的数据结构，满足以下性质：

复制性（Replicated）：数据可以在多个节点上各自保存一份副本，副本之间可以独立修改。
最终一致性（Eventual Consistency）：当所有节点重新连接并交换更新后，它们的状态会自动收敛到完全相同的结果。
无冲突性（Conflict-free）：这种收敛不需要任何冲突检测、冲突仲裁或人工干预——数学结构本身保证了合并结果的唯一性。

CRDT 分为两大家族：

State-based CRDT（CvRDT，基于状态合并）：节点互相传递完整的当前状态，合并函数（merge）将两个状态合并为一个。
Operation-based CRDT（CmRDT，基于操作传播）：节点互相传递操作（如”增加1”、”插入字符x”），保证操作的幂等性和交换律，从而保证最终结果一致。

我们先从 State-based 的经典例子讲起，因为它的数学结构最清晰。

二、G-Counter：最简单的 CRDT

G-Counter（仅增计数器）是最简单的 CRDT，对应寓言里的”只增不减”账本。

问题背景：多个服务器节点需要对某个计数器进行累加（比如统计点赞数），节点之间网络不稳定，随时可能断开。

传统方案的问题：每个节点都维护一个整数 count。A 节点 count=5，B 节点 count=5，合并时取哪个？如果 A 做了 3 次加法变成 8，B 做了 2 次加法变成 7，那么合并后应该是 10（5+3+2），但直接取 max(8,7)=8 是错误的。

G-Counter 的解法：

为每个节点分配唯一 ID。计数器不再是一个整数，而是一个向量——每个节点只负责记录自己的累加值：

Node A 的计数器状态: {A: 3, B: 0, C: 0}
Node B 的计数器状态: {A: 0, B: 2, C: 0}

合并规则：对每个节点 ID，取两个向量中的最大值：

Merge({A:3, B:0, C:0}, {A:0, B:2, C:0}) = {A: max(3,0), B: max(0,2), C: max(0,0)}
                                          = {A:3, B:2, C:0}

读取总值：把向量中所有值相加：3 + 2 + 0 = 5。

关键洞察：每个节点只修改自己那一列，永远是单调递增的，所以 max 操作永远是安全的——它不可能”倒退”已经发生的历史。

这正是寓言中隐士的”合并取最大”规则的数学表达。

三、格理论：CRDT 的数学基石

为什么”合并取最大”能保证无冲突？这背后是一门叫做格理论（Lattice Theory）的数学分支。

一个格（Lattice）是一个偏序集合，其中任意两个元素都有唯一的最小上界（Least Upper Bound / Join）。

State-based CRDT 要求状态空间构成一个联结半格（Join-semilattice），合并操作 ⊔（join）满足三条性质：

性质	数学表达	直觉含义
幂等性（Idempotency）	`a ⊔ a = a`	合并同一份数据两次，结果不变
交换律（Commutativity）	`a ⊔ b = b ⊔ a`	合并顺序无关，先A后B等于先B后A
结合律（Associativity）	`(a ⊔ b) ⊔ c = a ⊔ (b ⊔ c)`	分组方式无关，可以任意拆分合并

这三条性质共同保证了：无论消息以何种顺序到达，无论中间发生多少次网络分区，最终状态都唯一确定。

G-Counter 的 max 函数天然满足这三条：

max(a, a) = a ✓
max(a, b) = max(b, a) ✓
max(max(a, b), c) = max(a, max(b, c)) ✓

格理论将”无冲突合并”从一个直觉变成了可证明的数学性质。这是 CRDT 最深刻的洞见所在。

四、经典 CRDT 数据结构图谱

基于上述原理，工程中常用的 CRDT 数据结构如下：

PN-Counter（增减计数器）

只能增的计数器不够用——现实中需要增也需要减（如购物车数量）。

解法：维护两个 G-Counter，一个记录”增量”，一个记录”减量”：

PN-Counter = {
  P: {A: 5, B: 3},  // 增量向量
  N: {A: 2, B: 0}   // 减量向量
}
当前值 = sum(P) - sum(N) = (5+3) - (2+0) = 6

合并时，P 向量和 N 向量分别取最大：

fun merge(a: PNCounter, b: PNCounter): PNCounter {
    return PNCounter(
        p = mergeVectors(a.p, b.p),  // 每个节点取 max
        n = mergeVectors(a.n, b.n)
    )
}

G-Set（仅增集合）

只能添加元素，不能删除的集合。

合并规则：取两个集合的并集（∪），并集天然满足幂等性、交换律、结合律。

fun merge(a: GSet, b: GSet): GSet = GSet(a.elements union b.elements)

2P-Set（两阶段集合）

允许删除，但删除后不能再添加（一次性）。

2P-Set = { add: G-Set, remove: G-Set }
元素属于集合 ⟺ 在 add 中且不在 remove 中

限制明显：删除后不能重新加入。

OR-Set（Observed-Remove Set，观测删除集合）

这是解决”删除后再添加”问题的精妙设计。

核心洞见：不是删除”元素本身”，而是删除”元素的某次添加”。

每次添加元素时，附带一个唯一标签（UUID）：

add("apple", tag=uuid1)
add("apple", tag=uuid2)  // 同一个元素可以被添加多次（不同标签）

删除时，删除的是当前可见的所有标签：

remove("apple") → 删除 {uuid1, uuid2}

之后再次添加 "apple" 时，产生新标签 uuid3，它没有被删除，所以 “apple” 重新出现。

这解决了分布式系统里著名的”幽灵删除”悖论：

A 节点: add("apple") → remove("apple")
B 节点: add("apple")  (在A删除之前的离线操作)
合并后: "apple" 应该在集合里吗？

OR-Set 的答案：B 节点的 add("apple") 带有新 tag，A 节点的删除只删掉了 A 的 tag，所以 “apple” 在合并后仍然存在。这符合直觉：B 做了一次独立的添加，不应被 A 的删除覆盖。

LWW-Register（Last-Write-Wins Register）

最简单的值类型 CRDT：每次写入都附带时间戳，合并时取时间戳最大的版本。

data class LWWRegister<T>(val value: T, val timestamp: Long)

fun merge(a: LWWRegister<T>, b: LWWRegister<T>): LWWRegister<T> =
    if (a.timestamp >= b.timestamp) a else b

隐患：依赖物理时钟，而分布式系统中的时钟永远无法完全同步（参见：向量时钟的历史教训）。LWW 在实践中容易导致数据丢失，慎用。

五、文字编辑的 CRDT：RGA 与 WOOT

协同文档编辑是 CRDT 最复杂的应用场景。

问题：A 在第5位插入”好”，B 在第5位插入”坏”，合并后顺序如何？

简单的 OR-Set 无法解决有序序列的编辑问题，需要专门设计的算法：

RGA（Replicated Growable Array）：

每个字符被赋予一个全局唯一的标识符（节点ID + 序列号），插入时记录”插在哪个字符后面”，删除时使用逻辑删除（tombstone，墓碑标记）而非物理删除：

文档状态（逻辑）: [h(id:1) → e(id:2) → l(id:3) → l(id:4) → o(id:5)]

A 在 id:3 后插入 "X"(id:6)：... → l(id:3) → X(id:6) → l(id:4) → ...
B 在 id:3 后插入 "Y"(id:7)：... → l(id:3) → Y(id:7) → l(id:4) → ...

合并时：id:6 和 id:7 都在 id:3 后，用 ID 大小决定顺序
结果：... → l(id:3) → X(id:6) → Y(id:7) → l(id:4) → ...（或反之）

关键是：无论网络延迟多久，两个节点合并后的结果永远相同——因为 ID 的比较是确定性的。

现代协同编辑工具（如 Yjs、Automerge、ShareDB）都基于类似的 CRDT 变体。

六、CRDT 在 Android 工程中的落地

场景一：离线优先的 Todo App

// 传统方案的问题
data class TodoItem(val id: String, val done: Boolean, val updatedAt: Long)

// 离线时 A 完成了 todo，B 删除了 todo，合并时谁赢？
// 答案：取决于 updatedAt，但时钟不可信

// CRDT 方案
data class TodoItemCRDT(
    val id: String,
    val doneSet: ORSet<String>,    // 记录"已完成"操作，可撤销
    val deletedSet: ORSet<String>  // 记录"已删除"操作
) {
    val isAlive: Boolean get() = id !in deletedSet && id in doneSet
}

场景二：协同白板 App

多人在同一块白板上画图，每人可以在离线状态下添加/移动/删除图形：

// 每个图形用 OR-Set 管理存在性
// 图形的坐标用 LWW-Register 管理（最后一次移动的位置）
// 图形的层叠顺序用 G-Counter 向量管理

class WhiteboardCRDT {
    private val shapes: ORSet<ShapeId> = ORSet()
    private val positions: Map<ShapeId, LWWRegister<Point>> = mutableMapOf()
    
    fun merge(other: WhiteboardCRDT): WhiteboardCRDT {
        return WhiteboardCRDT(
            shapes = shapes.merge(other.shapes),
            positions = mergePositions(positions, other.positions)
        )
    }
}

场景三：Room + CRDT 离线同步

@Entity
data class CounterEntity(
    @PrimaryKey val id: String,
    val pVector: String,  // JSON 序列化的增量向量
    val nVector: String   // JSON 序列化的减量向量
)

class CounterRepository(private val dao: CounterDao) {
    suspend fun increment(id: String, nodeId: String) {
        val current = dao.get(id)
        val updated = current.copy(
            pVector = current.pVector.increment(nodeId)
        )
        dao.upsert(updated)
    }
    
    suspend fun mergeFromServer(remote: CounterEntity) {
        val local = dao.get(remote.id)
        val merged = local.merge(remote)  // CRDT 合并，无冲突
        dao.upsert(merged)
    }
}

七、CRDT 的局限与工程权衡

CRDT 不是银弹。理解它的局限，才能用好它。

局限一：意图丢失

CRDT 保证结构收敛，不保证语义正确。

经典例子：A 将文本 “Hello” 改为 “Helo”（删了一个 l），B 将 “Hello” 改为 “Hello World”（加了一段文字）。CRDT 合并后可能得到 “Helo World”——从结构上看没有冲突，但 A 的本意是”把多余的 l 删掉”，在 B 加入的新 World 里，这个 l 并不多余。

意图（intent）是无法被 CRDT 数学表达的。

局限二：墓碑（Tombstone）膨胀

OR-Set 的删除是逻辑删除：被删除的元素会留下一个”墓碑”标记，永远不消失（因为它可能还在某个离线节点上）。长期运行后，墓碑积累会导致内存持续增长。

解决方案：定期做 GC（垃圾回收），但 GC 需要所有节点在线参与，违反了 CRDT 的”随时离线”承诺。工程上需要权衡 GC 策略。

局限三：不适合所有场景

场景	推荐方案
协同文档编辑	CRDT（RGA/YATA）
分布式计数器	CRDT（PN-Counter）
购物车同步	CRDT（OR-Set）
银行余额	强一致性（不适合 CRDT，需要分布式事务）
座位/库存抢占	强一致性（资源竞争需要协调）
用户设置同步	LWW-Register（简单场景够用）

八、CRDT vs OT：两种协同编辑哲学

OT（Operational Transformation，操作转换）是另一种解决协同编辑的方案，比 CRDT 出现更早，被早期的协同文档产品采用。

核心思想：当收到其他节点的操作时，转换这个操作，使其适应本地已发生的变更。

A: insert("X", position=5)
B: insert("Y", position=5)

A 收到 B 的操作时，因为 A 已经在 5 处插入了 X，
所以需要将 B 的操作转换为 insert("Y", position=6)

OT 的问题：转换函数极难正确实现，尤其在三个以上节点时，需要一个中央服务器来保证操作顺序。

CRDT vs OT 对比：

维度	CRDT	OT
需要中央服务器	否（P2P 可行）	通常需要
正确性保证	数学证明	实现复杂，易出bug
内存开销	较高（tombstone）	较低
适合场景	P2P、离线优先	中央化协同
代表产品	Yjs、Automerge	ShareDB、早期 Google Docs

九、心法：设计”不争而胜”的系统

学习 CRDT，最终学到的不仅是数据结构，而是一种系统设计哲学：

1. 从”如何解决冲突”转向”如何设计出没有冲突的系统”

强一致性方案花大量精力在”如何协调”，CRDT 花大量精力在”如何设计”。前者是运行时的博弈，后者是设计时的智慧。

2. 单调性是稳定性的根源

所有 CRDT 成功的核心：数据只往一个方向演进（通常是”变大”或”增加信息”），从不倒退。这种单调性是收敛的数学保证。在系统设计中，寻找”只增不减”的不变量，往往是简化问题的关键。

3. 分离”事实”与”派生值”

PN-Counter 将”净余额”分解为”总入账”和”总出账”两个不可变的增量序列。这是数据建模的通用智慧：原始事实（events）应该是不可变的累积，派生值（state）通过计算得出。这也是 Event Sourcing 架构的核心思想。

4. 接受”最终”，放弃”立即”

CRDT 的代价是放弃实时强一致性，接受”最终一致”。这不是退而求其次，而是在可用性（Availability）和一致性（Consistency）之间做了明确的取舍——正是 CAP 定理所揭示的分布式系统基本权衡。

尾声：无声的立约

那位年迈的隐士离开南海千岛后，再未被人见到。但他留下的账本格式，在千年后的数字世界里，以一个学术名词的方式重生：

CRDT。

你在地铁上离线编辑的笔记，你和队友同时更新的项目看板，你在断网时完成的 Todo 条目——背后都是这套”无声立约”的哲学在运转。

数据结构本身就是契约。设计得足够精妙，万物不争，自然归一。

“夫唯不争，故天下莫能与之争。”
— 老子《道德经》第八十一章

无声立约者：CRDT与不争而胜的分布式哲学