Quorum机制

Quorum机制是一种简单有效的副本管理机制。

本节首先讨论一种最简单的副本控制规则 write all read one ，在此基础上，放松约束，讨论 quorum。

约定

为了简化讨论，本节先做这样的约定：更新操作（write ）是一系列顺序的过程，通过其他机制确定更新操作的顺序（例如 primary secondary 架构中由 primary 决定顺序），每个更新操作记为 w_i，i 为更新操作单调递增的序号，每个 w_i 执行成功后副本数据 都发生变化，称为不同的数据版本，记作 v_i 。

假设每个副本都保存了历史上所有版本的数据。

Write-all-read-one

Write all read one （简称 WARO ）是一种最简单的副本控制规则，顾名思义即在更新时写所有的副本， 只有在所有的副本上更新成功，才认为更新成功， 从而保证所有的副本一致，这样在读取数据时可以读任一副本上的数据。

假设有一种 magic 的机制，当某次更新操作 w i 一旦在所有 N 个副本上都成功，此时全局都能知道这个信息，此后读取操作将指定读取数据版本为 v i 的数据 ，称在所有 N 个副本上都成功的更新操作为“成功提交的更新操作”，称对应的数据 为“成功提交的数据”。

在 WARO 中，如果某次更新操作 w i 在某个副本上失败，此时该副本的最新的数据只有 v i 1 ，由于 不满足在所有 N 个副本上都成功，则 w i 不是一个“成功提交的更新操作”，此时，虽然其他 N 1 个副本上最新的数据是 v i ，但 v i 不是一个“成功提交的数据”，最新的成功提交的数据只是 v i 1 。

这里需要特别强调的是，在工程实践中，这种magic 的机制往往较难实现或效率较低。

通常实现这种 magic 机制的方式就是将版本号信息存放到某个或某组元数据服务器上。

假如更新操作非常频繁，那么记录更新成功的版本号 v i 的操作 将成为一个关键操作，容易成为瓶颈。

另外，为了实现强一致性，在读取数据的前必须首先读取元数据中的版本号，在大压力下也容易因为元数据服务器的性能造成瓶颈。

可用性

分析一下WARO 的可用性 。

由于更新操作需要在所有的 N 个 副本上都成功，更新操作才能成功，所以一旦有一个副本异常，更新操作失败，更新服务不可用。

对于更新服务，虽然有 N 个副本，但系统无法容忍任何一个副本异常。

另一方面， N 个副本中只要有一个副本正常，系统就可以提供读服务。

对于读服务而言，当有 N 个副本时，系统可以容忍 N 1 个副本异常。

从上述分析可以发现 WARO 读服务的可用性较高，但更新服务的可用性不高，甚至虽然使用了副本，但更新服务的可用性等效于没有副本。

Quorum定义

WARO 牺牲了更新服务的可用性，最大程度的增强读服务的可用性。

下面将 WARO 的条件进 行松弛，从 而使得可以在读写服务可用性之间做折中，得出 Quorum 机制。

在 Quorum 机制下，当某次更新操作 w i 一旦在所有 N 个副本中的 W 个副本上都成功，则就称该更新操作为“成功提交的更新操作”，称对应的数据为“成功提交的数据” 。

令 R > N - W ，由于更新操作 w i 仅在 W 个副本上成功，所以 在读取数据时，最多 需要读取 R 个副本则一定能读到 w i 更新后的数据 v i 。

如果某次更新 w i 在 W 个副本上成功，由于 W+R>N ，任意 R 个副本组成的集合一定与成功的 W 个副本组成的集合有交集，所以读取 R 个副本一定能读到 w i 更新后的数据 v i 。

例子

某系统有 5 个副本， W=3 R=3 ，最初 5 个副本的数据一致，都是 v 1 某次更新操作w 2 在前 3 副本上成功，副本情况变成 (v2, v2, v2, v1, v1)。

此时 任意 3 个副本组成的集合中一定包括 v2。

在上述定义中，令 W=N R=1 ，就得到 WARO ，即 WARO 是 Quorum 机制的一种特例 。

可用性

与分析WARO 相似，分析 Quorum 机制的可用性。

限制 Quorum 参数为 W+R=N+1 。

由于更新操作需要在 W 个副本上都成功，更新操作才能成功，所以一旦 N-W+1 个副本异常，更新操作始终无法在 W 个副本上成功，更新服务不可用。

另一方面，一旦 N-R+1 个副本异常，则无法保证一定可以读到与 W 个副本有交集的副本集合，则读服务的 一致性 下降。

这里再次强调：仅仅依赖quorum 机制是无法保证强一致性的。

因为仅有 quorum 机制时无法确定最新已成功提交的版本号，除非将最新已提交的版本号作为元数据由特定的元数据服务器或元数据集群管理，否则很难确定最新成功提交的版本号。

在下一节中，将讨论在哪些情况下，可以仅仅通过 quorum 机制来确定最新成功提交的版本号。

Quorum 机制的三个系统参数 N 、 W 、 R 控制了系统的可用性，也是系统对用户的服务承诺：数据最多有 N 个副本，但数据更新成功 W 个副本即返回用户成功。

对于一致性要求较高的 Quorum 系统，系统还应该承诺任何时候不读取未成功提交的数据，即读取到的数据都是曾经在 W 个副本上成功的数据。

读取最新成功提交的数据

上节中，假设有某种 magic 的机制使得读取者知道当前已提交的数据版本号。

本节取消这种假设，分析在 Quorum 机制下，如何始终读取成功提交的数据，以及如何确定最新的已提交的数据。

Quorum 机制只需成功更新 N 个副本中的 W 个，在读取 R 个副本时，一定可以读到最新的成功提交的数据。

但由于有不成功的更新情况存在，仅仅读取 R 个副本 却不一定能确定哪个版本的数据是最新的已提交的数据。

如何确定最新的提交数据？

对于一个强一致性系统，应该始终读取返回最新的成功提交的数据，在 quorum 机制下，要达到这一目的需要对读取条件做进一步加强。

（1）限制提交的更新操作必须严格递增，即只有在前一个更新操作成功提交后才可以提交后一个更新操作，从而成功提交的数据版本号必须是连续增加的。

（2）读取 R 个副本，对于 R 个副本中版本号最高的数据，

2.1 若已存在 W 个，则该数据为最新的成功提交的数据

2.2 若存在个数据少于 W 个， 假设为 X 个， 则继续读取其他副本，直若成功读取到 W 个该版本的副本，则该数据为最新的成功提交的数据；如果在所有副本中该数据的个数肯定不满足 W 个，则 R 中版本号第二大的为最新的成功提交的副本。

ps: 这些约定，其实只是为了保证读到最新的提交数据。

可以看出，在单纯使用 Quorum 机制时，若要确定最新的成功提交的版本，最多需要读取 R+(W-R-1) = N 个副本，当出现任一副本异常时，读最新的成功提交的版本这一功能都有可 不可用。

实际工程中，应该尽量通过其他技术手段，回避通过 Quorum 机制 读取最新的成功提交的版本。

例如，当 quorum 机制与 primary secondary 控制协议结合使用时，可以通过读取 primary 的方式读取到最新的已提交的数据。

基于 Quorum 机制选择primary

本节介绍一种介于 quorum 机制选择 primary 的技术。

基本 primary secondary 协议中， primary 负责进行更新操作的同步工作。

现在基本 primary secondary 协议中引入 quorum 机制，即 primary 成功更新 W 个副本 含 primary 本身 后向用户返回成功。

读取数据时依照一致性要求的不同可以有不同的做法：

如果需要强一致性的立刻读取到最新的成功提交的数据，则可以简单的只 读取 primary 副本上的数据即可，也可以通过上节的方式读取；如果需要会话一致性，则可以根据之前已经读到的数据版本号在各个副本上进行选择性读取；如果只需要弱一致性，则可以选择任意副本读取。

新 primiary 节点的选举

在primary secondary 协议中，当 primary 异常时，需要选择出一个新的 primary ，之后 secondary副本与 primary 同步数据。

通常情况下，选择新的 primary 的工作是由某一中心节点完成的，在引入quorum 机制后，常用的 primary 选择方式与读取数据的方式类似，即中心节点读取 R 个副本，选择R 个副本中版本号最高的副本作为新的 primary 。

新 primary 与至少 W 个副本完成数据同步后作为新的 primary 提供读写服务。

首先， R 个副本中版本号最高的副本一定蕴含了最新的成功提交的数据。

再者，虽然不能确定最高版本号的数是一个成功提交的数据，但新的 primary 在随后与 secondary 同步数据，使得该版本的副本个数达到 W ，从而使得该版本的数据成为成功提交的数据。

ps: 所以，这里只需要直接选择最高版本的作为 primary 即可。

例子

在 N=5 W=3 R=3 的系统中，某时刻副本最大版本号为 (v2, v2, v2, v1, v1)，此时 v1 是系统的最新的成功提交的数据 v2 是一个处于中间状态的未成功提交的数据。

假设此刻 原 primary 副本异常，中心节点进行 primary 切换工作。

这个时候选取新的 primary 就有 2 种场景。

（1）与 3 个副本通讯成功，v1 v1 v1

则直接变为 v1，v2 会被丢弃。

（2）与 3 个副本通讯成功，v2 v1 v1

则会变成 v2，后续会通过副本拷贝的方式，全部都称为 v2。

参考资料

《分布式系统原理》