详解分布式共识（一致性）算法Raft

所谓分布式共识（consensus），与 CAP理论 中的一致性（consistency）其实是异曲同工，就是在分布式系统中，所有节点对同一份数据的认知能够达成一致。保证集群共识的算法就叫共识算法，它与一致性协议这个词也经常互相通用。

当今最著名的共识算法就是Paxos算法。它由Leslie Lamport在1990年提出，很长时间以来都是一致性的事实标准。但是它有两个不小的缺点：难以理解和证明，难以在实际工程中实现。Google Chubby的工程师就曾有以下的评论：

于是2014年，来自斯坦福的两位大佬Diego Ongaro与John Ousterhout通过论文 《In Search of an Understandable Consensus Algorithm》 提出了一个新的共识算法Raft。从题目就可以看出，Raft的特点就是容易理解，在此基础上也容易实现，因此在real world中，它的应用也比Paxos要广泛，比较有名的如etcd、Kudu等。

Raft为了达到易懂易用的目标，主要做了两件事：一是分解问题（decomposition），即将复杂的分布式共识问题拆分为 领导选举 （leader election）、 日志复制 （log replication）和 安全性 （safety）三个子问题，并分别解决；二是压缩状态空间（state space reduction），相对于Paxos算法而言施加了更合理的限制，减少因为系统状态过多而产生的不确定性。

下面先简要介绍共识算法的基础——复制状态机，然后就来按顺序研究Raft是如何解决三个子问题的。

在共识算法中，所有服务器节点都会包含一个有限状态自动机，名为复制状态机（replicated state machine）。每个节点都维护着一个复制日志（replicated logs）的队列，复制状态机会按序输入并执行该队列中的请求，执行状态转换并输出结果。可见，如果能保证各个节点中日志的一致性，那么所有节点状态机的状态转换和输出也就都一致。共识算法就是为了保障这种一致性的，下图示出简单的复制状态机及其相关架构。

根据分布式系统的 Quorum机制 与NRW算法，集群中半数以上节点可用时，就能正确处理分布式事务，因此Raft集群几乎都使用奇数节点，可以防止脑裂并避免浪费资源。采用ZAB协议的ZooKeeper集群也是如此。

在Raft集群中，任意节点同一时刻只能处于领导者（leader）、跟随者（follower）、候选者（candidate）三种状态之一。下图示出节点状态的转移规则。

可见，集群建立时所有节点都是跟随节点。如果在一定时间过后发现没有领导节点，就会切换到候选状态，发起选举。得到多数票的候选者就会成为领导节点。如果候选节点或当前领导节点发现了更新的领导者，就会主动退回跟随状态。

领导节点全权负责管理复制日志，也就是从客户端接收请求，复制到跟随节点，并告诉跟随节点何时可以处理这些请求。如果领导节点故障或断开连接，就会重新进行选举。可见，领导节点的存在大大简化了共识算法的设计。

在上面的图中出现了任期（term）这个词。领导者并不是一直“在位”的，工作一段时间之后，就会选举出新的领导者来接替它。

由上图可见，蓝色表示选举时间段，绿色表示选举出的领导者在位的时间段，这两者合起来即称作一个任期，其计数值是自增的。任期的值就可以在逻辑上充当时间戳，每个节点都会保存一份自己所见的最新任期值，称为currentTerm。另外，如果因为票数相同，没能选出领导，就会立即再发起新的选举。

如果一个或多个跟随节点在选举超时（election timeout）内没有收到领导节点的心跳（一个名为AppendEntries的RPC消息，本意是做日志复制用途，但此时不携带日志数据），就会发起选举流程：

根据其他节点回复的消息，会出现如下三种结果：

获得多数票的节点只要当选，就会立即给其他所有节点发送AppendEntries，避免再次选举。另外，在同一任期内，每个节点只能投一票，并且先到先得（first-come-first-served），也就是会把票投给RequestVote消息第一个到达的那个节点。

至于上面的第三种情况，也就是所谓“split vote”现象，容易在很多跟随者变成候选者时出现，因为没有节点能得到多数票，选举有可能无限继续下去。所以，Raft设置的选举超时并不是完全一样的，而是有些许随机性，来尽量使得投票能够集中到那些较“快”的节点上。

领导节点选举出来后，集群就可以开始处理客户端请求了。前面已经说过，每个节点都维护着一个复制日志的队列，它们的格式如下图所示。

可见，日志由一个个按序排列的entry组成。每个entry内包含有请求的数据，还有该entry产生时的领导任期值。在论文中，每个节点上的日志队列用一个数组log[]表示。

当客户端发来请求时，领导节点首先将其加入自己的日志队列，再并行地发送AppendEntries RPC消息给所有跟随节点。领导节点收到来自多数跟随者的回复之后，就认为该请求可以提交了（见图中的commited entries）。然后，领导节点将请求应用（apply）到复制状态机，并通知跟随节点也这样做。这两步做完后，就不会再回滚。
这种从提交到应用的方式与最基础的一致性协议——两阶段提交（2PC）有些相似，但Raft只需要多数节点的确认，并不需要全部节点都可用。

注意在上图中，领导节点和4个跟随节点的日志并不完全相同，这可能是由于跟随节点反应慢、网络状况差等原因。领导节点会不断地重试发送AppendEntries，直到所有节点上的日志达到最终一致，而不实现强一致性。这就是CAP理论中在保证P的情况下，C与A无法兼得的体现。

日志复制的过程仍然遗留了一个问题：如果领导或者跟随节点发生异常情况而崩溃，如何保证日志的最终一致性？它属于下面的安全性问题中的一部分，稍后会解答它。

安全性是施加在领导选举、日志复制两个解决方案上的约束，用于保证在异常情况下Raft算法仍然有效，不能破坏一致性，也不能返回错误的结果。所有分布式算法都应保障安全性，在其基础上再保证活性（liveness）。

Raft协议的安全性保障有5种，分别是：选举安全性（election safety）、领导者只追加（leader append-only）、日志匹配（log matching）、领导者完全性（leader completeness）、状态机安全性（state machine safety） 。下面分别来看。

选举安全性是指每个任期内只允许选出最多一个领导。如果集群中有多于一个领导，就发生了脑裂（split brain）。根据“领导选举”一节中的描述，Raft能够保证选举安全，因为：

在讲解日志复制时，我们可以明显地看出，客户端发出的请求都是插入领导者日志队列的尾部，没有修改或删除的 *** 作。这样可以使领导者的行为尽量简单化，使之没有任何不确定的行为，同时也作为下一节要说的日志匹配的基础。

日志匹配的具体描述如下。
如果两个节点的日志队列中，两个entry具有相同的下标和任期值，那么：

第一点自然由上一节的“领导者只追加”特性来保证，而第二点则由AppendEntries RPC消息的一个简单机制来保证：每条AppendEntries都会包含最新entry之前那个entry的下标与任期值，如果跟随节点在对应下标找不到对应任期的日志，就会拒绝接受并告知领导节点。

有了日志匹配特性，就可以解决日志复制中那个遗留问题了。假设由于节点崩溃，跟随节点的日志出现了多种异常情况，如下图。

注意图中不是6个跟随节点，而是6种可能的情况。比如a和b是丢失了entry，c和d是有多余的未提交entry，e和f则是既有丢失又有冗余。这时领导节点就会找到两个日志队列中最近一条匹配的日志点，将该点之后跟随节点的所有日志都删除，然后将自己的这部分日志复制给它。例如对于上图中的情况e来说，最近一条匹配的日志下标为5，那么5之后的所有entry都会被删除，被替换成领导者的日志。

领导者完全性是指，如果有一条日志在某个任期被提交了，那么它一定会出现在所有任期更大的领导者日志里。这也是由两点来决定的：

根据这两个描述，每次选举出的领导节点一定包含有最新的日志，因此只存在跟随节点从领导节点更新日志的情况，而不会反过来，这也使得一致性逻辑更加简化，并且为下面的状态机安全性提供保证。

状态机安全性是说，如果一个节点已经向其复制状态机应用了一条日志中的请求，那么对于其他节点的同一下标的日志，不能应用不同的请求。这句话就很拗口了，因此我们来看一种意外的情况。

这里就有问题了，在时刻c的日志与新领导者的日志发生了冲突，此时状态机是不安全的。
为了解决该问题，Raft不允许领导者在当选后提交“前任”的日志，而是通过日志匹配原则，在处理“现任”日志时将之前的日志一同提交。具体方法是：在领导者任期开始时，立刻提交一条空的日志，所以上图中时刻c的情况不会发生，而是像时刻e一样先提交任期4的日志，连带提交任期2的日志。就算此时S1再崩溃，S5也不会重新被选举了。

如果想要更直观地理解Raft，建议参考 这里 ，是一个用动画来描述该算法的网页，形象生动。

①他没有同意你的邀请。因此用户无法进行下去。

②平台的服务器端受到巨大的压力，导致用户在平台上能正常使用的范围比较有限。

③用户使用的网络数据不佳，或者是由于访问的用户数量过多，使得该平台的内部程序运转发生了崩溃等现象。

Zab也是一个 强一致性算法 ，也是(multi-)Paxos的一种，全称是Zookeeper atomic broadcast protocol，是Zookeeper内部用到的一致性协议。相比Paxos，也易于理解。其保证了消息的全局有序和因果有序，拥有着一致性。Zab和Raft也是非常相似的，只是其中有些概念名词不一样。

Role(or Status)

节点状态：

Leading ：说明当前节点为Leader

Following ：说明当前节点为Follower

Election ：说明节点处于选举状态。整个集群都处于选举状态中。

Epoch逻辑时钟

Epoch相当于paxos中的proposerID，Raft中的term，相当于一个国家，朝代纪元。

Quorums：

多数派，集群中超过半数的节点集合。

节点中的持久化信息：

history:  a log of transaction proposals accepted; 历史提议日志文件

acceptedEpoch:  the epoch number of the last NEWEPOCH message accepted; 集群中的最近最新Epoch

currentEpoch:  the epoch number of the last NEWLEADER message accepted; 集群中的最近最新Leader的Epoch

lastZxid:  zxid of the last proposal in the history log; 历史提议日志文件的最后一个提议的zxid

在 ZAB 协议的事务编号 Zxid 设计中， Zxid  是一个 64 位的数字，

低 32 位是一个简单的单调递增的计数器，针对客户端每一个事务请求，计数器加 1；

高 32 位则代表 Leader 周期 epoch 的编号，每个当选产生一个新的 Leader 服务器，就会从这个 Leader 服务器上取出其本地日志中最大事务的ZXID，并从中读取 epoch 值，然后加 1，以此作为新的 epoch，并将低 32 位从 0 开始计数。

epoch：可以理解为当前集群所处的年代或者周期，每个 leader 就像皇帝，都有自己的年号，所以每次改朝换代，leader 变更之后，都会在前一个年代的基础上加 1。这样就算旧的 leader 崩溃恢复之后，也没有人听他的了，因为 follower 只听从当前年代的 leader 的命令。

ZAB协议

Zab协议分为四个阶段

Phase 0: Leader election（选举阶段，Leader不存在）

节点在一开始都处于选举阶段，只要有一个节点得到超半数Quorums节点的票数的支持，它就可以当选 prospective  leader 。只有到达 Phase 3 prospective leader 才会成为 established  leader (EL)。

这一阶段的目的是就是为了选出一个 prospective leader（PL） ，然后进入下一个阶段。

协议并没有规定详细的选举算法，后面我们会提到实现中使用的  Fast Leader Election 。

Phase 1: Discovery（发现阶段，Leader不存在）

在这个阶段，PL收集Follower发来的acceptedEpoch(或者)，并确定了PL的Epoch和Zxid最大，则会生成一个NEWEPOCH分发给Follower，Follower确认无误后返回ACK给PL。

这个一阶段的主要目的是PL生成NEWEPOCH，同时更新Followers的acceptedEpoch，并寻找最新的historylog，赋值给PL的history。

这个阶段的根本：发现最新的history log，发现最新的history log，发现最新的history log。

一个 follower 只会连接一个 leader，如果有一个节点 f 认为另一个 follower 是 leader，f 在尝试连接 p 时会被拒绝，f 被拒绝之后，就会进入 Phase 0。

1PL         Followers

2|<---------X--X--X        FOLLOWERINFO(FacceptedEpoch)

3X--------->|->|->|        NEWEPOCH(e′)

4|<---------X--X--X        ACKEPOCH(FcurrentEpoch, Fhistory, FlastZxid)，接着PL寻找所有Follower和PL中最新的history赋值给PLhistory

Phase 2: Synchronization（同步阶段，Leader不存在）

同步阶段主要是利用 leader 前一阶段获得的最新提议历史，同步集群中所有的副本。只有当 quorum 都同步完成，PL才会成为EL。follower 只会接收 zxid 比自己的 lastZxid 大的提议。

这个一阶段的主要目的是同步PL的historylog副本。

1PL         Followers

2X--------->|->|->|        NEWLEADER(e′ , Lhistory) 

3|<---------X--X--X        ACKNEWLEADER(e′,Lhistory)

4X--------->|->|->|        COMMIT message,Follow Deliver ⟨v, z⟩,PL->L

Phase 3: Broadcast（广播阶段，Leader存在）

到了这个阶段，Zookeeper 集群才能正式对外提供事务服务，并且 leader 可以进行消息广播。同时如果有新的节点加入，还需要对新节点进行同步。

这个一阶段的主要目的是接受请求，进行消息广播

值得注意的是，ZAB 提交事务并不像 2PC 一样需要全部 follower 都 ACK，只需要得到 quorum （超过半数的节点）的 ACK 就可以了。

1Client     Leader      Followers

2|         |          |  |  |

3   X-------->|          |  |  |      write Request

4|         X--------->|->|->|     sent Propose ⟨e′, ⟨v, z⟩⟩

5|         |<---------X--X--X     Append proposal to Fhistory,Send ACK(⟨e′, ⟨v, z⟩⟩) to L

6|         X--------->|->|->|     COMMIT(e′, ⟨v, z⟩),F Commit (deliver) transaction ⟨v, z⟩

zookeeper中zab协议的实现

协议的 Java 版本实现跟上面的定义有些不同，选举阶段使用的是 Fast Leader Election（FLE），它包含了 Phase 1 的发现职责。因为  FLE 会选举拥有最新提议历史的节点作为 leader，这样就省去了发现最新提议的步骤 。实际的实现将 Phase 1 和 Phase 2 合并为 Recovery Phase（恢复阶段）。所以，ZAB 的实现只有三个阶段：

Phase 1:Fast Leader Election(快速选举阶段，Leader不存在)

前面提到 FLE 会选举拥有最新提议历史（lastZixd最大）的节点作为 leader，这样就省去了发现最新提议的步骤。这是基于拥有最新提议的节点也有最新提交记录的前提。

每个节点会同时向自己和其他节点发出投票请求，互相投票。

选举流程：

选epoch最大的

epoch相等，选 zxid 最大的

epoch和zxid都相等，选择serverID最大的（就是我们配置zoocfg中的myid）

节点在选举开始都默认投票给自己，当接收其他节点的选票时，会根据上面的条件更改自己的选票并重新发送选票给其他节点，当有一个节点的得票超过半数，该节点会设置自己的状态为 leading，其他节点会设置自己的状态为 following。

Phase 2:Recovery Phase（恢复阶段，Leader不存在）

这一阶段 follower 发送它们的 lastZixd 给 leader，leader 根据 lastZixd 决定如何同步数据。这里的实现跟前面 Phase 2 有所不同：Follower 收到 TRUNC 指令会中止 LlastCommittedZxid 之后的提议，收到 DIFF 指令会接收新的提议。

1L         Followers

2X-----------------          LlastZxid ← ⟨LlastZxidepoch + 1, 0⟩

3|<---------X--X--X        FOLLOWERINFO(FlastZxid)

4X--------->|->|->|        NEWEPOCH(LlastZxid)

5X--------->|->|->|        SNAP,DIFF or TRUNC指令

6|<---------X--X--X        if TRUNC notAccept LlastZxid else(DIFF) accept,commit proposal else(SNAP) 

Phase 3:Broadcast Election(广播阶段，Leader存在)

同上

Leader故障

如果是Leader故障，首先进行Phase 1:Fast Leader Election，然后Phase 2:Recovery Phase，恢复阶段保证了如下两个问题，这两个问题同时也和Raft中的Leader故障解决的问题是一样的， 总之就是要保证Leader *** 作日志是最新的 ：

已经被处理的消息不能丢      

被丢弃的消息不能再次出现

总结

Zab和Raft都是强一致性协议，但是Zab和Raft的实质是一样的，都是mutli-paxos衍生出来的强一致性算法。简单而言，他们的算法都都是先通过Leader选举，选出一个Leader，然后Leader接受到客户端的提议时，都是先写入 *** 作日志，然后再与其他Followers同步日志，Leader再commit提议，再与其他Followers同步提议。如果Leader故障，重新走一遍选举流程，选取最新的 *** 作日志，然后同步日志，接着继续接受客户端请求等等。过程都是一样，只不过两个的实现方式不同，描述方式不同。 实现Raft的核心是Term，Zab的核心是Zxid，反正Term和Zxid都是逻辑时钟。

---