21.2 Quorum 与 W + R > N 的证明
一句话
quorum 的全部安全性只来自一条几何事实——任意两个 quorum 必相交；
W + R > N是这条事实在读写模型里的代数写法，f + 1（Raft）与2f + 1（PBFT）是它在两种故障模型下的两个特例。
先定义清楚三个词
- quorum（法定人数）：任何一个决策必须获得其同意的节点集合。多数派 quorum 的大小是
q = ⌊N/2⌋ + 1。 - W / R：写要成功的副本数 / 读要访问的副本数。W、R 都是 quorum 的一种特例。
- f：能容忍同时坏掉的节点数。崩溃模型
N = 2f + 1，拜占庭模型N = 3f + 1。
| N | q = ⌊N/2⌋+1 | 2q | 2q > N | 容错 f = N−q | quorum 个数 C(N,q) |
|---|---|---|---|---|---|
| 3 | 2 | 4 | true | 1 | 3 |
| 4 | 3 | 6 | true | 1 | 4 |
| 5 | 3 | 6 | true | 2 | 10 |
| 6 | 4 | 8 | true | 2 | 15 |
| 7 | 4 | 8 | true | 3 | 35 |
注意 4 节点和 6 节点的尴尬：容错没有增加，成本却增加了（N=4 与 N=3 都只容忍 1 个故障；N=6 与 N=5 都只容忍 2 个）。这就是共识集群通常选 3 或 5 的原因，而不是 4 或 6。
相交引理：为什么多数派一定能碰头
引理：设 A, B ⊆ {1..N}，若 |A| + |B| > N，则 A ∩ B ≠ ∅。
证明（反证）：若 A ∩ B = ∅，则 A ∪ B 有 |A| + |B| 个不同元素，全部落在只有 N 个元素的集合里，于是 |A| + |B| ≤ N，与条件矛盾。∎
把它套到多数派：q = ⌊N/2⌋+1 ⇒ 2q ≥ N+1 > N，所以任意两个多数派必相交。整个共识理论（以及所有 quorum 系统）的地基就是这一行。
W + R > N 的证明
模型假设（缺一条，定理就不成立，后面会逐条说）：
- 每个写带一个单调递增的版本号（时间戳、LSN、zxid、term+index 都行）；
- 读从它访问的 R 个副本里取版本最高的那个值返回；
- 写成功后不会被回滚（没有"补偿删除"）；
- 一个副本一旦确认写，就不会悄悄丢掉它（不丢数据）。
定理：若 W + R > N，则任何一次读都与"最近一次成功的写"相交，因此该读能看到这次写（或更新的值）。
证明：设最近一次成功的写落在集合 S_w，|S_w| = W；本次读访问集合 S_r，|S_r| = R。由 W + R > N 与相交引理，S_w ∩ S_r ≠ ∅。取其中任一节点 x：x 上有这次写，且按假设 4 它还在；读在 R 个副本里取最高版本（假设 2），x 的版本不低于这次写，所以返回的值不会比这次写更旧。∎
逆命题：若 W + R ≤ N，则存在一种执行使读看不到最近一次写——写只落 S_w，读只读 S_r 且 S_w ∩ S_r = ∅。这不是"概率问题"，是"可以构造"，所以不能靠运气。
下面这段程序把 N=3..7 的所有 (W, R) 组合穷举了一遍，验证"W + R > N"与"不存在不相交对"完全等价：
package main
import "fmt"
// 用位图表示一个 quorum：第 i 位为 1 表示节点 i 在集合里
func bits(x uint) int {
c := 0
for ; x > 0; x &= x - 1 {
c++
}
return c
}
func subsets(n, k int) []uint {
var out []uint
for m := uint(0); m < 1<<n; m++ {
if bits(m) == k {
out = append(out, m)
}
}
return out
}
// 是否存在一对不相交的 w-quorum 与 r-quorum
func disjointPair(n, w, r int) (uint, uint, bool) {
for _, a := range subsets(n, w) {
for _, b := range subsets(n, r) {
if a&b == 0 {
return a, b, true
}
}
}
return 0, 0, false
}
func set(m uint, n int) string {
s := "{"
for i := 0; i < n; i++ {
if m&(1<<i) != 0 {
if len(s) > 1 {
s += ","
}
s += string(rune('A' + i))
}
}
return s + "}"
}
func main() {
fmt.Println("| N | q = N/2+1 | 2q | 2q > N | 容错 f = N−q | quorum 个数 C(N,q) |")
fmt.Println("|---|---|---|---|---|---|")
for n := 3; n <= 7; n++ {
q := n/2 + 1
fmt.Printf("| %d | %d | %d | %v | %d | %d |\n", n, q, 2*q, 2*q > n, n-q, len(subsets(n, q)))
}
// 穷举校验：W+R>N 与「不存在不相交对」是否完全等价
checked, okCount := 0, 0
for n := 3; n <= 7; n++ {
for w := 1; w <= n; w++ {
for r := 1; r <= n; r++ {
checked++
_, _, dis := disjointPair(n, w, r)
if (w+r > n) == !dis {
okCount++
}
}
}
}
fmt.Printf("\n定理校验：N=3..7 共 %d 组 (W,R)，W+R>N 与「不存在不相交对」一致的有 %d 组\n\n", checked, okCount)
// N=5 的矩阵
n := 5
fmt.Println("N=5，行 W、列 R：交 = 必相交（读必看到最近写），× = 存在不相交对（可能读到旧值）")
fmt.Print("| W\\R |")
for r := 1; r <= n; r++ {
fmt.Printf(" %d |", r)
}
fmt.Println("\n|---|---|---|---|---|---|")
for w := 1; w <= n; w++ {
fmt.Printf("| **%d** |", w)
for r := 1; r <= n; r++ {
if _, _, dis := disjointPair(n, w, r); dis {
fmt.Print(" × |")
} else {
fmt.Print(" 交 |")
}
}
fmt.Println()
}
// 举一个不相交的实例：N=5, W=2, R=3
a, b, _ := disjointPair(5, 2, 3)
fmt.Printf("\n反例：写只落 %s，读只读 %s —— 交集为空，读永远看不到那次写\n", set(a, 5), set(b, 5))
}
输出（本机实测）：
| N | q = N/2+1 | 2q | 2q > N | 容错 f = N−q | quorum 个数 C(N,q) |
|---|---|---|---|---|---|
| 3 | 2 | 4 | true | 1 | 3 |
| 4 | 3 | 6 | true | 1 | 4 |
| 5 | 3 | 6 | true | 2 | 10 |
| 6 | 4 | 8 | true | 2 | 15 |
| 7 | 4 | 8 | true | 3 | 35 |
定理校验：N=3..7 共 135 组 (W,R)，W+R>N 与「不存在不相交对」一致的有 135 组
N=5，行 W、列 R：交 = 必相交（读必看到最近写），× = 存在不相交对（可能读到旧值）
| W\R | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| **1** | × | × | × | × | 交 |
| **2** | × | × | × | 交 | 交 |
| **3** | × | × | 交 | 交 | 交 |
| **4** | × | 交 | 交 | 交 | 交 |
| **5** | 交 | 交 | 交 | 交 | 交 |
反例：写只落 {A,B}，读只读 {C,D,E} —— 交集为空，读永远看不到那次写
读法：
- 矩阵的对角线不是安全线：
W=R=2, N=5时4 ≤ 5，存在不相交对，读可能读到旧值。安全的边界是W + R = 6那条斜线。 W=5（全写）时任意 R 都安全，但写没有任何容错：任何一台挂掉写就失败。W=1, R=5也相交（6 > 5），但一次写只落一个节点，那个节点挂了这次写就没了——相交不等于持久。这是 W=1 的隐藏代价。
参数怎么选：三种典型配置
| 配置 | N | W | R | 写延迟 | 读延迟 | 容错（写/读） | 适用 |
|---|---|---|---|---|---|---|---|
| 读写都多数派 | 3 | 2 | 2 | 1 RTT（等 2 个） | 1 RTT（问 2 个） | 1 / 1 | 元数据、配置、锁 |
| 读多写少 | 5 | 3 | 3 | 1 RTT（等 3 个） | 1 RTT（问 3 个） | 2 / 2 | 通用、跨 AZ |
| 写少读多（读优化） | 5 | 5 | 1 | 2 RTT（等全部） | 本地 | 0 / 4 | 只读镜像、报表 |
| 写多读少（写优化） | 5 | 1 | 5 | 本地 | 1 RTT（问全部） | 4 / 0 | 采集、日志（容忍丢最近写） |
🔑 参数选择不是"W+R>N 之后随便挑"，而是先定"哪个方向不能丢、哪个方向必须快"：写要可靠就抬 W，读要快就降 R，两者的代价都落在延迟与可用性上。
为什么 W + R > N 仍然不等于线性一致
这是最容易答错的一题。W + R > N 只保证"读能看到最近一次成功的写"，而线性一致还要求：
| 缺失的前提 | 反例 | 补法 |
|---|---|---|
| 写可能被回滚 | 写落到 2 个副本，其中 1 个随后崩溃又被一个旧值副本替换（无回滚日志），版本最高的值消失 | 需要提交协议（共识日志），不能只靠覆盖写 |
| 没有全序 | 两个并发写落在不同 quorum，读可能先看到 A 再看到 B，另一个客户端看到相反顺序 | 单 leader + 日志定序（见 21.6 Raft：日志复制） |
| 旧 leader 还在写 | 分区的少数派 leader 继续接受写，版本号甚至更高 | 任期/租约 + fencing（见 48.4 Leader 选举） |
| 读不取最高版本 | 读到第一个响应的副本（"最快者胜"） | 必须比较版本；或走 ReadIndex/租约（见 21.12 共识算法对比） |
所以 W + R > N 是必要不充分条件：Dynamo 风格的 AP 系统用它换"读到你自己的写（在多数派健康时）"，而线性一致需要共识（16.2 线性一致性 给了形式定义）。
quorum 在共识里被加强了一次
共识用的不只是"多数派相交"，而是"相交 + 候选人日志至少一样新"：
| 机制 | 作用 | 少了会怎样 |
|---|---|---|
| 多数派相交 | 新 leader 与旧 leader 的 quorum 必有交集 | 两个 leader 同时存在 |
| 选举限制（日志至少一样新） | 交集里的节点不会投票给日志更旧的候选人 | 落后的节点当选，覆盖已提交条目（图 8 反例，见 21.7 Raft：安全性证明） |
| 任期号单调 | 旧 leader 的请求被拒绝 | 旧 leader 复活后继续提交 |
⚠️ 三种"quorum 计算"的错误，线上都出现过：① 把 observer/learner 算进多数派（它们不投票也不该计数）；② 按机器数而不是副本数算（两个副本同机架，一起挂）；③ 跨机房时按全局 N 算多数派，但某一机房本地凑不出多数派 → 该机房整体不可用（要按故障域设计，见 36.4 两地三中心与多活）。
反模式
| 反模式 | 后果 |
|---|---|
用 W=1 追求写延迟，却对外声称"强一致" | 单副本写，节点一挂就丢数据 |
N=4/6 的集群 | 容错与 N−1 相同，成本更高、quorum 更大 |
把 sloppy quorum（hinted handoff）当成 W+R>N | 写落到了"临时节点"，与读集合可能不相交，必须靠 read-repair 兜底 |
认为 W+R>N 就能防脑裂 | 它只保证读能看到写，不阻止两个 leader 同时写 |
| quorum 里混入不参与投票的角色 | 实际 quorum 变小，安全性被悄悄削弱 |
| 只按节点数算 quorum，不看故障域 | 一个机架故障就能让整个集群失去多数派 |
自检
Q1 5 个节点，取 W=2, R=3，W+R=5 ≤ N。请构造一个"读不到刚写完的值"的执行。
▸ 答案：写只被 A、B 确认（W=2 就返回成功）；读只访问 C、D、E（R=3）。{A,B} ∩ {C,D,E} = ∅，读的三个副本上都没有这次写，取最高版本也只能拿到旧值。这正是程序输出的那个反例。要修：把 W 抬到 3，或把 R 抬到 4（3+3=6>5、2+4=6>5）。
Q2 为什么 N=4 的集群不划算？
▸ 答案：N=4 的多数派是 3，容错 N−q = 1，与 N=3 一样只容忍 1 个故障，但每次决策要等 3 个节点、集群多一台机器、quorum 个数从 3 变 4。N=6 同理（q=4，容错 2，与 N=5 相同）。所以共识集群的节点数取 2f+1：3、5、7。
Q3 W + R > N 保证了线性一致吗？如果读者的回答是"保证"，你会追问什么？
▸ 答案：不保证，只保证"读能看到最近一次成功的写"。需要追问四件事：① 写失败会不会被回滚（有没有提交协议）；② 并发写有没有全序（有没有 leader/日志）；③ 旧 leader/分区少数派还会不会接受写（有没有任期与 fencing）；④ 读是否取最高版本（还是谁先响应算谁）。四问里任何一个答不上来，都不能声称线性一致。
Q4 为什么说"相交不等于持久"？举一个 W+R>N 但仍然丢数据的配置。
▸ 答案：N=5, W=1, R=5 满足 6>5，读一定与写相交；但写只落在 1 个副本上，这个副本在数据被复制出去之前崩溃（且磁盘损坏/被替换），这次写就永久丢失。相交保证的是"读得到"，持久保证的是"写得下且不丢"——后者要求写落多个副本（W ≥ 2 且落盘），或由共识日志负责复制。
Q5 集群里加了两个 observer，quorum 会变吗？为什么？
▸ 答案：不会。observer 只同步日志、不参与投票，多数派仍按投票成员计算（如 3 个投票成员 + 2 observer，quorum 仍是 2）。如果误把 observer 计入分母（变成 5 个里的 3 个），实际需要 3 票才能提交，而真正能投票的只有 3 个——任何一台投票成员挂掉，集群就提交不了；更糟的是，如果实现里真的让 observer 投票，quorum 相交的前提也被破坏。