形式陈述 ​
强最终一致性(SEC)通常分成三项:
- eventual delivery:一个正确副本交付的更新最终由所有正确副本交付;
- termination:每次方法调用在所假设的故障模型下终止;
- strong convergence:任何两个已交付相同逻辑更新集合的副本,其抽象状态立即等价。
操作若非幂等,“更新集合”应理解为带全局唯一身份的事件集合,且每个事件按规定 multiplicity 执行;若协议保留因果顺序,合法历史还应是因果向下闭合的。Strong convergence 的量词不等待网络安静:只要两个副本此刻已吸收相同事件,它们此刻就必须等价。
状态型 CRDT用 join 的结合、交换、幂等证明第三项;操作型 CRDT用因果顺序加并发 effector 可交换性证明。两者的 eventual delivery 前提不同,却可以满足同一外部 SEC 规格。
SEC 不等于 linearizability。它没有要求每次读都能嵌入尊重真实时间的单一操作序,也允许分区期间正确副本暴露不同的中间状态。它同样不自动给出因果一致读、事务原子性或跨对象不变量。
直觉
普通“最终一致”只说停止更新并等待足够久后会靠拢,可能容许两个已见完全相同历史的副本因到达顺序不同而暂时不一致。SEC 加强了函数性:状态由已经吸收的更新历史唯一决定。网络负责让历史最终相同,数据类型负责让相同历史立刻映成相同结果。
这把安全与活性分开。Strong convergence 是安全性质:一旦发现同历史不同状态,已经出现反例;eventual delivery 是活性性质:任何有限观察都不能证明它永远不会发生。测试只等待几秒看到相等,不能替代对公平传播的论证。
“等价状态”应按可观察 query 定义,内部压缩表示可不同。例如一个副本保存完整 dot 集,另一个保存等价前缀摘要,只要未来 merge 与 query 行为一致即可;若压缩使旧值未来复活,就不再等价。仅有相同更新数量、相同最大时间戳或相同当前 query 都不足以判定 histories 相同。
例子与边界
两个 grow-only set 副本初态为空。A 加入
这见证 strong convergence。若 C 此刻只收到
分区期间 A 写 red 并读到 red,B 写 blue 并读到 blue;一个 LWW CRDT 可按 marker 在愈合后统一为 blue,从而满足 SEC。可是若 A 的读发生在 B 的写真实完成之后,仍可能读到 red,这不符合 linearizability 的实时顺序。收敛赢家没有回溯性地使分区期间读取线性化。
若整数 increment effectors 在 A 去重、在 B 重复执行一次,两边即便收到相同消息包也得不同数值。问题应归到 multiplicity 合同,而不能用“最后再同步一次”修复。反过来,A 只收到事件
推论与应用
SEC 适合作为 CRDT 验收规格:模型检查可枚举更新事件、合法交付偏序与重复策略,验证任何相同 history frontier 的 query 相等。网络故障注入则验证 eventual delivery 和崩溃恢复是否保留去重、因果依赖与未传播状态。Method termination 还要注明是否允许无限等待缺失依赖;后台交付可等待,不代表前台调用也可无界挂起。
产品文档仍应额外说明读取保证。SEC 系统可以提供本地低延迟读,也可叠加 session token 获得 read-your-writes;若需要 linearizable conditional update、唯一用户名或余额约束,必须加入协调或专门的 invariant-confluent 设计。
参考资料
- Marc Shapiro et al., “Conflict-Free Replicated Data Types,” SSS 2011, LNCS 6976, pp. 386–400.
- Victor B. F. Gomes et al., “Verifying Strong Eventual Consistency in Distributed Systems,” Proceedings of OOPSLA 1, 2017, Article 109.
- Sebastian Burckhardt, Principles of Eventual Consistency, Foundations and Trends in Programming Languages 1(1–2), 2014, Chs. 2–4.