CAP 与分片复制

01

基本想法

一致性意味着每次读取都能看到最近的写入。可用性意味着每个请求都能得到响应（成功或失败）。分区容错性意味着即使网络故障将系统分割成孤立的组，系统仍能工作。CAP 定理说，当分区发生时，你不能同时拥有这三个属性。

复制在节点之间复制数据，以便读取可以在本地提供并且写入在故障后仍能保存。分片将数据分割到节点上，以便系统可以水平扩展。它们一起决定系统在故障期间的行为。

在 CP 系统中，当分区发生时，少数分区中的节点拒绝提供请求以避免返回过时数据。这牺牲了可用性以获得一致性。在 AP 系统中，所有分区继续提供请求，但它们可能返回不同的答案，直到分区修复并且它们协调一致。

大多数真实系统既不是纯 CP 也不是纯 AP。它们提供可调一致性：你可以根据每个请求选择是等待所有副本的确认（强一致性，低可用性）还是只等待一个（高可用性，最终一致性）。

02

数学

在具有 n 个节点和复制因子 r 的复制系统中，每个数据项存储在 r 个节点上。读取法定人数 q_r 个节点和写入法定人数 q_w 个节点必须满足 q_r + q_w > r 以保证一致性，因为任何读取都与最新写入重叠。

对于强一致性（线性化），你需要 q_r + q_w > r 和 q_w > r/2。常见选择是 q_r = q_w = ⌈(r+1)/2⌉，即多数法定人数。如果 r = 3，你需要 2 个节点同意。这在保持一致性的同时容忍 ⌊r/2⌋ 个节点故障。

在分片系统中，数据使用哈希函数或范围分区跨 s 个分片进行分区。随机键在故障分片上的概率是 f/s，其中 f 是故障分片的数量。将每个分片复制 r 次将故障概率降低到 (f/s)^r，假设故障独立。

法定人数读取的延迟是来自 q_r 个副本的响应时间的中位数。尾部延迟很重要：如果一个副本很慢，第 99 百分位的请求延迟通常由最慢的副本主导。对冲（发送重复请求）以增加负载为代价减少尾部延迟。

03

动手试

工具模拟具有网络分区的三节点集群。在 CP 模式下，少数分区拒绝写入以保持一致。在 AP 模式下，所有分区接受写入，创建分歧状态。当分区修复时，AP 系统必须使用向量时钟或最后写入获胜来协调冲突的写入。

04

我在哪用到它

05

容易出错的地方

06

参考资料

COMP90024 集群和云计算中涵盖。基于 Brewer 的 CAP 定理（2000），Gilbert & Lynch 的正式证明（2002），和 Kleppmann 的《设计数据密集型应用》（2017），第 9 章。Dynamo 和 Cassandra 论文是典型的 AP 例子；Google Spanner 是 CP。

初稿于2023，2026年重写。