Zookeeper 选举理论

本章将对 Zookeeper 项目中与选举机制相关的前置知识进行相关介绍，本章是偏向理论知识，本章总结自如下文档。

> 1. The Part-Time Parliament 论文地址： https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf > 2. Paxos Made Simple 论文地址：https://lamport.azurewebsites.net/pubs/paxos-simple.pdf > 3. Implementing Replicated Logs with Paxos 文档地址: https://ongardie.net/static/raft/userstudy/paxos.pdf > 4. Zookeeper 索引文档: https://cwiki.apache.org/confluence/display/ZOOKEEPER/Index

Paxos

Paxos 该算法是由 Leslie Lamport 在 1990 年的 The Part -Time Parliament 论文中提出，这篇论文是一 篇比较晦涩的论文理解起来有较大的难度，在后来原作者进行改良编写了 Paxos Made Simple 论文，这篇论文的理解性起来就相对简单一些。本节对 Paxos 算法的说明还要感谢 Implementing Replicated Logs with Paxos 文档的作者。Paxos 算法分为两类Basic Paxos和Multi Paxos，本节探讨的是 Basic Paxos 并非 Multi Paxos。

1. Basic Paxos：每次有1个或多个节点针对一个变量进行投票，确定变量的值。
2. Multi Paxos：通过一系列Basic Paxos的实例来确定一系列变量的值，

接下来将开始进行 Paxos 算法的分析说明，首先需要明确 Paxos 算法解决的问题是什么，Paxos 算法解决的是在分布式环境中节点对某个值产生共同认知的算法，在分布式环境中存在N个节点（N建议是奇数），通过Paxos算法可以让N个节点对某一个值快速达成一致。

在 Paxos 算法分析过程中需要先对几个固有名词进行介绍。

1. Proposal 提案，它由两部分组成。
   1. Proposal Number 提案编号。
   2. Proposal Value 提案值。
2. Chosen 批准、通过、认可。如果一个提案值被批准，那么在后续 Paxos 算法中都将使用这个批准的值进行交互。

为了方便后续对提案的描述，请允许将提案使用[N,V]的方式表示，N表示提案编号，V表示本次提案的值。

在Paxos算法中设计到三种角色Proposer、Acceptor和Learner，它们的含义如下。

1. Proposer 提案发起方，提案发起方的职责是发起提案到Acceptor中进行处理，可以将提案发起方理解为对某个值提出操作的一方。
2. Acceptor 提案接收方，提案接收方是决策者，会对提案进行投票投票。一个提案得到半数以上的提案接收方接受，就说明该提案被批准（Chosen）。
3. Learner 提案学习方，提案学习方不会参与提案发起，也不会参与提案接收，它只能够从 Proposer 或者 Acceptor 中获取认可的数据（提案批准后的数据）。

通常情况在分布式环境中一个节点可以有如下两种角色的可能。

1. 节点只是Learner。
2. 节点既是Proposer又是Acceptor。

在Paxos算法中还需要满足两个基本要求，安全性（Safety）和活性（Liveness），它们的详细说明如下。

1. 安全性，具体要求如下。
   1. 只有提案中提出的值才可以被选中。
   2. 只有一个提案中的值已经被选中，那么其他参与者必须以这个值进行操作。
2. 活性。
   1. 确保一个值被选中，如果一直没有选中的值那么整个环境将不可用。

关于活性在Implementing Replicated Logs with Paxos文档中使用下图进行表示。

下面对上图进行解释，在分布式环境中存在5个节点S1、S2、S3、S4和S5，在同一时刻S1、S3和S5进行提案接收操作，此时S1和S2都认可值为red，S3和S4都认可值为blue，S5认可值为green，此时可以发现并没有超过半数（N/2+1）的节点数量认可值是red、blue和green中的某一个，因此他违背了Paxos算法中的活性要求。这个现象也可以称之为分票问题（Split Votes），由于一直没有半数的节点确认值应该是哪一个因此会一直重复这个值的确认过程从而导致环境不可用。

为了解决分票问题，是否可以让接受者认可每一个它收的值？对于这个方案在Implementing Replicated Logs with Paxos文档中使用下图进行表示。

在上图中可以发现S3这个节点选中了red和blue，并不是只选中一个值，它违背了安全性。为了解决安全性问题可以引入2阶段协议（2-phase protocol），这个协议定义：当已经认可一个值的时候，后续的值除非与当前认可值相同，否则将全部抛弃。对于这个方案在Implementing Replicated Logs with Paxos文档中使用下图进行表示。

在上图中可以发现S3节点首先认可值为blue，在后续时间段内S3收到消息说改变认可值为red，根据2阶段协议由于此时提案的值red并不是上一个认可值blue因此将其抛弃，认可值依然为blue。需要注意的是在这个方案中会涉及到对提案进行排序，在提案排序时就涉及到排序规则的确定，在Paxos算法中提出排序规则可以采用提案号进行处理，提案号定义：<Round Number,Server Id> ，提案号由两部分组成。

1. Round Number，这是一个自增长的整数，当前节点自己维护。
2. Server Id，这是服务的编号，在Zookeeper中通过zoo.cfg文件的myid属性定义。

上述讲述了在分布式系统中对一个值产生共识的基本逻辑以及基本要求，在Implementing Replicated Logs with Paxos文档中对二阶段的描述如图所示。

关于上图的中文流程如下。

1. 所有提案发起方选择一个提案编号n然后广播该提案（Prepare(n)）到所有服务。
2. 所有提案接收方接收提案（Prepare(n)），如果接收提案中的提案编号大于本地的提案编号则需要将本地提案编号覆盖为接收提案中的提案编号，并返回认可的提案编号和提案值。
3. 所有提案发起方收到半数以上的认可信息则向发布广播（Accept(n,value)）到所有服务，n为提案编号，value为认可的值。
4. 所有提案接收方接收到Accept信息判断提案编号是否大于等于本地提案编号，如果是则覆盖数据，并返回最小提案编号
5. 所有提案泛起方不在受理提案编号小于提案编号n的数据，反之则重复整个处理流程。如果不在产生提案编号那么此时值已经被选中。

在Implementing Replicated Logs with Paxos文档中还对Paxos算法中的三种现象进行了图示说明，第一种现象：提案已选中，即已经存在半数以上节点认可了某一个值，新提案中的值需要舍弃使用，具体如图所示。

在上图中存在S1、S2、S3、S4和S5五个节点，从S1节点发起提案广播（提案编号为3.1，提案值为X），此时率先获得了半数认可：S1、S2和S3收到提案并认可该提案，然后收到了S5发起的新提案（提案编号为4.5，提案值为Y）,假设S3节点需要进行两个提案的选择，就S3而言它会选择已经认可的提案编号3.1因此会将提案值设置为X，从而放弃Y的选择让S1、S2、S3、S4和S5认可X。

第二种现象：提案未选中，但是可以看到提案信息，即没有半数节点认可某一个值，但是新提案接收时包含了这个认可信息，具体如图所示。

在上图中存在S1、S2、S3、S4和S5五个节点，从S1节点发起提案广播（提案编号为3.1，提案值为X），此时只有少数节点认可提案（S3认可），紧接着S5发起新提案提案编号为4.5，提案值为Y），此时S3、S4和S5认可提案4.5，但是由于S3存在历史认可提案编号3.1因此它会认可上一个提案中的值而抛弃提案编号4.5中的值，因此S3此时的认可值为X，接着收到了来自S1和S2认可的提案编号3.1，认可值为X，此时值X占据半数，产生共识。

第三种现象：提案未选中，受理信息不可见，即没有半数节点认可某一个值，但是新提案接收时不包含了这个认可信息，具体如图所示。

在上图中存在S1、S2、S3、S4和S5五个节点，从S1节点发起提案广播（提案编号为3.1，提案值为X），此时只有少数节点认可提案（S1认可），紧接着S5发起新提案提案编号为4.5，提案值为Y），接下来开始受理阶段，主要关注S3节点，由于S3节点此时有两个提案正在处理，根据提案排序规则需要认可提案编号大的，所以它的认可值为Y，此时S4和S5也在参与受理阶段的处理，它们并没有收到提案编号3.1的干扰因此直接选择提案编号4.5，认可值为Y，此时认可值Y达到半数，产生共识。

注意在第三种现象基础上可能产生一种活锁的情况，具体如图所示。

在上图中节点S3在发起提案号3.1后还没有对提案编号3.1进行受理就收到了提案编号3.5，接着收到提案编号3.1的通过信息，由于本地提案编号是3.5，提案编号3.1小于3.5将会舍弃循环往复该操作整个服务一直处于确认序号请求上始终没有半数认可而形成活锁。解决活锁最简单的方式就是引入随机超时机制，通过这个随机值可以使得某一个提案先提交。

ZAB

本节将对Zookeeper项目中的ZAB协议进行说明，ZAB协议是Zookeeper中用来传播状态变更的源自广播协议。在ZAB中存在三种类型的角色。

1. Leader，领导者，在Zookeeper集群环境中只允许存在一个领导者，领导者主要负责三个操作。
   1. 发起和维护与各个Follower以及Observer之间的心跳。
   2. 负责处理所有的写入请求。
   3. 将实际数据广播到Follower和Observer。
2. Follower，跟随者，在Zookeeper集群环境中允许存在多个Follower，跟随者主要负责三个操作。
   1. 回应Leader的心跳。
   2. 处理读取请求。
   3. 将写入请求转发给Leader。在处理写请求时对请求进行投票。
3. Observer，观察者，观察者和跟随者类似，但是观察者不具备投票权利。

在ZAB协议中每个节点都有四种状态。

1. LOOKING: 初识状态，一般出 现于系统刚启动时的状态或者Leader宕机后。一般称该状态为选举进行中。
2. FOLLOWING：跟随状态，只出现于Follower节点。
3. LEADING：领导状态，只出现于Leader节点。
4. OBSERVING，观察状态，只出现于Observer节点。

在ZAB协议中约定所有的写操作都必须通过Leader完成，然后Leader将数据写入到本地日志后在进行数据广播分发到Follower和Observer。如果Leader无法工作，ZAB协议将会从Follower中选出一个新的Leader，该过程称为选举。简单了解了选举的概念，下面对需要进行选举的三种情况进行说明。

1. 集群初始化阶段。
2. 集群运行期间节点无法与Leader保持通讯。
3. 集群中超过半数的Follower宕机。

在ZAB协议中涉及两种数据结构类进行通讯，第一种是用于客户端与服务端之间的初次握手，数据结构定义如下

class LearnerInfo {
    int protocolVersion;
    int serverid;
}

第二种是用于Leader和Follower之间的通讯，数据结构定义如下。

class QuorumPacket {
  int type;
  long zxid;
  buffer data;
  vector<org.apache.zookeeper.data.Id> authinfo; 
}

在Leader与Follower通讯时存在多种QuorumPacket结构，具体信息见表。

在ZAB中Follower节点存在如下数据信息

1. history：历史数据信息
2. lastZxid：最后操作的zxid
3. acceptedEpoch：接受的选举周期
4. currentEpoch：当前选举周期

在ZAB协议中必须要满足如下三个条件。

1. 使用 best-effort 领导者选举算法。
2. Follower和Observer一次只能有一个Leader。
3. 服务器必须按照接受的属性处理数据包。

在ZAB协议中一旦Leader被确认（在ZAB中并没有规定Leader的选举算法）将进行三个阶段的处理操作，这三个阶段：第一阶段创建选举周期，第二阶段同步，第三阶段广播。

第一阶段处理流程如下。

1. Leader开始接受来自Follower的连接。
2. Follower连接Leader发送FOLLOWERINFO。
3. Leader一旦拥有大多数（2/N+1）的Follower连接就停止接受连接，并向所有Follower发送LEADERINFO(e)，其中e大于所有Follower中的acceptedEpoch数据。
4. 当Follower接收到LEADERINFO(e)数据信息包时将进行如下操作。
   1. 如果e > acceptedEpoch ，Follower将设置acceptedEpoch为e，并发送ACKEPOCH(e)数据包
   2. 如果 e == acceptedEpoch，Follower不做操作
   3. 如果e < acceptedEpoch，Follower关闭与Leader的连接，重新返回选举。
5. Leader等待接收数量的Follower发送ACKEPOCH数据包。
6. 如果Leader中所有的Follower连接都不满足如下条件，Leader将断开Follower连接重新返回选举。
   1. Follower.currentEpoch <= Leade.currentEpoch
   2. Follower.currentEpoch = Leade.currentEpoch 并且 Follower.lastZxid<=Leader.lastZxid

第二阶段处理流程如下。

1. Leader对所有Follower都执行如下操作。
   1. 将Follower添加到连接列表集合中，用于发送处理建议，建议有如下情况
      1. 如果Follower的zxid远远小于Leader的zxid会发送SNAP数据包。
      2. 如果Follower存在Leader选择跳过的事务，将发送TRUNC(zxid)数据包。zxid为Follower在跟随阶段认可的最后一个zxid。
      3. 如果Leader发送的事务是Follower中丢失的，将发送DIFF，Leader会将丢失的数据发送给Follower。
   2. 发送NEWLEADER数据包
   3. Leader将所有需要处理的消息发送给Follower
2. Follower与Leader同步，但是在没有收到NEWLEADER(e)数据包之前不会做任何修改操作，一旦收到NEWLEADER(e)数据包就会更新f.currentEpoch为数据包中的e，然后发送ACK( e<< 32)数据包。
3. 一旦Leader收到大多数的Follow发送的ACK( e<< 32)数据包，它将会发送UPTODATE数据包到Follower。
4. 当Follower接收到UPTODATE数据包时将更新状态，并开始接收客户端请求并向客户端提供服务。
5. Leader再次开始接受Follower的连接，变量nextZxid需要设置为 (e<<32)+1。

第三阶段处理流程如下。

1. Leader将PROPOSE(zxid, data)数据包发送到Follower。(zxid = nextZxid，nextZxid递增 )
2. Follower将PROPOSE数据包中的数据进行记录并发送ACK(zxid)数据包给Leader。
3. Leader收到多数Follower发送的ACK数据包后将会发送COMMIT(zxid)给所有Follower。

数据操作

本节将对ZAB中的数据操作进行相关说明，对于数据操作而言可以分为两种，第一种是读操作、第二种是写操作。在了解两种数据操作后将其放入到ZAB中会有如下几种操作情况。

1. 通过Leader进行写入操作。
2. 通过Follower或者Observer进行写入操作。
3. 通过Leader进行读取操作。
4. 通过Follower或者Observer进行读取操作。

接下来先对通过Leader进行写入操作进行分析，处理流程如图所示。

sequenceDiagram
participant C as Client
participant L as Leader
participant F1 as Follower
participant F2 as Follower
participant F3 as Follower
participant O as Observer

C ->>L: 发送写请求
L ->> F1: 发送提案
L->>L :ACK
F1 ->> L: ACK
L ->> F2: 发送提案
F2 ->> L: ACK
L ->> F3: 发送提案
Note right of L: Leader收到半数ACK后进行COMMIT
L ->> F1: COMMIT
L ->> F2: COMMIT
L ->> F3: COMMIT
L->> O:COMMIT
L ->> C: 响应

通过Leader进行写入操作主要分为如下几个操作步骤。

1. 客户端向Leader发起写请求。
2. Leader将写请求转换为提案发送给所有连接的Follower，等待Follower返回ACK信息，注意Leader自己会默认携带一个ACK。
3. Follower收到提案信息后返回ACK。
4. Leader接收Follower返回的ACK信息，当ACK数量达到大多数（2/N+1）时将发送COMMIT信息完成数据提交。注意：在接收ACK时不需要等所有的Follower返回ACK只需要抵达半数即可。
5. Leader向客户端返回响应。

接下来对通过Follower或者Observer进行写入操作进行分析，在这个操作过程中与通过Leader写入最大的差异是请求首先进入的是Follower或者Observer，由于ZAB规定只有Leader可以进行写入操作，因此只需要将请求从Follower或者Observer转发到Leader，然后执行Leader写入操作流程即可，处理流程如图所示。

sequenceDiagram
participant C as Client
participant L as Leader
participant F1 as Follower
participant F2 as Follower
participant F3 as Follower
participant O as Observer

C ->>F1: 发送写请求
F1->> L: 写入请求转发到Leader

L ->> F1: 发送提案
L->>L :ACK
F1 ->> L: ACK
L ->> F2: 发送提案
F2 ->> L: ACK
L ->> F3: 发送提案
Note right of L: Leader收到半数ACK后进行COMMIT
L ->> F1: COMMIT
L ->> F2: COMMIT
L ->> F3: COMMIT
L->> O:COMMIT
L ->> F1: 响应
F1->>C:响应

最后对通过Leader进行读取操作和通过Follower或者Observer进行读取操作进行分析，在ZAB中Leader、Follower和Observer都允许进行数据读取操作，因此只需要在本地将数据进行读取返回给客户端即可，处理流程如图所示。

sequenceDiagram
participant C as Client
participant L as Leader
participant F1 as Follower
participant O as Observer

C ->> L: 读取请求
L->>C: 响应

C ->> F: 读取请求
F->>C: 响应
C ->> O: 读取请求
O->>C: 响应

选举机制

本节将对Zookeeper项目中的选举机制进行分析，这部分内容填补了ZAB中Leader的选举过程，在Zookeeper项目中采用FastLeaderElection（后续简称为FLE）进行实现。在FLE中如果要成为Leader需要满足以下条件。

1. 选择epoch（选举周期）最大的。
2. 如果epoch相等则选择zxid最大的。
3. 如果epoch和zxid都相等则选择server_id最大的。server_Id是在Zookeeper的zoo.cfg中配置的myid属性。

接下来对选举机制中的投票流程进行说明，具体处理流程如下。

1. 选举周期累加1，该选举周期由参与选举者自行维护（操作对象是类FastLeaderElection中的logicalclock变量）。
2. 初始化选票，所有参与参与选举的节点都给自己投票认可自己是Leader（处理方法是类FastLeaderElection中的updateProposal方法）。
3. 发送初始化选票，将选票发送到参与选举的节点（处理方法是类FastLeaderElection中的sendNotifications方法，简易流程：选票放入到sendqueue集合中，线程WorkerSender进行消息发送）。
4. 接收他人选票，将数据放入到本地选票集合中。如果无法获取任何外部选票，需要判断是否与集群中的其他节点保持有效连接，如果是则需要发送自己的选票，反之则需要建立连接（简易流程：通过线程WorkerReceiver将他人发送的选票进行接收放入到recvqueue集合中）。
5. 判断选举周期。选举周期的处理操作对象是自己的选票和他人的选票，处理策略是随着logicalclock变量而改变的，具体细节如下。
   1. 外部选票的logicalclock大于自己选票的logicalclock，此时当前节点的选举周期小于外部选票的周期，需要清空自己的选票箱，并且将自己的logicalclock变量更新为外部选票的logicalclock，然后执行选票初始化再进行选票PK判断是否需要变更选票，处理完成后将自己的选票发送到其他节点。
   2. 外部选票的logicalclock等于自己选票的logicalclock，进行选票PK。
   3. 外部选票的logicalclock小于自己选票的logicalclock，此时当前节点的选举周期大于外部选票的周期，需要将外部选票舍弃，然后处理下一个外部选票。
6. 选票PK，选票PK的两个数据对象是 [sid（myid)，zxid] 和 [vote id ， vote zxid]。sid表示自身选票的服务id，zxid表示自身选票的事务id，vote id表示选票认可的服务id，vote zxid表示外部选票的事务id。对比细节如下。
   1. 外部选票的logicalclock大于自己选票的logicalclock，放弃自身的所有数据均采用外部选票的数据。
   2. 外部选票的logicalclock等于自己选票的logicalclock，接着对比zxid，对比细节如下。
      1. 若外部选票的zxid大于自身选票的zxid，则将自身选票数据舍弃，更新为外部选票的数据，并将新的选票发出给其他参选人。
      2. 若外部选票的zxid小于自身选票的zxid，则使用自身选票，将选票发送给其他参选人。
      3. 若外部选票的zxid等于自身选票的zxid，则需要比较sid(myid)和 vote id，两者大的获胜。
7. 归票，如果已经存在大多数（2/N+1）的节点认可选票（注意这里的选票可能是经过更新的选票），则停止投票，反之则需要继续接收投票。
8. 更新服务状态，若大多数节点将选票投给自己则将服务器状态更新为LEADING，反之则更新为FOLLOWING。

在整个选举过程中4~7操作会一直进行，直到有一个Leader被选举。目前已经了解到整个选举过程的处理细节，接下来需要对Zookeeper集群环境下三种场景进行分析。

第一种情况是Zookeeper集群初始化启动阶段，由于在集群选举中需要满足奇数个服务，因此设模拟Zookeeper服务节点数量为3，分别是S1（myid=1）、S2（myid=2）和S3（myid=3）。因为此时处于Zookeeper集群初始化阶段三个节点的logicalclock数据为0，由于开始选举后需要将logicalclock值累加1，此时数据为1，并且在初始化阶段并未产生任何数据因此zxid也为0。此时所有节点都需要进行初始化选票，为说明方便并且与选举流程中的比较优先级对应，将选票使用三部分表述，第一部分为logicalclock，第二部分为sid（myid）推荐的Leader服务id，第三部分为zxid。初始化阶段每个节点都将选票投给自己即sid设置为当前节点的myid属性，此时三个节点的选票以及票仓如下。

选票初始化完成后会进入接收他人选票阶段，假设S1收到S2和S3的选票，此时会进行如下操作。

1. 对比logicalclock，由于所有选票此时logicalclock都为0，因此需要对比sid。
2. 对比sid，数字大的获胜。

经过上述操作由于S3的选票sid最大因此S1需要修改选票为[1,3,0]，同时需要清空自己的票仓。同理S2会收到S1和S3的选票，S3会收到S1和S2的选票，经过上述操作后此时三个节点的选票以及票仓如下。

此时S1、S2和S3将选票广播由于此时选票都是[0,3,0]，因此S3成为Leader，S1和S2成为Follower。

第二种情况是是在集群环境中Follower发生网络分区，无法与Leader建立有效连接。假设S1节点发生了这样的现象，此时S1节点的服务状态会变为LOOKING并发起新的一轮投票。S1发起新的投票将选票投给自己，选票编号[2,1,0]，将选票信息与S2和S3进行交互，此时由于S2中明确表示S3是Leader，会选票[2,3,3]将信息返回给S1，S3同理。在得到选票信息后S1会进行选票PK，PK后会改票为[2,3,3]。

第三种情况是是在集群环境中Leader进行了重启操作。沿用第一种情况S1和S2是Follower节点，S3是Leader节点，此时Leader离线，S1和S2无法与Leader保持正常通讯，因此触发选举机制。由开始了一次新的选举机制因此logicalclock数值为2，logicalclock和sid都可以明确，此时S1和S2的选票如下。

1. S1选票：[2,1,zxid]
2. S2选票：[2,2,zxid]

在上述两张选票中zxid会有差异，差异产生的原因是在原有Leader存活阶段只需要半数Follower写入即可认为写入成功，S1和S2都有可能是半数中的一部分，或者不属于半数，因此这两张选票zxid会有差异：有可能相同也有可能不相同。假设zxid相同，那么会比较sid，大的生出；假设zxid不相同，大的胜出。

假设S1在选票PK中获胜成为了Leader，现在S3从宕机阶段进行恢复（重启），在启动完成的时候服务状态是LOOKING会进行一次选举，此时S3会先将票投给自己，S3选票[3,3,Last_Zxid]，然后将选票信息广播到其他节点，在S2节点由于S2认可S1节点是Leader因此会返回选票[3,3,zxid]，同理在S1节点也会收到类似信息（类似的含义：如果在S3重启阶段没有发生事务操作，选举操作将会得到一样的数据，反之则会改变选举周期编号和zxid），由于存在半数以上的节点认可S1为Leader因此S3成为Follower与S1节点完成通讯。

总结

本章是一篇偏向理论。本章开篇对分布式一致性算法Paxos做出相关介绍，接着对Zookeeper项目中专门设计的ZAB算法进行介绍，在ZAB介绍之后对选举机制进行相关介绍，主要围绕FastLeaderElection算法进行相关介绍，对Zookeeper项目中的核心选举流程进行详细说明。