Raft协议
概念与术语
Leader：领导者，为客户端提供服务(生成写日志)的节点，任何时候Raft系统中只能有一个Leader。
Follower：跟随者，被动接受请求的节点，不会发送任何请求，只会响应来自Leader或者Candidate的请求。如果接受到客户请求，会转发给Leader。
Candidate：候选人，选举过程中产生，Follower在超时时间内没有收到Leader的心跳或者日志，则切换到Candidate状态，进入选举流程。
TermId：任期号，时间被划分成一个个任期，每次选举后都会产生一个新的TermId，一个任期内只有一个Leader。TermId相当于Paxos的ProposalId。
currentTerm：更新的Term。
RequestVote：请求投票，Candidate在选举过程中发起，收到Quorum(多数派）响应后，成为Leader。
AppendEntries：附加日志，Leader发送日志和心跳的机制
Election Timeout：选举超时，如果Follower在一段时间内(超时时间为150ms-300ms内随机数)没有收到任何消息(追加日志或者心跳)，就是选举超时。
Leader Election：领导选举，选举超时即开始领导选举。
Raft协议主要包括三部分：
- Leader选举
- 日志复制
- 成员变更
一个节点的状态只有如下三种形式的一种：
- Follower 状态
- Candidate 状态
- Leader 状态
Leader选举
Leader流程
服务器启动时初始状态都是Follower，如果在超时时间内没有收到Leader发送的心跳包，则进入Candidate状态进行选举，服务器启动时和Leader挂掉时处理一样。为了避免选票瓜分的情况，比如5个节点ABCDE，Leader A 挂掉后，还剩4个节点，raft协议约定，每个服务器在一个任期只能投一张票，假设B，D分别有最新的日志，且同时发起选举投票，则可能出现B和D分别得到2张票的情况，如果这样都得不到大多数确认，无法选出leader。为了避免这种情况发生，raft利用随机超时机制避免选票瓜分情况。选举超时时间从一个固定的区间随机选择，由于每个服务器的超时时间不同，则leader挂掉后，超时时间最短且拥有最多日志的follower最先开始选主，并成为leader。一旦candidate成为leader，就会向其他服务器发送心跳包阻止新一轮的选举开始。
发送日志信息:(term,candidateId,lastLogTerm,lastLogIndex)
Candidate流程
1.在超时时间内没有收到leader的日志(包括心跳)
2.将状态切换为candidate,自增currentTerm,设置超时时间
3.向所有节点广播选举请求，等待响应，可能会有以下三种情况：
(1).如果收到多数派回应，则成为leader
(2).如果收到leader的心跳，且leader的term>=currentTerm，则自己切换为follower状态，
否则，保持Candidate身份
(3).如果在超时时间内没有达成多数派，也没有收到leader心跳，则很可能选票被瓜分，则会自增currentTerm,进行新一轮的选举
Follower流程
1.如果term < currentTerm，说明有更新的term，返回给candidate。
2.如果还没有投票，或者candidateId的日志(lastLogTerm,lastLogIndex)和本地日志一样或更新，则投票给它。
注意：一个term周期内，每个节点最多只能投一张票，按照先来先到原则
关键词：随机超时，FIFO
日志复制流程
leader向follower发送日志时，会顺带邻近的前一条日志，follwer接收日志时，会在相同任期号和索引位置找前一条日志，如果存在且匹配，则接收日志；否则拒绝，leader会减少日志索引位置并进行重试，直到某个位置与follower达成一致。然后follower删除索引后的所有日志，并追加leader发送的日志，一旦日志追加成功，则follower和leader的所有日志就保持一致。只有在多数派的follower都响应接受到日志后，表示事务可以提交，才能返回客户端提交成功。
发送日志信息:(term,leaderId,prevLogIndex,prevLogTerm,leaderCommitIndex)
leader流程
1.接收到client请求，本地持久化日志
2.将日志发往各个节点
3.如果达成多数派，再commit，返回给client。
备注：
(1).如果传递给follower的lastLogIndex>=nextIndex,则从nextIndex继续传递
.如果返回成功，则更新follower对应的nextIndex和matchIndex
.如果失败，则表示follower还差更多的日志，则递减nextIndex，重试
(2).如果存在N>commitIndex，且多数派matchIndex[i]>=N, 且log[N].term == currentTerm,
设置commitIndex=N。
follower处理流程
1.比较term号和自身的currentTerm，如果term<currentTerm，则返回false
2.如果(prevLogIndex,prevLogTerm)不存在，说明还差日志，返回false
3.如果(prevLogIndex,prevLogTerm)与已有的日志冲突，则以leader为准，删除自身的日志
4.将leader传过来的日志追加到末尾
5.如果leaderCommitIndex>commitIndex,说明是新的提交位点，回放日志，设置commitIndex =
min(leaderCommitIndex, index of last new entry)
备注：默认情况下，如果日志不匹配，会按logIndex逐条往前推进，直到找到match的位置，有一个简单的思路是，每次往前推进一个term，这样可以减少了网络交互，尽快早点match的位置，代价是可能传递了一些多余的日志。
关键词：日志连续一致性，多数派，leader日志不变更
快照流程
避免日志占满磁盘空间，需要定期对日志进行清理，在清理前需要做快照，这样新加入的节点可以通过快照+日志恢复。
快照属性：
1.最后一个已经提交的日志（termId，logIndex）
2.新的快照生成后，可以删除之前的日志和以前的快照。
删日志不能太快，否则，crash后的机器，本来可以通过日志恢复，如果日志不存在，需要通过快照恢复，比较慢。
leader发送快照流程
传递参数(leaderTermId, lastIndex, lastTerm, offset, data[], done_flag)
1.如果发现日志落后太远(超过阀值)，则触发发送快照流程
备注：快照不能太频繁，否则会导致磁盘IO压力较大；但也需要定期做，清理非必要的日志，缓解日志的空间压力，另外可以提高follower追赶的速度。
follower接收快照流程
1.如果leaderTermId<currentTerm, 则返回
2.如果是第一个块，创建快照
3.在指定的偏移，将数据写入快照
4.如果不是最后一块，等待更多的块
5.接收完毕后，丢掉以前旧的快照
6.删除掉不需要的日志
集群配置变更
C(old): 旧配置
C(new): 新配置
C(old-new): 过渡配置，需要同时在old和new中达成多数派才行
原则：配置变更过程中，不会导致出现两个leader
二阶段方案：引入过渡阶段C(old-new)
约定：任何一个follower在收到新的配置后，就采用新的配置确定多数派。
变更流程
1.leader收到从C(old)切换到C(new)配置的请求
2.创建配置日志C(old-new),这条日志需要在C(old)和C(new)中同时达成多数派
3.任何一个follower收到配置后，采用的C(old-new)来确定日志是否达成多数派(即使C(old-new)这条日志还没达成多数派)
备注：1，2，3阶段只有可能C(old)节点成为leader，因为C(old-new)没有可能成为多数派。
4.C(old-new)日志commit(达成多数派)，则无论是C(old)还是C(new)都无法单独达成多数派，即不会存在两个leader
5.创建配置配置日志C(new),广播到所有节点
6.同样的，任何一个follower收到配置后，采用的C(new)来确定日志是否达成多数派
备注：在4，5，6阶段，只有可能含有C(old-new)配置的节点成为leader。
7.C(new)配置日志commit后，则C(old-new)无法再达成多数派
8.对于不在C(new)配置的节点，就可以退出了，变更完成。
备注：在7，8阶段，只有可能含有C(new)配置成为leader。
所以整个过程中永远只会有一个leader。对于leader不在C(new)配置的情况，需要在C(new)日志提交后，自动关闭。
相关阅读
http://thesecretlivesofdata.com/raft/ （强烈推荐阅读，动画的形式化繁为简地讲解raft）
https://raft.github.io/
https://raft.github.io/raft.pdf
https://medium.com/@techgeek628/raft-understandable-distributed-consensus-987b3783d48a
