两个副本在断网时各自接受写入，恢复通信后还能自动合并，这是 CRDT 最吸引人的地方。它解决的却是一个比“数据库正确”更窄的问题：副本收到同一组更新后，能否得到等价状态。实时顺序、读新鲜度、跨对象唯一性和余额下界不会随“最终收敛”四个字自动出现。

本篇用状态型 PN-Counter 与 OR-Set 拆开两层判断。第一层检查乱序、重复状态传递后是否收敛；第二层检查合并结果是否仍满足应用不变量。实验会得到一个刻意刺眼的结果：两个副本逐字一致，用户名却同时属于两个用户。

分布式系统（35）：两次选择的负载均衡复现实验

系统模型决定“无冲突”的含义

设有两个正确副本 east 与 west。网络可以延迟、乱序、重复或暂时隔离消息；状态型实验假定反熵最终会把必要状态送达。副本不会伪造状态，replica id 稳定且不会被另一节点重用。一次本地更新先改变本地内存，没有磁盘持久化、进程崩溃或成员变更。

在这个模型里，“无需协调”表示本地更新不等待一个同步的全局排序点。副本仍要通信，永久丢失唯一更新也不会凭 merge 恢复。分区期间读到旧值也不违反收敛，因为副本尚未接收同一组更新。

flowchart LR
  C[共同状态 S0] --> E[east 离线更新]
  C --> W[west 离线更新]
  E --> P[网络分区]
  W --> P
  P --> A[反熵交换状态]
  A --> J[双方计算同一个 join]
  J --> Q{应用不变量仍成立?}
  Q -->|不一定| B[另做协调或改数据表示]

强最终一致性（Strong Eventual Consistency，SEC）关心的是：看到同一更新集合的副本状态等价，并且更新在传播前提满足时最终可见。它不要求两个副本在传播完成前每次读取都相同，也不为多个对象提供串行化历史。

状态型 CRDT 把 merge 设计成 join

状态型 CRDT（CvRDT）把有效状态组织成 join-semilattice。若偏序记为 <=，本地更新只能沿偏序增长，merge(a,b) 返回两者的 least upper bound。结合律、交换律和幂等律分别吸收分组差异、到达顺序与重复状态：

1
2
3
join(join(a, b), c) = join(a, join(b, c))
join(a, b)          = join(b, a)
join(a, a)          = a

这三条等式解释了为什么状态快照可以重复传输。它们不等于“任何业务值取并集都正确”；偏序、状态中保留的信息和并发语义都要随数据类型设计。

PN-Counter：分量只增，读值可以下降

PN-Counter 由两个 G-Counter 组成。每个副本只增加自己的正分量 P[id] 或负分量 N[id]，合并时对每个分量取最大值，读值为：

1
value = sum(P) - sum(N)

east 离线执行 +5,-2，west 执行 +4,-1。两种相反顺序各再重复传一次状态，最终都得到 P={east:5,west:4}、N={east:2,west:1}，值为 6。程序还对三个固定状态检查了 join 的结合、交换与幂等性质。

“状态单调”不表示查询值只增。P 和 N 的每个分量都沿偏序增长，sum(P)-sum(N) 仍可下降。更不能把客户端重试直接当成状态重传：重复 merge 是幂等的，同一次“扣 1”若被本地执行两遍，负分量会真的多 1。

可迁移模式：把重复吸收到状态身份里

问题 状态中保留什么 merge 如何消除传输差异 仍未解决什么
分布式计数 每个稳定副本的单调分量 逐分量最大值 操作重试身份、余额下界
集合添加 每次 add 的唯一 tag tag 集合并集 删除语义、元数据回收
多版本寄存器 值及其因果上下文 删除被支配版本、保留并发版本 业务选胜

可迁移的判断不是“都用 set union”，而是先找出不能被重复传输混淆的身份，再为整个 payload 定义 join。

OR-Set 必须记住删掉的是哪次添加

普通集合只有当前元素，无法区分“从未添加”“已经删除”和“某个旧副本还在重放被删除的添加”。OR-Set 为每次 add 生成唯一 tag。remove 只把当前已观察到的该元素 tags 放进 removed 集合；merge 对 adds、removed 和因果计数分别求 join。元素存在，当且仅当至少一个 add tag 尚未进入 removed。

实验先由 seed 添加 tea@seed#1 并同步到两端。分区期间，east 删除它并添加 coffee；west 没看到删除，又生成 tea@west#1 并添加 cake。两种相反且含重复的状态传递顺序都收敛到 {cake, coffee, tea}。

flowchart TD
  S[共同 tea@seed#1] --> E[east 删除 seed#1]
  S --> W[west 添加 tea@west#1]
  E --> J[合并 adds 与 removed]
  W --> J
  J --> R[seed#1 已删<br/>west#1 存活]
  R --> V[可见 tea]

并发 add 获胜是 OR-Set 的规格，不是网络故障。east 合并后再次删除 tea，此时它已经观察到两个 tea tags；新状态传播后，两端都只剩 cake 与 coffee。

错误变异只从本地 adds 中抹掉 seed#1，却不保留 removed。它与仍持有旧 tag 的状态合并后，tea 复活。墓碑或等价的因果摘要承担了“这个 tag 已被删除”的信息；在旧状态不可能回流得到证明以前，不能按墙钟时间随意清掉。

LWW 收敛不等于保存并发意图

LWW-Register 给每次写一个唯一全序键，merge 保留最大者。两个离线副本分别写 A 与 B 后，它一定能选出一个结果，所以可以收敛；另一个并发值也会被确定性丢弃。若全序依赖物理时钟，时钟偏差可能让更早的真实写入拥有更大时间戳。

MV-Register 选择另一种语义：因果上更新的版本覆盖旧版本，并发版本同时保留，交给后续读取或应用处理。两种寄存器都可以是 CRDT，却回答了不同的业务问题。“Conflict-free”表示合并规则没有未决分支，不表示规则没有损失。

flowchart LR
  A[并发写 A] --> L[LWW 全序选胜]
  B[并发写 B] --> L
  L --> O[只保留一个值]
  A --> M[MV 保留并发版本]
  B --> M
  M --> T[后续显式解决]

Operation-based 与 delta-state 不是免费压缩

经典操作型 CRDT（CmRDT）把更新拆为源端 generator 和各副本执行的 effector。其证明通常要求可靠、恰好一次的因果交付，并要求并发 effectors 可交换。把传输改成至少一次后，increment(1) 会不会重复执行，必须由去重或操作幂等性回答；不能借用状态 join 的幂等性。

Delta-state CRDT 仍使用状态型 join，但发送本次更新产生的 delta-state 或多个 delta 的 join，而不是每次发送完整状态。若要保持普通状态型 CRDT 的因果合并语义，delta-interval 的传播还要满足 causal delta-merging condition。它减少的是可发送状态范围，不会自动消除因果上下文、重传记录和元数据增长。

本地程序只运行完整状态 merge。操作型与 delta-state 只讲模型差异，没有伪造运行结果。

两个副本一致，唯一用户名仍然重复

跨对象反例包含 user-a.aliases 与 user-b.aliases 两个独立 OR-Set。east 查询本地索引，认为 mira 无占用，于是写入 user-a；west 在隔离状态下也通过相同检查，把 mira 写入 user-b。两边的本地状态都满足“当前只有一个 owner”。

恢复通信后，每个用户对象分别 merge。两种顺序和重复传递得到逐字相同的最终状态，但 owners 为 [user-a,user-b]。副本收敛为同一个错误答案。

sequenceDiagram
  participant E as east
  participant W as west
  E->>E: 本地检查 mira 未占用
  W->>W: 本地检查 mira 未占用
  E->>E: user-a 添加 mira
  W->>W: user-b 添加 mira
  Note over E,W: 分区恢复，逐对象 join
  E->>W: user-a 状态
  W->>E: user-b 状态
  Note over E,W: 状态相同，mira 有两个 owner

I-confluence 把这个边界写成可检查条件：从共同祖先出发，两个各自满足不变量的状态合并后也必须满足不变量。普通唯一性并发插入不满足该条件，因此若同时要求收敛、事务可用和全局唯一，就要改变其中一个条件。可选方案包括给名字分配不相交所有权、确定性选胜并补偿失败方，或在冲突写入前协调。

这不推出“所有跨对象不变量都需要共识”。Bounded Counter 把可消费 rights 预分配到副本，本地只有足够 rights 才允许扣减；rights 不足时再等待转移或拒绝。数据表示和准入规则改变后，原本会破坏下界的事务集合也随之改变。

安全性、活性与故障恢复

状态型收敛的证明骨架很短。每个副本状态是已见更新对应 delta 的 join。结合、交换和幂等使括号、顺序和重复不影响结果；当两个副本最终包含同一 delta 集合时，它们计算同一个 join。这个论证依赖 delta 没有永久丢失、merge 实现正确以及身份不重用。

安全性要分两层写。数据类型层可以检查“相同更新集合不分叉”；应用层还要检查唯一性、引用完整性、余额或库存等不变量。E01 的用户名场景故意让第一层通过、第二层失败。

活性依赖通信最终恢复、反熵持续调度、至少一个持有所需更新的副本存活。纯异步网络无法给出固定收敛期限。节点崩溃且唯一新状态未持久化时，更新会丢失；永久分区时，双方也不会最终看到同一更新集合。

超时和重试同样分层处理。重复状态快照可由幂等 join 吸收，重复业务命令仍要请求身份或操作级去重。节点恢复时还要解决 replica id、旧状态和删除摘要的生命周期；把新进程误当成旧身份，或过早回收 causal context，都可能破坏证明前提。

运行有限实验

正式程序位于 examples/distributed-systems/crdt-e01/check.py，只使用 Python 标准库。所有运行资料和临时变量都放在仓库内：

1
2
3
4
5
mkdir -p examples/distributed-systems/.build/e01/tmp
export TMPDIR="$PWD/examples/distributed-systems/.build/e01/tmp"
export TMP="$TMPDIR" TEMP="$TMPDIR" PYTHONDONTWRITEBYTECODE=1
python3 -B examples/distributed-systems/crdt-e01/check.py \
  --output examples/distributed-systems/.build/e01/observations.json

Python 3.12.3 正式运行退出 0；--help 退出 0，未知 scenario 退出 2。--scenario invariant --expect-unique 先写出结构化反例，再因 caller_expected_unique=false 退出 1。正式源码 SHA-256 为 24cf8eb476345e3af6813f87b953b9daa5fabc724a448f478e9e7d7b20c25891。

门槛 本地观察
PN-Counter 乱序/重复收敛 两种顺序均为 6
join 三律 固定三个状态全部通过
OR-Set 并发 add/remove tea@west#1 存活
同步后 remove tea 的两个 tags 均被删除
丢删除标记变异 陈旧 seed#1 使 tea 复活，变异被检出
唯一用户名 两副本收敛；owners 为两个，不变量失败

完整输出见观察结果，来源与运行命令见实验证据，验证范围见验证说明。

工程选择表

需求 可先考虑 必须另答的问题
离线计数、允许最终汇总 G/PN-Counter 身份生命周期、操作重试、上下界
集合并发增删 OR-Set 或明确的 remove-wins 变体 并发语义、因果元数据、GC
并发写只能留一个 LWW-Register 全序来源、时钟偏差、被丢值
并发写必须都保留 MV-Register 读取接口和后续解决者
全局唯一或余额下界 I-confluence 分析、rights/所有权或协调 拒绝、等待、补偿和故障恢复

CRDT 的工程成本主要落在元数据、反熵、成员身份、语义选择和不变量分析上。一个 merge 函数写得很短，不代表系统边界也很短。

两个推演练习

为什么 OR-Set 的 remove 不能只写“删除元素 tea”？

因为该命令没有说明它删除的是哪些 add。若 west 在并发分支生成了尚未被 east 观察的 tag，直接删除元素会把并发 add 一并抹掉；若只删本地值却不传播已删除 tag，旧副本又会使它复活。Observed-remove 用 tag 集合明确了 remove 的知识边界。

PN-Counter 已经收敛，为什么库存仍可能变成负数？

假设库存初值为 1，两个隔离副本都按本地值接受一次扣减。合并能正确累计两次扣减，结果为 -1。错误不在 merge，而在两个本地准入判断不能同时成立。预分配 rights、单一所有者或同步协调可以改变可接受操作集合。

E02 转向 GFS/HDFS 与 Bigtable/HBase。那一篇不再讨论同一对象的无协调 merge，而是比较文件块、tablet/region、元数据控制面和故障恢复路径。

参考资料