Leader选举

概述

在Zookeeper集群正常运行期间，一旦选举出Leader，所有服务器的集群状态一般不会发生改变，即使是新机器加入、非Leader机器挂了，也不会影响Leader。但是一旦Leader挂了，那么整个集群将暂时无法对外服务，而是进入新的一轮Leader选举。服务器运行期间的Leader选举和服务器启动期间的Leader选举基本过程是一致的。

在服务器启动期间，如果超过2台机器启动了，那么这些机器会尝试去选举出一个Leader。Leader用于处理客户端请求。

Leader选举的隐式条件是至少要有2台服务器。

服务器启动时期的Leader选举

下面我们假设当前有Server1、Server2、Server3 三台机器为例子。在服务器集群初始化节点，有一台机器（假设这台机器myId=1，我们称他为Server1）启动的时候，那么1台机器是无法进行选举的。当第二台机器（myId=2，称为Server2）启动的时候，两台机器试图找出一个Leader，因此进入Leader选举流程，如下：

• 每个Server发出一个投票
  • 每次投票包含的最基本元素，包括：服务器本身的myId和ZXID。我们以（myId，ZXID）来表示。
  • 初始情况，每个服务器都会投自己一票。即Service1的投票为（1，0），Server2的投票为（2，0）。
  • 然后Server1、Server2将各自的投票发给集群中其他机器
• 接收来自各个服务器的投票
  • 每个服务器都会接收来自其他服务器的投票。
  • 在接收到投票的时候，先判断该投票的有效性，包括检查是否本轮投票、是否来自LOOKING状态的服务器。
• 处理投票
  • 服务器需要将别人的投票和自己的投票进行PK。PK规则如下：
    • 优先检查ZXID。ZXID比较大的服务器优先作为Leader
    • 如果ZXID相同，则比较myId，myId比较大的服务器作为Leader服务器
  • 对于Server1来说，它的投票是（1，0），而接收到的投票是（2，0）。根据上述规则，Server2的投票胜出。
  • 由于Server2投票胜出，Server1将自己的投票更新为（2，0），然后重新将投票发出去
  • 对于Server2来说，不需要更新自己的投票信息，只需要再一次向集群中发出上次的投票信息即可。
• 统计投票
  • 每次投票后，服务器都会统计是否有过半机器收到相同的投票。对于Server1和Server2来说，都统计出集群中已经有2台机器接受了（2，0）这个投票信息。即认为已经选举出Leader了（Server2为Leader）
• 改变服务器状态
  • 一旦确定了Leader，每台服务器都将更新自己的状态。如果是Follower，那么就变更为FOLLOWING状态；如果是Leader，则更新为LEADING状态。

服务器运行时期的Leader选举

我们假设正在运行的Zookeeper集群由3台机器组成，分别为Server1、Server2、Server3。当前Leader是Server2。假设某一瞬间，Leader挂了，那么开始Leader选举：

• 变更状态：
  • 所有的机器状态变更为LOOKING（寻找Leader状态），然后开始进入Leader选举流程
• 每个Server会发出一个投票
  • 每个Server会生成一个投票，投票信息为（myId，ZXID）。因为是运行时，所以每台服务器上的ZXID可能不同，我们假定Server1的ZXID为123，Server3的ZXID为122。
  • 在第一轮投票中，每个Server都会投票给自己，即Server1产生投票（1，123），Server3产生投票（3，122）。然后各自将这个投票发送给集群中所有机器
• 接收来自各个服务器的投票
• 处理投票
  • 投票的PK和上面规则一样，显然Server1会成为Leader。
• 统计投票
• 改变服务器状态

算法分析

首选介绍一些专业术语

术语解释

SID：服务器ID。是一个数字，用来唯一标识Zookeeper集群中的一台机器。

ZXID：事务ID。用来唯一标识一次服务器状态变更。在某一时刻，集群中每台机器的ZXID值不一定完全一致。

Vote：投票。通过投票选出Leader。为（myId，ZXID）的形式

Quorum：指Zookeeper集群中过半的机器数。如果集群总机器数是n，那么quorum=（2/n）+ 1;

下面开始算法分析：

进入Leader选举

当Zookeeper集群中一台服务器出现下面2种情况之一时，就会进入Leader选举：

• 服务器初始化启动
• 服务器无法和Leader保持连接

当一台机器进入Leader选举流程时，当前集群也可能处于以下2种状态：

• 集群中本来就已经存在一个Leader
  • 会被告知Leader信息，当前机器仅仅需要和Leader服务器建立起连接，进行同步状态
• 集群中确实不存在Leader

第一次投票

当集群中不存在Leader的时候，所有机器都试图去寻找一个Leader，这种寻找Leader的状态称为“LOCKING”。

当一台机器处于LOCKING状态，它就会向其他机器发送消息，我们称这个消息为“投票”。

这个投票消息中包含了2个最基本的信息：所推举的服务器的SID和ZXID，分别代表了被推举服务器的唯一标识和事务ID。

变更投票

集群中每台机器发出投票之后，也会收到其他机器发来的投票。每台机器会根据规则，处理其他机器的投票，并以此决定是否需要变更自己的投票。（变更规则在《概述》里面讲了。）

然后把投票再一次发出去。

确定Leader

经过第二次投票以后，集群中所有机器收到其他机器的投票，然后开始统计投票。如果一台机器收到过半的投票，那么该机器就称为Leader。

小结

简单来说，哪台机器上的数据越新，越有可能成为Leader。原因很简单，数据越新，那么该机器的ZXID越大，越能够保证数据的恢复，不丢失。

实现细节

本节讲述FastLeaderElection的实现。

服务器状态

LOOKING：寻找Leader状态。当服务器处于该状态时，它会认为当前集群中没有Leader，因此需要进入Leader选举流程。

FOLLOWING：跟随者状态。表明当前服务器的状态是跟随者（Follower）

LEADING：领导者状态。表明当前服务器是领导者。

Observing：观察者状态，表明当前服务器是观察者

投票数据结构

QuorumCnxManager

在Leader选举过程中，QuorumCnxManager负责各个机器之间的网络通讯。

QuorumCnxManager内部维护了一个消息队列。用于保存接收到的、待发送的消息。除了接收队列以外，所有队列都按SID分组形成队列集合。举个例子，假设集群中除了当前机器以外，还有4台机器，那么就会为这4台机器分别创建一个发送队列，互不干扰。

为了能够互相投票，Zookeeper集群中所有机器都必须要两两建立起网络连接。QuorumCnxManager启动的时候，会去监听Leader选举的通讯端口。为了避免2台机器之间重复建立TCP连接，Zookeeper规定2台机器之间，只有SID大的机器能够主动发起连接，否则断开连接。如果当前服务器发送自己的SID更大，那么就会断开当前连接，然后主动去和其他服务器连接。

###FastLeaderElection

FastLeaderElection是选举算法的核心部分，首先我们约定几个概念：

• 内部投票：服务器自身的投票
• 外部投票：其他服务器发来的投票
• 选举轮次：Leader选举的轮次，称为logicalclock
• PK：内部投票和外部投票进行对比，确定是否需要变更内部投票

选票管理

算法核心

• 自增选举轮次
  • Zookeeper规定了所有投票必须在同一选举轮次中，才有效。
    • Zookeeper在开始新一轮投票时，会将logicallock进行自增。（这样子做是为了避免之前选票的干扰）
• 初始化选票
  • 每个服务器都将自己选举为Leader
• 发送初始化选票
• 接收外部选票
• 判断选举轮次
  • 外部投票的选举轮次大于内部投票
    • 发现自己的投票轮次落后了，那么立即更新自己的选举轮次，清空所有已经收到的投票，然后使用初始化投票来PK以确定是否变更内部投票。最终再将内部投票发送出去
  • 外部投票轮次小于内部投票
    • 服务器直接忽略该外部投票。重新返回接收外部选票的步骤
  • 外部投票和内部投票一致，那么进入PK步骤
• 选票PK
• 变更投票
• 选票归档
  • 将收到的外部投票放入到选票集合。按服务器SID来区分
• 统计投票
• 更新服务器状态

参考

https://blog.****.net/weixin_41098980/article/details/80109789

《Paxos到Zookeeper 分布式一致性原理与实践》