CAP 到 PACELC：分布式一致性模型的演进 — 主题精读笔记 未开始

题记与说明

• 日期：2026-11-04
• 形式：主题研究（5 个来源交叉精读，全部为网络检索成功后逐篇全文精读，非仅凭已有知识）
• 主题：CAP 到 PACELC：分布式一致性模型的演进（2000 猜想 → 2002 证明 → 2012 澄清与 PACELC → 2014/2015 系统性批评）

来源清单（均为本次实际读取）

检索过程：WebSearch 两轮定位三篇原始论文的可访问镜像（CMU 镜像 PDF 为 2002 年老字体编码，pdftotext 提取乱码，已改用 Princeton 镜像验证成功）；两篇批评文章用 webReader 全文抓取。

演进主线（时间轴）

1. 1998 秋：CAP 定理雏形首次出现（Brewer 2012 自述："The theorem first appeared in fall 1998. It was published in 1999 and in the keynote address at the 2000 Symposium on Principles of Distributed Computing"）。
2. 2000-07：Brewer 在 PODC 2000 特邀报告提出 CAP 猜想（当时只是经验命题，非定理）。
3. 2002：Gilbert & Lynch 在 SIGACT News 形式化并证明该猜想：异步网络模型下不可能同时实现一致性、可用性与分区容错；部分同步模型下任意丢消息仍不可能；但超时协议可拿到实用折中。
4. 2012-02：IEEE Computer 同期两篇关键文章——Brewer 本人澄清"2/3"表述误导并提出显式分区管理；Abadi 提出 PACELC，把"无分区时一致性-延迟权衡"纳入框架。（Abadi 2010 年博客《Problems with CAP, and Yahoo's Little Known NoSQL System》是其思想前身。）
5. 2014–2015：Brooker 评估 PACELC"更好但仍不理想"；Kleppmann 主张彻底弃用 CP/AP 标签，转向 linearizability / causal consistency 等精确术语（并另有论文 *A Critique of the CAP Theorem*）。

七维提取

一、核心问题

这份工作群在解决什么问题——分四层递进：

1. 形式化层（GL02）：Brewer 的经验直觉"分布式 web 服务无法同时保证 C、A、P"是否为真？在什么模型下、以什么精度为真？
2. 澄清层（Brewer12）：CAP 十年间被（尤其被 NoSQL 营销）滥用为"三选二"教条，作者本人要收回这个过度简化的表述：CAP 到底禁止什么、允许什么？分区期间的系统该怎么工程化地设计？
3. 扩展层（Abadi12）：CAP 只约束分区发生时（罕见），但各家系统（Dynamo/Cassandra/PNUTS/Riak）在正常运行时就降低一致性——用 CAP 解释不通。真正主导设计的另一个权衡（一致性 vs 延迟）如何与 CAP 统一成一个框架？
4. 批判层（Brooker14、Kleppmann15）：CAP 与 PACELC 作为描述/分类系统的工具是否合格？CP/AP 二分法还能不能继续用？

二、主要主张

Gilbert & Lynch 2002（把猜想变成定理）

• 摘要原文："*When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three. In this note, we prove this conjecture in the asynchronous network model, and then discuss solutions to this dilemma in the partially synchronous model.*"
• Theorem 1（异步模型）："*It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties: Availability, Atomic consistency in all fair executions (including those in which messages are lost).*" 证明思路：把网络分成两组 G1、G2，G1 内完成一次写（由可用性保证完成），G1↔G2 消息全部丢失；G2 内随后的一次读必然返回旧值 v0（G2 无法区分两种执行），违反原子性。
• Corollary 1.1：连"平时原子 + 丢消息时可用"也不行——异步模型下节点无法区分消息丢失与任意延迟。
• Theorem 2（部分同步模型）：即使有时钟与已知时限 tmsg/tlocal，任意丢消息时"永远可用 + 原子一致"仍不可能。
• 但部分同步下存在实用算法：超时后返回本地已知值，牺牲原子性换可用性；并提出 Delayed-t 一致性——分区愈合后的 t 时间内必须恢复一致，给 eventual consistency 一个显式时间上界。结论名句："*most real-world systems today are forced to settle with returning 'most of the data, most of the time.'*"

Brewer 2012（作者本人纠偏）

• 核心："*CAP prohibits only a tiny part of the design space: perfect availability and consistency in the presence of partitions, which are rare.*"（CAP 只禁止设计空间中极小的一角：分区存在时的完美可用性与完美一致性——而分区很罕见。）
• "2 of 3"三重误导：(a) 分区罕见，未分区时没理由牺牲 C 或 A；(b) C/A 的选择可以按子系统、按操作、甚至按具体数据/用户细粒度切换；(c) 三个属性都是连续量而非二值——可用性 0–100%，一致性有多个层级，连"分区是否存在"系统内部都可能意见不一。
• CAP-延迟联系（PACELC 的伏笔）："*Operationally, the essence of CAP takes place during a timeout... the partition decision: cancel the operation and thus decrease availability, or proceed with the operation and thus risk inconsistency.*" 且"重试通信（Paxos、两阶段提交）只是推迟决定"；实用主义定义："*pragmatically, a partition is a time bound on communication.*"（分区就是通信的时间界限。）
• 工程方法论三步：检测分区 → 进入显式 partition mode（可限制部分操作）→ 恢复（合并状态 + 补偿外部化错误）。工具：高层原子操作×不变量交叉表、version vectors（因果依赖）、CRDT（Shapiro 等，Dynamo 购物车并集即单调集合运算，代价是"已删除商品可能复活"）、补偿事务/saga。ATM 侧栏给出经典案例：stand-in mode 允许提款但限制净提款额 ≤ k（约 200 美元），把"选 A 还是选 C"变成有界风险。
• 结论："*System designers should not blindly sacrifice consistency or availability when partitions exist. Using the proposed approach, they can optimize both properties through careful management of invariants during partitions.*"

Abadi 2012（PACELC）

• 开篇主张："*The CAP theorem's impact on modern distributed database system design is more limited than is often perceived. Another tradeoff—between consistency and latency—has had a more direct influence on several well-known DDBSs. A proposed new formulation, PACELC, unifies this tradeoff with CAP.*"
• 关键纠偏："*It is wrong to assume that DDBSs that reduce consistency in the absence of any partitions are doing so due to CAP-based decision-making.*"——CAP 只在故障期施加限制，正常运行时不约束任何能力；无分区时系统完全可以同时做到 ACID + 高可用。
• 枚举复制实现的三条路径（同时写所有副本 / 先写固定 master / 先写任意节点）及其子选项，论证每一种都内含一致性-延迟权衡；"For data replication over a WAN, there is no way around the consistency/latency tradeoff."
• PACELC 定义原文："*if there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?*"（读作 pass-elk。）
• 系统分类（按最初设计的默认配置）：PA/EL：Dynamo、Cassandra、Riak；PC/EL：PNUTS（正常时用一致性换延迟，分区时拒绝少数派写入、保一致性——"实际上默认配置是 CP"，这反证其降一致性是为延迟而非 CAP）；PA/EC：MongoDB（基线一致，master 故障时新旧 master 状态分叉、手工回滚）；PC/EC：VoltDB/H-Store、Megastore、BigTable/HBase。
• 概念辨析：PC 不代表"分区时更一致"，而是"分区时不把一致性降到基线以下、而是降可用性"；ELC 只适用于复制型系统（不复制则任何故障=极端延迟）。

Brooker 2014（评估 PACELC）

• 定调："*CAP is confusing. PACELC is better, but still not ideal.*""*the CAP theorem has been too successful.*"
• 列举 CAP 五大教学误区：①"任选两个"（现实中 P 不可牺牲）；②"分区时不可能一致且可用"——GL 定理只阻止所有人同时 C+A，多数派一侧完全可以既 C 又 A；③一致性并非全有全无——分区期间仍可提供 read-your-writes、单调读、因果一致性等；④"最终一致性都是因为 CAP"；⑤版本混杂（Brewer 猜想 vs GL 定理常被混为一谈）。
• PACELC 主要修正①④，并"makes it clear that even in the absence of partitions there's a tradeoff between consistency and latency"——延迟这一实践上极重要的维度 CAP 完全没覆盖。
• 但 PACELC 仍有两个软肋：PA/EC 的"分区"判定模糊（"When is there a partition? Is a single dropped connection or lost packet a partition?"）；PC/EL 语义别扭（"PC/EL is madness... What does it mean to be more consistent during a partition?"——只能靠 Abadi 本人补充解释来圆）。

Kleppmann 2015（弃用 CP/AP）

• 总主张："*The CAP theorem is too simplistic and too widely misunderstood to be of much use for characterizing systems. Therefore I ask that we retire all references to the CAP theorem... Instead, we should use more precise terminology to reason about our trade-offs.*"
• 定理的极窄定义：C 实为 linearizability（与 ACID 的 C 无关）；A 是"任何非故障节点都必须响应"（许多标榜高可用的系统达不到）；P 其实是"运行在可能延迟/丢消息的异步网络上"——根本没得选。
• 模型三限制：只研究单个 read-write register（多对象事务直接出范围）；只考虑网络分区这一种故障（节点崩溃、磁盘满、bug 等都不在）；"*the CAP theorem says nothing about latency, which people tend to care about more than availability. In fact, CAP-available systems are allowed to be arbitrarily slow...*"（CAP 意义上可用的系统可以慢到任意程度。）
• 用"两个数据中心复制链路断了"重演 CAP 证明：要么双活违反 linearizability，要么只允许主 DC 读写（从 DC 停服，即非 CAP-available）。顺带指出：选 C 的一方若能把流量切到主 DC，应用层可以零宕机——CAP-不可用 ≠ 应用不可用。
• 逐一检验：单主复制（多数关系库默认）不是 CAP-available（分区时无法写）；若读从库（异步复制）又不是 linearizable——所以"neither CP nor AP, they are just 'P'"。快照隔离/MVCC 数据库故意非线性化（PostgreSQL SSI 提供 serializability 而非 linearizability）。MongoDB 单主 → 非 A；Kyle Kingsbury 实测最高一致性设置下仍有非线性化读 → 非 C。Riak/Cassandra/Voldemort：R=W=1 时是 CAP-available，R+W>N 的 quorum 在少数派一侧不可用；且 sloppy quorum + read repair 组合会产生"删除数据复活"等非线性化边界案例。ZooKeeper（公认"CP"）默认读不走 sync 不 linearizable、少数派不能写、3.4.0 的 read-only mode 反而是 CAP-available——但它提供原子广播+因果一致会话保证，远强于"AP"的 Riak。结论："*The fact that we haven't been able to classify even one datastore as unambiguously 'AP' or 'CP' should be telling us something: those are simply not the right labels to describe systems.*""*It is simply not possible to encode this subtlety in one bit of information.*"

三、方法

四、数据与证据

• GL02：两个定理 + 一个推论的完整证明（异步模型下利用"无法区分消息丢失与延迟"构造矛盾执行；部分同步下利用超长静默区间构造）。数学上无懈可击，但对象是单寄存器读/写、100% 可用性的极端定义。
• Brewer12：一手时间线（1998 秋首次提出、1999 发表、2000 PODC keynote）；ATM stand-in mode（净提款上限 k≈$200）案例；Facebook"更新后 20 秒内读主副本、之后回落就近副本"；Yahoo PNUTS 为 WAN 延迟牺牲强一致。证据以工程案例为主，无系统性实验数据。
• Abadi12（定量证据最扎实）：
  • Rao, Shekita, Tata（VLDB 2011）对 Cassandra 的实验：quorum reads 相比 weak reads 提升一致性的代价是"延迟相差可达 4 倍以上"（原文："The difference in latency between these two options can be a factor of four or more"）。
  • Wada 等（CIDR 2011）对 SimpleDB 的"反例"及解释：单区域内一致读延迟并无显著上升——因为实验在单一 Amazon 区域（US West）进行、master 与读请求物理距离近；若跨区域复制，代价立现。Amazon 官方文档本身就警告一致读会增加延迟、降低吞吐。
  • Brutlag（Google，2009）：延迟增加仅 100ms 就会显著降低用户继续使用/回访的概率——这是"为什么 L 值得与 C 同框"的商业论据。
  • 关键概念区分："CAP 权衡由故障的发生触发，而复制的一致性-延迟权衡由故障的可能性本身引起"——即使永远不发生故障，为高可用而复制这件事就已经把权衡摆上台面。
• Brooker14 / Kleppmann15：概念证据为主。Kleppmann 引用 Kyle Kingsbury（aphyr）对 MongoDB 的非线性化读实测、ZooKeeper 文档（默认读不含 sync）、ZooKeeper 3.4.0 read-only mode、PostgreSQL SSI 文档、sloppy quorum/read repair 的边界案例（删除复活、副本数漂移破坏 quorum 条件）。
• 充分性评估：形式化结论（不可能性）证据充分；工程结论（各家系统为何这样设计）靠案例 + 二手实验，Abadi 也承认 PNUTS 归类"admittedly somewhat confusing"；批评方未提出统一替代框架，只给出术语谱系。

五、结论与效果

1. 理论层：CAP 在其精确定义下为真——异步网络中线性化 + 全节点可用 + 分区容错三者不可能兼得；部分同步 + 丢消息时仍不可能；这为一切讨论画定了不可逾越的角落。
2. 理解层：但"三选二"是教学记忆法的失败版。正确读法：P 无得选（异步网络不可拒绝）；真正的选择只在分区发生时在 C 与 A 之间，且可按操作/子系统粒度反复切换；三个属性皆连续；未分区时 CAP 不施加任何约束，系统完全可以同时 C+A。
3. 工程层：对分区的正确姿态不是"选边"而是管理：检测 → 显式 partition mode → 恢复与补偿；version vectors、CRDT、有界风险（ATM k 限额）、补偿事务让"分区时既保 A 又让状态最终收敛"在特定操作集下可构造。
4. 框架层：PACELC 把被 CAP 遗漏的日常权衡（一致性 vs 延迟）纳入统一表述，解释了 Dynamo/Cassandra/Riak（PA/EL）、PNUTS（PC/EL）、MongoDB（PA/EC）、VoltDB/Megastore/HBase（PC/EC）的默认配置成因——"降一致性主要是为了延迟，不是 CAP"。
5. 批判层：PACELC 优于 CAP 但非终点：分区判定边界模糊、PC/EL 语义需作者亲自补丁；而 CP/AP 二分法在精确定义下连一个系统都装不进去——单主复制、MongoDB、ZooKeeper 皆是"仅 P"。终局共识：以 per-operation 的一致性谱系（linearizability、sequential、causal、RYW、monotonic reads…）+ 具体故障模型替代标签。
6. 整体效果：这条演进线完整呈现了"口诀（猜想）→ 定理 → 定理被口诀反噬 → 作者澄清 → 框架扩展 → 口诀体系退役"的概念生命周期；此后学界沿 Bailis 的 Highly Available Transactions、RedBlue consistency 等方向继续把"可用性下的最强一致性"形式化（本次精读的来源中仅作引用出现，未展开，此为边界说明）。

六、局限

• GL02 模型极窄（Kleppmann 指出）：单 read-write register；只考虑消息丢失型分区一种故障；可用性定义为"任何非故障节点必须响应"，现实 SLA（99.9% 请求 1 秒内成功）与 CAP-可用性互不蕴含；不谈延迟——"CAP-available systems are allowed to be arbitrarily slow"。
• Brewer12 是工程散文而非框架：不变量×操作交叉表与"逐格决策"成本高昂；补偿事务的正确性判定他自己承认是开放问题（"How best to apply these ideas to partition recovery is an open problem"）；CRDT 只能覆盖 locally verifiable invariants（原文自己标注此限制）。
• Abadi12 的分类有时效性：明确声明按各系统"最初设计的默认配置"归类；MongoDB 的 rollback 手工对账、PNUTS 行为等后来版本可能已变化；Kleppmann 引用的 MongoDB 测试也是 2015 年时点快照。PACELC 的 L 维度未量化吞吐、尾延迟（p99）等运营指标；对多副本/多领导者/分片拓扑的表达力有限（只有 C/L 一个轴）。
• Brooker14 自认不足：PA/EC 的分区判定线（一次丢包算不算分区）PACELC 未回答；PC/EL 需要 Abadi 的补充解释才能自洽——"subtle edge ... of the same kind that exists in CAP"。
• Kleppmann15 只破不立：给出术语谱系与文献路线图，但未提供同等级的"snappy"替代框架（他自己也承认找不到）；产业界至今仍惯用 CP/AP（以及 PACELC 标签）交流。
• 本次精读自身的边界：2026 年视角下，2015 年后的发展（HARPS/PCAP/CISE、Bailis HAT 系列的完整形式化、各大云数据库的一致性 SLA 实践）不在本次 5 个来源范围内，笔记仅标注延伸方向，未做展开。

七、对我的启发

1. 用词纪律先行：以后说 CAP，先自问是否在用定理原义——C=linearizability、A=任何非故障节点必须响应、P=不可选。给系统贴 CP/AP 标签基本无效；有效的表述是"哪些操作、在哪种故障下、保持哪一档一致性"。
2. 把延迟当一等公民：跨 WAN 复制时，R+W>N 的成本是每一次操作都在支付（Abadi 引实验：quorum 读比弱读延迟高可达 4 倍），而 CAP 的代价只在罕见分区时支付。做架构决策应先画延迟预算表、再谈一致性档位——这与个人项目的自托管服务（本机/单区域）同样适用：单区域内的"强一致"其实很便宜（Wada 的 SimpleDB 反例正是这个道理）。
3. 分区管理三步法可直接移植：检测（timeout 即判定，且时间界限可按业务响应目标人为设定）→ partition mode（列出不变量×操作矩阵，决定禁止/延迟/修改）→ 恢复（version vectors 排序 + 补偿）。做分布式 LLM 应用/多机系统的设计评审时，这比"我们选 AP"有价值得多。
4. 有界风险思维：ATM 的 k=$200 限额示范了第三条路——不禁止操作也不放任，而是量化并封顶不一致的代价。任何"可用性 vs 一致性"争论都值得先问一句：能不能给风险设个上界？
5. 概念传播的教训：CAP 是"slogan 被自己的成功反噬"的经典案例（Brooker："too successful"；Kleppmann：请让它退休）。写作/分享技术概念时，口诀负责传播、原文负责精度，两者要在文内明确绑定；引用他人框架时优先回到原始论文核对定义——本次连"Princeton 镜像 6 页版与 SIGACT News 9 页版"这类版本差异都实际遇到，是活生生的提醒。
6. 与既有笔记的关联：与本库《SQLite 内幕》（单机 B-tree/WAL，一致性无需权衡的基线）、《事件驱动系统与消息队列》（AP 侧折中的典型实现）可对照阅读，形成"单机→单区域复制→跨区域/跨 WAN"的完整谱系。

重要原文引述备查

"When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three." — Gilbert & Lynch 2002, Abstract

"There must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time." — Gilbert & Lynch 2002 §2.1（Abadi 2012 引用同一句作为 CAP-C 的定义）

"most real-world systems today are forced to settle with returning 'most of the data, most of the time.'" — Gilbert & Lynch 2002, Conclusion

"CAP prohibits only a tiny part of the design space: perfect availability and consistency in the presence of partitions, which are rare." — Brewer 2012

"Operationally, the essence of CAP takes place during a timeout, a period when the program must make a fundamental decision—the partition decision: cancel the operation and thus decrease availability, or proceed with the operation and thus risk inconsistency." — Brewer 2012

"pragmatically, a partition is a time bound on communication." — Brewer 2012

"System designers should not blindly sacrifice consistency or availability when partitions exist." — Brewer 2012, Conclusion

"In reality, CAP only posits limitations in the face of certain types of failures, and does not constrain any system capabilities during normal operation." — Abadi 2012

"It is wrong to assume that DDBSs that reduce consistency in the absence of any partitions are doing so due to CAP-based decision-making." — Abadi 2012

"if there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?" — Abadi 2012（PACELC 定义）

"The difference in latency between these two options can be a factor of four or more." — Abadi 2012 转述 Rao/Shekita/Tata VLDB 2011 对 Cassandra 的实验

"CAP is confusing. PACELC is better, but still not ideal." — Brooker 2014

"The trickier ground starts with PA/EC... When is there a partition? Is a single dropped connection or lost packet a partition? ... If PA/EC is tricky, PC/EL is madness." — Brooker 2014

"The CAP theorem is too simplistic and too widely misunderstood to be of much use for characterizing systems. Therefore I ask that we retire all references to the CAP theorem." — Kleppmann 2015

"the CAP theorem says nothing about latency, which people tend to care about more than availability. In fact, CAP-available systems are allowed to be arbitrarily slow to respond, and can still be called 'available'." — Kleppmann 2015

"So these systems are neither 'CP' nor 'AP', they are just 'P', whatever that means. (Yes, the 'two out of three' formulation does allow you to pick only one out of three, or even none out of three!)" — Kleppmann 2015

"The fact that we haven't been able to classify even one datastore as unambiguously 'AP' or 'CP' should be telling us something: those are simply not the right labels to describe systems." — Kleppmann 2015

"(I guess that would be PC/EL in Abadi's PACELC framework, but I don't find that any more enlightening than CAP.)" — Kleppmann 2015 评 ZooKeeper

延伸阅读（来源中引用、本次未展开）

• Gilbert & Lynch, *Perspectives on the CAP Theorem*, IEEE Computer 2012（GL 本人的后续阐释）https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf
• Kleppmann, *A Critique of the CAP Theorem*（其正式论文版）
• Mahajan, Alvisi, Dahlin, *Consistency, Availability, and Convergence*（Brewer 引用：选 A 时因果一致性是最优结果）
• Shapiro 等, *Conflict-Free Replicated Data Types (CRDTs)*, SSS 2011
• Bailis 等, Highly Available Transactions 系列（一致性谱系与可用性关系）
• Doug Terry 用棒球例子讲多级最终一致性
• Brewer PODC 2000 keynote 原始幻灯：http://vis.usal.es/rodrigo/documentos/sisdis/papers/Brewer2000-CAPTherorem.pdf ；ACM DL 记录 https://dl.acm.org/doi/10.1145/343477.343502