分布式系统Quorum机制

简介

分布式系统由于不同节点的存在，分区(Part)不可避免。为了保证数据的可用性(A)，一般可采用多副本，因此存在副本一致性(Consistency)的问题。

最简单保证副本一致性的方式就是WARO(Write All Read One)。WARO存在极大的写放大问题，Quorum机制是

WARO牺牲了更新服务的可用性，最大程度地增强了读服务的可用性。而Quorum就是更新服务和读服务之间进行一个折衷。

Quorum机制是“抽屉原理”的一个应用。

定义如下：假设有N个副本，更新操作wi 在W个副本中更新成功之后，才认为此次更新操作wi 成功。称成功提交的更新操作对应的数据为：“成功提交的数据”。对于读操作而言，至少需要读R个副本才能读到此次更新的数据。**其中，W+R>N ，即W和R有重叠。

一般，W+R=N+1

假设系统中有5个副本，W=3，R=3。初始时数据为(V1，V1，V1，V1，V1）--成功提交的版本号为1

当某次更新操作在3个副本上成功后，就认为此次更新操作成功。数据变成：(V2，V2，V2，V1，V1）--成功提交后，版本号变成2

因此，最多只需要读3个副本，一定能够读到V2(此次更新成功的数据)。而在后台，可对剩余的V1 同步到V2，而不需要让Client知道。

二，Quorum机制分析

①Quorum机制无法保证强一致性

所谓强一致性就是：任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据。强一致性是程度最高的一致性要求，也是实践中最难以实现的一致性。

 因为，仅仅通过Quorum机制无法确定最新已经成功提交的版本号。

比如，上面的V2 成功提交后（已经写入W=3份），尽管读取3个副本时一定能读到V2，如果刚好读到的是(V2，V2，V2），则此次读取的数据是最新成功提交的数据，因为W=3，而此时刚好读到了3份V2。如果读到的是（V2，V1，V1），则无法确定是一个成功提交的版本，还需要继续再读，直到读到V2的达到3份为止，这时才能确定V2 就是已经成功提交的最新的数据。

1）如何读取最新的数据？---在已经知道最近成功提交的数据版本号的前提下，最多读R个副本就可以读到最新的数据了。

2）如何确定 最高版本号 的数据是一个成功提交的数据？---继续读其他的副本，直到读到的 最高版本号副本 出现了W次。

②基于Quorum机制选择 primary

中心节点(服务器)读取R个副本，选择R个副本中版本号最高的副本作为新的primary。

新选出的primary不能立即提供服务，还需要与至少与W个副本完成同步后，才能提供服务---为了保证Quorum机制的规则：W+R>N

至于如何处理同步过程中冲突的数据，则需要视情况而定。

 比如，(V2，V2，V1，V1，V1），R=3，如果读取的3个副本是：(V1，V1，V1)则高版本的 V2需要丢弃。

如果读取的3个副本是（V2，V1，V1），则低版本的V1需要同步到V2

三，Quorum机制应用实例

HDFS高可用性实现

 HDFS的运行依赖于NameNode，如果NameNode挂了，那么整个HDFS就用不了了，因此就存在单点故障(single point of failure)；其次，如果需要升级或者维护停止NameNode，整个HDFS也用不了。为了解决这个问题，采用了QJM机制(Quorum Journal Manager)实现HDFS的HA（High Availability）。注意，一开始采用的“共享存储”机制，关于共享存储机制的不足，可参考：（还提到了QJM的优点）

In a typical HA cluster, two separate machines are configured as NameNodes. At any point in time, exactly one of the NameNodes is in an Active state, and the other is in a Standby state. The Active NameNode is responsible for all client operations in the cluster, while the Standby is simply acting as a slave,
maintaining enough state to provide a fast failover if necessary.

为了实现HA，需要两台NameNode机器，一台是Active NameNode，负责Client请求。另一台是StandBy NameNode，负责与Active NameNode同步数据，从而快速 failover。

那么，这里就有个问题，StandBy NameNode是如何同步Active NameNode上的数据的呢？主要同步是哪些数据呢？

数据同步就用到了Quorum机制。同步的数据 主要是EditLog。

In order for the Standby node to keep its state synchronized with the Active node, both nodes communicate with a group of separate daemons called “JournalNodes” (JNs).

数据同步用到了一个第三方”集群“：Journal Nodes。Active NameNode 和 StandBy NameNode 都与JournalNodes通信，从而实现同步。

''''''''''''''''''''''''''''''''''

每次 NameNode 写 EditLog 的时候，除了向本地磁盘写入 EditLog 之外，也会并行地向 JournalNode 集群之中的每一个 JournalNode 发送写请求，只要大多数 (majority) 的 JournalNode 节点返回成功就认为向 JournalNode 集群写入 EditLog 成功。如果有 2N+1 台 JournalNode，那么根据大多数的原则，最多可以容忍有 N 台 JournalNode 节点挂掉。

这就是：Quorum机制。每次写入JournalNode的机器数目达到大多数(W)时，就认为本次写操作成功了。

'''''''''''''''''''''''''''''''''

这样，每次对Active NameNode中的元数据进行修改时，都会将该修改写入JournalNode集群的大多数机器中，才认为此次修改成功。

当Active NameNode宕机时，StandBy NameNode 向JournalNode同步EditLog，从而保证了HA。

Active NameNode 向 JournalNode 集群提交 EditLog 是同步的 但 Standby NameNode 采用的是定时从 JournalNode 集群上同步 EditLog 的方式，那么 Standby NameNode 内存中文件系统镜像有很大的可能是落后于 Active NameNode 的， 所以 Standby NameNode 在转换为 Active NameNode 的时候需要把落后的 EditLog 补上来。

具体的同步过程可参考： Hadoop NameNode 高可用 (High Availability) 实现解析

In order to provide a fast failover, it is also necessary that the Standby node have up-to-date information regarding the location of blocks in the cluster. In order to achieve this, the DataNodes are configured with the location of both NameNodes, and send block location information and heartbeats to both.

此外，为了实现快速failover，StandBy NameNode 需要实时地与各个DataNode通信以获得每个数据块的地址信息。为咐要这样？

因为：每个数据块的地址信息不属于“元信息”，并没有保存在 FsImage、CheckPoint...，这是因为地址信息变化比较大。比如说，一台DataNode下线了，其上面的数据块地址信息就全无效了，而且为了达到指定的数据块“复制因子”，还需要在其他机器上复制该数据块。

而快速failover，是指Active NameNode宕机后，StandBy NameNode立即就能提供服务。因此，DataNode也需要实时向 StandBy NameNode 发送 block report

另外，还有手动failover 和 自动 failover，自动failover需要Zookeeper的支持，具体可参考官网：HDFS High Availability Using the Quorum Journal Manager

如何避免“Split Brain”(脑裂)问题？

Split Brain 是指在同一时刻有两个认为自己处于 Active 状态的 NameNode。

when a NameNode sends any message (or remote procedure call) to a JournalNode, it includes its epoch number as part of the request. Whenever the JournalNode receives such a message, it compares the epoch number against a locally stored value called the promised epoch. If the request is coming from a newer epoch, then it records that new epoch as its promised epoch. If instead the request is coming from an older epoch, then it rejects the request. This simple policy avoids split-brain

简单地理解如下：每个NameNode 与 JournalNodes通信时，需要带一个 epoch numbers(epoch numbers 是唯一的且只增不减)。而每个JournalNode 都有一个本地的promised epoch。拥有值大的epoch numbers 的NameNode会使得JournalNode提升自己的 promised epoch，从而占大多数，而epoch numbers较小的那个NameNode就成了少数派(Paxos协议思想)。

从而epoch number值大的NameNode才是真正的Active NameNode，拥有写JournalNode的权限。注意：（任何时刻只允许一个NameNode拥有写JournalNode权限）

when using the Quorum Journal Manager, only one NameNode will ever be allowed to write to the JournalNodes, so there is no potential for corrupting the file system metadata from a split-brain scenario.

具体实现可参考：（还提到了QJM的优点）