前言

之前简单介绍过Paxos算法，并且推导了整个算法的产生，说明了实现过程，但是显而易见Paxos算法非常难理解，并且更难以实现，Raft算法的出现用来代替Paxos算法，实现更加容易，由于本人水平有限，可能文中出现错误，还请大家指出。

基础概念介绍

Raft是一种用于管理复制日志的一种一致性算法，它将通过一些功能将一致性的一些问题分解，从而更方便理解。

一、Raft的重要功能

Leader选举、日志复制（数据同步）、日志压缩（数据快照）、安全性等等

二、Raft的角色

Raft算法中将服务节点分为了三种角色：

Leader（领导者）： 主服务节点，用来处理客户端的请求，并且将数据同步到Follower节点，只有当大多数Follower节点复制成功后才算数据写入成功。
Follower（跟随者）：从服务节点，用来保持和Leader的数据同步，并且接受Leader心跳，当超过一定时间没有收到心跳则发起选举流程。
Candidate（候选者）：当选举阶段发生时，Follower发起选举并将自身更新为候选者的角色，该角色只在选举阶段出现。

三、Leader任期（Term）

Raft算法将整个服务的时间划分为一个个Term周期，每个Term周期也就是Leader所当选的任期，该任期通过一个连续的数字来表示，每个任期开始的时候都会选举一个新的Leader来带领其他Follower，如果一个新的任期没有选举出Leader则Term+1，开始下一个任期的选举，通常具有最新任期的节点视为拥有最全的数据。

Raft保证在一个任期期间，最多只有一个Leader。

简单来说就像是总统的选举，每个任期为5年，当出现一些情况时，会进行总统的重新选举，也自然到达一个新的任期。

四、服务通信

在Raft算法中，各个不同节点之间的通信使用的是RPC协议，在整个算法中的通信分为以下三种

• RequestVote：选举投票请求，主要在Leader选举期间发生。
• AppendEntries：Leader发起的心跳，并且也同时进行日志的复制。
• InstallSnapshot：Leader向Follower同步日志快照信息，主要用来新加入的Follower节点和日志同步落后太多的节点与Leader同步数据。

Leader选举

一、什么是Leader的选举？

Raft算法规定了，只有Leader节点才能处理读写请求，Follower节点只进行数据的同步和Leader的选举。选举时采用RequestVote RPC通信

在服务器启动运行时刻，所有节点默认都为Follower角色，然后会等待一段时间没有收到Leader的心跳，则延迟随机时间来进行角色转化（Candidate）发起选举。
为什么需要延迟随机时间，这是为了多个Candidate节点同时发起选举，会造成选票分票导致无法选举成功，而延迟一段随机时间可以提高选举成功率。

在服务的运行当中，如果一个Follower节点与Leader节点失联超过一个Term周期，则Follower自动转化为Candidate角色，发起Leader的新一个Term任期选举，并且优先选自己作为Leader。选举发起时，Candidate请求其他节点投票给自己，如果收到了大多数节点的投票，则当选Leader开始一个新的Term任期，其他节点则更新自己的Term为最新任期，在Leader的任期期间，会持续的发送心跳（AppendEntries）来维持自己的Leader地位。

二、超时

通过上述选举描述，可以看到有两种超时时间：

1. 选举超时：也就是每个Follower节点随机延迟的时间，用来避免选票分票、提高选举成功率。
2. 心跳超时：也就是Leader节点持续发送心跳的时间，如果Follower接受心跳超时，则会进行新一轮的选举。

三、选举的条件

在进行Leader选举投票时，如何确定该给谁投票呢？Raft规定了下面几个优先级。

1. Term最大的优先
2. 如果Term相同，则具有最新日志编号（LogIndex）的
3. 如果LogIndex也相同，选择最先发起投票的

而一个Leader如何放弃自己的Leader地位呢？
如果遇到Term比自己大的节点，则放弃Leader地位，转为Follower。
这是因为可能由于网络分区，导致新的Leader节点产生，而恢复后应该与最新的Leader保持同步，避免脑裂。

四、选举流程

首先我们默认有一个5节点构成的分布式集群，然后描述服务的选举流程

1、服务器初始阶段

可以看到，在初始阶段，没有leader节点，大家都不会收到Leader的心跳，这时候每个节点维护自己的随机选举超时时间，这时候S5节点由于时间最短，转化为Candidate发起选举，当选Leader并且维护自己Term任期。

2、Leader宕机或网络分区选举

通过上图可以看到，在Term为1的任期期间，收到了客户端10条操作日志，并且同步给了其他四个节点，其中S1和S3同步最新，而Logindex10还没有进行提交。如果此时S5节点宕机，S1-S4节点无法收到心跳，则发起新一轮的Leader选举。那么谁将会当选Leader呢？

根据Raft选举条件限制：
（1）S2和S4由于数据同步较慢，肯定无法当选Leader
（2）由于S1和S3任期相同，Logindex也相同，根据选举超时时间，由S3先发起选举投票，则最终由S3当选。
（3）而由于Logindex=10并没有被大多数节点提交，所以并不会返回给客户端10这条记录更新成功。最新的数据依然为9

3、原Leader恢复

通过上图可以看到，S3当选了Leader后对外持续提供服务，并且为新的任期Term = 2 ，此时S5恢复了，S5原先为Leader当发现新的Term比自己大时，降级为Follower节点和Leader同步数据。

日志复制

日志复制是保证数据一致性的重要组成部分，由于Leader节点才能处理数据写请求，所以如何保证其他Follower节点也能同步数据呢？

日志复制阶段，也就是心跳持续发送阶段采用AppendEntries RPC通信

一、日志复制概念

（1）客户端每一次数据更新，都有一条对应的日志记录LogIndex，并且由Term和执行命令组成。
（2）如果Logindex被大多数机器复制成功，便认为可以提交了，此时由Leader更新状态机向客户端返回成功。
（3）日志会被持久化到磁盘当中，保证持久性
（4）如果不同的日志中存在两条相同的任期号和索引编号，则认为存储的命令是一致的。因为leader 最多在一个任期里的一个日志索引位置创建一条日志条目，日志条目在日志的位置从来不会改变。
（5）日志的创建是有序的。
（6）日志在一些异常情况下可能会被覆盖。

二、日志复制流程

（1）在Leader向Follower发送心跳时，会同时带着需要复制的日志消息体Entries与当前日志的前一条日志Entries，用来做简单的一致性校验（前一条相同才可以）。
（2）当存在Follower日志与Leader不一致时，通过强制Follower覆盖为Leader日志来保证一致性，具体是：Leader从Follower最后一条日志向前依次判断，找到相同日志的位置然后进行覆盖。

正常情况流程：

正常情况就没什么可以说的，只要Leader发送心跳时，同步复制日志即可

异常情况流程：

（1）网络分区

如上图所示，当发生网络分区时，S1和S5无法与其他节点进行通信，导致V2这条日志数据无法同步复制给大多数节点，导致V2无法更新成功这时候由于S2\S3\S4无法收到Leader的心跳，开始新一轮的选举，假设S2当选Leader。

（2）Leader选举

如上图所示，在S2任期期间收到了并且同步了V3\V4日志，此时当S1和S5恢复后发现数据不一致，这时S1会自动降级为Follower节点，并且强制从V1日志开始进行数据覆盖同步。

（3）日志覆盖

上述情况只是简单的介绍了数据不一致的情况，其实一个Follower可能会丢失掉Leader上的一些条目，也有可能包含一些Leader没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

节点新增：
当新加入一个节点时，直接同Leader复制日志即可。

日志压缩

由于日志的记录不可能无限制的增加，这样非常影响回放效率，影响可用性，所以Raft采用了SNAPSHOT快照的方式来对日志进行压缩，这样快照之前的日志都可以不用再进行存储。

其中在做SNAPSHOT快照时，每个副本都会对自己当前的系统状态和已经提交日志做压缩快照。

快照载入使用InstalledSnapshot RPC通信完成。

快照的组成

1. 日志元数据，最后一条已提交的 log entry的 log index和term。这两个值在SNAPSHOT之后的第一条log entry的AppendEntries RPC的完整性检查的时候会被用上。
2. 系统当前状态。

快照的频率

由于快照生成非常消耗CPU，所以不建议太过频繁，而是采用当日志到达一定大小后进行快照生成。

快照的载入回放

在生成快照后什么时候才会使用呢？

1. 新节点加入：在一个新节点加入集群时，通过快照来进行快速的载入
2. 落后太多的节点：有时候Follower落后了太多，无法通过日志来进行覆盖的时候，采用快照先进行数据载入

总结

通过上面已经比较清楚的理解了Raft算法。
接下来通过几个问题来进行总结

Raft和Paxos的区别？

1. 其中相对于Paxos，Raft更好理解也更容易实现。
2. Paxos是一种通用的解决分布式一致性的算法，Raft进行了扩展优化。
3. Paxos可以有多个发起提案的节点，Raft只有Leader发起
4. multi-Paxos任意节点可以当选Leader，Raft只有最新提交日志的当选。
5. Raft对每一次选举都有Term任期号

Raft的特点

1. Raft每一次数据提交都有Logindex编号和Term任期号
2. 整个日志由有序的日志条目组成
3. Raft选举时，每个节点具有随机时间，大幅度避免了选票分票情况。

Raft主要由哪几部分组成？

1. Leader选举
2. 日志复制
3. 日志压缩等

Raft PreVote机制作用？

由于网络分区的问题，有可能某节点无法与其他节点通信并且收不到Leader的心跳，这样会导致该节点进行选举，并且由于无法通信会一致不断的增加Term编号，编号会越来越大，这样当该节点恢复后，其他所有节点都要同步更新自己Term，并且Leader降级为Follower节点发起选举。整个集群被这一个节点搞乱了。

所以采用PreVote机制，首先发起预投票，只有其他节点同意选举后再真正发起选举。

Raft里面的lease（租约）机制作用？

Raft为了防止只靠心跳机制出现双主情况。也就是网络分区的时候出现双Leader节点，从而牺牲一定的可用性换一致性。
客户端的任何读写请求都是通过Leader节点进行的，Leader又分为Region Leader（逻辑上的概念）和Raft Leader，实际上请求是由Region Leader转发给Raft Leader处理的。Region Leader和Raft Leader可能是同一个节点。

如果没有租约机制：
比如现在由S1\S2\S3节点为分区1，Leader为S1。网络分区后S4\S5节点为分区2，老的Leader为S4。
这时候读请求分配到S4时造成数据不一致。
如果有租约机制：
Raft Leader选举成功时，将自己注册到一个节点上，由该节点作为Region Leader，为Raft Leader设置一个lease失效间隔，当时效过期时更新租约lease，这样就可以避免请求转发给老的Leader。

还以上面说的为例，这时候客户端的请求发到Region Leader，但是因为网络分区无法请求到S4节点，则lease时效后重新为S1更新为当前租约的Leader

参考文献

https://zhuanlan.zhihu.com/p/32052223
https://blog.csdn.net/daaikuaichuan/article/details/98627822
https://www.jianshu.com/p/072380e12657