法定人数系统 | Codeboy's Blog

形式陈述

给定有限副本集合 $U$ ， $|U|=N$ 。法定人数系统是一个非空集合族 $\mathcal Q\subseteq 2^U$ ，其中每个 $Q\in\mathcal Q$ 称为一个 quorum。若所有承担冲突操作的 quorum 都满足

Q_1\cap Q_2\ne\varnothing,

则任意两次此类操作都共享至少一个参与者，旧证据与新证据因而有机会相遇。交集大小来自包含—排除公式：对任意 $Q,Q'\subseteq U$ ，

|Q\cap Q'|=|Q|+|Q'|-|Q\cup Q'|\ge |Q|+|Q'|-N.

因此两个大小至少为 $q$ 的 quorum 相交至少 $2q-N$ 个节点； $q>N/2$ 保证交集非空。系统还需满足相对于故障集合 $F$ 的可用性：故障发生后至少存在一个 $Q\in\mathcal Q$ 使 $Q\cap F=\varnothing$ ，否则相交性虽保住了安全，操作却无法完成。

复制寄存器常把读集合族 $\mathcal Q_r$ 与写集合族 $\mathcal Q_w$ 分开。若每次从 $N$ 个副本中读 $r$ 个、写 $w$ 个，为使每次读与最近写相交以及任意两次写相交，需要

r+w>N,\qquad 2w>N.

第一式由 $|Q_r\cap Q_w|\ge r+w-N$ 得到，第二式由 $|Q_w\cap Q'_w|\ge 2w-N$ 得到。这些不等式只给出相交的组合条件；版本号、写入顺序和并发冲突处理仍需协议定义。在最多 $f$ 个 Byzantine 节点的模型中，交集非空不够，因为唯一交点可能说谎；若要保证交集中至少一个正确节点，就须令相关 quorum 的交集大小至少为 $f+1$ 。

直觉

quorum 的作用是避免每次操作都等待全体副本，同时又不让关键证据彼此错过。一次写只接触部分节点，后续读取也只接触部分节点，但两组人必然有重叠，于是至少有人有机会见过新状态。它建立的是“证据交接通道”，不是自动的一致性算法：交点上的节点需要持久保存什么、如何比较版本、何时承诺，都要由上层协议补齐。

安全与可用性在这里拉向相反方向。quorum 越大，两个集合越容易产生足够大的交集，也越能排除矛盾决定；与此同时，一次操作要等更多节点，故障或分区时更难凑齐。quorum 系统的设计就是在给定故障模型下选择这条边界，而不是机械地取简单多数。

例子与边界

五副本系统中写 quorum 向读 quorum 传递版本证据 — 写集合与读集合在副本 r₃ 相交，持久版本证据可由此接力；红色公式强调集合非空相交本身并不自动推出协议安全。

设 $N=5$ ，选择 $r=3,w=3$ 。任意读写 quorum 至少相交 $3+3-5=1$ 个副本，任意两个写 quorum 也至少相交一个副本。一次操作只需三个响应，所以两个副本不可用时仍可能完成。若读写集合都只取两个，则集合 $\{1,2\}$ 与 $\{3,4\}$ 可以完全分离，读者可能看不到已完成写入的任何见证。

网络分区时，两个互不连通的分区不可能各自包含一个严格多数 quorum。较小分区停止服务，保住了双方不能各自形成冲突决定的安全性；若强行允许两边都继续写，则必须接受冲突合并或放弃强一致保证。这里的取舍来自集合相交事实，不是通信库的偶然行为。

在 $N=3f+1$ 的常见 Byzantine 配置中，大小 $2f+1$ 的两个 quorum 至少相交

2(2f+1)-(3f+1)=f+1

个节点。即使其中 $f$ 个都是 Byzantine，仍留有一个正确节点。这个计数绑定于“最多 $f$ 个 Byzantine 故障”的假设；换成崩溃故障、认证广播或不同提交规则后，阈值必须重新推导，不能把 $2f+1$ 当作 quorum 的定义。

推论与应用

Paxos 中，新 ballot 的 Phase 1 quorum 必须与每个可能选定旧值的 Phase 2 quorum 相交。共同 acceptor 报告其持久 accepted 记录，proposer 再按 ballot 继承值；若共同节点可以遗忘记录或新 proposer 可以忽略记录，即使集合仍相交，两个值也可能分别被选定。Basic Paxos 让两阶段都用多数，Flexible Paxos 则揭示真正必要的是相关 Phase 1 与 Phase 2 集合族交叉相交，而非机械要求所有同阶段 quorum 两两相交。

Raft 让选举 quorum 与提交 quorum 相交，并用“一任期一票”和日志新旧限制规定交点如何携带证据。读写复制可用不对称的 $r,w$ 调整读写延迟；PBFT 等 Byzantine 协议则要求交集含足够的正确见证者。加权投票、网格 quorum 与分层 quorum 都表明，简单多数只是集合族的一种选择。

对具体协议，验证 quorum 不能只检查集合大小。还应写清哪些操作族必须互相相交、故障后哪些 quorum 仍可达、交集里需要多少正确节点，以及节点保存的证据是否跨轮次有效；缺少任一项，相交公式都不足以推出协议安全。

参考资料

David K. Gifford, “Weighted Voting for Replicated Data,” Proceedings of the 7th ACM Symposium on Operating Systems Principles, 1979, pp. 150–162。
Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman, “Flexible Paxos: Quorum Intersection Revisited,” OPODIS 2016, LIPIcs 70, Article 25。
Dahlia Malkhi and Michael Reiter, “Byzantine Quorum Systems,” Distributed Computing 11, 1998, pp. 203–213。

形式陈述 ​

反向链接

形式陈述