Zookeeper Leader选举算法及选举过程

喜欢ヅ旅行 2022-09-04 07:51 263阅读 0赞

谈zk的选举过程之前，我们必须先了解下zk支持哪些选举算法。

## zk选举算法 ##

在ZooKeeper中，提供了三种Leader选举的算法，分别是

> 1.  LeaderElection
> 2.  UDP版本的FastLeaderElection
> 3.  TCP版本的FastLeaderElection

可以通过在配置文件**zoo.cfg**中使用**electionAlg属性来指定**，分别使用数字**0~3**来表示。

>  *  **0**\-代表LeaderElection，这是一种纯UDP实现的Leader选举算法
>  *  **1**\-代表UDP版本的FastLeaderElection，并且是非授权模式
>  *  **2**\-也代表UDP版本的FastLeaderElection，但使用授权模式
>  *  **3**\-代表TCP版本的FastLeaderElection

值得一提的，是从3.4.0版本开始，ZooKeeper**废弃了0、1、2这三种Leader选举算法**，只保留了3-TCP版本的FastLeaderElection选举算法。

## 重要参数 ##

在分析选举原理前，先介绍几个重要的参数。

**1、服务器 ID(myid)**：编号越大在选举算法中权重越大

>         每个Zookeeper服务器，都需要在数据文件夹下创建一个名为myid的文件，该文件包含整个Zookeeper集群唯一的ID（整数）。例如某Zookeeper集群包含三台服务器，hostname分别为zoo1、zoo2和zoo3，其myid分别为1、2和3，则在配置文件中其ID与hostname必须一一对应，如下所示。在该配置文件中，`server.`后面的数据即为myid
> 
> server.1=zoo1:2888:3888
> 
> server.2=zoo2:2888:3888
> 
> server.3=zoo3:2888:3888

**2、事务 ID(zxid)**：值越大说明数据越新，权重越大

>         类似于RDBMS中的事务ID，用于标识一次更新操作的Proposal ID。为了保证顺序性，该zxid必须单调递增。因此Zookeeper使用一个64位的数来表示，高32位是Leader的epoch，从1开始，每次选出新的Leader，epoch加一。低32位为该epoch内的序号，每次epoch变化，都将低32位的序号重置。这样保证了zkid的全局递增性。

**3、逻辑时钟(epoch-logicalclock)**：同一轮投票过程中的逻辑时钟值是相同的，每投完一次值会增加

## **zk服务器状态** ##

*  ***LOOKING*** 不确定Leader状态。该状态下的服务器认为当前集群中没有Leader，会发起Leader选举
 *  ***FOLLOWING*** 跟随者状态。表明当前服务器角色是Follower，并且它知道Leader是谁
 *  ***LEADING*** 领导者状态。表明当前服务器角色是Leader，它会维护与Follower间的心跳
 *  ***OBSERVING*** 观察者状态。表明当前服务器角色是Observer，与Folower唯一的不同在于不参与选举，也不参与集群写操作时的投票

## **选票数据结构** ##

每个服务器在进行领导选举时，会发送如下关键信息

*  *logicClock* 每个服务器会维护一个自增的整数，名为logicClock，它表示这是该服务器发起的第多少轮投票
 *  *state* 当前服务器的状态
 *  *id* 当前服务器的myid
 *  *zxid* 当前服务器上所保存的数据的最大zxid

**服务器自己的投票叫：（self\_id,self\_zxid），收到的票叫(vote\_id,vote\_zxid)**

每次对收到的投票的处理，都是对(vote\_sid, vote\_zxid)和(self\_sid, self\_zxid)对比的过程。

规则一：如果vote\_zxid大于self\_zxid，就认可当前收到的投票，并再次将该投票发送出去。

规则二：如果vote\_zxid小于self\_zxid，那么坚持自己的投票，不做任何变更。

规则三：如果vote\_zxid等于self\_zxid，那么就对比两者的SID，如果vote\_sid大于self\_sid，那么就认可当前收到的投票，并再次将该投票发送出去。

规则四：如果vote\_zxid等于self\_zxid，并且vote\_sid小于self\_sid，那么坚持自己的投票，不做任何变更。

## **zk选举流程简图** ##

![1de38c09771e273196b8dc4be6e699bc.png][]

## 投票流程 ##

***自增选举轮次***  
        Zookeeper规定所有有效的投票都必须在同一轮次中。每个服务器在开始新一轮投票时，会先对自己维护的epoch-logicClock进行自增操作。

***初始化选票***  
        每个服务器在广播自己的选票前，会将自己的**投票箱清空**。该投票箱记录了所收到的选票。例：服务器2投票给服务器3，服务器3投票给服务器1，则服务器1的投票箱为(2, 3), (3, 1), (1, 1)。票箱中只会记录每一投票者的最后一票，如投票者更新自己的选票，则其它服务器收到该新选票后会在自己票箱中更新该服务器的选票。

***发送初始化选票***  
        每个服务器最开始都是通过广播把票投给自己。

***接收外部投票***  
        服务器会尝试从其它服务器获取投票，并记入自己的投票箱内。如果无法获取任何外部投票，则会确认自己是否与集群中其它服务器保持着有效连接。如果是，则再次发送自己的投票；如果否，则马上与之建立连接。

***判断选举轮次***  
收到外部投票后，首先会根据投票信息中所包含的epoch-logicClock来进行不同处理

>  *  **外部投票的logicClock大于自己的logicClock**。说明该服务器的选举轮次**落后**于其它服务器的选举轮次，立即清空自己的投票箱并将自己的logicClock更新为收到的logicClock，然后再对比自己之前的投票与收到的投票**以确定是否需要变更自己的投票**，最终再次将自己的投票广播出去。
>  *  **外部投票的logicClock小于自己的logicClock**。当前服务器直接**忽略该投票**，继续处理下一个投票。
>  *  **外部投票的logickClock与自己的相等**。当时进行**选票PK**。

***选票PK***  
选票PK是基于(self\_id, self\_zxid)与(vote\_id, vote\_zxid)的对比

>  *  外部投票的logicClock大于自己的logicClock，则将自己的logicClock及自己的选票的logicClock变更为收到的logicClock，然后再对比自己之前的投票与收到的投票**以确定是否需要变更自己的投票**，最终再次将自己的投票广播出去。
>  *  若logicClock一致，则对比二者的zxid，**若外部投票的vote\_zxid比较大，则将自己票中的self\_zxid与self\_myid更新为收到的票中的vote\_zxid与vote\_myid并广播出去**，另外将收到的票及自己更新后的票放入自己的票箱。如果票箱内已存在(self\_myid, self\_zxid)相同的选票，则直接覆盖
>  *  若二者zxid一致，则比较二者的myid，若外部投票的vote\_myid比较大，**则将自己票中的self\_zxid与self\_myid更新为收到的票中的vote\_zxid与vote\_myid并广播出去**，另外将收到的票及自己更新后的票放入自己的票箱

***统计选票***  
如果已经确定有过半服务器认可了自己的投票（可能是更新后的投票），则终止投票。否则继续接收其它服务器的投票。

***更新服务器状态***  
投票终止后，服务器开始更新自身状态。若过半的票投给了自己，则将自己的服务器状态更新为LEADING，否则将自己的状态更新为FOLLOWING

zookeeper 的 leader 选举存在两个阶段，一个是**服务器启动时 leader 选举**，另一个是**运行过程中 leader 服务器宕机**。

### 1、服务器启动时的 leader 选举 ###

每个节点启动的时候都 LOOKING 观望状态，接下来就开始进行选举主流程。这里选取三台机器组成的集群为例。第一台服务器 server1启动时，无法进行 leader 选举，当第二台服务器 server2 启动时，两台机器可以相互通信，进入 leader 选举过程。

*  （1）每台 server 发出一个投票，由于是初始情况，server1 和 server2 都将自己作为 leader 服务器进行投票，每次投票包含所推举的服务器myid、zxid、epoch，使用（myid，zxid）表示，此时 server1 投票为（1,0），server2 投票为（2,0），然后将各自投票发送给集群中其他机器。
 *  （2）接收来自各个服务器的投票。集群中的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票（epoch）、是否来自 LOOKING 状态的服务器。
 *  （3）分别处理投票。针对每一次投票，服务器都需要将其他服务器的投票和自己的投票进行对比，对比规则如下：
    
     *  a. 优先比较 epoch
     *  b. **检查 zxid，zxid 比较大的服务器优先作为 leader**
     *  c. **如果 zxid 相同，那么就比较 myid，myid 较大的服务器作为 leader 服务器**
 *  （4）统计投票。**每次投票后，服务器统计投票信息，判断是都有过半机器接收到相同的投票信息**。server1、server2 都统计出集群中有两台机器接受了（2,0）的投票信息，此时已经选出了 server2 为 leader 节点。

> 不是有三台server吗？怎么server2就被确定为leader？
> 
> 首先server1、server2、server3部署的时候肯定有先后顺序的，不可能同时启动。当server1、server2依次启动后，server3还未启动，这时候server1收到了server2投票信息（2,0），依据上述对比规则，server1接受了server2的投票，更新了自己的投票为（2,0），并把票再次投给别的服务器，因为每次投票后，服务器就会统计投票信息，有过半票数，则成为leader。此时server3并未启动，但是server2已经有两票，所以server就成为leader。

*  （5）改变服务器状态。一旦确定了 leader，每个服务器响应更新自己的状态，如果是 follower，那么就变更为 FOLLOWING，如果是 Leader，变更为 LEADING。此时 server3继续启动，直接加入变更自己为 FOLLOWING。

### 2、运行过程中的 leader 选举 ###

当集群中 l**eader 服务器出现宕机或者不可用**情况时，整个集群无法对外提供服务，进入新一轮的 leader 选举。

*  （1）变更状态。leader 挂后，其他非 Oberver服务器将自身服务器状态变更为 LOOKING。
 *  （2）每个 server 发出一个投票。在运行期间，每个服务器上 zxid 可能不同。
 *  （3）处理投票。规则同启动过程。
 *  （4）统计投票。与启动过程相同。
 *  （5）改变服务器状态。与启动过程相同。

[1de38c09771e273196b8dc4be6e699bc.png]: /images/20220829/3554cf3041594d1ab202af7cc31fd682.png