“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.