读《从Paxos到Zookeeper 分布式一致性原理与实践》笔记之Leader选举

待我称王封你为后i 2022-07-13 00:38 121阅读 0赞

# 1.    Zookeeper技术内幕  #

## 1.1. Leader选举 ##

### 1.1.1.  Leader选举概述 ###

**        服务器启动时期的Leader选举**

**        **ZooKeeper的集群规模至少是2台机器，这里我们以3台机器组成的服务器集群为例。在服务器集群初始化阶段，当有一台服务器（我们假设这台机器的myid为1，因此称其为Serve1)启动的时候，它是无法完成Leader选举的，是无法进行Leader选举的。当第二台机器（同样， 我假设这台服务器的myid为2,称其为Server2)也启动后，此时这两台机器巳经能够进行互相通信，每台机器都试图找到一个Leader,于是便进入Leader选举流程。

**        **1.每个Server会发出一个投票。

**        **由于是初始情况，因此对Serve1和Server2来说，都会将自己作为Leader服务器来进行投票，每次投票包含的基本的元素包括：所推举的服务器的myid和ZXID,我们以（myid，ZXID)的形式来表示。因为是初始化阶段，因此无论是Server1还是Server2，都会投给自己，即Server1的投票为（1，0），Server2的投票为（2, 0），然后各自将这个投票发给集群中其他所有机器。

**        **2.  接收来自各个服务器的投票。

**        **每个服务器都会接收来自其他服务器的投票。集群中的每个服务器在接收到投票后，首先会判断该投票的有效性，包括检査是否是本轮投票、是否来自LOOKING 状态的服务器。

**        **3.  处理投票。

**        **在接收到来自其他服务器的投票后，针对每一个投票，服务器都需要将别人的投票和自己的投票进行PK, PK的规则如下。

**        **l  优先检査Epoch，Epoch高的作为Leader。

**        **l  在检査ZXID。ZXID比较大的服务器优先作为Leader。

**        **l  如果Epoch、ZXID相同的话，那么就比较myid。myid比较大的服务器作为Leader服务器。

**        **现在我们来看Server1和Server2实际是如何进行投票处理的。对于Server1来说， 它自己的投票是（1，0)，而接收到的投票为（2, 0)。首先会对比两者的Epoch，我们假设两个的Epoch相同，在比较ZXID， 因为都是0,所以无法决定谁是Leader。接下来会对比两者的myid，很显然，Server1发现接收到的投票中的myid是2,大于自id，于是就会更新自己的投票为（2,0）， 然后重新将投票发出去。而对于Server2来说，不需要更新自己的投票信息。

**        **4.  统计投票。

**        **毎次投票后，服务器都会统计所有投票，判断是否已经有过半的机器接收到相同的投票信息。对于Server1和Server2服务器来说，都统计出集群中已经有两台机器接受了（2, 0）这个投票信息。这里我们需要对“过半”的槪念做一个简单的介绍。所谓“过半”就是指大于集群机器数量的一半，即大于或等于（n/2+1）。 对于这里由3台机器构成的集群，大于等干2台即为达到“过半”要求。

**        **那么，当Server1和Server2都收到相同的投票信息（2, 0）的时候，即认为已经选出了Leader。

**        **5.  改变服务器状态。

**        **一旦确定了Leader,每个服务器就会更新自己的状态：如果是Follower,那么就变更为FOLLOWING,如果是Leader,那么就变更为LEADING。

**        **以3台服务器为例，启动时期的选举过程，如下图所示

![20161217115021439][]

**        服务器运行期间的Leader选举**

**        **在ZooKeeper集群正常运行过程中，一旦选出一个Leader,那么所有服务器的集群角色一般不会再发生变化——也就是说，Leader服务器将一直作为集群的Leader,即使集群中有非Leader集群挂了或是有新机器加入集群也不会影响Leader。但是一旦Leader所在的机器挂了,那么整个见群将暂时无法对外服务，而是进入新一轮的Leader选举。服务器运行期间的Leader选举和启动时期的Leader选举基本过程是一致的。

**        **我们假设当前正在运行的ZooKeeper服务器由3台机器组成，分別是Server1、Server2和Server3,当前的Leader是Server2,假设在某一个瞬间，Leader挂了，这个时候便开始Leader选举。

**        **1.变更状态。

**        **当Leader挂了之后，余下的非Observer服务器都会将自己的服务器状态变更为LOOKING,然后开始进人Leader    选举流程，

**        **2.  每个Server会发出一个投票

**        **在这个过程中，需要生成投票信息（myid，ZXID)。因为是运行期间，因此每个服务器上的ZXID可能不同，假定Server1的ZXID为123,而Server3的ZXID 为122。在第一轮投票中，Server1和Server3都会投自己，即分别产生投票（1，123)和（3，122)，然后各自将这个投票发给集群中所有机器。

**        **3.  接收来自各个服务器的投票。

**        **4.  处理投票。

**        **对于投票的处理，和上面提到的服务器启动期间的处理规则是一致的。在这个例子里面，由于Server1的ZXID为123,Server3的ZXID为122,那么显然，Server1会成为Leader。

**        **5.  统计投票。

**        **6.  改变服务器状态。

### 1.1.2.  Leader选举算法分析 ###

**        **接下来我们就一起深入Leader选举算法，看看Leader选举的技术内幕。

**        进入Leader选举**

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

**        1、**服务器初始化启动。

**        2、**服务器运行期间无法和Leader保持连接。

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

**        1、**集群中本来就巳经存在一个Leader。

**        2、**集群中确实不存在Leader。

**        **我们先来看第一种巳经存在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，8）。

**        **我们假设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选举算法的核心所在。为了便于描述，我们首先定义一些术语。

**        **l  vote\_sid:接收到的投票中所推举Leader服务器的SID。

**        **l  vote\_zxid:接收到的投票中所推举Leader服务器的ZXID。

**        **l  self\_sid:当前服务器自己的SID。

**        **l  self\_zxid:当前服务器自己的ZXID。

**        **每次对于收到的投票的处理，都是一个对（vote\_sid，vote\_zxid)和（self\_sid，self\_zxid) 对比的过程，假设Epoch相同的情况下。

**        **规则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集群的投票变更过程。

![20161217115209495][]

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

**        **对干Server3来说，它接收到了（4, 8）和（5, 8）两个投票，对比后，由子自己的ZXID要大于接收到的两个投票，因此不需要做任何变更。

**        **对于Server4来说，它接收到了（3, 9）和（5, 8）两个投票，对比后，由于（3, 9）这个投票的ZXID大于自己，因此需要变更投票为（3, 9）,然后继续将这个投票发送给另外两台机器。

**        **同样，对TServer5来说，它接收到了（3, 9）和（4, 8）两个投票，对比后，由于（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。

### 1.1.3.  Leader选举的实现细节 ###

**        **Leader选举的流程概要:

![20161217115255599][]

**        **Leader选举算法实现的流程示意图：

![20161217115519605][]

[20161217115021439]: /images/20220713/182119daeefa4059a11d883ad460eb51.png
[20161217115209495]: /images/20220713/d2512bd96dcb4b5481cef37e4b0eb0cd.png
[20161217115255599]: /images/20220713/88bd950d2d204a238912e692c774f2b1.png
[20161217115519605]: /images/20220713/18c9b4bfaa594b62aa1d735d772c958f.png