分布式一致性算法03 RAFT协议
一、基本概念
Raft算法首选会选举一位领导者（Leader），所有的写请求都先提交给Leader，Leader通过日志复制（Log Replication）来保持集群中所有节点的状态一致。
在这个过程中有一些限制：
1、Leader只能有一个，Leader会通过心跳包告知其他节点，“我是Leader，我还活着，你们别想选举”
2、Leader和Follower之间通过日志同步的方式达成一致；在一条日志中，包含了索引编号、指令、Leader任期等信息
3、日志记录了所有的事务操作，必须在所有节点上顺序一致（索引编号是递增的）
4、Raft算法通过任期编号和选举超时机制来避免分裂脑现象，确保在任期内只有一个Leader
二、RAFT算法通常涉及三种角色
领导者（Leader）：负责处理所有客户端请求，将日志条目（Log Entries）复制到其他节点。
跟随者（Follower）：接收领导者的日志条目并保持与领导者的心跳连接。
候选者（Candidate）：当跟随者在一定时间内没有收到领导者的心跳时，它们会变成候选者并尝试成为新的领导者。
在实际情况中，一个节点通常只会承担一个角色，但这个角色通过选举机制是可以相互转换的。
三、RAFT Leader初始过程
1、当系统初始化时，或者Leader状态异常无法正常发送心跳包后，会开启选举过程。
2、此时，每个节点都是Follower，每个Follower都持有一个时间随机的选举计时器。
3、当一个Follower的选举计时器超时后，该Follower会判定Leader不可用，于是它自增任期号，并转换为Candidate。
4、Candidate首选会给自己投票，并向其他节点发送 RequestVote RPCs 请求投票，该请求中包含新任期号以及日志信息。
5、其余节点收到请求后，会检查请求中的任期号和自己的日志信息。如果受到的任期号更大，它们会投票给该Candidate。
6、如果一个Candidate从集群中大多数节点那里收到投票，它就赢得了选举，成为新的Leader。
7、新的Leader会立即向所有节点发送心跳信息，以通知它们自己的存在，并防止它们变成Candidate。
四、选举过程举例
假设一个5节点组成的Raft集群P1~P5，其中P1是Leader，其余为Follower，此时任期为Term1。此时P1故障，无法发送心跳包。
1、P2~P4节点都为Follower状态，每个节点都会初始化一个随机的选举计时器。
计时器分别为：P2 100ms，P3 200ms，P4 300ms，P5 400ms
2、由于一直收不到心跳包，P2的选举计时器会首先超时。
此时P2会在任期号Term1上增加，生成任期号Term2，并转换为 Candidate 状态。
3、P2给自己投票，并向其他全部节点发送 RequestVote RPCs 请求投票，并带上任期号Term2
4、P3~P5收到投票后，对比Term2和自己日志中的任期号
如果日志任期号更达，则拒绝投票
在本例中，Term2任期号更大，P3~P5就都会投票给P2
5、P2收到P3~P5的投票，加上自己的一票，超过半数，选举成功，P2成为新的Leader
6、P2会立即向所有节点发送心跳信息，其他竞选失败的Candidate，退回为Follower状态，开始跟随Leader的日志。
所有Follower会重置选举计时器，等待再次成为Candidate，并发起选举。
7、在日志复制之前，P2需要确定自己的日志与Follower的日志是否一致。它会发送AppendEntries RPC请求给Follower，并在请求中包含自己日志的最后一个日志Entry（索引和命令）和任期（PrevLogEntry和PrevLogTerm）。
如果Follower的日志与Leader匹配，则可以开始日志同步。
如果Follower的日志与Leader不匹配，它会发送一个失败的响应。Leader则会回退一个日志Entry，再次与Follower确认，直至双方一致为止。此时，Leader会将最新日志同步给Follower，从而让双方日志完全一致。
8、P2此时正式成为Leader，开始接收请求，并开始同步日志（AppendEntries RPC）
投票过程有一些限制：
单次投票：当Follower收到不同Candidate的同一Term的 RequestVote RPCs时，只会投票给第一个
仅投票给日志完整性高的Candidate：当Follower收到Candidate的RequestVote RPCs时，如果Candidate的日志完整性不如自己高，则拒绝投票
过半投票：Candidate必须有过半的投票，才能升级为Leader，从而避免脑裂
当然，也会有一些特殊情况：
系统启动：节点启动后默认为Follower，由于没有Leader，各节点很快会进入选举超时，并转换为Candidate，并发起选举。
选举失败：没有任何Candidate获得足够的票数，这样会继续进入下一轮选举，而且这个等待选票的时间，也是随机的
四、Raft算法的工作流程
当完成Leader的选举后，工作流程就比较简单了。
接收请求：
客户端向Leader发送一个写请求，比如设置键值对key1=value1。
日志复制：
Leader创建一个新的日志条目，并将其追加到自己的日志末尾。
日志同步：
Leader将这个日志条目发送给跟所有的Follower，包含了日志条目的信息以及领导者的任期号等。
Follower收到日志后，首先验证任期是否有效，如果任期有效，而且日志条目与本地日志记录兼容，则存储这个日志条目到自己的日志末尾。
跟随者在成功存储日志条目后，会向领导者发送一个确认响应（包含当前的任期号和成功标识）。
日志提交：
Leader等待Follower的确认消息，一旦收到大多数Follower的确认，它就将日志记录为“已提交”状态。
此时，Leader会向客户端返回操作成功。
应用日志：
Leader会在心跳包以及新日志复制的消息中，带上当前最新日志索引编号。
Follower接收到指令后，会将编号小于等于最新日志索引编号的日志条目，应用到自己的状态机中。
由于所有节点都按照相同的日志条目顺序执行操作，因此所有节点的状态机最终将保持一致。
五、效率提升
仅Leader接收请求：
避免集群多次通讯达成一致的过程，Leader接收并处理全部请求，然后同步给Follower。大幅提高吞吐能力。
日志压缩：
为了减少存储空间的使用，会定期进行日志压缩，保留关键的日志信息，而丢弃已经被持久化和应用的日志条目。
随机选举计时器：
通过随机时间，避免了所有节点一起发起投票，只投给自己的情况。用相对较低
单节点变更：
当增减节点的时候，保证一次只增减1个节点，可以有效的避免脑裂的出现
