NRW 仲裁参数——分布式副本读写的数值问题
问题
分布式系统把数据复制到 N 个节点上。写入时让 W 个节点确认，读取时查询 R 个节点。W 和 R 取多少，才能保证读到最新写入的数据？
"取多数派"是工程师最常见的直觉回答，但"多数"到底是多少——N 的一半多一个？还是 N 的三分之二？这两个数字分别在什么条件下出现，背后的推导和权衡，远比"取多数派"三个字复杂。
起源：Gifford 加权投票（1979）
NRW 模型的源头是 David K. Gifford 在 1979 年 SOSP 会议上发表的论文 Weighted Voting for Replicated Data。Gifford 的模型比今天常见的等权版本更一般化：每个副本节点被分配一个投票权重 wᵢ，所有节点的总票数 V = Σwᵢ。读仲裁所需票数 Vr 和写仲裁所需票数 Vw 必须满足两个约束：
1 | |
约束 1 保证任何一次读操作至少触碰到一个持有最新版本的节点——读集合和写集合必然有交集。约束 2 保证任何两次写操作至少有一个公共节点，从而可以对写入排出全序。
当每个节点的权重都等于 1 时，V = N，两个约束退化为等权形式：
1 | |
这就是今天的 NRW 模型。
同年，Robert H. Thomas 独立发表了 A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases，从数据库并发控制的角度提出了多数派投票，与 Gifford 的工作殊途同归。
核心数学：鸽巢原理
W + R > N 的正确性证明只需要一条初等工具——鸽巢原理（又称抽屉原理）：如果 n+1 个物体放进 n 个抽屉，至少有一个抽屉里有两个物体。
设上一次成功的写操作写入了节点集合 Sw（|Sw| = W），当前的读操作查询了节点集合 Sr（|Sr| = R）。两个集合的元素都取自同一个全集——大小为 N 的节点集合。
1 | |
鸽巢原理直接给出结论：两个子集的元素数之和超过全集大小，交集非空。Sw ∩ Sr ≠ ∅，读操作至少能碰到一个持有最新数据的节点。
客户端收到 R 个响应后，通过版本号或时间戳从中挑出最新值。
这条性质和 Paxos 正确性证明用的是同一条定理。Paxos 论文中的叙述是"任取两个多数派 Q₁ 和 Q₂，|Q₁| + |Q₂| > N，所以 Q₁ ∩ Q₂ ≠ ∅"——和上面的推导完全一致。
约束 2 的作用
R + W > N 保证读写交叉，但还不够。如果 W ≤ N/2，两次并发写入可以成功写入两个不相交的节点集合。后续读操作虽然能读到某个最新值，但无法判断两个值之间的先后顺序。
W > N/2 保证任何两次写操作的写入集合也有交集。公共节点同时持有两次写入的记录，可以用版本号排出全序。
Dynamo 风格的系统有时放松约束 2，允许 W ≤ N/2。代价是并发写入可能在不同节点集合上各自成功，产生冲突版本。这些系统用版本向量（vector clock）或最后写入胜出（Last-Write-Wins, LWW）来事后解决冲突，而不是在写入时通过 quorum 交叉来预防冲突。
配置空间
固定 N 之后，W 和 R 的取值形成一个连续的权衡谱。不同的 (N, W, R) 组合对应不同的一致性、可用性和性能特征。
N = 3 的配置
| 配置 | W | R | 写容错 | 读容错 | 特点 |
|---|---|---|---|---|---|
| 均衡 | 2 | 2 | 1 | 1 | 读写对称，最常见 |
| ROWA | 3 | 1 | 0 | 2 | 读最快，任何一个节点故障都阻塞写入 |
W = 1 不满足 W > N/2 = 1.5 的约束，无法保证写入全序，因此不是合法的严格仲裁配置。
ROWA（Read-One-Write-All）是 W = N, R = 1 的极端选择。PacificA 协议就采用了这种设计——所有 Secondary 确认后 Primary 才返回成功，换取读操作只需查询 Primary 一个节点。
N = 5 的配置
| 配置 | W | R | 写容错 | 读容错 |
|---|---|---|---|---|
| 均衡 | 3 | 3 | 2 | 2 |
| 写重读轻 | 4 | 2 | 1 | 3 |
| ROWA | 5 | 1 | 0 | 4 |
容错公式
写操作最多容忍 N − W 个节点同时故障，读操作最多容忍 N − R 个节点同时故障。系统整体的容错上限取两者中的较小值。
W 和 R 是一对跷跷板：W 越大，每次写入的一致性越强，但能容忍的故障数越少，延迟也越高（要等更多节点响应）。R 同理。CAP 定理在 NRW 模型里具象化为 W 和 R 的数值选择。
W 的取值：过半还是三分之二？
一个广泛流传的印象是"写仲裁占 N 的三分之二"。这个印象在 N = 3 的场景下恰好正确（W = 2 = N × 2/3），但推广到一般情况时会产生误导。根源在于它混淆了两种不同的故障模型。
崩溃故障模型（Crash Fault）
Paxos、ZAB、Raft 处理的是崩溃故障：节点要么正常运行，要么完全停止响应，不会发出错误信息。
在这个模型下，集群需要 N = 2f + 1 个节点来容忍 f 个同时崩溃。多数派大小 = f + 1 = (N + 1) / 2。
| N | f | 多数派 | 占 N 的比例 |
|---|---|---|---|
| 3 | 1 | 2 | 66.7% |
| 5 | 2 | 3 | 60.0% |
| 7 | 3 | 4 | 57.1% |
| 9 | 4 | 5 | 55.6% |
| 2f+1 | f | f+1 | → 50% |
随着 N 增大，多数派占比单调下降，极限值是 50%。三分之二只是 N = 3 这个最常用部署规模下的巧合。
拜占庭故障模型（Byzantine Fault）
PBFT 等协议处理的是拜占庭故障：节点可能发出任意错误信息，包括恶意伪造。
在这个模型下，集群需要 N = 3f + 1 个节点来容忍 f 个拜占庭节点。仲裁大小 = 2f + 1 = (2N + 1) / 3。
| N | f | 仲裁 | 占 N 的比例 |
|---|---|---|---|
| 4 | 1 | 3 | 75.0% |
| 7 | 2 | 5 | 71.4% |
| 10 | 3 | 7 | 70.0% |
| 3f+1 | f | 2f+1 | → 66.7% |
随着 N 增大，仲裁占比趋向三分之二。
差一个 f 的直觉
崩溃节点沉默不语，不会投假票，多数即可判定真相。拜占庭节点会投假票：最坏情况下 f 个坏节点全部投了假票，好节点的真票必须压过 f 张假票。f + 1 张真票对 f 张假票才能胜出，总共需要收集 2f + 1 张票——三分之二门槛由此而来。
换句话说，crash-fault 模型下沉默节点"不占名额"，只需要在应答者中取多数；Byzantine 模型下恶意节点"占名额还捣乱"，需要额外的票数来抵消它们的干扰。
两种模型在 N = 3 时的巧合
| 故障模型 | N | f | 仲裁 |
|---|---|---|---|
| Crash | 3 | 1 | 2 |
| Byzantine | 4 | 1 | 3 |
N = 3 的 crash-fault 仲裁恰好是 2，等于 N 的三分之二。但 N = 3 的 Byzantine 场景需要 N = 4 才能容忍 1 个拜占庭节点（3f + 1 = 4），仲裁是 3。两种模型的数值只在 N = 3 的 crash-fault 配置下巧合地碰上了"三分之二"，推广到更大的 N 后差距越来越大。
共识协议与副本仲裁：同源不同路
Paxos/Raft 里的 quorum 和 Dynamo 风格系统里的 NRW 建立在同一条数学性质上（多数派交叉），但解决的问题层次不同。
| 维度 | 共识协议（Paxos/Raft） | 副本仲裁（Dynamo/Cassandra） |
|---|---|---|
| 目标 | 多个提案者就单一值达成一致 | 多副本读写保证能看到最新值 |
| 写入语义 | 两阶段（Prepare + Accept） | 直接并行写 W 个节点 |
| 冲突处理 | 协议内建（高编号提案覆盖低编号） | 需要额外机制（版本向量、LWW） |
| 提供的一致性 | 线性一致性 | 仅保证读到某个最新副本 |
| 读取路径 | 读 leader 或走一轮 quorum read | 查 R 个节点取最新版本 |
共识协议在 quorum 交叉之上叠加了提案编号排序、日志复制、领导者选举等机制，目标是全局操作的线性一致性。副本仲裁的裸 NRW 只保证"读到的 R 个响应中包含最新值"，不对操作的全局顺序做任何承诺。
Quorum 交叉是地基。共识协议在地基上盖了一栋有承重结构的建筑（提案编号、日志、选举），Dynamo 风格的 NRW 只在地基上搭了平房。平房够用的场景不需要多层建筑的复杂度。
Flexible Paxos：打破对称 quorum
2016 年，Heidi Howard 等人发表 Flexible Paxos: Quorum Intersection Revisited，指出标准 Paxos 对 quorum 的要求过于保守。
标准 Paxos 要求所有 quorum 都是多数派（> N/2），不区分 Phase 1（Prepare）和 Phase 2（Accept）的大小。Flexible Paxos 发现：真正需要交叉的只有一对——Phase 1 quorum 必须和 Phase 2 quorum 交叉。
原因在于 Paxos 的安全性证明只在一个地方用到了 quorum 交叉——新提案者在 Phase 1 收集信息时，必须碰到至少一个在旧提案的 Phase 2 中投过票的节点。只要 Q₁ + Q₂ > N（Q₁ 是 Phase 1 大小，Q₂ 是 Phase 2 大小），这个交叉就有保证。两个 Phase 1 quorum 之间、两个 Phase 2 quorum 之间都不需要交叉。
这打开了一个新的配置维度。Q₁ 和 Q₂ 可以不对称：
| Q₁（Prepare） | Q₂（Accept） | 条件 Q₁+Q₂>N | 场景 |
|---|---|---|---|
| N | 1 | N+1 > N ✓ | 全员 Prepare，单节点 Accept |
| ⌊N/2⌋+1 | ⌊N/2⌋+1 | 标准 Paxos | 对称多数派 |
| 1 | N | N+1 > N ✓ | 单节点 Prepare，全员 Accept |
在领导者稳定的系统中（Raft 和 ZAB 的常态），Phase 1 只在领导者换届时执行，频率极低；Phase 2 每次提交都要跑。Flexible Paxos 允许用大的 Q₁（反正极少执行）换取小的 Q₂（每次提交都执行），直接降低稳态提交延迟。
对 NRW 参数选择的启示：如果读操作远比写操作频繁（或反之），不必对称地分配 R 和 W——让低频操作承担更大的 quorum 开销，高频操作用最小 quorum 即可。
Sloppy Quorum 与 Hinted Handoff
Amazon Dynamo 论文（DeCandia 等，2007）引入了 Sloppy Quorum 这一工程妥协。
严格 quorum 要求 W 个确认必须来自数据所属的 N 个首选节点。当首选节点中有部分不可达时，严格 quorum 会阻塞写入。Sloppy Quorum 放宽了这个要求：允许写入请求被路由到一致性哈希环上的下一个可用节点——即使该节点不属于原来的 N 个首选节点。
收到这种"代管"数据的节点会在本地标记一条提示：“这份数据应该属于节点 X”。等 X 恢复后，代管数据被移交给 X。这个过程就是 Hinted Handoff。
代价很直接：Sloppy Quorum 违反了 W + R > N 的前提。W 个确认可能包含不属于原始 N 的节点，后续读操作如果只查原始 N 中的 R 个节点，就可能漏掉这些写入。Sloppy Quorum 把一致性让给了可用性——一个明确的 AP 倾斜。
Cassandra 通过 consistency level 提供了粒度控制：设为 QUORUM 走严格仲裁，设为 ONE 或 ANY 走 sloppy 路径。运维人员可以逐操作地选择一致性和可用性之间的平衡点。
实际系统的 NRW 选择
| 系统 | 复制模型 | NRW 暴露方式 | 默认配置 | 说明 |
|---|---|---|---|---|
| Cassandra | 无主 | 每次操作指定 consistency level | ONE | QUORUM = ⌊RF/2⌋+1，RF 是 replication factor |
| DynamoDB | 内部 quorum | 不暴露 NRW | 最终一致 | 用户只看到"最终一致读"和"强一致读"两个选项 |
| Riak | 无主 | 直接暴露 N/R/W 参数 | N=3, R=2, W=2 | 均衡配置 |
| Kafka | 主从 + ISR | min.insync.replicas + acks | acks=1 | acks=all + min.insync.replicas=2 近似 W=2 |
| ZooKeeper | ZAB 共识 | 不可配 | 多数派 | 写入需多数 follower 确认 |
| etcd | Raft 共识 | 不可配 | 多数派 | 读可配为 linearizable 或 serializable |
Kafka 的 ISR 机制与经典 NRW 有显著差异。Kafka 不使用固定大小的 quorum，而是维护一个动态的 ISR（In-Sync Replicas）集合——只有跟上 leader 复制进度的 follower 才在 ISR 中。acks=all 要求 ISR 中所有副本确认，min.insync.replicas 限定 ISR 的最小规模。
差别在于：ISR 可以缩小到只剩 leader 一个节点，此时 acks=all 退化为单节点确认，不提供任何冗余保护。经典 NRW 的 W 是固定的，不会因节点状态变化而降级。换言之，Kafka 的"quorum"是弹性的，在极端情况下会自动降低安全水位来维持可用性；经典 NRW 则是宁可阻塞写入也不降低安全水位。
NRW 不解决的问题
线性一致性
W + R > N 保证"读到的 R 个响应中包含最新值"，但不保证多个客户端看到相同的操作顺序。两个客户端同时执行 quorum read，可能从不同的 R 集合得到不同版本——一个看到新值，另一个看到旧值。在严格的线性一致性定义下，如果一次写入已经对某个客户端可见，它就必须对所有后续读取可见。裸 quorum read 不提供这个保证。
要在 quorum 之上实现线性一致性，常见手段包括：
- 读修复（Read Repair）：读取时发现过期副本后主动推送最新值，使后续读取收敛到一致状态。
- 两阶段读（ABD 算法）：读到最新值后再写回一轮 quorum，确保后续读取能看到这个值。代价是每次读操作的延迟翻倍。
- 走共识协议的 linearizable read 路径（如 Raft 的 ReadIndex 或 Lease Read），本质上借助 leader 做了一次隐式的全局排序。
并发写入冲突
两个客户端同时写入不同的值时，quorum 机制本身不决定哪个值胜出。冲突解析需要额外策略：
| 策略 | 做法 | 代价 |
|---|---|---|
| Last-Write-Wins（LWW） | 按物理时间戳排序，保留最晚的写入 | 丢弃并发写入；依赖时钟同步（NTP 的精度有限） |
| 版本向量（Vector Clock） | 每个节点维护向量时钟，检测因果无关的并发写入 | 冲突暴露给应用层决策；向量长度随节点数增长 |
| CRDTs | 使用满足交换律和结合律的数据结构，并发修改自动合并 | 仅适用于特定数据类型（计数器、集合、LWW-Register 等） |
Dynamo 选择了版本向量加应用层解析（购物车场景下合并所有冲突版本，宁可多出物品也不丢失物品）。Cassandra 选择了 LWW。Riak 两者都支持，由用户在 bucket 级别选择。
成员变更
NRW 模型的推导假设 N 是固定值。真实系统中节点的加入和退出会改变 N。在新旧配置切换的瞬间，如果新旧配置的 quorum 没有交叉，就可能出现短暂的不一致窗口。
这本质上就是共识协议中成员变更（membership change）问题的翻版。Raft 的联合共识（Joint Consensus）和单节点变更方案都是为了在切换期间保证新旧配置的任何两个 quorum（一个来自旧配置，一个来自新配置）仍然有交叉。
参考资料
- Gifford, D. K. “Weighted Voting for Replicated Data.” SOSP, 1979.
- Thomas, R. H. “A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases.” ACM TODS, 1979.
- Herlihy, M. “A Quorum-Consensus Replication Method for Abstract Data Types.” ACM TOCS, 1986.
- Lamport, L. “The Part-Time Parliament.” ACM TOCS, 1998.
- DeCandia, G. et al. “Dynamo: Amazon’s Highly Available Key-value Store.” SOSP, 2007.
- Lakshman, A. and Malik, P. “Cassandra: A Decentralized Structured Storage System.” LADIS, 2009.
- Ongaro, D. and Ousterhout, J. “In Search of an Understandable Consensus Algorithm.” USENIX ATC, 2014.
- Howard, H., Malkhi, D., and Spiegelman, A. “Flexible Paxos: Quorum Intersection Revisited.” OPODIS, 2016.
