分布式一致性协议之Raft

Raft 算法解决的核心问题是在分布式环境下如何保持集群状态的一致性，简而言之就是一组服务，给定一组操作，最后得到一致的结果。

Raft 算法通过选举 领导人（leader） ，由领导人复制 日志（log） 到 跟随者（follower） ，跟随者执行日志指令来达到最后集群状态的一致，整个算法也分成了两部分，领导人如何选举和跟随者如何安全的执行日志指令。

领导人选举

Raft 算法中一个节点在任意时刻只能处在 领导人（leader） ， 候选人（candidate） ， 跟随者（follower） ，同时强调强领导来简化整个流程，所以他的日志数据流只能从领导人复制到跟随者，跟随者之间也不能传递日志。

通常情况下，系统中只有一个领导人并且其他节点全部都是跟随者，跟随者都是被动的，他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求

下面是三个状态的状态转换图；

节点启动的时候，都是跟随者状态，在一段时间没有收到来自领导者的心跳，就从跟随者转变为候选人，发起选举；如果收到含自己的多数选票则转换到领导者；如果发现其他节点比自己更新，则切换到跟随者状态。为了确定其他节点比自己更新， Raft 又引入了 任期（term） 的概念。

算法起始，任期是0，当有节点当选 领导者 时，任期号为 1 ，新领导人选出后，任期在之前的任期号加 1 。当节点从跟随者转化为候选人的时候，任期号也要增加 1 。

任期起到逻辑时钟的作用

选举流程

当一个跟随者节点长时间没有收到领导者心跳包，猜测领导者节点可能挂了，发起新领导者节点选举。

• 增加自己当前的 任期 ，转换状态到 候选人 ；
• 投自己一票，并且给其他节点发送请求给自己投票的请求；
• 等待其他节点回复，在等待过程中又可能发生下面的情况
  1. 赢得选举，成为领导者；
  2. 被告知其他节点当选领导者，自己退回跟随者状态；
  3. 超时时间没有收到足够多的选票，则重复整个选举过程；

下面的这个gif就展示了这个过程；

日志复制

当选出了 领导人 系统就可以对外提供服务，客户端把请求发送给集群，如果是跟随者收到则转发给领导者，由领导者统一处理，领导人会调度这些请求，顺序告知所有跟随者，保证所有节点的状态一致。

Raft 是基于复制状态机实现的，其核心思想就是 相同的初始状态 + 相同的输入 = 一致的最终状态 ，领导者将客户端请求打包到一个个 log entry ，将这些 log entries 发送到所有跟随者节点，然后大家按相同顺序应用 log entry 中的命令，则状态肯定是一致的。

复制流程

log entry
log entry
log entry
log entry
log entry

每个 log entry 中，除了需要执行的命令之外还有领导者节点的任期号，用于处理异常情况；同时我们也可以看到，当日志被复制到大多数节点，即可向客户端返回成功的消息，一旦返回了结果，就必须保证系统在任何异常情况都不会发送回滚。

Raft 通过第一个阶段的 commited 和第二个阶段的 apply ，保证了状态机的一致性。

当然还有各种异常情况，我们下面讨论当节点崩溃的情况下会有一些异常，影响状态机顺序的执行相同的指令。

领导人选举安全（Election safety）

选举安全性，即在一个任期内最多一个 领导人 被选出，如果有多余的领导人被选出，则被称为 脑裂（brain split） ，如果出现 脑裂 会导致数据的丢失或者覆盖。 Raft 通过下面两点保证了不会出现 脑裂的情况 ；

• 一个节点某一任期内最多只能投一票；
• 只有获得大多数选票才能成为领导人；

通过增加约束避免了 脑裂 的情况出现，保证了同一时间集群中只有一个 领导者 。但是当一个节点崩溃了一段时间，他的状态机已经落后其他节点很多，突然他重启恢复被选举为 领导者 ，这个时候，客户端发来的请求再经由他复制给其他节点的状态机执行，就会出现集群状态机状态不一致的问题。

其他算法可能会同步落后的日志给领导者，然后在由领导者复制日志给其他节点，但是 Raft 认为这样会增加算法的复杂性，直接放弃了这种方法，而是采用 拒绝 投票给那些日志没有自己新的节点。

通过比较两份日志中，最后一条日志条目的索引值和任期号，来定义谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更新。如果两份日志最后的条目任期号相同，那么日志比索引大的日志新。

拒绝 日志比自己旧节点投票是基于这样一种思考，要当选领导者，就必须获得大多数节点的选票，意味着他必须至少比大多数节点的日志新或者一致，这样拒绝比自己旧日志节点的投票请求，就保证了状态比大多数节点落后的节点是不会当选领导者。

如果一个 领导者 把日志复制到大多数其他节点，在应用到状态机之前崩溃了，新选出的领导者，是不知道被复制到大多数节点的日志是否应用到了状态机。

(a)中，S1 是领导者，部分的复制了索引位置 2 的日志条目；

(b)中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处；

(c)中，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交；

(d)中，S1又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。注意： 虽然s2复制日志过半，但是S5节点的任期号大，日志新，是可以接收S2选票 ；反之S1在崩溃前把新接收到的日志复制到大多数机器中，如(e)所示的情况。

(e)中那样，那么在后面任期里面这些新的日志条目就会被提交（因为S5 就不可能选举成功）。 这样在同一时刻就同时保证了，之前的所有老的日志条目就会被提交。

候选者和跟随者安全性

候选者 ， 跟随者 奔溃以后，领导者就是简单的周期性的发送 RPC 请求，如果重启发生在节点处理完日志复制，响 RPC 请求之前，收到一样的 RPC 请求正常返回即可，没有任何问题。如果崩溃时间太长，重启以后落后其他节点日志太多，将会采取 快照 的方式进行恢复。

Raft 的 RPC 请求是幂等的。

可用性

Raft 的要求之一就是安全性不能依赖时间：整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果。但是，可用性（系统可以及时的响应客户端）不可避免的要依赖于时间。这个时候就又会有一些限制；

• 服务器故障的时间必须比消息交换的时间长，否则每当一个节点要收集到足够多选票的时候就宕机了，新一轮的投票又重复这个过程，导致足够的时间选出领导人。

• 广播的世界必须小于选举超时时间一个数量级，这样领导者才能发送稳定的心跳阻止跟随者进入候选人状态。

• 当领导者崩溃后，整个系统在大约等于选举超时时间中不可用，所以平均故障间隔时间要大于选举超时时间几个数量级，系统可用性才比较高。

  一般来说，广播时间在10毫秒左右，选举超时时间在300毫秒左右，服务器平均故障时间都大于一个月。

本文作者是深入浅出区块链共建者清源，欢迎关注清源的 博客 ，不定期分享一些区块链底层技术文章。

深入浅出区块链 - 打造高质量区块链技术博客，学区块链都来这里，关注 知乎 、微博。