Zooker选举算法

Zookeeper具体选举算法

1. Leader选举算法

可通过electionAlg配置项设置Zookeeper用于领导选举的算法。

到3.4.10版本为止，可选项有

• 0 基于UDP的LeaderElection
• 1 基于UDP的FastLeaderElection
• 2 基于UDP和认证的FastLeaderElection
• 3 基于TCP的FastLeaderElection

在3.4.10版本中，默认值为3，也即基于TCP的FastLeaderElection。另外三种算法已经被弃用，并且有计划在之后的版本中将它们彻底删除而不再支持。

2. FastLeaderElection

2.1 服务器状态

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

2.2 选票数据结构

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

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

2.3 投票流程

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

初始化选票 每个服务器在广播自己的选票前，会将自己的投票箱清空。该投票箱记录了所收到的选票。

例：服务器2投票给服务器3，服务器3投票给服务器1，则服务器1的投票箱为(2, 3), (3, 1), (1, 1)。票箱中只会记录每一投票者的最后一票，如投票者更新自己的选票，则其它服务器收到该新选票后会在自己票箱中更新该服务器的选票。

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

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

判断选举轮次 收到外部投票后，首先会根据投票信息中所包含的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一致，则对比二者的vote_zxid，若外部投票的vote_zxid比较大，则将自己的票中的vote_zxid与vote_myid更新为收到的票中的vote_zxid与vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱。如果票箱内已存在(self_myid, self_zxid)相同的选票，则直接覆盖
• 若二者vote_zxid一致，则比较二者的vote_myid，若外部投票的vote_myid比较大，则将自己的票中的vote_myid更新为收到的票中的vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱

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

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

3. 几种领导选举场景

3.1 集群启动领导选举

• 集群刚刚启动，所有的LogicClock都为1，zxid为0
• 服务器初始化以后，都将票投给自己
• 图上(1, 1, 0)解释，
  • 第一位选票的服务器的logicClock
  • 第二位被推荐的服务器的myid
  • 推荐的服务器的最大的zxid
  • 由于该步骤中所有选票都投给自己，所以第二位的myid即是自己的myid，第三位的zxid即是自己的zxid。

• Server1收到Server2的选票（1, 2, 0）（1, 3, 0），由于所有的logicClock都相等，所有的zxid都相等，根据选举原则，应该将自己的选票按照服务器3的选票更新为（1, 3, 0），并将自己的票箱全部清空，再将服务器3的选票与自己的选票存入自己的票箱，接着将自己更新后的选票广播出去。此时服务器1票箱内的选票为(1, 3)，(3, 3)。
• Server2收到Server3的选票后也将自己的选票更新为（1, 3, 0）并存入票箱然后广播。此时Server2票箱内的选票为(2, 3)，(3, ,3)。
• Server3根据上述规则，无须更新选票，自身的票箱内选票仍为（3, 3）
• 由于三个服务器最新选票都相同，最后三者的票箱内都包含三张投给服务器3的选票。

• 三个Server一致认为此时Server3应该是Leader。因此Server1和2都进入FOLLOWING状态，而Server3进入LEADING状态。之后Leader发起并维护与Follower间的心跳。

3.2 Follower重启

Follower重启，或者发生网络分区后找不到Leader，会进入LOOKING状态并发起新的一轮投票。

• Server3收到Server1的投票后，将自己的状态LEADING以及选票返回给Server1。Server2收到Server1的投票后，将自己的状态FOLLOWING及选票返回给Server1。

• Server1知道Server3是Leader，并且通过Server2与Server3的选票可以确定Server3确实得到了超过半数的选票。因此服务器1进入FOLLOWING状态

3.3 Leader重启

Leader（服务器3）宕机后，Follower（服务器1和2）发现Leader不工作了，因此进入LOOKING状态并发起新的一轮投票，并且都将票投给自己。

• 因此进入LOOKING状态并发起新的一轮投票，并且都将票投给自己
• 服务器1和2根据外部投票确定是否要更新自身的选票。这里有两种情况
  • 服务器1和2的zxid相同。例如在服务器3宕机前服务器1与2完全与之同步。此时选票的更新主要取决于myid的大小
  • 服务器1和2的zxid不同。在旧Leader宕机之前，其所主导的写操作，只需过半服务器确认即可，而不需所有服务器确认。换句话说，服务器1和2可能一个与旧Leader同步（即zxid与之相同）另一个不同步（即zxid比之小）。此时选票的更新主要取决于谁的zxid较大
• 服务器1的zxid为11，而服务器2的zxid为10，因此服务器2将自身选票更新为（3, 1, 11）

• 经过上一步选票更新后，Server1与Server12均将选票投给Server11，因此Server12成为Follower，而Server11成为新的Leader并维护与Server2的心跳。
• 当旧的Leader回复以后，重复Follower的步骤

参考文章

• 技术世界