1 raft共识算法
raft是强leader模型，通过选举leader来实现一致性，leader拥有完全的能力来管理复制日志。leader从客户端获取日志条目，复制到其他的服务器中，告诉他们什么时候应用这个日志到状态机是安全的。
leader这个角色简化了复制日志的管理。leader可以在不咨询其他服务器的前提下添加新的日志条目，数据只从leader流向其他服务器。
如果一个leader宕机或者失联了，一个新的leader就会被选举。
Raft把一致性问题分解为三个独立的部分：
- leader选举。当现有的leader失败后，新的leader必须被选举产生。
- 日志复制。leader必须接收客户端的日志条目然后通过集群复制，强制其他服务器的日志和leader的一样。
- 安全性。如果一个服务器应用了一条日志，那么其他的服务器应用的相同条目的日志内容就是一样的。 这样的话，follower已经应用的日志和leader相同，follower的snapshot也不会和leader冲突。
2 State
2.1 所有节点都维护的需要持久化的状态
int m_me; // raft节点的标识
int m_currentTerm; // 当前trem（任期）
int m_votedFor; // 记录当前任期给谁投了票
std::vector<raftRpcProctoc::LogEntry> m_logs; // 日志条目数组（日志：index,term,指令）2.2 所有节点都维护的易失性状态
都初始化为0
int m_commitIndex; // 已经被提交的最新的log的index
int m_lastApplied; // 已经应用给状态机（kvsrver）的最新的log的index2.3 只有leader需要维护的易失状态
// 对于每一个节点，leader（当前节点）下次应该从哪个日志开始发送;初始化未leader的log的最大index+1
std::vector<int> m_nextIndex;
// 对于每一个节点，在哪个日志和leader（当前节点）匹配;初始化为0
std::vector<int> m_matchIndex; 3 服务器规则
3.1 所有的服务器
- 如果commitIndex>lastApplied：增加lastApplied，应用log[lastApplied]到状态机
- 如果RPC的请求或者回复中的term T>currentTerm：设置currentTerm=T，转为follower
3.2 Follower
- 回复来自candidate和leader的RPC
- 如果经过了选举超时(election timeout)还没有收到当前leader的AppendEntries或者candidate的投票请求：转为candidate
3.3 candidate
- 转为candidate之后，开始选举：
- 给所有的服务器发送RequestVote RPC
- 重设选举定时器
- 为自己投票
- 增加currentTerm
- 如果收到大多数服务器的选票：成为leader
- 如果收到新leader的AppendEntries RPC：转为follower
- 如果经过了选举超时(选举定时器到达了)：开始一个新的选举
3.4 leader
- 定时发送空的AppendEntries RPC(心跳)给所有的服务器
- 如果收到了客户端指令：将新的条目添加到本地日志中，在应用到状态机之后返回结果。当前项目中kvserver负责与客户端通信。
- 如果最大的日志索引>=follower的nextIndex：发送从包含nextIndex开始的日志条目的AppendEntries RPC：
- 如果因为日志的不一致导致失败：leader减小nextIndex然后重试
- 如果成功：更新follower的nextIndex和matchIndex
- 如果存在一个N，N>commitIndex，大部分的matchIndex[i]>=N。而且log[N].term==currentTerm，设置commitIndex=N。（只有当前term有日志提交，才更新commitIndex）
4 安全性
论文：
选举安全：在给定的期限内，最多只能选举一位leader。§5.2
只能leader添加日志：leader永远不会覆盖或删除其日志中的条目； §5.3
日志匹配：如果两个日志包含具有相同索引和任期的条目，则在给定索引之前的所有条目的内容都是相同的。§5.3
leader完整性：如果某一任期内一条日志被提交，则该条目将出现在之后任期leader中。§5.4
leader提交了某一条日志，说明该日志被复制到大多说节点。然后leader宕机，其它节点发起选举。没有复制这条日志的节点的log比大多数节点旧，所以不可能获得大多数选票，不能成为leader .只有复制了上一任leader提交的最新的日志的节点才能成分下一任leader.
状态机安全性：如果服务器已在其状态机应用给定索引日志条目，则其他任何服务器都不会在该索引处应用其他内容的日志条目 §5.4.3
5 选举
leader向所有follower定时发送心跳信号（不携带日志条目的AE RPC），以维护其领导地位。只要服务器收到来自leader或者candidate有效RPC，就会保持follower状态。如果follower在称为选举超时(election timeout)的时间段内没有任何通信，则它假定没有可行的leader，并开始竞选新leader。
5.1 开始选举
转为candidate之后，开始选举：
- 给所有的服务器发送RequestVote RPC
- 重设选举定时器
- 为自己投票
- 增加currentTerm
5.2 选举结果
一个candidate继续保持它的状态直到有以下一种情况发生：
- 它赢得了选举
- 另一个服务器成为了leader
- 没有leader产生
5.2.1 赢得了选举
在一个任期内（一次选举过程，也是一个term），如果收到大多数服务器投票，candidate就赢得了选举。
每个服务器在一个任期中最多给一个candidate投票，而且是基于先来先服务原则(限制：投票要求candidate的日志不比自己旧)。
这个大多数规则保证了最多一个candidate可以赢得某一任期的选举(选举安全性)。
一旦一个candidate赢得了选举，它就成为了leader。它给集群中所有的服务器发送心跳以建立它的地位，同时也阻止了新的选举发生。
5.2.2 另一个服务器成为了leader
当等待投票的时候，candidate可能收到另一个服务器声明已经成为leader的AppendEntries RPC。
如果这个leader的任期不低于这个candidate的任期，这个candidate就承认leader的正当性然后成为follower。
如果这个RPC中的任期比candidate的任期小，这个candidate就就拒绝这个RPC，然后继续保持candidate状态。(可能是旧的leader重连)
5.2.3 没有leader产生
没有candidate赢得或者输掉这个选举。原因就是多个follower同时成为candidate，投票会分散给各个candidate，从而没有candidate获得了大多数的票。
当这种情况发生，每个candidate会等到超时然后增加它的任期号开始新一轮的选举。然而，没有额外的措施的话，分裂投票的情况还会出现。
Raft使用随机的选举超时(randomized election timeout)来解决分裂投票。选举超时在一定的范围(150-300ms)内随机获得。这会把所有的服务器分散开来，因此在大多数情况下，只有一个服务器会经历完选举超时。 它在其他服务器到达选举超时之前赢得选举和发送心跳。 每个candidate在选举开始时都会重置选举定时器，并等待该定时结束后再开始下一次选举。
5.3 选举流程
5.3.1 electionTimeOutTicker
负责查看是否该发起选举，如果该发起选举就执行doElection发起选举。
5.3.2 doElection
改变状态为candidate,发起选举，构造需要发送的rpc对象，调用sendRequestVote发送rpc并处理rpc响应结果。发送给所有节点，每个节点对应一个线程。
当前节点状态变化：
m_status = Candidate;
m_currentTerm += 1;
m_votedFor = m_me; // 自己给自己投，也避免candidate给同辈的candidate投tips:
- 发起选举后，会重置选举定时器。如果选举定时器超时就必须重新选举，不然没有选票就会一直卡住；
- 重竞选超时导致重新选举，term也会增加
5.3.3 sendRequestVote
负责发送选举中的RPC，在发送完rpc后还需要负责接收并处理对端发送回来的响应。
5.3.4 RequestVote
接收别人发来的选举请求，主要检验是否要给对方投票。
