Quorum 机制是怎么样的？

分布式系统的设计中会涉及到许多的协议、机制用来解决可靠性问题、数据一致性问题等，Quorum 机制就是其中的一种。我们通过分布式系统中的读写模型来简单介绍它。

分布式系统中的读写模型 　　分布式系统是由多个节点（指代一台服务器、存储设备等）构成，由于网络异常、宕机等节点并不能保证正常工作，特别是在节点数量很大的时候，出现异常状况的节点几乎是肯定的。为了保证系统的正常运行，能够提供可靠的服务，分布式系统中对于数据的存储采用多份数据副本（注：这里的副本并非只用来备份，它可参与提供系统服务）来保证可靠性，也就是其中一个节点上读取数据失败了那么可以转向另外一个存有相同数据副本的节点读取返回给用户。这个过程对于用户来说是透明的。那么随之而来的就会带来数据的副本数据的不一致性，例如：用户提交一次修改后，那么原先保存的副本显然就与当前数据不一致了。解决这个问题最简单的方法 Read Only Write All ，就是在用户提交修改操作后，系统确保存储的数据所有的副本全部完成更新后，再告诉用户操作成功；而读取数据的时候只需要查询其中的一个副本数据返回给用户就行了。 在很少对存储的数据进行修改的情形下（例如存档历史数据供以后分析），这种解决方案很好。如遇到经常需要修改的情形，写操作时延时现象就很明显，加上并发或者连续的执行的话效率就可想而知了。实质，这是由于 Write 和 Read 负载不均衡所致，Read 很轻松，Write 深表压力！

从小学的抽屉原理说起 为什么从抽屉原理说起？一来大家对这个比较熟悉，二来它与Quorum机制有异曲同工的地方。回顾抽屉原理，2个抽屉每个抽屉最多容纳2个苹果，现在有3个苹果无论怎么放，其中的一个抽屉里面会有2个苹果。那么我们把抽屉原理变变型，2个抽屉一个放了2个红苹果，另一个放了2个青苹果，我们取出3个苹果，无论怎么取至少有1个是红苹果，这个理解起来也很简单。我们把红苹果看成更新了的有效数据，青苹果看成未更新的无效数据。便可以看出来，不需要更新全部数据（并非全部是红苹果）我们就可以得到有效数据，当然我们需要读取多个副本完成（取出多个苹果）。这就是Quorum机制的原型，其实质是将Write All 的负载均衡到 Read Only 上。

  简单概括说来就是， Quorum 是一种集合 , l 中任意取集合S,R ，S,R 都存在交集。当然，本文并不打算多讲它的数学定义方面的理解，这里只是提供个信息，看不懂也没事联系到前面的分布式读写模型就能很容易理解这个了。

  回到文章的开头，我们来看看是怎么运用Quorum机制来解决读写模型中读写的负载均衡。其实，关键的是更新多少个数据副本后，使得读取时总能读到有效数据？回想我们的的红苹果，假设总共有 N 个数据副本，其中 k 个已经更新，N-k 个未更新的，那么我们任意读取 N-k+1 个数据的时候就必定至少有1个是属于更新了的k个里面的，也就是 Quorum 的交集，我们只需比较 读取的 N-k+1 中版本最高的那个数据返回给用户就可以得到最新更新的数据了。

  那么对于写模型呢？我也只需要完成 k个副本的更新后，就可以告诉用户操作完成而不需要 Write All 了，当然告诉完用户完成操作后，系统内部还是会慢慢的把剩余的副本更新，这对于用户是透明的。可以看到，我们把 Write 身上的部分负载转移到了Read上，Read读取多个副本，使得Write不会过于劳累，不好的是弱化了分布式系统中的数据一致性。至于转移多少负载比较合适，这个需要根据分布式系统的具体需求中对数据一致性的要求。不过，CAP 理论告诉我们没有完美的方案。 

Quorum机制 苹果抽屉理论只是对它的理解，引用参考文献中对Quorum的定义：

先做这样的约定：更新操作（write）是一系列顺序的过程，通过其他机制 确定更新操作的顺序（例如primary-secondary 架构中由primary 决定顺序），每个更新操作记为wi， i 为更新操作单调递增的序号，每个wi 执行成功后副本数据都发生变化，称为不同的数据版本，记 作vi。假设每个副本都保存了历史上所有版本的数据。

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

由于更新操作需要在所有的N 个副本上都成功，更新操作才能成 功，所以一旦有一个副本异常，更新操作失败，更新服务不可用。对于更新服务，虽然有N 个副本， 但系统无法容忍任何一个副本异常。另一方面，N 个副本中只要有一个副本正常，系统就可以提供 读服务。对于读服务而言，当有N 个副本时，系统可以容忍N-1 个副本异常。 从上述分析可以发现WARO 读服务的可用性较高，但更新服务的可用性不高，甚至虽然使用了 副本，但更新服务的可用性等效于没有副本。

Quorum 定义 在Quorum 机制下，当某次更新操作wi 一旦在所有N 个副本中的W 个副本上都成功，则就称 该更新操作为“成功提交的更新操作”，称对应的数据为“成功提交的数据”。令R>N-W，由于更新 操作wi 仅在W 个副本上成功，所以在读取数据时，最多需要读取R 个副本则一定能读到wi 更新后 的数据vi 。如果某次更新wi 在W 个副本上成功，由于W+R>N，任意R 个副本组成的集合一定与 成功的W个副本组成的集合有交集，所以读取R 个副本一定能读到wi 更新后的数据vi。如图 2-10， Quorum 机制的原理可以文森图表示。

某系统有5 个副本，W=3，R=3，最初5 个副本的数据一致，都是v1，某次更新操作 w2 在前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 个副本上成 功的数据。

读取最新成功提交的数据 Quorum 机制只需成功更新N 个副本中的W 个，在读取R 个副本时，一定可以读到最新的成功 提交的数据。但由于有不成功的更新情况存在，仅仅读取R 个副本却不一定能确定哪个版本的数据 是最新的已提交的数据。对于一个强一致性Quorum 系统，

若存在个数据少于W 个，假设为X 个，则继续读取其他副本，直若成功读取到W 个 该版本的副本，则该数据为最新的成功提交的数据；如果在所有副本中该数据的个数肯定不满 足W 个，则R 中版本号第二大的为最新的成功提交的副本。 例: 在读取到（v2 v1 v1）时，继续读取剩余的副本，若读到剩余两个副本 为（v2 v2）则v2 是最新的已提交的副本；若读到剩余的两个副本为（v2 v1）或（v1 v1）则v1 是最新 成功提交的版本；若读取后续两个副本有任一超时或失败，则无法判断哪个版本是最新的成功提交 的版本。

可以看出，在单纯使用Quorum 机制时，若要确定最新的成功提交的版本，最多需要读取R+ （W-R-1）=N 个副本，当出现任一副本异常时，读最新的成功提交的版本这一功能都有可能不可用。 实际工程中，应该尽量通过其他技术手段，回避通过Quorum 机制读取最新的成功提交的版本。例 如，当quorum 机制与primary-secondary 控制协议结合使用时，可以通过读取primary 的方式读取到 最新的已提交的数据。

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

在primary-secondary 协议中，当primary 异常时，需要选择出一个新的primary，之后secondary 副本与primary 同步数据。通常情况下，选择新的primary 的工作是由某一中心节点完成的，在引入 quorum 机制后，常用的primary 选择方式与读取数据的方式类似，即中心节点读取R 个副本，选择 R 个副本中版本号最高的副本作为新的primary。新primary 与至少W 个副本完成数据同步后作为新 的primary 提供读写服务。首先，R 个副本中版本号最高的副本一定蕴含了最新的成功提交的数据。 再者，虽然不能确定最高版本号的数是一个成功提交的数据，但新的primary 在随后与secondary 同 步数据，使得该版本的副本个数达到W，从而使得该版本的数据成为成功提交的数据。

例：在N=5，W=3，R=3 的系统中，某时刻副本最大版本号为（v2 v2 v1 v1 v1），此时v1 是 系统的最新的成功提交的数据，v2 是一个处于中间状态的未成功提交的数据。假设此刻原primary 副本异常，中心节点进行primary 切换工作。这类“中间态”数据究竟作为“脏数据”被删除，还 是作为新的数据被同步后成为生效的数据，完全取决于这个数据能否参与新primary 的选举。下面 分别分析这两种情况。

第一、如图 2-12，若中心节点与其中3 个副本通信成功，读取到的版本号为（v1 v1 v1），则任 选一个副本作为primary，新primary 以v1 作为最新的成功提交的版本并与其他副本同步，当与第1、 第2 个副本同步数据时，由于第1、第2 个副本版本号大于primary，属于脏数据，可以按照2.2.2.4 节中介绍的处理脏数据的方式解决。实践中，新primary 也有可能与后两个副本完成同步后就提供 数据服务，随后自身版本号也更新到v2，如果系统不能保证之后的v2 与之前的v2 完全一样，则新 primary 在与第1、2 个副本同步数据时不但要比较数据版本号还需要比较更新操作的具体内容是否 一样。

第二、若中心节点与其他3 个副本通信成功，读取到的版本号为（v2 v1 v1），则选取版本号为 v2 的副本作为新的primary，之后，一旦新primary 与其他2 个副本完成数据同步，则符合v2 的副 本个数达到W 个，成为最新的成功提交的副本，新primary 可以提供正常的读写服务。