详解zookeeper的leader选举算法_zk选举leader 节点是相互广播还是顺序广播

zookeeper是一个基于观察者模式设计的分布式服务管理框架，负责管理和存储数据，接收观察者的注册。存储结构类似于linux目录结构，默认每个节点最多能存储1M数据，因此并不能当做平常的RDB使用。zookeeper做为一个中间层，使得客户端和服务端的耦合性很小，可被应用于统一命名服务、统一配置管理、统一集群管理、服务器节点动态上下线、软负载均衡等场景。

特点

感觉zookeeper本身就是为了集群模式而生，脱离了集群的zookeeper就没有什么存在的意义。zookeeper集群包含1个leader和多个flower（类似于master/slaver），leader负责数据更新时投票的发起和系统状态的更新。而follower用于接收客户端请求并向客户端返回结果，同时在leader选举中参与投票。集群中只要有半数以上的节点存活，集群就能正常服务。

另外，对于数据来说zookeeper集群是全局一致性的，每个节点保存一份相同的数据副本（leader会将数据广播到每一个flower），因此在一定时间范围内，客户端能读取到最新数据。数据更新请求按顺序执行，来自同一个客户端的更新请求按其顺序依次执行，数据更新也是一致性的，一次数据更新，要么成功，要么失败。

以下选举算法分析基于TCP版本的FastLeaderElection选举说明，zookeeper总共有4种leader选举算法，但从3.4.0版本之后只保留了这种选举算法。

术语解释

SID：服务器ID

SID是一个数字，用来标识一台zookeeper集群中的机器，每台机器不能重复，和myid的值一致。

ZXID：事务ID

ZXID是一个事务ID，用来唯一标识一次服务器状态变更的时间戳。在某一个时刻，集群中每台机器的ZXID值不一定全都一致，这和zookeeper服务器对于客户端“更新请求”的处理逻辑有关。

Vote：投票

Leader选举，顾名思义必须通过投票来实现。当集群中的机器发现自己无法检测到Leader机器的时候，就会开始尝试进行投票。

Quorum：过半机器数

这是整个Leader选举算法中最重要的一个术语，我们可以把这个术语理解为是一个量词，指的是zookeeper集群中过半的机器数，如果集群中总的机器数是n的话，那么可以通过下面这个公式来计算quorum的值：

quorum = (n/2 + 1)

例如，如果集群机器总数是3，那么quorum就是2。

算法分析

当zookeeper集群中的一台服务器出现以下两种情况之一时，就会开始进入Leader选举。

1.服务器初始化启动。
2.服务器运行期间无法和Leader保持连接。

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

1.集群中本来就已经存在一个Leader。
2.集群中确实不存在Leader。

我们首先来看第一种已经存在Leader的情况。这种情况通常是集群中的某一台机器启动比较晚，在他启动之前，集群已经可以正常工作，即已经存在了一台Leader服务器。针对这种情况，当该机器试图去选举Leader的时候，会被告知当前服务器的Leader信息，对于该机器来说，仅仅需要和Leader机器建立连接，并进行状态同步即可。

下面我们重点来看在集群中Leader不存在的情况下，如何进行选举。

开始第一次投票

通常有两种情况会导致集群中不存在Leader，一种情况是在整个服务器刚刚初始化启动时，此时尚未产生一台Leader服务器；另一种情况就是在运行期间当前Leader所在的服务器挂了。无论是哪种情况，此时集群中的所有机器都处于一种试图选举出一个Leader状态，我们把这种状态称为“LOOKING”，意思是说正在寻找Leader。当一台服务器处于LOOKING状态的时候，那么他就会向集群中所有其他机器发送消息，我们称这个消息为“投票”。

在这个投票消息中包含了两个最基本的信息：所推举的服务器的SID和ZXID，分别表示了被推举服务器的唯一标识和事务ID。下文中我们将以“(SID, ZXID)”这样的形式来标识一次投票信息。举例来说，如果当前服务器要推举SID为1、ZXID为8的服务器成为Leader，那么他的这次投票信息可以表示为(1, 9)。

我们假设zookeeper由5台机器组成，SID分别为1、2、3、4和5，ZXID分别为9、9、9、8和8，并且此时SID为2的机器是Leader服务器。某一时刻，1和2所在的机器出现故障，因此集群开始进行Leader选举。

在第一次投票的时候，由于还无法检测到集群中其他机器的状态信息，因此每台机器都是将自己作为被推举的对象来进行投票。于是SID为3、4和5的机器，投票情况分别为：(3, 9)、 (4, 8)和(5, 8)。

变更投票

集群中的每台机器发出自己的投票后，也会接收到来自集群中其他机器的投票。每台机器都会根据一定的规则，来处理收到的其他机器的投票，并以此来决定是否需要变更自己的投票。这个规则也成为了整个Leader选举算法的核心所在。为了便于描述，我们首先定义一些术语。

vote_sid：接收到的投票中所推举Leader服务器的SID。
vote_zxid：接收到的投票中所推举Leader服务器的ZXID。
self_sid：当前服务器自己的SID。
self_zxid：当前服务器自己的ZXID。

每次对于收到的投票的处理，都是一个对（vote_sid, vote_zxid）和（self_sid, self_zxid）对比的过程。投票规则如下：
1：如果vote_zxid大于self_zxid，就认可当前收到的投票，并再次将该投票发送出去。
2：如果vote_zxid小于self_zxid，那么就坚持自己的投票，不做任何变更。
3：如果vote_zxid等于self_zxid，那么就对比两者的SID。如果vote_sid大于self_sid，那么就认可当前接收到的投票，并再次将该投票发送出去。
4：如果vote_zxid等于self_zxid，并且vote_sid小于self_sid，那么同样坚持自己的投票，不做变更。

根据上面这个规则，我们结合下图来分析上面提到的5台机器组成的zookeeper集群的投票变更过程。

每台机器都把投票发出后，同时也会接收到来自另外两台机器的投票。

对于Server3来说，他接收到了(4, 8) 和 (5, 8)两个投票，对比后，由于自己的ZXID要大于接收到的两个投票，因此不需要做任何变更。
对于Server4来说，他接收到了(3, 9) 和 (5, 8)两个投票，对比后，由于(3, 9) 这个投票的ZXID大于自己，因此需要变更投票为(3, 9)，然后继续将这个投票发送给另外两台机器。
同样，对于Server5来说，他接收到了(3, 9) 和 (4, 9)两个投票，对比后，由于(3, 9)这个投票的ZXID大于自己，因此需要变更投票为(3, 9)，然后继续将这个投票发送给另外两台机器。

确定Leader

经过这第二次投票后，集群中的每台机器都会再次受到其他机器的投票，然后开始统计投票，如果一台机器收到了超过半数的相同的投票，那么这个投票对应的SID机器即为Leader。如上图所示的Leader选举例子中，因为zookeeper集群的总机器数为5台，那么：

quorum = (5/2 + 1) = 3

也就是说，只要收到3个或3个以上（含当前服务器自身在内）一致的投票即可。在这里，Server3、Server4和Server5都投票(3, 9)，因此确定了Server3为Leader。

小结

简单的说，通常哪台服务器上的数据越新，那么越有可能成为Leader，原因很简单，数据越新，那么他的ZXID也就越大，也就越能够保证数据的恢复。当然，如果集群中有几个服务器具有相同的ZXID，那么SID较大的那台服务器成为Leader。