法定人数系统 | 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 越大，两个集合越容易产生足够大的交集，也越能排除矛盾决定；与此同时，一次操作要等更多节点，故障或分区时更难凑齐。对允许任取 $q$ 个副本的阈值 quorum，要在任意至多 $f$ 个崩溃后仍凑齐，就需 $q\le N-f$ ；再结合 $2q>N$ ，才得到常见的 $N>2f$ 。这是相交与可用性联立后的结果，而非“多数”本身含有故障恢复能力。

例子与边界

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

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

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

读写相交也不能独自保证线性一致读。三个副本初值均为 0，一次未完成写只把副本 A 更新为版本 1；读者先读 A、B，返回 1，随后另一个读者读 B、C，却返回 0。两次读都取多数，仍产生新值之后倒退。ABD 寄存器让第一次读在返回前把最高版本写回一个 quorum，使后继读必然遇到该版本；是否需要这一步取决于完整协议，不能只看 $r+w>N$ 。

在 ABD 的固定多数多写者扩展中，接收证据的还包括写者自己的查询阶段。先前的写传播或读写回已经得到一个多数确认，新写的查询再与它相交，从而看见不低于先前操作的标签；新写把计数加一，才获得严格更大的标签。这里相交承担的是“传播阶段到后继查询阶段”的交接，交点上的状态单调性和消息先后把集合事实变成实时顺序保证。它没有要求同一组节点永远可用，也不意味着任何其他 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，§5 的两阶段交叉相交证明。
Dahlia Malkhi and Michael Reiter, “Byzantine Quorum Systems,” Distributed Computing 11, 1998, pp. 203–213。

形式陈述 ​

反向链接

形式陈述