“CRDT 是CAP 定理中选择可用性一侧后的系统性答案:分区期间各副本继续服务,靠代数性质而非拒绝写入来保证愈合后一致,是最终一致性从口号变成可证明规格(强最终一致性)的关键一步。它支撑离线…”
形式陈述
Gilbert 与 Lynch 给出的严格形式如下:在允许网络分区(节点组之间的消息可被全部丢失)的异步系统中,不存在一个读写共享对象的实现同时保证:
- 一致性(C):对象满足线性一致性,即所有操作看起来按某个与实时先后相容的全序瞬时生效;
- 可用性(A):每个非故障节点收到的每个读写请求最终都按该对象的操作规格完成;仅返回“暂不可用”或把强一致读替换成另一种降级接口,不算完成原请求。
其中分区容忍(P)不是与 C、A 并列的可选目标,而是对环境的描述:网络被允许把节点划分成无法互通的组。定理断言的是在这类环境中 C 与 A 不可兼得——存在包含分区的执行,使任何实现要么违反线性一致性,要么让某个请求永远得不到响应。
直觉
不可能性的核心是两段不可区分的执行。分区把节点
矛盾不在于“没有信息就只会猜旧值”,而在于同一份可见信息对应两种必须给出不同答案的世界。只要两侧都必须独立完成任意读写请求,协议就无法用等待更多跨组消息来消除这个歧义。
例子与边界
实际系统的两种典型姿态可以对照理解。CP 姿态:采用多数派 quorum 的复制系统在分区时让少数派一侧拒绝服务或阻塞——牺牲那一侧的可用性,换取全局单一的最新值。AP 姿态:各分区继续本地读写,分区愈合后再合并冲突——各侧继续完成本地操作,但需要放宽全局线性一致性;例如,在冲突合并与更新传播满足相应条件时,提供最终一致性。分区愈合本身并不自动保证数据收敛。同一个系统也可以按数据类别混合两种姿态。
常见误读有三。其一,"三选二"的口号具有误导性:分区不是可以"不选"的选项,而是环境事实;若模型排除永久分区,在相应的可靠通信与非故障假设下,C 与 A 可以同时满足;但运行中的节点仅凭消息尚未到达,无法区分很长但有限的延迟与永久断连。因而要求永久分区期间也响应的协议,也可能在没有消息丢失的长延迟执行中返回不一致结果。其二,这里的 C 专指线性一致性——把任何含义下的"consistency"(如数据库 ACID 中的 C)代入都会得到似是而非的结论;弱化一致性定义、限制操作类型或放宽可用性定义,都会得到不同的可行性边界。其三,CAP 不讨论无分区常态下"延迟换一致性"的权衡,那是 PACELC 等后续框架补充的内容。
推论与应用
CAP 定理的实际价值在于强迫设计者把"分区期间的行为"写进服务规格:拒绝哪些请求、降级到什么语义、愈合后如何收敛,都不再能含糊其辞。它解释了为什么基于多数派的共识与状态机复制系统在失去 quorum 的一侧必须停写,也解释了为什么高可用存储要投资于冲突解决机制(如无冲突复制数据类型)。在知识链条上,它与 FLP 不可能性互为参照:FLP 说异步加崩溃使共识无法保证终止,CAP 说分区使线性一致与全员响应无法兼得——两者都以"信息不可达"为杠杆,把工程直觉升格为定理。
参考资料
- Seth Gilbert and Nancy Lynch, Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services, SIGACT News 33(2), 2002,pp. 51–59。
- Eric Brewer, “CAP Twelve Years Later: How the Rules Have Changed,” Computer 45(2), 2012, 23–29.