作者：杨冬 欢迎转载，也请保留这段声明。谢谢！
出处：https://andyyoung01.github.io/ 或 http://andyyoung01.16mb.com/

Raft是一个比Paxos更易理解和实现的分布式一致性算法。它允许一组机器像一个整体一样工作，即使其中一些机器出现故障也能够继续工作下去。

分布式系统中的一致性算法可以使系统中的各个agents保持一致的值，并且可以从这些agents当中选举出一个leader。Paxos和Raft是两个比较知名的一致性算法。它们有类似的性能，不过Raft更简单一些，更容易理解，所以在分布式存储实现中更加流行。Consul和Etcd就是在Raft算法的基础上实现的。

1. Raft基本概念

1.1 角色

一个Raft集群包含若干个服务器节点。在任何时刻，每一个服务器节点都处于这三个状态之一：跟随者Follower、候选人Candidate或者领导人Leader。

• Follower：刚启动时所有节点为Follower状态，响应Leader的日志同步请求，响应Candidate的请求。
• Candidate：Follower状态服务器准备发起新的Leader选举前需要转换到的状态，是Follower和Leader的中间状态。
• Leader：集群中只有一个处于Leader状态的服务器，负责响应所有客户端的请求。

三者之间的转换关系如下图所示：

后面会结合选举过程来详细看看角色转换的过程。

1.2 Term（周期）

如下图所示，每个Term由选举开始，在这个时间内若干处于Candidate状态的服务器竞争产生新的Leader（图中蓝色部分）。如果某个服务器成为了Leader，那在接下来的时间便成为一般的操作时间（图中绿色部分）；如果没有选举出Leader（图中t3），则Term递增，开始新一任期选举。每次Term的递增都将发生新一轮的选举，Raft保证一个Term内最多只有一个Leader。

2. Raft协议步骤

2.1 Leader选举

• 当整个系统启动时，所有节点都是跟随者身份。经过一段时间跟随者没有接收到任何消息，也就是选举超时，然后他就会认为系统中没有可用的领导者，他就将身份变换为候选人。然后开始进行选举以选出新的领导者。这个选举超时时间为150ms到300ms之间的随机值。
• 在选举之前，Follower增加其Term编号并改变状态为Candidate状态，然后向集群内的其他服务器发出RequestVote RPC，这个状态持续到发生下面三个中的任意事件：
  1. 它赢得选举：Candidate接受了大多数服务器的投票，成为Leader，然后向其他服务器发送心跳告诉其他服务器。
  2. 另外有服务器获得选举：Candidate在等待的过程中接收到自称为Leader的服务器发送来的RPC消息，如果这个RPC的Term编号大于等于Candidate自身的Term编号，则Candidate承认Leader，自身状态变成Follower；否则拒绝承认Leader，状态依然为Candidate。
  3. 一段时间过去了，没有新的Leader产生：出现这种情况则Term递增，重新发起选举；之所以会出现这种情况，是因为有可能同时有多个Follower转为Candidate状态，导致分流，都没有获得多数票。
• 如果Follower经过一段时间没有收到任何心跳信息（心跳超时），则可以认为Leader不存在，需要进行Leader选举；如果系统中存在Leader，Leader会周期性的发送心跳来告诉其他服务器它是Leader。
• 一个服务器节点要想继续保持着Follower状态除非他从Leader或者Candidate处接收到有效的RPCs。
• 一旦候选人赢得选举，他就立即成为领导人。然后他会向其他的服务器发送心跳消息来建立自己的权威并且阻止新的领导人的产生。
• 如果某个Leader发现集群中有Term编号大于自身Term编号的Leader时，便改变其Leader身份成为Follower。

2.2 Log复制

Log复制主要作用是用于保证节点的一致性，这阶段所做的操作也是为了保证一致性与高可用性；当Leader选举出来后便开始负责客户端的请求，所有请求都必须先经过Leader处理，这些请求或说成命令也就是这里说的日志。Leader接受到客户端命令之后，将其追加到Log的尾部，然后向集群内其他服务器发出AppendEntries RPC（也作为心跳信息），这引发其他服务器复制新的命令操作，当大多数服务器复制完之后，Leader将这个操作命令应用到内部状态机，并将执行结果返回给客户端。
如下图所示的Log结构图：

每个Log中的项目包含2个内容：Term编号（方框上部的数字）和操作命令本身；还有一个全局的Log Index来指示Log项目在Log中的顺序编号。当大多数服务器在Log中存储了该项目，则可认为该项目是可以提交的，比如上图中的Log Index为7之前的项目都可以提交。
在最后面参考资料的动画演示中，也展示了当网络出现问题，导致整个集群分区成两个部分，然后又恢复后，日志的复制过程。

2.3 安全性

安全性是用来保证每个节点都执行相同序列的安全机制，如当某个Follower在当前Leader提交命令时不可用了，稍后可能该Follower又会被选举为Leader，这时新Leader可能会用新的Log覆盖先前已提交的Log，这就是导致节点执行不同序列；安全性就是用于保证选举出来的Leader一定包含先前已经提交Log的机制。
为了达到安全性，Raft增加了两个约束条件：

1. 要求只有其Log包含了所有已经提交的操作命令的那些服务器才有权被选为Leader。
2. 对于新Leader来说，只有它自己已经提交过当前Term的操作命令才被认为是真正的提交。

3. 参考资料

• Raft动画演示
• 寻找一种易于理解的一致性算法（扩展版）
• 英文论文原文下载