概念

官方上说，Raft是一个共识算法(consensus algorithm)。我们一般喜欢把它叫做Raft协议。细品“共识”，“协议”，一定是有很多人参与才能叫做“共识”或者“协议”，要是一个人玩，想怎么玩就怎么玩。因此，Raft是一个让多方（一般就是多个服务器）都来遵守的一套“规则”，而这套规则的目的，是实现分布式系统（也就是这一群服务器）的容错或者高可用。

从论文来看，Raft最大的优势（相较于Paxos）就是好理解（在保证Safety的情况下），好理解带来的优势就是能更好更快地用于实践中并扩展。既然都说了，就是为了好理解才搞出这样一个共识算法，那我们肯定要来理解一哈~

复制状态机

共识算法和复制状态机（Replicated State Machine）息息相关。共识算法就是为了保证复制状态机的这个复制的log能保持一致性才产生的。那啥是复制状态机？

简单的说，其实就是状态机(State Machine) + 操作日志（Log），举个栗子??就是MySQL里的全量备份 + binlog，或者MongoDB的全量备份 + Oplog。通过这两个部分，任何一个服务器都“可以”达到一个与其他服务器相同的状态。“可以”不是“必定”，共识算法，就通过设定一些规则，来保证这个一致性。

Raft规定的角色

• leader 接受客户端的请求，并发送日志到其他角色，一般情况只有一个leader。
• follower 只做回应。例如回应leader的心跳，回应leader传送日志的请求，回应candidates的选举请求。
• candidate 当一个follower半天收不到leader的心跳，他就跃跃欲试觉得自己行了，发起选举，尝试自己来当leader，此时角色从follower转变为candidate。一旦大多数都支持他，那他就变成新的leader
  

Raft制定了哪些规则？

其实主要就是上述3个状态的转换条件。

Raft重要的组成部分

Leader Election

选举leader是通过心跳机制来进行的。一个单纯的心跳就是一个不含任何log信息的AppendEntries RPCs。一开始，大家都是follower,当超过election timeout的时间后还没有收到leader的心跳，那么这个follower将升级为candidate, 它自己的current term+1， 并向其他节点发送选举请求。此后，有三种情况：

• 该节点赢得了选举，也就是在该term里收到了大部分其他节点的同意票。在同一个term里，一个节点根据先来后到的规则，顶多投出一票。之后，他成为了leader并向其他节点发送心跳。
• 被捷足先登了。candidate在等待其他节点回复的同时也可能会收到其他节点选举自己的请求。这个时候判断该请求的term是不是比自己的大，如果大于等于自己的，那么“好吧，我退出”，他回到follower的状态；如果小于，那么他继续自己的candidate状态。
• 搞了半天一个能选上的都没有。如果同时有很多follower变成candidate了，那么票数可能被分票了，投不出来，没有一个candidate能获得“绝大多数”票。此时，超过了超时时间过后，他又会开启新的一轮选举（term+1）。为了避免这个情况，Raft会让每个节点的election timeout不用，方法就是在150ms-300ms中随机一个超时时间。

Log Replication

leader的一个重要职责就是发送日志。当leader的一份日志复制请求发送给各位follower并收到了大部分回应后，leader就将这份日志设置为“committed”并返回客户端。当follower知道了这份日志“committed”后，就根据顺序执行该日志，改变本地状态（或者说磁盘里的数据）。

当然，如果leader crash了就会出现日志不一致的情况，如下图：

当顶部的节点变为leader的时刻，follower的日志状态可能是a-f都有可能。每个方形代表了一份日志（log entry），里面的数字是该日志的term。有些follower还没收到一些log entry，如a-b,有些呢收到了一些没提交的log entry如c-d,还有些比如f,它在term 2的时候是leader，但是日志还没有提交就crash了，它立刻重启后又成为term 3的leader，又收到一些log entries又crash了，然后一直crash着。

Raft是怎么解决这些问题的呢？Raft规定，leader要求follower的日志和自己保持一致，如有多的，就被覆盖，如有少的，就加上。

这个机制是靠leader维护一个nextIdx[]的数组，代表着他需要发给每个follower的log entry的index。当一个节点成为leader的时候，这个数组被初始化为它本地的log entries的index的最大值。然后通过AppendEntries RPC consistency check来收敛一致，即leader将自己对应这个follower的index发送给follower,如果follower发现和自己的最大index不一致，该RPC会fail,fail以后，leader将这个index-1(不一定是1，如f的情况，leader的index从4减到1发送给f,就终于可以success了)，然后再做尝试，最终都会达到一致。

Safety

以上就是Raft的基本内容了。但是整个过程会有各种各样的corner case, 而我们要求的底线是一致的，例如committed的log不能丢失等。所以Raft设置了一些额外的限制，比如什么样的节点才能成为leader来保证safety。

选举的限制

Raft在选举中，保证只有包含所有committed log的节点才能赢得选举成为leader（针对上面这个问题，非常非常intutive的限制）。也就是说，当一个candidate发起选举，如果它最后成为了leader，它收到了大部分同意选票的节点中，每一个committed log都至少出现在这些节点的一个中（有一点绕？）。

机制就是，当candidate发起选举的RPC时，会把自己的log发给其他人，其他人如果发现自己的log更“up-to-date”一点，就不投这票（“我条件更好，我不选你”）。这个“up-to-date”的定义就是，比较最后一个log entry的index和term，如果term更大，就比较新。如果term一样，谁的log多谁就比较新。

提交日志的限制

todo

应用

资源

动画看Raft，很直观！
Raft官方介绍，也有动画，也很直观！
Raft论文资料