彻底搞懂 Raft 算法

前言

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

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

由于强一致性在某些场景是必须要被保证的，像是金融支付、票务系统等等，所以本篇会介绍强一致性系列的算法。

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 等等；好理解的另一个优势就是实现的人相当多，所以可以找到相当多的参考实现，大家上 GitHub 搜寻 Paxos 及 Raft ，就会发现两者光是在 Repostiory 数量就有近 3 倍的差距。

接下来我会介绍 Raft 算法的细节，会从节点记录的内容 — 状态（State）、任期（Term）、日志（Log）及数据状态机（State Machine）开始，接着说明两大模组 — 领导者选举（Leader Election）及日志复制（Log Replication）。

节点状态（State）

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

任期（Term）

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

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

日志（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）

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

两阶段提交优化

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

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

分区容错（Partition Tolerance）

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

总结

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

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

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