从故障发生的角度看raft算法

raft算法是一种保证数据高可用的一致性算法，它和 Paxos 算法 相比，提供了相似的功能和性能，但是提供了更好的阅读成本，因此在推出之后便受到了业界较大的欢迎。其最为显著的特点就是强化了Leader的作用，来减少了处理一致性问题时的多状态的复杂性。比较著名的etcd，TiKV都使用它进行数据一致性的保证。本文尝试从故障发生的视角来解析一下这个算法。

1 起源：复制状态机的实现

一致性算法的出发点是解决分布式的环境下，如何让多台机器作为一个整体进行工作，当其中的某一些机器发生故障时，整体系统的数据不会发生错乱，系统可以正常继续正确工作下去。于是就产生了复制状态机的理念，在一组服务器中产生多个具有相同状态的副本，在其中的某些机器宕机之后其他的机器还能正常地运行。

大多数的复制状态机由图中的三大部分组成，分别是一致性协调模块，日志模块以及应用的状态机。通过一致性协调模块来保证集群中的各个机器上的日志模块的内容是一致的，而日志模块是由一系列的执行指令序列来组成的，因此如果所有的机器都按照日志模块的指令顺序进行应用，那么最后状态机里面的各个状态肯定也就是一致的了。这种实际使用的复制状态机系统通常都有如下几个特性：

• 安全性保证（保证不会对客户端返回一个错误的结果）
• 可用性 只要集群中的大部分机器是可用的，那么集群就可以对外提供服务
• 不依赖时序保证一致性 网络的延迟或者时钟的错误只有在极端错误的情况下才会对系统产生影响

2 raft的基础

raft也是采取了上述的状态机的模型，只是它使用了强领导人的机制，在集群中选择一个领导者，只由领导者从客户端接收处理数据，并将该数据复制到其他从属者的机器上，并在安全性的各种机制的保证下，让这些状态在所有的机器上来进行应用。当领导者出现问题的时候，会从集群中再推选中一名新的领导者，来重新进行集群的管理。下面我首先对raft的一些基本的概念进行一下介绍。

2.1 raft角色和转换关系

raft中的角色主要包含三种，分别是领导者Leader ，待选者Candidate和跟随者Follower。其中，领导者的作用刚才也大概介绍了，它是raft的集群的主要负责人，从客户端接收消息，并进行日志复制，和数据应用。同时一个领导者来需要通过不停的发送append消息来确保其跟随者与其保持一样的状态。跟随者是当前集群的从属者，被动地接收来自于Leader的消息，时刻保证自身的日志和Leader一致，并查看是否有可以应用的条目并进行应用。在一个正常的集群中，其实只有领导者和跟随者两个角色的，但是当系统发生故障的时候，尤其是老的领导者的机器发生故障的时候，就会重新进行领导者的选举，下面会详细的讲述一下，这个时候就会有待选者的角色。待选者是从跟随者到领导者的过度状态，确保集群中可以选择有且只有一个领导者。其转换关系可以用一个论文的图来展示一下：

当系统在初始情况下，都是跟随者，当跟随者超时没有收到领导者的信息之后就会进入待选者的状态，而待选者会随机一个等待时间，等时间到之后就会提高任期，并发起投票来竞争领导者，如果某一个待选者收到了大多数的选票，这个待选者就是成为领导者。而如果一个领导者接收到了一个比自己还大的任期，就会从领导者转换为跟随者。一个待选者如果接收到了一个领导者发送来的消息或者一个新的任期的话，也会立即转变为跟随者的状态。

2.2 raft功能组成

raft的主要内部功能包含如下几个部分，分别是领导者的选举，日志的复制，集群成员的变化以及日志的压缩。

2.2.1 领导人选举 首先来说一下领导人的选举过程。在raft协议中，时间是按照任期的形式来进行分片的。开始时进行选择产生第一个任期，然后任期开始，直到这个任期的领导人出现问题之后任期结束，进行下一次的选举过程，产生新的任期，但是在极端情况下，某一个选举有可能是不成功的，因此会重新选举一次，直到选出一个新的领导者，也开辟一段新的任期。

在所有的服务器中，也会保存有当前的任期号，在相互之间的通信中，通过比较任期号的大小，可以进行上述的角色之间状态的转变。

在任期最初的领导人的选举中，刚才也提及到，当一个跟随者在一段时间内没有接收到领导者的任何信息时，就会进入到待选者的状态，于是它就准备发起选举来竞争性的领导者，这个类似于电路中的看门狗电路的作用。开始选举的时前，它会提高自己当前的任期，然后发送投票给集群中的所有其他可投票的节点，但是raft不是立即发送投票消息的，而是待选者随机一段很小的时间（大概为几百毫秒）之后再进行发送，这样可以防止很多的待选者同时发送投票消息导致所有的选票被瓜分，进行导致选举失败的情况。这样在绝大部分的情况下，只有一个服务器会去进行选举，而其他待选者在超时之前新的领导者就已经建立，并立即重新进入到跟随者的状态中，这是一个非常简洁但有效的领导人选举的方式。

当一个待选者发送往投票通知之后，可能会面临着多种情况：

1） 获得大部分的选票，选举成功，成为新的领导者，此时它需要立即给其他服务器发送心跳包来维持领导者的角色， 阻止其他的领导者的产生。

2）接收到来自于其他新的领导者的消息，立即成为一个跟随者。

3）其他的服务器并不认可自己成为领导者，这时待选者会继续等待自身的超时，然后重新提高任期号，进行下一轮的选举。

2.2.2 日志复制

当领导者接收到了客户端的数据变动要求时，就会在本地的日志先附加上日志记录，然后将日志转发给所有的跟随者来进行日志的复制，当日志被安全地复制到大多数的跟随者机器上之后，领导人就会去应用这个状态并将结果发送给客户端。其日志在各个机器的存储基本结构主要如下所示：

一个日志系统中最为关键的信息是日志的索引号，日志序列按照索引号单调线性地往上增长，还有在日志中的每一个改变序列都会保存当前的任期号信息。另外一个比较重要的就是提交索引号，由于每个机器的数据应用是一定按照顺序从前向后的应用，因此有一个提交索引号用于标识当前提交到的地址。需要注意的是日志的流动是一定要从领导者到跟随者的方向。日志复制是保证一致性的根本所在，其可以出现各种各样的不一样的错乱的问题，我们后面专门来讲述。

2.2.3 集群成员变化

一般的一个raft的集群的机器总数都是固定的，但是也可能存在这种情况，有些机器坏的比较彻底了，需要新补充一些进入到这个集群，因为为了保证动态新补充成员的能力，raft还提供的成员变化的能力。在新增加成员的时候，主要面临的是可能新老机器中会出现不一样的状态的情况，这个问题在raft的论文中解释了比较完整，这里不作为这个文章讲述的重点，就不展开了。

2.2.4 日志压缩

当一个raft集群运行了很长时间之后，就会产生大量的日志信息，正常也就占用了大量的空间，因此，raft提供了利用快照的方式来进行日志数据的压缩，即把一段时间内产生的日志日志，归结为一系列的状态量，然后只需保存这些个状态量，以及这个状态量之后的日志信息即可，这个类似于数据库的快照的处理方式，不同的就是要保证各个机器产生的压缩内容也都是一致的。

3 约束以及产生的特性

3.1 raft五大原则

上面介绍了raft的一些基本的内容，下面解释一下raft是如何保证数据的一致性的。首先，raft协议要求保证下面的5大原则。

1）选举安全特性其实是通过了选择中具体的操作来确定在一次的选举中只有一个领导人被选择出来，因为一个强有力的领导人是整个raft集群可以正常工作的基础。

2）领导人的只附加原则是指所有的信息流都是从领导者流入到跟随者中，这样可以保证领导者自身的数据的一致性，保证了不会出现领导者已经应用的日志被出现更改的情况。

3）日志匹配原则，其实是两个原则的组合体：

• 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
• 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。

当领导者把自身的日志信息复制到跟随者中去时，还会携带上一次的任期号和索引号，每个跟随者接收到的时候会去check一下之前日志序列中的任期号和索引号是否是一致的，如果不一致的话，则告诉领导者当前的日志复制失败，于是领导者会再将之前的日志序列来和这个跟随者对齐，直到能到完全匹配到为止，我们称这个过程为raft的日志匹配过程，这个过程也就是上述原则可以保证的一个具体的实现了。这个原则也就保证了跟随者的日志是可以和领导者是一致的。

4）领导人的完全特性则是说新的领导人肯定是拥有之前的领导人的提交提交应用的日志条目信息的。这个主要是防止在领导人发生关系转化的时候已经应用的日志一定是不会发生变化的。它的具体的实现途径是靠选举的投票，选举的投票并不是谁要投票，一个跟随者就投票给他，而是投票给比自己更新的待选者，反过来说，只有那些更加新的待选者可以获得获得绝大多数的选票进行成为一个合格的领导者。

5）状态机安全特性则是说，当一个领导者应用到一个日志条目后，其他的跟随者也会去应用到这个条目为止，这个是依靠领导者的信息同步来决定的。

综上可以看到，这五条原则约束联合起来共同作用可以来保证整体的数据的一致性。

3.2 具体的执行行为

所有服务器：

• 如果commitIndex > lastApplied，那么就 lastApplied 加一，并把log[lastApplied]应用到状态机中（5.3 节）
• 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，那么就令 currentTerm 等于 T，并切换状态为跟随者（5.1 节）

跟随者（5.2 节）：

• 响应来自候选人和领导者的请求
• 如果在超过选举超时时间的情况之前都没有收到领导人的心跳，或者是候选人请求投票的，就自己变成候选人

候选人（5.2 节）：

• 在转变成候选人后就立即开始选举过程
  • 自增当前的任期号（currentTerm）
  • 给自己投票
  • 重置选举超时计时器
  • 发送请求投票的 RPC 给其他所有服务器
• 如果接收到大多数服务器的选票，那么就变成领导人
• 如果接收到来自新的领导人的附加日志 RPC，转变成跟随者
• 如果选举过程超时，再次发起一轮选举

领导人：

• 一旦成为领导人：发送空的附加日志 RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以阻止跟随者超时（5.2 节）
• 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端（5.3 节）
• 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex，那么：发送从 nextIndex 开始的所有日志条目：
  • 如果成功：更新相应跟随者的 nextIndex 和 matchIndex
  • 如果因为日志不一致而失败，减少 nextIndex 重试
• 如果存在一个满足N > commitIndex的 N，并且大多数的matchIndex[i] ≥ N成立，并且log[N].term == currentTerm成立，那么令 commitIndex 等于这个 N （5.3 和 5.4 节）

4 从故障的角度看raft集群运行过程

下面从实际集群运行的两个阶段来介绍一下故障发生时的raft集群的处理方式。

4.1 集群选举阶段

集群在选举阶段，不管是否有机器发生故障，都会按照选举的原则来产生新的领导，也就是如果有新的领导产生出来，那这个新的领导，一定是获得了大多数的成员的认可，并且自身携带有较新的日志信息，且包含有之前的所有的提交信息。

4.2 集群工作阶段通常情况

集群的工作阶段，如果有跟随者发生了故障，只要发生故障数量较小，不会影响到日志复制的大多数的原则，那么整体功能是不受影响的，领导者回去不停地重试，尝试去附加信息给那些挂掉的跟随者。

集群工作阶段，如果领导者发生了故障，会进行重新的领导选举，产生新的领导者。

4.3 数据处理全过程中发生故障

我们再理一下客户端修改数据的全过程，由客户端上行消息给领导者，领导者自身日志append之后，再交由其他的跟随者去附加日志，在收到大多数的节点日志附加成功之后，再提交该日志进行应用，并最后返回给客户端。在这个过程中：

4.3.1 如果客户端上行消息到领导者，领导者还没有任何处理就挂掉，没有影响，重新选举即可

4.3.2 如果客户端上行消息到领导者，领导者附加日志成功之后，然后故障了，客户端不会收到响应，同时会选择一个新的领导者，这个领导者会用它的日志来更新到这个老领导者的错误日志

4.3.3 如果客户端上行消息到领导者，领导者附加日志成功之后也发送给了其他的跟随者了，这时候领导者故障了，这个时候新的领导者选举出来，由于是最新的那个节点，所以也获得了之前的日志记录，这个时候新的领导者是不会去处理这条日志记录的，它会去把自己的日志再流转给其他的服务节点，等到下一个日志记录可以提交的时候，才会一并地把这个日志记录也提交上去。

4.3.4 如果领导者附加日志成功，也发送给其他跟随者，但是这时大部分跟随者故障了，领导者没有接受到大多数的日志复制返回，这时领导者不会去进行处理，也就不会去给客户端返回，日志也就存在于少部分的机器上面，这个时候假设有新的跟随者由存活了，这时，领导者的附加日志通知又会把这个记录附加给这些跟随者，但是仍然不会去提交。对于客户端而言，是有可能收不到服务器的响应的，而收不到响应的同时有可能服务器已经在大部分的机器上进行了日志的复制，并应用到状态机了，因此，raft协议此时要求客户端进行重发机制，客户端重发的时候带上一个序列号，如果服务器进行执行过该指令存在于日志中，则执行返回结果，否则的话，再执行一次。

4.3.5 如果领导者也接收到了大部分的日志复制响应，还没有应用到状态机就挂了，或者是感刚刚应用完状态机还没有给客户端响应就挂了，这个和刚才的情况一样，客户端收不到响应重试，集群重新选择领导者，这个领导者一定有这条日志记录，并在下一次地数据变动的时候提交应用改记录。

4.3.6 一切都顺利进行，给予了客户端响应回包。

4.4 异常的积累之后和其他特殊情况下的影响和消除

4.4.1 多次异常后的日志混乱情况

当我们的领导者进行了反复地更换，更为严重的是，如果一个领导者选举出来后，刚处理者请求就又发生了故障，就有可能导致其自身以及其他跟随者的日志状态出现非常严重的混乱。这个时候选择出来一个新的领导者之后，应该如何处理这种混乱呢。日志可以分为如下的几种情况。

上图中出现了可能日志比当前的领导者短的情况（挂了感刚刚起来），比当前领导者提前的情况（领导了一段时间，刚写了本地日志就挂了），和当前领导者日志差异很大（领导了一段时间挂了，又领导又挂）等等情况，这个时候，之前的日志匹配原来在这里就可以发挥作用了，根据日志从领导者流入跟随者的原来，所有的跟随者都会和领导者慢慢进行日志的匹配，直到和当前的领导者日志达到一样为止，其实在实际过程中，不会一下子出现这么多的不一致，而是出现其中的个别现象，因此raft的日志匹配是非常迅速而且是高效的。

4.4.2 新当选的领导者提交上一任期的日志的约束

另外一个值得注意的就是上一个任期的没有提交的日志条目的问题，其实，新当选的领导者之后不要直接提交，而要等到当前任期的时候有新的条目可以提交的时候再去一起提交。

这个约束来源于上述图中的问题，假设

• 首先s1是领导者，并将2号日志复制到s2上
• 然后s1挂了，s5作为了新领导者，处理一个请求，日志没有复制完就又挂了
• 然后s1当选新领导者，并将3号日志复制到了s3，并处理请求本地附加了日志4

这个时候3号日志已经在绝大部分的机器上复制了，s1要不要提交这个日志呢，如果提交了的话，接着s1挂掉，s5是有可能当选为新的领导者的，此时它就可能将自己的3号日志再复制到其他机器上，就会把已经提交的2号日志给覆盖了，影响了一致性的原则。所以raft要求对于新领导者遇到了老的term的日志，先不用急着提交，等到自身有其他的日志可以提交的时候再一起提交，因为如果如图中4号日志也可以提交的时候一起提交，那么就算这个时候s1挂掉，那么s5也没有机会选举为新的领导者了，于是之后它的日志也会被最新的日志给覆盖掉。

4.4.3 脑裂问题

脑裂是由于在分布式环境下，节点之前的网络存在故障导致出现多个网络分区，这时候在自动选主的条件下就有可能产生脑裂现象。如下图所示，在一个raft集群中假设有5个节点，其中3个节点在一个机房内，另外2个节点在另外一个机房。假设先开始2个节点中的5号节点是集群的领导者，集群正常工作着。当这两个机房之间的网络出现故障了，于是其中一个机房的3节点就是超时开始自动选主，这是其中的一个节点按照多数选票的原则是有可能被选为领导者的，而原先的领导者却浑然不知，于是就出现了双主脑裂现象。

raft协议对这种情况的处理是，虽然出现了双主，但是由于老的领导者是不可能在数据复制阶段拿到大多数的确认的，所以老的领导者将不能够正常地写入数据，而新的领导者是可以正常写入数据的，当两者之间的网络恢复正常之后，老的领导者接收到了比它任期大的领导者发的消息，就会自动地转换为了跟随者，集群也就恢复了正常的状态。这里面可能出现的问题就是客户端是有可能从老的领导者分区中读取到老的数据的，这个在一般的情况下也是可以接受的。

5 总结

raft这类的一致性协议是分布式系统构建的一些基本理论，本文介绍了raft的基础，并对raft协议从故障发生的角度进行了解读，并介绍了raft用于保证其数据一致性设计的缘由。如果大家看到文中出现的一些问题，欢迎指正。