30分钟了解Raft算法

Raft算法是什么

当存储系统单点部署时，单个节点出故障就会导致数据丢失、系统不可用等问题，因此各大公司用于生产的存储系统一般都会部署多个节点。分布式系统最大的挑战是数据一致性问题，即需要保证多个不同节点上的数据保持一样。

最简单的分布式存储系统如上所述，有一个master节点和slave节点，client的写入操作全部到master，读取操作可根据需求选择master和slave节点。该方案能够较好的解决数据一致性问题，但是引入了另一个问题，当master挂掉时，存储系统将不可用。

Raft是一个共识算法（Consensus Algorithm），它保证当集群中小于一半的节点挂掉时，存储系统仍然可用。单个Raft节点由三部分组成：

• 共识模块
  • 接收请求，并复制到所有节点；当一个请求被超过一半的节点接收时即commit（也就是应用到状态机中，代表请求成功）
• 日志
  • 请求以日志的形式写到磁盘中，保证数据不丢
• 状态机
  • committed的日志以相同的序列进入多个节点的状态机后，将得到相同的结果，这个机制保证不同节点的存储数据是相同的
    在系统运行正常时，Raft集群跟上面的简单一主多从集群非常相似，但是当主节点挂掉时，Raft算法可以自动选出新的主节点，保证集群可用性。

Raft算法将共识问题分解成以下三个子问题：

• 选主
  • 一个集群中同一时刻有且只有一个Leader，当原来的leader挂掉时，新的leader马上会被选出来
• 日志复制
  • leader接收client的请求且将日志复制给follower
• 安全性
  • Raft算法保证，当任何一个节点将某条日志应用到状态机之后（也就是committed），那么所有节点都将保证这个index的日志是同一条（这里又引入了一个日志index的概念，后续会介绍）

选主

节点的状态

每个raft节点的状态会在follower、candidate、leader之间转变。

• 节点启动时状态为follwer
  • 当一段时间之内，没有收到来自leader的心跳，则转变为candidate
  • 如果收到leader的心跳，则维持follower
• candidate将向所有节点发起选举，
  • 如果在选举过程中，发现leader已经存在，则变回follower
  • 如果选举成功，变为leader
  • 如果选举不成功，但是又没收到来自leader的心跳，则term+1，继续下一轮选举
• leader将向所有节点发送心跳，维持自己的leader地位
  • 如果发现有更高term的leader存在，则变为follower

这里又引入了一个term的概念。raft算法保证，同一个term最多只可能存在一个leader，这是由Raft的选主机制决定的，下一节会细讲。

节点间RPC通信

为了说明选主过程，我们需要引入两个rpc方法。

一个用于竞选，叫做RequestVote

message RequestVoteRequest {
    int64 term = 1;
    int64 candidateId = 2;
    int64 lastLogIndex = 3;
    int64 lastLogTerm = 4;
}

message RequestVoteReply {
    int64 term = 1;
    bool  voteGranted = 2;
}

一个用于心跳（以及后续会讲到的日志复制），叫做AppendEntries

message AppendEntriesRequest {
    int64          term = 1;
    int64          leaderID = 2;
    int64          prevLogIndex = 3;
    int64          prevLogTerm = 4;
    repeated Entry entries = 5;
    int64          leaderCommit = 6;
}

message AppendEntriesReply {
    int64 term = 1;
    bool  success = 2;
}

message Entry {
    int64  operation = 1;
    string key = 2;
    string value = 3;
    int64  index
}

选主的过程

以五个节点的集群为例：

1）初始状态下，所有节点的term都为1，状态都为follower，同时开始一轮倒计时。如果在倒计时结束前，follower收到RequestVote或者ApependEntries的请求，且请求中的term大于等于follower的term，则保持follower状态。如果倒计时结束，没有收到请求，则转变为candidate。这里有一个细节，每个节点的倒计时时间是随机的，有快有慢，所以会有节点先于其他节点成为candidate。

2）有一个节点先于其他节点成为candidate，向剩余节点发送RequestVote，它需要得到多数票才能成为Leader。另外一个follower在一个term里只能投票给一个candidate，由此可以保证一个集群在一个term里只有一个leader。

3）成为leader后，需要向其他节点不断发送心跳，维持leader地位。
 

4）如果其他pod收不到心跳，则会认为leader挂了，则会term+1并转变为candidate参与竞选。图中2号leader挂掉，3号成为新leader。

5）此时如果2号leader又活过来了，它会收到来自其他leader的term更大的心跳，转变为follower。

日志复制

竞选成功后，leader需要承担起日志复制的责任。

一次成功的日志复制过程

1）leader收到请求，写入自身日志，然后使用AppendEntries命令发送给followers。这条日志目前处于uncommitted状态，图中用虚线表示。这里注意，每条日志都会带上term和index信息，确保唯一性。

2）follower收到请求，反馈给leader成功。当leader确认大于一半的节点成功复制日志后，这条日志就转变成committed状态，可以提交到状态机里了，图中用实线表示。

3）在下一次心跳时，leader把commited信息告知各节点。

raft如何保证日志的一致性

1）Raft 保证：如果不同的节点日志集合中的两个日志条目拥有相同的 term 和 index，那么它们一定存储了相同的指令。这是因为：每一个term最多只会选出一个leader，leader同一个index只会写一条日志，且leader不会修改日志。

2）同时 Raft 也保证：如果不同的节点日志集合中的两个日志条目拥有相同的 term 和 index，那么它们之前的所有日志条目也全部相同。这是因为：leader 发出的 AppendEntries请求中会额外携带上一条日志term和index，如果follower在本地找不到相同的日志，则拒绝接收这次新的日志。

3）所以，只要 follower 持续正常地接收来自 leader 的日志，那么就可以通过归纳法验证follower和leader拥有相同的日志序列。

leader遇到的实际情况

分布式系统非常复杂，当leader上任时，有可能会遇到a-f的各种情况：

• a、b两个follower日志复制的进度略落后与leader
• c、d两个follower日志比leader多几条
• e、f两个follower日志比leader多几条同时少几条

这里需要注意，raft的机制（在下一节会细讲）保证选上的leader拥有所有committed的日志，follower比leader多出的日志全部都是uncommitted的。

下面讲这些情况发生的原因：

• a和b少几条日志
  • 比较简单，中间挂掉了导致少复制了一些日志
• c比leader还多一条term6的日志
  • term6的leader将11号日志复制给c后挂掉了，没能复制给其他节点，现在的leader在term8竞选成功
• d比leader多两条term7的日志
  • 情况跟c差不多，term7的leader将两条日志同步给d后挂掉了，没能同步给现在的leader
• e比leader多出两条term4的日志，少term5、6的日志
  • term4的leader同步两条日志给e后来不及committed就挂掉了，随后e自身也挂掉了，没能收到term5、6的日志
• f比leader多处term2、3的日志，少term5、6的日志n
  • 跟e类似，term2、3的leader同步日志给f后来不及committed就挂掉了，然后f自身也挂掉了

至于leader处理不一致的方法很简单：向前回溯follower跟自身的分歧点，然后从分歧点开始修复覆盖follower的日志。

安全性

到目前为止的这套机制还不能100%保证一致性，想象以下情况：

因此仍然需要增加一些选主和日志commit的限制，才能保证一致性

选举限制

回过头来看选举的RPC请求，candidate竞选时会带上log index和term，follower只会给日志比自己新的candidate投票。因为leader当选必须获取超过一半的选票，所以能当选的leader一定比超过一半的节点拥有更新的日志。又由于一条日志想要commit，必须复制到超过一半的节点上，那么leader一定拥有所有已经committed的日志。

message RequestVoteRequest {
    int64 term = 1;
    int64 candidateId = 2;
    int64 lastLogIndex = 3;
    int64 lastLogTerm = 4;
}

message RequestVoteReply {
    int64 term = 1;
    bool  voteGranted = 2;
}

日志commit限制

复习一下commit是什么：一条日志确认生效，应用到状态机中。
一般情况下，leader将日志复制到超过一半的节点后，即可commit日志，但是这么做在以下case时会出现问题：

a) term2的leader s1将日志复制到s2节点后挂掉了
b) s5节点在term3选为leader，日志3还没来的急复制就挂掉了
c) s1节点在term4重新选为leader，将日志2复制到s3后挂掉，此时日志2已经复制到超过一半的节点了，符合commit条件
d) 因为此时s2、s3、s4的最新日志都是2，不比s5新，s5可以获得多数票；s5再次成为leader时，把日志3复制给s1-s4，覆盖了已经提交的日志2
e) 位了避免这种情况，引入一条日志commit限制：leader只能commit当前term内的日志，之前的日志只能顺带同时提交；图中s1成为leader，把日志2复制出去后，没有commit，等到日志4复制出去后，才顺带commit，这样s1-s3的日志都比s5新，s5无法成为leader

以上就是Raft算法的介绍了，更全面的信息可以关注参考资料。

参考文档

• raft官网 raft.github.io/
• raft paper raft.github.io/raft.pdf
• 深度解析 Raft 分布式一致性协议
• 分布式理论(六) - 一致性协议Raft
• 终于明白了，一文搞懂Raft协议