Skip to content

CAP 定理

CAP theorem

网络分区期间,系统不能同时保证所有请求可用与线性一致性。

条目类型
定理

形式陈述

Gilbert 与 Lynch 给出的严格形式如下:在允许网络分区(节点组之间的消息可被全部丢失)的异步系统中,不存在一个读写共享对象的实现同时保证:

  • 一致性(C):对象满足线性一致性,即所有操作看起来按某个与实时先后相容的全序瞬时生效;
  • 可用性(A):每个非故障节点收到的每个请求最终都得到响应。

其中分区容忍(P)不是与 C、A 并列的可选目标,而是对环境的描述:网络被允许把节点划分成无法互通的组。定理断言的是在这类环境中 C 与 A 不可兼得——存在包含分区的执行,使任何实现要么违反线性一致性,要么让某个请求永远得不到响应。

直觉

不可能性的核心是一幅两节点图景:分区把节点 G1G2 隔开,客户端向 G1 写入新值,可用性强迫 G1 在收不到 G2 任何回音的情况下确认写入;随后客户端向 G2 读取,可用性又强迫 G2 独自作答。G2 对刚才的写入一无所知,只能返回旧值,而"写入已确认后读到旧值"恰是线性一致性禁止的场景。换句话说,一致性要求信息跨越分区流动,可用性要求两侧都不等待,分区又切断了信息流——三者在同一个执行里逻辑冲突。它不是工程上的"很难兼顾",而是与"感知不可能超过光速"同类的信息论式论证:答案所需的信息根本没有路径到达作答者。

CAP 的不可区分执行
例子与边界

实际系统的两种典型姿态可以对照理解。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.
关系图谱11 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组