最近，”Quorum”这个词变得并不罕见了。在类似Zookeeper、etcd、Serf这样的集群环境中，以及类似Cassandra、Riak这样的分布式数据库（NoSQL类型）中，我们经常听到这个词，它指的是确保数据复制的一致性机制。

然而，即使读了许多幻灯片和网上文章，我还是觉得”Quorum”这个词的意思基本上是指由多数节点进行多数决策。

尽管如此，为什么被称为“Quorum”？由于对这个问题感到好奇，所以我借此机会进行了调查。

在这种情况下，我想将”Quorum”定义为一个非常抽象且强大的概念，它是将多数决定的概念推广的结果。

在分散系统中，数据的复制

最近，分散系统变得越来越常见。在分散系统中，数据几乎不会被保存在一个地方，而是会被复制并保存在多个节点上，即存在多个副本。

通过复制可以提高读取吞吐量，通过将复制返回给客户端可以提高读取速度，但从分布式系统的”故障容忍性”的角度来看，即使其他节点停止，也可以进行数据的读取和写入，也就是说，数据的可用性增强了。

然而，这并不是免费的，随着复制的增加，一旦在数据修改时无法有效地管理复制品，问题就会变得更加复杂。如果复制品的内容出现差异，那么就很难为客户提供一致的读取数据。

在分散系统中，由于多个进程组被网络隔离，因此我们希望它们能在网络被分割的情况下仍能正常工作（即具有网络分区容忍性）。

2000年代初期に証明された有名なCAP定理によれば、这个C、A、P三个属性无论如何都不能同时满足，只能同时满足其中两个。

经常听到的Quorum是指多数决定/过半数对吗？

我有点偏离了话题，但在复制管理方法中，经常听说的是使用Quorum的方法。（还有其他方法，如ROWA（Read One Write All），Primary Copy ROWA）

这些被称为NoSQL（如Cassandra、Riak等）以及Paxos、RAFT等算法，是在著名的分布式一致算法和领导者选举算法中使用的。

在中国，这个Quorum经常被解释为”过半数/多数决定”，很多人经常理解为”Quorum？啊，是指多数决定/过半数的事情吧？”。

半数以上的节点完成了基于一致性的复制实现，具体如下所示。

使用过半数/多数决来管理复制品的方法：

• 書込時: 過半数1以上のノードに、タイムスタンプ2付きで書込めるまで待つ

読込時: 過半数のノードから複製を読み込んで、一番新しいタイムスタンプのものをクライアントに読込結果として返す

这样做可以保证在读写任何一种情况下都能“确保”获取到最新的时间戳数据，同时需要进行另外一种处理才能进行多个同时写入。

然而，光是這樣一個名稱「Quorum」就代表過半數/多數決這一概念，讓我不禁猜想其中必有所異，於是這次我做了一些研究。

对于这次调查的资料

经过各种调查研究，下面的课程第7节精确而完整地总结了。因此，我将其作为主要资料进行总结。

分散计算原理（2003年夏季）
（瑞士联邦工科大学苏黎世分校（ETH Zurich）分布式计算研究组开设的课程）

什么是Quorum？

首先从定义的角度开始。

假设有一个节点集合$V = \{ v_1, v_2, …, v_n \}$。我们称包含在$V$中的子集合的集合$\mathcal{S} \subset 2^V$为一个拜占庭共识系统，满足以下条件。拜占庭共识系统的元素被称为决议。

どの２つのquorum $Q_1, Q_2$も共通部分を持つ($Q_1 \cap Q_2 \neq \emptyset$)

我明白了，这个集合集合确实成为了这个仲裁系统，其中包括了具有绝大多数大小的节点的集合。

即使不达到过半数，只要是使用了法定人数制度，就一定会在法定人数之间存在共同部分，因此可以用以下方式对使用过半数的方法进行泛化。

使用Quorum系统来管理复制。

• readとwriteで共通のquorum systemを定義する

書込時,読込時にはその中からquorumを一個選んで、quorumに所属するすべてのノードに書込/読込処理を行う(どれか一個でも失敗したらエラーとする)

使用相同的quorum系统进行读取和写入是关键。因此，即使每次写入/读取处理选择的quorum不同，也一定会包含重复的节点，从而可以读取到最新的数据。

只要在所有节点中，至少有一个法定人数仍然存在，数据将会被保留。换句话说，即使有一半以下的节点发生故障停止，系统仍将持续提供数据。

使用Quorum System实现分布式锁。

使用共识系统，可以实现分布式锁。实现方法很简单。

• quorumを選んで、各ノードから順にlockを得る。一つでもlockが得られなかったら、それまで得られたlockをreleaseしてやり直す

releaseするときはlockを得た時のquorumの全ノードのlockをreleaseする

在中文中，只需要一個選項來重新詮釋這句話：
只有一个选择。然而，如果没有定义以锁定顺序为依据，而且两个以上的quorum存在共同部分，则可能会发生死锁，因此需要注意。

例如，考虑下面这个Quorum系统（$v_2, v_3$是共有部分）。

$$V = \{ v_1, v_2, v_3, v_4 \}\;,\; \mathcal{QS} = \{Q_1=\{v_1, v_2, v_3\}, Q_2=\{v_2, v_3 ,v_4\}\}$$ can be paraphrased in Chinese as:

$$V = \{ v_1, v_2, v_3, v_4 \}\;,\; \mathcal{QS} = \{Q_1=\{v_1, v_2, v_3\}, Q_2=\{v_2, v_3 ,v_4\}\}$$

化简为：
$$V = \{ v_1, v_2, v_3, v_4 \}\;,\; \mathcal{QS} = \{Q_1=\{v_1, v_2, v_3\}, Q_2=\{v_2, v_3 ,v_4\}\}$$

假设选择了Q1进程从v1开始，选择了Q2进程从v4开始逆序获取锁进行执行。如果在Q1获取了v2的锁的情况下无法获取v3的锁，同时Q2获取了v3的锁的情况下无法获取v2的锁，那么就会发生永远无法进行的情况，也就是发生了死锁。为了防止这种情况发生，需要通过节点的ID等方式以一定的顺序来进行访问。

通过按照一定的访问顺序获取锁，可以避免死锁的发生。然而，这会大大降低获取锁的效率。为了更高效地操作，还有其他方法可供选择（参考”Theorem 19.8, Principles of Distributed Computing”）。

共识系统有很多种。

作为共识系统，因为只要求“任意选择都有重复”，所以不仅仅是过半数，还可以想出许多其他的共识方案。

发生了许多事情。我将从文本中逐一介绍。

首先复习一下：过半数（Majority）

$$ \mathcal{Majority} = \{ Q \subseteq V\;|\;|Q| = \lfloor n/2\rfloor+1 \}$$

$$ \mathcal{Majority} = \{ Q \subseteq V\;|\;|Q| = \frac{n}{2}+1 \}$$

$$ \mathcal{Majority} = \{ Q \subseteq V\;|\;|Q| = \text{向下取整}(n/2)+1 \}$$

$$ \mathcal{Majority} = \{ Q \subseteq V\;|\;|Q| = \text{取整}(n/2)+1 \}$$

$$ \mathcal{Majority} = \{ Q \subseteq V\;|\;|Q| = \text{下取整}(n/2)+1 \}$$

可能可以选择超过一半的集合，但基于quorum的条件是它们都应该有共同的部分，所以我们只需要考虑一个最小需要四个节点的quorum系统就足够了。

明显的Quorum: 单例模式(Singleton)

$$ \mathcal{Singleton} = \{ \{ v_{\cdot} \} \}$$
$$ \mathcal{Singleton} = \{ \{ v_{\cdot} \} \}$$

这是一个由一个节点组成的Quorum系统。从复制管理的角度来看，无论有多少个节点，都将读操作集中在一个特定的节点上。尽管可能不太有用，但这也是一种完备的Quorum系统。

接下来，将会引入一个有趣的议员制度。

网格

当考虑节点的大小为$V$，满足$|V|=n$为平方数（即$\sqrt{n}$是一个整数）时，节点可以被布置成一个正方形。

因此，我们会按照以下方式选择法定人数（可以考虑从第$i+1$行开始的各种选择）。

$$ \mathcal{Grid} = \{\;\{ (i\text{ row in total})\cup (select\; one\; at\; random\; from\; each\; of\; the\; following\; rows}) \}\;|\; 1 \leq i \leq \sqrt{n}\; \}$$

$$\mathcal{Grid} = \{\;\{ (第i行全部)\cup (随机从第i+1行及以下选择一个)\}\;|\;1 \leq i \leq \sqrt{n}\;\}$$

上面是当固定每一列时得到的情况，下面是当从每一行中选择一个不重复的元素时得到的情况。关键在于取出所有的第i行，在其他的选举机制中，至少会选择到i行中的一个节点，从而满足选举机制的条件。

下面将会提及，$\mathcal{Grid}$ 具有较弱的抗故障性质。下面所述的B-网格是为了解决这个问题而设计的。

B-网格 (B-

B-网格与网格类似，将节点排列成网格状。令$|V|=n=d \cdot h \cdot r$。网格的形状是一个 $h \cdot r$ 行 $d$ 列的长方形。行被分为 $h$ 个组（称为band），每个band有 $r$ 行。每个band内的行被称为minicolumn。

在B-网格中，quorum系统的选择如下所示（参见上图）。

$$ \mathcal{BGrid} = \left\{\; \left\{\text{从整体中选择一个minicolumn}\right\} \cup \left\{\text{从每个minicolumn中选择一个节点，其中只选择第i个band的节点}\right\} \; | \; 1 \leq i \leq h \right\}$$

每个选区都类似于网格的行，覆盖了所有列，而且每个选区都在每个块中具有迷你列，因此一定会有共同部分。

有限投影平面（Finite Projective Plane: FPP）

也有提出了使用具有更高抽象度的几何特性的抽象共识系统的建议。这个系统使用了被称为投影平面的空间。在我们常见的平面中，平行的两条直线无论如何也无法相交，但在投影平面这样的空间中，任意两条直线都具有相交的特性，这是一个神奇的空间。

更具体地说，投影平面可以通过“点的集合”、“线（点的集合）的集合”和它们之间的连接关系来定义，它指的是满足以下三个性质的组合。

• $k^2 + k + 1$個の点と$k^2 + k + 1$個の線を持つ

• 各線は$k+1$個の点をもち、各点は$k+1$個の線に属す

• どの2つの線も一点だけを共有する

異なる2点を含む線はただ一つである

我完全没有亲身体验。让我们在$k=2$时试着理解一下。下图是$k$等级为2时称为”Fano平面”的图形。

在这种情况下，quorum系统是指由线（由三个点组成的集合）组成的集合。即上图中的

• 三角形の各辺

• 各辺の中点と頂点を結ぶ3つの中線

各辺の中点と接する内接円(コレも線です)

不管找哪两条线，都能确保一定有一个点是共享的。

Quorum系统的优缺点(评价标准)。

嗯，我了解到有许多不同的法定人数。从似乎没有用的$\mathcal{Singleton}$，到常用的$\mathcal{Majority}$，还有网格布置和被称为射影平面的复杂一些的选项。

在研究”quorum system”时，已经提出了几种”用于比较quorum system的度量标准”。让我们来确认这些度量标准的定义，并进行比较我们在本文中介绍的quorum system。

负载

从直觉上来说，就是每个节点被访问的频率。定义本身是根据对决策策略$W$对quorum的访问方式而变化的定义。

定义：将$W$作为quorum system $\mathcal{Q}$上的概率密度，则称之为访问策略(access strategy)。$P_W(Q)$表示选择访问策略$W$时访问$Q$的概率。

• $W$によって導かれるノード $v$ のload $l_w(v)$を下記で定義する(含まれるquorumがアクセスされる確率を全部足す)。

• $$

• l_W(v) = \sum_{Q\in\mathcal{Q}, v\in Q} P_W(Q)

• $$

• $W$によって導かれる quorum system $\mathcal{Q}$の load $L_W(\mathcal{Q})$を下記で定義する(平たく言えば一番 load の高いものを全体の load とする)。

• $$

• L_W(\mathcal{Q}) = \max_{v \in V} l_W(i)

• $$

• quorum system $\mathcal{Q}$ のload $L(\mathcal{Q})$を下記で定義する(すべての$W$の中で最小となる load の値)

• $$

• L(\mathcal{Q}) = \min_{W} L_W(\mathcal{Q})

$$

参考: 共识系统的负载下界是$1/\sqrt{n}$。也就是说，无论如何，负载都无法小于这个值。相反，如果能够达到这个负载值，则可以说它在负载方面是最优的。

强韧性

什么是基于法定人数制度的故障容忍度指标？基于法定人数制度的容错性要求是指在法定人数内的所有节点都正常工作。换句话说，如果法定人数内的任何一个节点发生故障，那么多数法定人数和共同部分将不复存在，导致系统无法保证正常运行。弹性度指标定义了当有多少节点停机时，所有法定人数都无法保持正常的健康状态。

定义：拜占庭容错系统 $\mathcal{Q}$ 的弹性 $R(\mathcal{Q})$ 是指满足以下条件的最大 $f$。对于 $V$ 中的任意包含 $f$ 个节点的子集 $F$，至少存在一个与其不相交的拜占庭赞成集。

故障发生的可能性 (The likelihood of failure occurrence)

弹性是指一个节点能够承受多少个停止故障节点。但是现在改为考虑概率。当节点的可靠性为$p$时，Quorum系统的故障概率被定义为任何Quorum内包含停止故障节点的概率。

定义: 具有故障概率$F_p(\mathcal{Q})$的决策系统$\mathcal{Q}$可以通过以下方式定义:

$$
F_p(\mathcal{Q}) = Pr[\forall Q\in\mathcal{Q},\, \exists v\in Q\,s.t. v\text{停止故障}]
$$

在本次介绍的Quoroum System进行对比

让我们使用上述的负载、弹性和故障概率这些指标来比较我们在本节介绍的quorum系统。虽然详细的分析请参考《分布式计算原理》，但总结成表格如下：

Regarding how to read the table, intuitively…

• Load: ノードがどのくらいの頻度でアクセスされるか ➔ 小さいほどよい

• Resilience: どのくらいの故障台数まで耐えられるか ➔ 大きいほどよい

Failure Probability: どのくらいの確率でquorum全体が使えなくなるか ➔ 小さいほどよい

我将分别查看它们。

• Singleton: 1個しかノードを使わないのでダメダメですね。

• Majority: Resilienceがほぼ半数なのでかなり高いです。$n$ が大きくなった時の故障率もほぼ0へ漸近するのですが、Loadが $1/2$ とかなり高めです。

• Grid: Loadは最適。ResilienceもMajorityと比べると$\sqrt{n}$と小さめです。ただし、故障率が$n$が大きくなるに連れて1に近づいてしまうのでNGです。

• B-Grid: Load, ResilienceはGridと同じで、故障率も0へ漸近していくので良さそうです。

FPP: Gridと同じです

根据上述考虑，我认为稍微粗略地来说，如果用◯×修改上面的表格，可能会变成下面这样。这样你就会发现，比多数派更好的法定人数制度也是存在的。

根据这张表，B-Grid看起来很好，但B-Grid的尺寸受到限制，分析中也需要注意节点利用率假设不超过1/3这一点。

就实际应用而言，从这个列表中可以看出，广泛使用Majority的原因是可以很好地理解其重要性（即使负载相对较大，韧性也很重要，同时通过为读写操作分配权重，Majority系统还可以调整读写时的负载）。

其他的Quorum们

这次提到的仲裁系统只是基本的一些。除了这些之外，还有许多不同机制的仲裁系统被提出。

此外，目前的共识系统模型只考虑了停止故障，但在分布式系统中被认为最棘手的拜占庭故障也被研究出了一种具有拜占庭容错性质的拜占庭共识系统。

对于经典的Quorum System而言，必须要求没有任何的交集才能进行。但是，也有一种被称为概率性准则系统（Probabilistic Quorum System）的研究，它允许准则之间以一定的概率进行交集。

请参考相关文献以获取更多信息。(我已经提供了一份包含较新和过去研究成果引用的调查资料)

总结

在NoSQL等开源软件和产品的数据一致性设置中经常听到的关键词是”Quorum”。一开始我简单地将其理解为”多数决/过半数”，但在进一步调查后发现其实非常复杂，理解和提及”Quorum就是多数决”只是冰山一角，更深层次的了解需要了解Quorum System这个系统，同时我也意识到在考虑分布式系统的”操作保证”方面，Quorum是一个非常强大的工具。

学习除过半数之外的Quorum后，与简单明了的过半数多的Quorum相比，虽然负载更重，但在弹性和故障概率上更为优越。此外，在B-Grid中，尽管存在解析上的技术性方面，但从渐近角度来看，它似乎比多数派更好。

如果这篇文章能帮助大家更好地理解”Quorum System”，我会感到非常幸福。

参考资料

• “The Origin of Quorum Systems”, Marko Vukolić, 2010

• “Selected Results from the Latest Decade of Quorum Systems Research”, Michael G. Merideth and Michael K. Reiter, 2010

今回参照したテキスト

Principles of Distributed Computing
Principles of Distributed Computing (Summer 2003)