深入浅出Zookeeper---3、Leader选举-灵析社区

PAXOS选举算法

Paxos算法概述

背景

主流分布式一致性算法包括Paxos，Raft和ZAB，它们之间有怎样的区别与关系？

Google Chubby的作者Mike Burrows说过，世上只有一种一致性算法，那就是Paxos，所有其他一致性算法都是Paxos算法的不完整或衍生版。

什么是Paxos

Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其解决的问题就是在分布式系统中如何就某个值（决议）达成一致。

Paxos的作用

常见的分布式系统中，总会发生机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序）等情况。 Paxos 算法是分布式一致性算法用来解决一个分布式系统如何就某个值(决议)达成一致性的问题。

拜占庭问题

什么是拜占庭问题

拜占庭将军问题是一个共识问题：一群将军想要实现某一个目标，必须是全体一致的决定，一致进攻或者一致撤退；但由于叛徒的存在，将军们不知道应该如何达成一致。

举例来说：

假设有三个拜占庭将军，分别为A、B、C，他们要讨论的只有一件事情：明天是进攻还是撤退。为此，将军们需要依据“少数服从多数”原则投票表决，只要有两个人意见达成一致就可以。

如果A和B投进攻，C投撤退，那么传递结果：

那么A的信使传递给B和C的消息都是进攻；
B的信使传递给A和C的消息都是进攻；
而C的信使传给A和B的消息都是撤退。
通过以上决策，三个将军就都知道进攻和撤退占比是 2 : 1 。显而易见，进攻方胜出，第二天大家都要进攻，三者行动最终达成一致。
但是，如果稍微做一个改动：三个将军中出了一个叛徒呢？叛徒的目的是破坏忠诚将军间一致性的达成，让拜占庭的军队遭受损失。
假设A和B是忠诚将军，A投进攻，B投撤退，如果你是C这个叛徒将军，那么你该做些什么，才能在第二天让两个忠诚的将军做出相反的决定呢？
进攻方和撤退方现在是 1 : 1 ，无论C投哪一方，都会变成 2 : 1 ，一致性还是会达成。但是，作为叛徒的C，你必然不会按照常规出牌，于是你让一个信使告诉A的内容是你“要进攻”，让另一个信使告诉B的则是你“要撤退”。
至此，A将军看到的投票结果是：进攻方：撤退方 = 2 : 1 ，而B将军看到的是 1 : 2 。第二天，忠诚的A冲上了战场，却发现只有自己一支军队发起了进攻，而同样忠诚的B，却早已撤退。最终，A的军队败给了敌人，拜占庭的军队遭受损失。

拜占庭问题情形在计算机世界中也会出现，如果三个节点中有一个异常节点，那么最坏情况下两个正常节点之间是无法保证一致性的。那么你之前听说过的 etcd 这样的系统可以保证三个节点有一个宕机的情况下依然可以对外提供一致性服务是为什么呢？因为这类系统并没有考虑拜占庭故障，在他们的假设里故障节点可能会停止服务，可能会超时，但是不会发送异常消息。尽管拜占庭的“幽灵”很难处理，但在实际工作应用中，却并不需要过分去考虑它，因为对于大多数系统来说，内部环境里，硬件故障导致消息错误的概率本身就很低，还要按照拜占庭叛徒的策略来处理故障就更为困难了。

Paxos角色

Paxos将系统中的角色分为三种：

Proposer：提议者，提出提案Proposal（未经批准的决议）信息，它包括提案编号 (Proposal ID) 和提议的值 (Value)。
Acceptor：决策者，参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则标识该Proposal为批准。
Learner：最终决策学习者，不参与决策，从Proposers/Acceptors学习最新达成一致的决议（Value）。

在具体的实现中，一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor或 Learner。Proposer负责提出提案，Acceptor负责对提案作出裁决（accept与否），Learner负责学习提案结果，Acceptor告诉Learner哪个value被选定，Learner则无条件认为相应的value被选定。

为了避免单点故障，会有一个Acceptor集合群，Proposer向Acceptor集合群发送提案，Acceptor集合群中，只有一半以上的成员同意了这个提案（Proposal），就认为该提案被接受选定了。

Paxos算法详解

Paxos包含三种算法： Basic Paxos，Multi Paxos和Fast Paxos。

1. Basic Paxos

Basic Paxos 执行过程分为两个阶段：

       阶段一（Prepare阶段）：        
       1. Proposer选择一个提案Proposal编号为N，然后向半数以上的Acceptor发送编号为N的 Prepare请求。 
       2. 如果某个Acceptor收到一个编号为N的Prepare请求，如果小于它已经响应过的请求，则拒绝。 
       3. 如果N大于该Acceptor已经响应过的所有请求的编号，那么它就会将它已经接受过（已经经 过第二阶段accept的提案）的编号最大的提案作为响应反馈给Proposer，如果还没有的 accept提案的话返回{pok，null，null}空信息，同时该Acceptor承诺不再接受任何编号小于 N的提案。
       阶段二（accept阶段）： 
       1. 如果一个Proposer收到半数以上Acceptor对其发出的提案响应，那么它就会发送一个针对 [N,V]提案的Accept请求给半数以上的Acceptor。注意：N是提案的编号，V就是该提案的决议，该决议是响应编号中最大提案的value。如果响应中不包含任何提案，那么V值就由 Proposer自己决定。 
       2. 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于 N的Prepare请求做出过响应，那么它就接受该提案。如果N小于Acceptor以及响应的 prepare请求，则拒绝，不回应或回复error（当proposer没有收到过半的回应，那么它会重 新进入第一阶段，递增提案号，重新提出prepare请求）。

整体流程：

上述介绍了Basic Paxos算法，但在算法运行过程中，可能还会存在一种极端情况，当有两个proposer依次提出一系列编号递增的议案，那么会陷入死循环，无法完成第二阶段，也就是无法选定一个提案。由此产生了活锁问题，如何解决？再看下面的Multi Paxos算法。
2. Multi Paxos

原始的基础Paxos算法只能对一个值进行决议，而且每次决议至少需要两次网络来回，在实际应用中可能会产生各种各样的问题，所以不适用在实际工程中。因此，Multi Paxos基于Basix Paxos做了改进，可以连续确定多个值并提高效率：

1. 针对每一个要提议的值，运行一次Paxos算法实例（Instance），形成决议。每一个Paxos实例使用唯一的Instance ID标识。 
2. 在所有Proposers中选主，选举一个Leader，由Leader唯一提交Proposal给Acceptors进行表决。 这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下， Prepare阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

示例：

在Basic Paxos协议中，每一次执行过程都需要经历Prepare->Promise->Accept->Accepted 这四个步骤，这样就会导致消息太多，影响性能。

在Multi Paxos的实际过程中：如果Leader足够稳定的话，Phase 1 里面的Prepare->Promise 完全可以省略掉，从而使用同一个Leader去发送Accept消息。

实质上，Multi Paxos模式下首先对所有Proposers进行Leader选举，再利用Basic Paxos来实现。

选出Leader后，只由Leader来提交Proposal，如果Leader出现宕机，则重新选举Leader，在系统中仅有一个Leader可以提交Proposal。 Multi Paxos通过改变Prepare阶段的作用范围，从而使得Leader的连续提交只需要执行一次Prepare阶段，后续只需要执行Accept阶段，将两阶段变为一阶段，提高了效率。
3. Fast Paxos

上述Paxos协议中，消息最后到达Learner一般都要经历 Client–>Proposer–>Acceptor–>Learner 多个步骤，实质上由Learner是真正执行任务，为了更快的让消息到达Learner，如果Proposer本身没有数据需要被确认的话，那么可以跳过Proposer这一步，直接将请求发送给Accepter，由leader先进行检查，这样的操作叫做Fast Paxos。

选主过程剖析

第一步（初始化投票）

初始化投票，所有服务器的logicClock都为1，zxid都为0，每个节点都会投票给自己，投票信息（1，1，0）主要分为三部分：

第一位数代表服务器的logicalClock（自增的整数），即选举轮次，它表示这是该服务器发起的第多少轮投票； 
第二位数代表被推荐的服务器的myid，它是ZooKeeper集群唯一的ID； 
第三位数代表被推荐服务器的最大zxid，类似于RDBMS中的事务ID，实质上用于标识一次更新操作的事务Proposal（提议）ID。

ZXID组成：

zxid（Zookeeper Transaction Id）是 ZAB 协议的事务编号，其是一个 64 位的整数：

低 32 位是一个单调递增的计数器，每当 Leader 服务器产生一个新的事务 Proposal 时，递增 1。 
高 32 位代表 Leader 的 epoch 编号，有点类似于 Raft 的任期(改朝换代），每当选举一个新 Leader 时，就会从新 Leader 取出本地日志中的最大事务 Proposal 的 zxid，解析出 epoch 然后加 1，并将低 32 位置 0 来开始新的 zxid。

第二步更新投票信息

服务器1收到服务器2的选票（1, 2, 0）和服务器3的选票（1, 3, 0）后，由于所有的logicClock都相等，所有的zxid都相等，因此根据myid判断应该将自己的选票按照服务器3的选票更新为（1, 3, 0）。投票规则：

优先检查ZXID。ZXID比较大的服务器优先作为Leader。
如果ZXID相同，那么就比较myid。myid较大的服务器作为Leader服务器。

服务器1将自己的票箱全部清空，再将服务器3的选票与自己的选票存入自己的票箱，接着将自己更新后的选票信息广播出去。此时服务器1票箱内的选票为1号选举3号(1, 3)，3号选举3号(3, 3)。
服务器2收到服务器3的选票后，与服务器1的处理逻辑一样，也将自己的选票更新为（1, 3）并存入票箱然后广播。此时服务器2票箱内的选票为(2, 3)，(3, 3)。
服务器3根据上述规则，无须更新选票，自身的票箱内选票仍为（3, 3）。
服务器1与服务器2更新后的选票广播出去后，由于三个服务器最新选票都相同，最后三者的票箱内都包含三张投给服务器3的选票。

第三步确定集群角色

根据上述选票结果，三个服务器一致认为此时服务器3应该是Leader。因此服务器1和2都进入FOLLOWING状态，而服务器3进入LEADING状态。之后由Leader发起并维护与Follower间的心跳。

FOLLOW重启选举剖析

如果FOLLOW跟随者节点出现问题重启之后，是如何实现重新选举？

第一步：

第二步：

服务器3收到服务器1的投票后，将自己的状态LEADING以及选票返回给服务器1。
服务器2收到服务器1的投票后，将自己的状态FOLLOWING及3号主节点的选票信息返回给服务器1。
服务器1知道服务器3是Leader，并且通过服务器2与服务器3的选票可以证实服务器3确实得到了超过半数的选票。因此服务器1进入FOLLOWING状态。

LEADER重启选举剖析

Leader如果重启之后该如何选举？

第一步：

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

第二步：

服务器1和2根据外部投票确定是否要更新自身的选票。这里就会出现两种情况：

 1. 服务器1和2的zxid相同。例如在服务器3宕机前服务器1与2完全同步，zxid一致。此时选票的更新主要取决于myid的大小，根据选举规则，myid越大的优先级越高。 
 2. 服务器1和2的zxid不同。在旧Leader宕机之前，其所主导的写操作，只需过半服务器确认即可，而不需所有服务器确认。这个时候，服务器1和2可能其中有一个与旧Leader同步（即zxid与之相同），而另 一个则没有同步（即zxid比之小）。这时选票的更新主要取决于谁的zxid较大，优先选取为主节点。
 3.

在第一步的图中所示，服务器1的zxid为11，而服务器2的zxid为10，因此服务器2将自身选票更新为（3, 1, 11）。

第三步：

经过第二步的选票更新后，服务器1与服务器2均将选票投给服务器1，因此服务器2成为Follower，而服务器1成为新的Leader并维护与服务器2的心跳。

第四步：

旧的Leader节点3恢复后，进入LOOKING状态并发起新一轮领导选举，并将选票投给自己。此时服务器1会将自己的LEADING状态及选票（3, 1, 11）返回给服务器3，而服务器2将自己的FOLLOWING状态及选票（3, 1, 11）返回给服务器3，旧的Leader节点3已经被新的Leader节点1取代，这就类似于上面所讲的FOLLOW重启选举的过程。