前言

上一次分享了CAP 定理，我们了解到在有网路分区（Partition）的情况下，我们只能在一致性（Consistency）与可用性（Availability）之间二择一，更进一步地说，我们其实是在光谱的两端— 强一致性（Strong Consistency）与最终一致性（Eventually Consistency）之间做选择。

在最终一致性上，我们通常会听到很多方法论，像是上篇提到的读时修复（Read Repair）、写时修复（Write Repair）、反熵（Anti-Entropy）等等；不过在强一致性上，我们比较常听到某论文发表的强一致性演算法，原因是强一致性要有合理的数学佐证，大家才会相信，除此之外，还需要经过大规模的落地验证，大家才会对其效能认可，因此被广泛运用在商业上的强一致性算法比较少，经典常见的像是Paxos、ZooKeeper的ZAB、Raft等等。

在开始之前，如果还没读过上一篇《分散式架构的限制理论— CAP定理》的，建议可以先阅读理解分散式系统的限制。由于强一致性在某些场景是必须要被保证的，像是金融支付、票务系统等等，所以这篇会介绍强一致性系列的算法。

Paxos 共识演算法家族

若要说到共识演算法，那一定会提及Paxos，原因是Paxos刚被提出时缺少工程面的实作细节，比较像个理论框架，导致后面有实作细节的算法看起来都像Paxos，甚至有人会说「这世界只有一种共识演算法，那就是Paxos」。这里暂时不会展开Paxos的细节，因为Paxos算法是出名的难，导致后来作者Lamport甚至还自己出了《Paxos Made Simple》来解释自己的算法，不过这里提及Paxos是因为Paxos的重要性在于它有严谨的数学证明，如果真的想理解Paxos，建议可以先理解Paxos家族的其他演算法，像是本篇要提到的Raft，最后如果对于Paxos在工程端的实作有兴趣的，可以参考Google团队对Paxos的实战总结《Paxos Made Live — An Engineering Perspective》。

共识演算法分类— BFT vs. CFT

从解决的问题类型来看，共识演算法分成两种，分别是拜占庭容错演算法（Byzantine Fault Tolerance, BFT）与故障容错演算法（Crash Fault Tolerance, CFT）。拜占庭容错演算法主要在解决如果有节点作恶的情况下，如何同步集群的状态，常见的拜占庭容错演算法有PBFT；故障容错演算法主要都在处理节点故障或是遇到网路问题时，如何让整个集群的状态维持一致，常见的故障容错演算法有ZAB、Raft等等。

虽然拜占庭问题（Byzantine Generals' Problem）跟拜占庭容错演算法PBFT被提出的时间都相当早，但可以说是到了区块链出现，才找到大规模的应用场景，而大部分企业内部应用的，还是属于故障容错演算法，像是Google透过Paxos达成共识的分布式锁系统—Chubby，而今天我们要介绍的就是常见于企业内部的共识机制— Raft。

Raft 共识机制

Raft是Diego Ongaro在Stanford念博班时的博士论文，在2013年与他的指导教授John Ousterhout一同撰写《In Search of an Understandable Consensus Algorithm》，并在2014年的USENIX Annual Technical Conference上获得Best Paper Award 。

从论文名称就可以看出作者们有多想表达其他共识机制不好理解，一个好理解的算法最大的优点就是，在工程面上不容易出错，这也导致了2013年后的新系统如果需要强一致性，通常会优先考虑Raft，像是2013年的etcd、InfluxDB、2014年的Consul、IPFS以及2015年的CockroachDB等等；在联盟链链里，通常也会把Raft当共识演算法的选择之一，像是Corda、Quorum以及1.4.1版后的Fabric，虽然Raft不是拜占庭容错演算法，但在大家可以互相信任彼此的情况下，联盟链还是可以以Raft为共识机制。好理解的另一个优势就是实作的人相当多，所以可以找到相当多的参考，甚至是作者参与实作的版本，大家上GitHub搜寻Paxos及Raft，就会发现两者光是在Repostiory数量就有近3倍的差距。

接下来我会介绍Raft演算法的细节，会从节点记录的内容—状态（State）、任期（Term）、日志（Log）及资料状态机（State Machine）开始，接着说明两大模组—领导者选举（Leader Election）及日志复制（Log Replication）。这篇只探讨理论，之后有机会的话，我会再写一篇探讨Hashicorp Raft原始码的文章。

节点状态（State）

在Raft里面，节点有三种状态，分别是—领导者（Leader）、候选人（Candidate）及跟随者（Follower）。Raft属于强领导者模型（Strong Leader），所以一个Raft集群中只能存在一个领导者，其他节点会以领导者为尊，领导者说什么就是什么，这也导致了Raft只能做到故障容错（CFT），而无法处理拜占庭容错（BFT）。

任期（Term）

任期听起来是只有领导者才需要的东西，没错，但是Raft 为了做到故障容错，在集群里面的任一个节点都有可能在领导者故障后成为候选人，并参与领导者选举，所以每个节点都要知道现在的任期。

任期是一个严格递增的数字，Raft是强领导者模型，所以一个任期内至多只会有一个领导者，只有有领导者在的时间，才能对外提供服务。以下图为例，每个任期一开始都是领导者选举（蓝色区段），后面是集群可以对外服务的时间（绿色区段），每一个任期只有在领导者故障后，集群才会发起下一次的选举，所以每次任期的时间长度不固定，也有可能发生领导者选举失败的任期（如t3），代表该任期没有领导者，所以直接进行下一轮的领导者选举。

任期（Term）。图片修改自 In Search of an Understandable Consensus Algorithm。

日志（Log）

日志由索引（Index）、任期（Term）及指令（Command）组成，索引一样是个严格递增的数字，任期在这里代表在哪个任期记录的日志，指令代表要做什么操作。以下图为例，红色框框圈起来的代表「日志索引4 发生在任期2，指令是把x 设定成2」。

资料状态机（State Machine）

State Machine的中文翻译应该是状态机，但这里我们用资料状态机比较好跟节点状态区分。Raft透过日志记录使用者发送的指令，但写进日志只是一个记录，并不代表资料的状态真的改变了，在日志复制那节，我会再说明从新增日志到改变资料状态的条件，但这里我们先知道新增日志跟改变资料状态是两回事。

上一篇有提到CP 模型通常会用两阶段提交（Two-Phase Commit, 2PC），这也是为什么Raft 要把日志跟资料状态机分开的原因，写进日志是第一阶段，改变资料状态机是第二阶段。以下图为例，假设每次新增日志都达成改变资料状态的条件，那资料的状态也会随着日志里的指令而改变。

领导者选举（Leader Election）

上面我们有提到节点有三种状态— 跟随者（Follower）、候选人（Candidate）以及领导者（Leader），以下我们就依据不同的节点状态及每个状态可能会遇到的事件，来理解Raft领导者选举的机制。

跟随者（Follower）

每个节点刚启动时都是跟随者，跟随者会维护领导者心跳信息的计时器（Timer），依据计时器倒数的结果，会有下面两种可能：

继续当跟随者：计时器倒数为0 前，收到领导者心跳信息（Heartbeat）或是候选人投票请求讯息（RequestVote RPC），节点会重置倒数钟继续当跟随者（如下图节点B 跟C ）。 成为候选人：计时器倒数为0 时，都没收到领导者心跳信息，也没有收到其他候选人的讯息，跟随者判定现在集群里没有领导者而发起选举，变成候选人。节点从跟随者变成候选人时会把自己的任期（Term）加一，并投自己一票（如下图节点A）。上面有提到一个任期最多只会有一个领导者，所以节点在发起选举时把任期加一，代表节点认为上个任期已经结束了，进入下一个任期。

候选人（Candidate）

节点成为候选人后会立即向每个节点发出投票请求（RequestVote RPC），并维护一个选举超时（Election Timeout）的计时器，依据投票结果，会有下面三种情况：

成为领导者：只要候选人获得超过半数的票数，候选人就会把自己的状态改成领导者（如下图节点A），并开始对其他节点发送心跳信息。 退回跟随者：候选人在选举期间发现已经有同任期的领导者，或者是更高任期的领导者时，把自己的状态改回跟随者。 选举超时（Election timeout）：当候选人的倒数钟倒数为0 时，自己没办法变成领导者，也没有接到其他领导者的心跳信息，此时节点会判定这次选举失败，开始下一次的选举，候选人会把自己的任期加一，代表新任期的开始，同时把自己的票数重置为1，最后向其他节点再次发送投票请求。

领导者（Leader）

节点在担任领导者期间，会持续向其他节点发送心跳信息，防止其他节点举办选举，但集群也可能因为分区（Partition）而有两个领导者，当分区恢复后，其中一位领导者发现另一位领导者任期比他高时，任期低的领导者会退回跟随者，让集群恢复只有一位领导者的状态。

投票原则

上面是节点在三种状态下可能会遇到的情况，接下来说明节点遇到投票请求（RequestVote RPC）时，会怎么投票：

任期高的不投给任期低，日志索引高的不投给日志索引低的节点，这点是为了确保只有日志最完整的节点可以成为领导者。 若候选人满足上一点，节点会优先投给最早发送投票请求的候选人。 每个节点在一个任期内，只能投一张票。

日志复制（Log Replication）

上面有提到从写进日志（Log）到改变资料状态机（State Machine）是有条件的，这一节会说明Raft如何进行日志复制，并改变资料状态机。由于Raft是强领导者模型，所以也只有领导者可以接收客户端的写入请求进行处理，领导者收到客户端的请求后，会把客户端的指令写进日志，接下来进行发送日志复制请求（AppendEntries RPC）给其他节点，只要领导者收到超过半数的成功回覆，领导者就会执行这条日志的指令（Command），改变自己的资料状态机，并回覆成功给客户端。

上述情况是个理想的情况，但现实中可能因为各种问题，造成每个Follower的日志不一致（如下图）。Raft在日志复制请求（AppendEntries RPC）的设计上，不允许直接复制最新的日志，而跳过中间尚未复制的日志。如下图领导者如果发送索引8的日志复制请求给第一个跟随者，这个跟随者目前最新的日志只有到索引5，所以会拒绝领导者的请求，此时领导者会继续发送索引7的日志复制请求给第一个跟随者，跟随者一样会拒绝，直到领导者发送索引6的日志复制请求给第一个跟随者时，跟随者才会接受，并从索引6开始重新同步到索引8。

所以如果Raft 集群要对外服务，则至少要有一半以上的节点有完备的日志记录时，才可以对外服务，因为没有完备日志记录的节点，就无法对最新写进日志的要求回覆成功。

Raft 设计巧思

说完了Raft 运作的机制，我们回过头来看Raft 设计上的两个巧思— 选举超时时间随机、两阶段提交优化以及分区容错。

超时时间随机（Randomized timeout）

从跟随者到候选人的GIF 可以发现，每个节点的计时器倒数的时间是不一样的，所以有的节点比较快变成候选人，有的则还在倒数，这样的设计是为了避免节点们同时发起投票，导致票数分散，进而造成选举失败，大家还记得上面有说，每个选举任期只有在有领导者之后才能对外服务，所以Raft 要尽量保证选举可以成功，另外为了避免节点频繁发起选举，Raft 论文建议把超时设定在150–300ms 之间。

两阶段提交优化

在上一篇我们有提到，两阶段提交应该要在集群都完成执行阶段（Commit Phase）后，才回覆给客户端，不过在Raft 里面，只有领导者完成了执行阶段就回覆给客户端了，所以等于省略的一半的讯息传播，这是Raft 的一个优化。

不过大家一定会想，那跟随者们怎么知道什么时候可以进行执行阶段大家还记得我们前面提到的心跳信息吗其实心跳信息也是日志复制请求信息（AppendEntries RPC），而日志请求信息里面会带leaderCommit，代表领导者目前最新进入执行阶段的日志索引（Index），所以领导者在传播心跳信息时，不仅是通知跟随者们不要发起选举，同时也在进行日志复制以及同步资料状态机（State Machine）的状态，借此降低过多的信息量。

分区容错（Partition Tolerance）

大家经过上一篇后，一定会好奇Raft怎么处理分区容错的问题，以下面的GIF为例，Raft集群再发生分区后，确实可能产生两个领导者，导致脑裂的问题，不过我们上面有提到，日志复制只有在大多数节点成功响应之后，领导者才会回传成功给客户端，所以不管分区怎么切，至多只会有一个分区有超过一半的节点，因此也只有一个领导者可以继续对外服务，其他的领导者即使接到客户端的请求，也只能回覆失败。

总结

上一篇我们提到，两阶段提交可以让集群内大多数节点的状态维持一致，达到强一致性，Raft对经典的两阶段提交做了优化，让达成强一致性的流程更为简单；在拜占庭容错算法PBFT里，则是把两阶段提交提升为三阶段提交，透过改变流程避免部分节点作恶，造成无法共识。

希望经过这篇文章，可以让读者理解Raft 演算法的运作方式，Raft 在2014 年发表后就迅速获得许多系统采用的其中一个原因就是好理解，另一个原因是Raft 在实作上完美的与系统解耦（Decouple），让系统可以基于Raft 做开发，其他共识机制像是Zookeeper 的ZAB，在发表之初就是为了Zookeeper 服务的，所以其他系统比较难基于ZAB 之上做开发。

Raft在线上有许多教材及各种语言的实作版本，大家如果有想进一步了解，很推荐直接看论文，如果大家觉得直接看论文太刺激的话，也可以看作者在伊利诺大学（University of Illinois Urbana -Champaign）亲自讲解Raft的影片，最后如果想深入原始码研究的话，可以研究Hashicorp的版本，原因是这个版本已经被应用在各大系统如Consul、IPFS及InfluxDB。