前言
单点系统的数据是天然一致的，但为了避免单点故障问题，我们引入了分布式系统。
将数据以副本的形式保存在多个节点上，可以有效避免单点故障造成的服务不可用以及数据丢失的情况。
但如何去保证多个节点的一致性呢，如何达成分布式共识，raft算法就应运而生了。
现在市面上有很多对raft的实现，比如etcd、consul等等。
本文主要带大家了解一下raft中的leader选举与日志复制流程
raft节点的角色划分与任期
在raft中，有以下三种角色：
follower 跟随者
所有节点的初始状态，内部都会有一个超时时间。对于每一个follower，其超时时间是随机的。
这个超时时间，规定了在倒计时结束后仍然收不到leader的心跳，follower就会转变为candidate。
为什么每个follower的超时时间是随机的，改成一样的可以吗？
不可以，相同的超时时间会造成多个follower同时转变为candidate，选票被瓜分，导致获取不到半数以上的选票，就需要进行新一轮的选举，效率低下。
candidate 候选者
follower在转变为candidate后，超时时间重置，倒计时结束时就会向其他节点拉取选票。
如果能获得半数以上（包含自己投给自己的）的选票，则当选为leader，这个过程就叫做leader选举。
为什么在转变后，会重置超时时间，直接进行leader选举不行吗？
follower的超时时间是随机的，但不保证不会随机到相同的时间。那么此时再进行一次倒计时，可在大概率上避免选票被瓜分的情况。
为什么要获得半数以上的选票，获得一半选票行不行？
显然是不行的，因为这样在极端情况下会在一个集群中选举两个leader出来，产生脑裂问题。
leader 领导者
raft集群通过leader与客户端进行交互，leader不断处理写请求与发送心跳给follower。
follower在收到leader的心跳后，其超时时间会重置，即重新开始倒计时。
term 任期
无论当前节点处于什么角色，内部都会有一个任期编号，初始值为0。
当follower转变为candidate时，任期编号将会自增。
每个节点在当前的任期内，只能投出一份选票。
任期有什么用呢？
- 高任期的节点向低任期的节点拉取选票时，低任期的节点将会把自己的任期修改为高任期，因此来实现任期的统一。
- leader宕机恢复后发现自己的任期比其他节点小，则自动转变为follower。是因为任期的增加，表明原leader宕机期间已经发生了新的选举，需要以新的选举结果为准。
- 低任期的节点向高任期的节点拉取选票时，高任期的节点将直接拒绝。
角色之间的转变过程图
leader选举过程
假设当前raft集群共有5个节点，初始状态都为follower，任期也都是0。
图中f代表follower，c代表candidate，l代表leader，t表示任期编号。
f1的超时时间最短，因此f1转变为c1，重置超时时间，任期加1。
当c1重置完超时时间，倒计时结束后，将会向其他节点拉取选票。
其他节点投出自己的选票，并将自己的任期加1。
由于c1得到半数以上的选票，则转变为leader，并不断向其他节点发送心跳。
leader宕机后恢复
在某一时刻，leader由于故障宕机，此时follower收不到心跳消息。
f3的超时时间最短，最先转变为candidate，此时任期加1，并向其他节点请求投票。
其余节点投出选票，任期加1。此时，c3得到半数以上的票，转变为leader，并向其他节点发送心跳。
l1宕机恢复后，会向各个节点发送一个当前任期的请求。
l1发现其他的节点的任期比自己大，于是主动降级为follower并同步任期，接收来自l3的心跳信息。
如何解决脑裂问题？
假如在一个集群或系统中，同时出现1个以上的leader，这样的现象就是脑裂。
多个leader会向follower同时发号施令，follower不清楚该接受哪个leader的指令，最终会造成内部混乱。
在没有出现网络分区的情况下，raft通过以下两条约束来避免脑裂：
- 每个节点在一个任期内，只能投票一次。
- 获得半数以上的选票，才能成为leader。
在固定的选票下，获得半数以上选票的才能成为leader，有效避免了脑裂问题。
如果在现网络分区的情况呢？
先说结论，其实和leader宕机恢复很像，低任期的leader在发现有高任期的leader后，会主动降级为follower。
一开始，集群内部只有一个leader。后来发生了网络分区，l1无法向f3、f4与f5发送心跳。
f3、f4与f5将会开启新一轮选举，接着f4获得当前所有的选票，即3份，为半数以上，当选为新的leader。
当网络分区结束后，集群内部会短暂的出现两个leader的情况。
l1发现l4的任期比自己的大，于是主动降级为follower，并接收来自l4的心跳。
日志复制
我们知道，只有leader能处理外部客户端的数据的增删改操作，leader会将顺序接收到的操作指令序列化成日志，之后节点上的某个程序(有些文章称之为状态机)执行日志中的命令，只要各个节点上的日志相同，则程序执行后产生的结果就相同。
日志结构
那么日志具有怎样的一个结构呢？
一份日志主要包含以下信息：
- 索引值，可以理解为该条日志在文件中所处的行号
- 任期编号，创建这条日志的leader所处的任期
- 客户端的指令，在提交后，会被状态机执行
日志复制过程
因此raft集群的重点在于leader需要将自己的日志同步到follower节点，以保证整个raft集群的数据一致性。
这样我们在访问任意一个节点时，都能获得相同的返回数据。
一个简要的日志复制过程如下：
首先，经过一轮选举后，产生了一个leader。
当l1接收到客户端的数据修改的指令后，首先会append到自己的本地日志中，状态为未提交，之后会向follower节点发起append请求。
当follower节点接收到append请求后，同样也会append到自己的本地日志中，状态为未提交。
当半数以上的follower写入成功后，leader会将日志提交，并应用到状态机中执行，同时回应客户端修改成功。
最后leader通知follower节点将日志提交
在这个时候，整个raft集群实现了分布式的数据一致性。
我们整理一下日志复制的过程：
日志是如何保持一致的
上图描述的是一个在理想状态下的复制过程，在实际场景中，可能会出现leader宕机、网络分区的情况，这些情况会导致日志的不一致，那么raft是怎么保证日志的一致性的呢？
raft集群是一个strong leader的系统，因此会强制follower复制leader的日志。
leader会在心跳信息中，将已提交的日志数据不断发送给follower，复制请求中包含上一条日志的索引值与任期（记为l.pre.index与l.pre.term），当前日志的索引值与任期（记为l.cur.index与l.cur.term）。
follower在收到复制请求后，先查找自身l.pre.index索引值的日志term，是否等于l.pre.term，如果等于，则将l.cur.index与l.cur.term追加到本地日志中，并返回复制成功。
如果follower中l.pre.index索引值的日志term，不等于l.pre.term，则返回复制失败。此时leader会将更前面一条的日志发送过来，如果依然复制失败，则继续往前，一直从后往前找到第一个共同的日志。并从这里开始往后复制，使得follower与leader的日志一致。
举个例子：
假设该集群在运行一段时间后，leader与其中一个follower的日志情况如下：
1、此时leader需要follower复制索引为5的日志，于是将索引4和5的日志一起发送给了follower。
2、follower发现索引4的日志，任期和leader日志不一致，因此返回复制失败。
3、leader发现复制失败后，将索引3和4的日志一起发送给了follower。
4、follower发现索引3的日志，任期是一致的，这就找到了和leader共同的日志项，于是覆盖索引4的本地日志，返回复制成功。
5、leader发现复制成功，便不再往前递归寻找。
6、下一轮的心跳信息中，leader将索引4和5的日志一起发送给了follower。
7、follower比对发现索引4的日志一致，于是将索引5的leader日志追加到本地日志中，此时leader与follower的日志一致了。