https://blog.csdn.net/qq_22351805/article/details/113568597
本人博客原地址：raft:分布式一致性算法笔记
创作时间： 2021.01.27 17:22:15
本文主要记录leader选举与log复制过程的学习与思考。内容可能过于啰嗦，力求尽量对细节能有完整的描述，能对代码实现有所脾益。
首先我们先对raft要有一个大概的认知：raft是一种基于日志复制的分布式一致性算法，用于解决分布式环境下多节点数据的一致性问题。多节点通过投票机制选举leader节点（超半数投票），客户端请求只能通过leader节点访问，当leader节点向follower节点复制日志时，超半数节点（包括leader）复制完成即可向客户端返回已提交状态。这里需要注意的是，超半数节点复制完成不等于已提交，提交动作是leader节点完成，然后告知follower节点更新状态。
下面的说明，均以经典的5节点为背景。
一、主要概念：（可先大致了解，后面图文解析更方便理解）
1、leader，follower，candidate
leader节点：接收客户端请求，客户端发起请求后，先在leader记录日志，然后leader复制到follower节点，当leader接受到超半数follower响应完成复制时，标识已提交并向客户端响应，告知follower已提交状态。
Follower节点：接收leader的日志并持久化，接收leader的已提交通知并修改状态。
Candidate：Leader选举过程中的临时角色。当follower等待一段时间（选举超时时间）后进入该状态，并开始发起投票。
2、选举超时时间与任期
选举超时时间：每个follower在启动后都会随机赋予一个超时时间，follower启动后开始等待，在这个超时时间内，如果没有收到其他的投票请求，心跳请求或者日志复制请求，follower进入candidate状态，并开始发起投票，如果这段时间有收到上述请求，则复位等待时间，重新开始等待。
任期：每一次Leader选举就开始新的任期。在成功选举Leader之后，Leader会在整个term内管理整个集群。若当前任期没有选举出leader，则开始下一个任期选举。
3、日志复制
每个节点上都会有个log数组，，记录每次的日志消息（logentry），每个logentry对应log数组的一个下标，logentry记录有发送改logEntry的leader的任期和具体的log内容。
logEntry 在每个节点复制完成后告知leader。leader节点收到大多数回复后向客户端响应已提交并记为commited（实际的已提交），而后告知follower已提交状态，follower标识commited（实际上没有告知的请求，而是通过下一次心跳检测请求（日志内容为空）或者日志复制请求，后面会讲到）,leader标记commited之后同步执行当前日志的命令结果写入状态机（Replicated state machines）状态机可以理解为磁盘存储或者内存存储等能够保存数据状态的设备。
在开始下一部分内容之前，可以先玩下raft演示，不过后面第三章的图文解析将用更详细的演示图。
二、raft算法规则设计
这部分内容对理解raft和代码实现都是很有意义的。当然也可先大致了解一下，后面看完图文解析之后再回过头来细细品味，或者一边对照着一点看图文解析，或者直接跳过这章看第三章图文解析。
1、节点需要记录的信息
currentTerm：当前最新期次号，当前节点所处任期（初始为0，不断递增）
voteFor：当前任期，该节点投票给了哪个节点，标识candidateID。（没有则为空）
log[]：消息日志数组，每条日志对应一个下标，每条日志包含指令本身内容和所属任期
commitIndex：最后一条确认提交日志的下标。（初始为0，不断递增），leader节点接收到大多数节点确认后更新该值，也就是说，log[]的长度可能大于commitIndex。
lastApplied：最后确认的已提交执行的日志下标（初始为0，不断递增，leader更替可能导致该值小于commitIndex）
以下是主节点才有的属性
nextIndex[]：主节点为每一个节点保存的下一条将要同步的日志的下标（初始为leader日志长度+1，可根据follower节点日志情况调整）
matchIndex[]：主节点为每一个节点保存的已经匹配上的最后一条日志下标。（leader更替可能导致改制远小于nextIndex，因此leader会逐渐将nextIndex-1检测，直至两者相差1。）2、选举请求与响应（RequestVote RPC）
follower经过选举超时时间等待之后，转为candidate发起投票。
请求参数：
term：candidate要竞选成为leader的任期号，值为转candidate前的follower的currentTerm+1；
candidateID：候选人ID；
lastLogIndex：candidate节点最后一条日志记录的下标；
lastLogTerm：candidate节点最后一条日志记录的所属任期（由于某些任期没有选举出leader，或者选举出leader后没有发生过日志复制，该值可能小于转candidate前的follower的当前任期（currentTerm）。）
返回结果：
term：follower当前任期号，该值如果大于candidate的currentTerm，那么candidate的currentTerm复制为该值。
voteGranted：投赞成票值为true，反对票值为false；请求端规则：（这个论文没有写，我在这里加上便于理解）
follower转为candidate之后，当前任期增加1，即currentTerm=currentTerm+1；
接收端规则：
- 1、如果接收到的请求的term<=本follower节点的currentTerm，返回false，原论文这里只有小于，实际应该小于或者等于，因为相等的情况下，说明follower早就投过同任期的票了。
- 2、如果candidate的日志跟自己的一样或者比自己的新，则投出赞成票
那么怎样才算是更新呢，论文里提到：比较两个节点日志中的最新的日志记录，然后比较这两条日志记录的下标和所属任期号，所属任期号比较大的日志记录，那么它就是较新的，如果所属任期号相同，再比较下标值，下标值较大的则是较新的那一条。- 3、若请求参数里的term大于自己的currentTerm，follower投票后，将自己的currentTerm赋值为请求参数term；（这条也是自己加的，论文体现在后面的节点规则中，）
3、AppendEntries RPC
由leader发起，用于日志记录备份请求，或者心跳检测请求
请求参数：
term：leader节点的当前任期号currentTerm。
leaderID：主节点ID，follower更新到votedFor字段；当follower接收到客户端请求，follower告诉客户端主节点是哪个，并将请求转发过去。
prevLogIndex：即将要复制的日志记录的上一条日志记录的下标
prevLogTerm；即将要复制的日志记录的上一条日志记录的所在任期号；
entries[]：需要复制的日志数组；（心跳检测只是entries没有内容而已)
leaderCommit：leader节点要提交的日志记录下标；返回：
term：follower的任期号，leader用于对该节点的状态更新
success：follower包含prevLogIndex，prevLogTerm对应的日志，则备份成功返回true，否则返回false；
接收端处理规则：
1、如果传送过来的term小于follower节点的当前任期号currentTerm，返回false；
2、如果follower节点对应prevLogIndex，prevLogTerm的位置没有日志记录，返回false；
3、如果follower已经存在一条日志与新传输的日志冲突（下标相同，但是任期号不同），则删除该日志及其index大于这条记录的日志。
4、追加所有不存在的日志；
5、如果leaderCommit大于follower节点的commitIndex，将commit设置为（leaderCommit和最新日志记录下标的最小值），体现在leader节点的日志比follower多，follower追加日志的场景。4、各个节点逻辑规则
所有节点规则：
- 如果commitIndex>lastApplied，则将lastApplied逐次加1，执行lastApplied下标对应日志的内容。
- RPC请求或者响应里的任期号term T大于自己的当前任期号currentTerm，则将自己的当前任期号设置为T；（确保所有节点的currentTerm都是最新的）
follower节点的规则：
- 对来自leader和candidate的RPC请求应答；
- 如果选举超时时间内没有收到leader节点的AppendEntries RPC请求，或者没有收到其他候选人的投票请求，则自己变为候选人。
- 如果follower收到leader节点的AppendEntries RPC请求，或者收到candidate节点的vote请求后投了赞成票后，该follower节点复位超时等待时间，重新计时（比如，原先分配的超时时间为1s，在等待了500ms后接收到以上的两种情况请求，重新分配一个超时时间1.1s,重新开始等待计时。）保证leader节点任期稳定。（这条是自己加的。论文没有）
candidate节点：
- 成为候选人后，开始选举过程：
- 将自身的当期任期号+1，即currentTerm= currentTerm+1；
- 投自己一票；
- 重新开始选举超时计时
- 发送requestvote RPC请求到其他节点；
- 如果获得大部分节点的赞成票，则成为leader；
- 如果接收到新leader的appendEntries RPC，则回退到follower；
- 如果该任期没有结果，重新等待所有节点中的其中一个（包括自己）成为candidate，重新开始选举过程；
leader节点 ：
- 成为leader后，马上发送一轮空内容的appendEntriesRPC请求（即心跳请求），且重复发送，避免其他的节点等待计时到达超时等待时间发起新的选举操作。
- 接收到客户端命令后，将其封装为日志追加到日志数组，执行该命令后，返回结果给客户端；
- 如果leader的最后一条日志记录的下标大于或者等于某个follower节点的nextIndex，则发送appendEntriesRPC请求，entries数组中包含leader节点log数组该follower的nextIndex及大于nextIndex的所有日志。
- 如果成功：更新leader中该follower的nextIndex和、matchIndex；
- 如因为一致性问题，追加失败（即appendEntries RPC接收端处理规则的第2条）。则将nextIndex-1，再次发起appendEntries RPC。
- 如果存在一个满足N > commitIndex和大部分节点的matchIndex >= N并且log[N].term == currentTerm的 N，则将commitIndex赋值为 N。这条规则隐藏两层意思，一是存在多条日志已经被多数follower节点复制，也就是先更新matchindex，当多数节点的matchIndex都更新后才更新commitIndex。二是leader只能提交当前任期的日志，如果有往期的日志有多数复制了，不能由当前任期的leader提交，二是在当期leader提交当期日志时，间接提交。这也表明有可能有些日志没有执行到状态机，那么就需要检测lastApplied是否小于commitIndex，从而执行往期的指令。
安全约束：
- election safety：对于任意一个任期，最多只有一个leader；
- leader append-only：leader节点从不删除或者覆盖自身的日志，只追加；
- log matching：如果两个日志在相同下标位置的日志所属任期号相同，则表明这两条日志及更早的日志都相同
- leader completeness：如果某个日志在某个任期被提交了，那个这条日志一定会出现更高任期的leader节点日志里。
- state machine satety：如果leader已经在给定下标位置的日志应用到状态机，那么其他任何节点都不能再同一个下标提交不同的日志
日志匹配特性（Log Matching Property）：
- 如果在不同节点日志数组里的两条日志记录拥有相同的下标和任期号，那么它们包含的命令肯定是一样的。
- 如果在不同节点日志数组里的两条日志记录拥有相同的下标和任期号，那么这些日志在这个下标以前的日志记录都是完全相同的。
解释：**一、**leader的日志只能追加不能删除或者覆盖，因此所有follower的日志里，如果下标和任期号与leader的相同，那么他们的日志内容肯定一样。**二、**由于leader发送一个 AppendEntries RPC时，请求中包含请一个日志记录的下标和所属任期号，follower找不到对应下标和任期的日志时，拒绝更新该日志，leader会继续往前检测下标和任期在follower对应的日志存不存在。
三、选举与日志复制图文解析
在开始之前，先介绍一个模拟raft的工具,如下图：
场景模拟演示与解析
这部分内容，会根据不同场景解释第二章中的规则；
1、选举
场景1：所有节点都正常
刚启动，所有节点开始选举超时时间计时
（1） s4最先到达选举超时时间成为candidate，节点当前任期currentTerm从1设置为2,向其他节点发起RequestVote RPC请求，并投了自己一票。（请求参数term=2，candidateID=s4）
（2） s1、s3、s5接收到s4的vote请求后，voteFor设置为vote请求参数的candidateID：s4,currentTerm设置vote请求参数的任期号2，投出赞同票；
s2在还没接收到s4发起的RequestVote RPC的时候，也到达了选举超时时间，也成为了candidate，currentTerm从1设置为2,向其他节点发起RequestVote RPC请求。在接收到s2的vote请求后，发现自己的currentTerm跟s4的一样，投了反对票。（follower的当前任期号大于或者等于candidate的任期号，follower都会投反对票）
（3） s4接收到三个赞同票加上自身一票，一共4票，超过半数，成为leader，并开始发送心跳请求。
s1,s3,s4,s5收到s2的vote请求后，节点任期号均与s2相等，投出反对票。
（4） s2无法获得多数赞同票，并在接收到leader节点的心跳请求后，回退为follower。leader节点s4在收到心跳请求响应后，为每个节点设置nextIndex（初始值：1）和matchIndex（初始值：0）（这两个值leader节点维护）。
follower节点每收到一次请求（AppendEntries RPC）均重置等待时间，重新计时，保证leader节点稳定，这也要求AppendEntries RPC请求发送间隔要远远小于选举超时时间。
场景2：leader节点宕机，剩下4个节点参与选举
四节点选举时，存在两种情况（1、一个候选者获取多数选票，2、两个候选者各获得一半选票），不过这里合并一起讲。
（1） s4宕机后，所有的follower节点继续选举超时计时。
（2） s1、s5同时到达选举超时时间，均称为candidate，任期号均+1，各自给自己投一票，发起vote请求。并重新开始选举超时计时。
（3） s2节点currentTerm为2，接收到s1的请求后，发现自己的currentTerm小于s1的currentTerm，s2的currentTerm设置为s1的currentTerm，并投出赞同票，紧接着又收到s5的vote请求，此时s2、s5的currentTerm相同（即s2已经投过任期号为3的票了），s2投出反对票。s3则是先接收到s5的vote请求，对s5投了赞同票，对s1投了反对票。
（4） 此时，s1、s5均只获得两个选票，无法成为leader，继续向挂掉的节点发起vote请求，试图获得选票，当然是不会获得回应的。
（5） 在s1、s5继续向s4发送vote请求的同时，四个节点继续选举超时计时
（6） s5首先结束等待，转为candidate，currentTerm+1设置为4，发送vote请求。
（7） s1、s2、s3currentTerm设置为4，均投出赞同票，voteFor设为s5；
（8） s5成为leader，发送心跳请求，为每个follower节点设置nextIndex和matchIndex。
**场景3：宕机节点重启，并很快到达选举超时计时** 这种情况实际包含了s4正常重新加入集群的情况，只不过前面多了一点插曲 > >（2）s4重启，并很快选举超时计时结束，成为candidate，currentTerm+1设置为3，发起vote请求。 （3）其与四个节点当前任期均为4，均投反对票，在响应中反馈term为4； （4）s4收到响应后，将currentTerm设置为4。leader节点s5发送心跳请求（带参数leaderID:s5）,s4接收心跳请求后，更新voteFor字段值为s5并向s5响应成功，leader s5收到响应后设置s4节点的nextIndex和matchIndex。
**场景4：某个follower节点在某段时间因为网络问题无法收到leader的心跳请求，在这段时间内成为candidate，在发送vote请求时，网络又恢复正常** > （1）follower节点s1，因网络问题无法收到leader节点s5的心跳请求，到达选举超时计时，成为candidate，currentTerm+1设置为5，在发送vote请求时，网络恢复正常。此时leader也在持续发送心跳包。 （2）此时s1的任期号大于其余所有节点的任期号（包括leader，目前先不考虑存在日志情况），其余所有节点均投了赞同票（图中小箭头“-”为false，“+”为true）并各自将currentTerm设置为5。s5停止发送心跳请求，s2/s3/s4对原先leader的心跳请求响应false； （3）s1获得大多数选票，成为leader，开始发送心跳请求，维护所有follower节点的nextIndex和matchIndex。 这种场景会导致leader节点频繁变更造成动荡，当然这种场景发生的几率很小，这就是为何论文中要求，心跳检测间隔时间<<选举超时时间<<故障发生时间间隔。这么看来，似乎没有什么优化的必要。
以上均是不含日志情况下的选举（日志条数一样的情况类似），下面将分析日志条数不一样的场景
首先先模拟场景（这个模拟也是模拟脑裂的场景，只不过这个模拟工具无法实现网络阻隔，但是这难不倒我们，我们可以分步来）
（1）leader s5在在任期3完成日志复制
（2）s5掉线后，重新选举了s3为leader，此时（假设）出现网络阻隔，s1/s2/s5可以相互访问，s3/s4可以相互访问，阻断后，leader s3继续接收客户端请求完成日志复制，并同步到s4;
（3）阻隔后，s5重新启动，并由s1/s2/s5三个节点重新选举出leader s1(五个节点三个赞同票)，这里虽然停掉了s3/s4，但通过想象我们可以当做这两个节点还在运行，这样就模拟出了脑裂的场景，s1和s3两个leader同时存在
（4）如果此时网络恢复正常。此时如果s3发送心跳请求，则会被s1/s2/s5拒绝该请求响应false（s3任期较小）；或者s1发送心跳请求，s3/s4接收请求并响应true。这两种情况都会让s3/s4纳入s1的管辖。s1记录s3/s4的matchIndex为2、nextIndex为3；如下图：下面两个场景（所有节点在到达选举超时时间之前任期号相同，但日志长度不一样的两种场景）的分析，则从这个图开始，这里先将s1 resume一下，重新开始计时。
（1）leader 节点s1 resume之后，重新开始计时
（2）假设此时s1最先计时完成结束等待 成为candidate，currentTerm+1设置为6，发起投票，投票请求中lastLogIndex为2，lastLogTerm为3。
（3）s2/s5最后的log entry的index为2等于vote请求的lastLogIndex，log[lastIndex].term为3等于vote请求的lastLogTerm。这两个节点投出赞同票；s3/s4 log[lastIndex].term为4，日志更新，投反对票。
（4）但s1依旧获取多数票，成为leader；leader s1维护matchIndex表和nextIndex表，此时所有follower节点matchIndex均为2，nextIndex均为3；s3/s4的多余日志后续会删除（后面的日志复制小节解析）
（5）假设在（1）之后，不是s1先结束超时等待，而是s3，那么s3成为candidate，currentTerm设为6，投票请求中lastLogIndex为5，lastLogTerm为4。此时所有的follower收到请求都响应true。
（6）s3成为leader，维护matchIndex表和nextIndex表，此时所有follower节点nextIndex均为6（leader初始化给所有的follower的nextIndex设置为lastIndex+1），后续s3发送心跳包，逐个index（nextIndex–）检查matchIndex（后面的日志复制小节解析）
继续上面的场景
（1）关闭s4/s3,重新选举s1为leader（s1发起投票，获得s2/s5的赞同票）
（2）leader收到客户端请求，添加新日志。
（3）重启s3/s4,让s3到达超时发起vote请求，明显只有s4会将currentTerm从6变为7 ，响应true；其他follower节点的currentTerm本来就是7，响应false；当然这里只是为了演示需要做了个中间状态。现在resume s1。
（4）s3到达超时计时发起vote请求，可以看到，由于s1的最后一个log entry的任期号为7，大于vote请求的lastLogTerm，该节点投了反对票。
（5）反过来，如果是s1发起vote请求，s1的最后一个log entry的任期号是大于其与所有follower的最后一个log entry 的任期号，s1将获得所有赞同票。
当candidate和follower日志不同的时候，选举情况看似复杂，其实是归结起来就两句话：日志里最后一个log entry的term更大的日志更加新，如果这个term相等，那么最后个log entry 的index更大的日志更新。
2、日志复制
场景1、leader固定一个，新增日志顺序复制
（1）集群初始化选举完成之后，s5当选为leader（currentTerm：2），leader中记录所有follower节点matchIndex为0；nextIndex为1；commitIndex为0；lastApplied为0；
（2）leader节点s5接收到客户端请求,将命令包装成日志，s5节点log[]添加日志记录。
（3）leader节点向其他节点复制日志，请求内容（leaderID：s5,prevLogIndex:0,prevLogTerm:2，leaderCommit：0）,所有follower接收日志请求完成复制。leader节点为响应已被收到的follower设置matchIndex和NextIndex，如s1,matchIndex设置为1，nextIndex设置为2；leader 节点接收到多数follower响应，commitIndex设置为1，同时将命令执行到状态机lastApplied+1；（由于lastApplied不那么重要，后续忽略它）
（4）leader确认提交后需要告知follower，论文里没有使用专门的请求来告知通知状态，那么就是复用AppendEntries RPC（要么心跳请求，要么日志复制请求）。请求内容prevLogIndex:1,prevLogTerm:2，leaderCommit：1；follower收到请求后，设置自身节点commitIndex=leaderCommit;
(5)全部follower节点均文成commitIndex修改，表明已提交状态；
场景2、在leader复制完日志收到大多数确认之后，发生网络问题，leader切到其他节点。
（1）s5继续接受客户端请求，添加日志记录
（2）s5向follower发送日志复制请求，follower接收到请求，检测index== prevLogIndex== 1的位置包含log[prevLogIndex].term == prevLogTerm == 2的日志，发现存在对应log entry，则完成日志复制返回true（如不存在logentry则返回false，若存在log entry ,但logentry.term不等于prevLogTerm，删除掉并返回false，这样就保障了follower节点跟leader节点的顺序一致）并收到大多数成功恢复，为每个响应true的follower设置matchIndex+1，nextIndex+1, 并设置自身commitIndex+1；
（3）s5收到全部响应后提交日志，但还没来得急向follower发送下一次心跳请求告知已提交状态（即commitIndex+1）就发生网络震荡，然后s1当选为leader，任期号为3，为所有节点初始化matchIndex为0，nextIndex为3。并继续通过心跳请求中的prevLogIndex（值为nextIndex-1）开始往前检测最后match的index。follower中prevLogIndex对应位置若不存在日志或者存在日志但所属term不等于prevLogTerm则返回false，leader将对应的follower的nextIndex-1，并继续发送心跳请求检测matchIndex;
（4）此时s1.commitIndex比s5.commitIndex小1,不更新commitIndex，其余的follower.commitIndex== s1.commitIndex,也不更新。按规则，当前任期leader不提交往期日志的规则，index为2的log entry，即便完成了大多数复制，依然无法提交
（5）此时再发生网络震荡s5重新当选，任期号为4；
（6）由于s5的commitIndex本就是已提交后+1过的，因此发送心跳包时，心跳请求中的leaderCommit== s5.commitIndex == 2 大于其余follower.commitIndex == 1。所有的follower节点修改commitIndex为2。也就是所有follower提交index为2的log entry。这看起来是不是像当期leader提交往期日志，然而并不是，index为2的logentry，在任期2的时候就已经提交了，并执行到状态机，但是只有s5知道，因此s5重新当选后，只不过是同步状态。那么如果在发生网络问题，切换leader之前，leader节点还没有收到大多数确认呢：
这种情况下，leader从s5切到s1再切回s5，都不会提交index为2的log entry。因为此时所有的节点commitIndex都是1。
那么往期的多数复制的日志什么时候提交呢？请看下图：
（1）在集群任期2时，发生网络震荡，经过几次选举，在任期5选举s1为leader，发送心跳请求后，并没有提交index为2的log entry。
（2）此时leader 节点s1接收到客户端请求，写入日志。向follower节点发起日志复制请求。
（3）follower节点复制完成后，响应true，leader节点s1为成功响应的follower节点设置matchIndex+1，nextIndex+1；leader节点s1接收到大多数成功响应后，提交日志，commitIndex设置为3，这里隐式将index为2的log entry提交了；此时lastApplied== 1小于commitIndex，log[]中的log entry将从index2开始逐条执行到状态机，知道lastApplied== commitIndex。
（4）leader节点s1向其他节点发起心跳请求，此时请求中的参数leaderCommit为3；follower接受到请求后，修改commitIndex为3，表示已提交相应log entry。
为什么采取这样的方式？：既然讲到这里，那就一起吧各节点日志长度不一样的场景一起在这里解析：
（1）假设此时s3/s4/s5与s1/s2发生网络隔离，此时leader节点s1陆续收到客户端请求，但此时只有s2一个follower存活并完成日志复制，matchIndex为6，nextIndex为7。
（2）（3）因此同时，s3/s4/s5选举了s5为leader，任期号为6、并接收到了客户端请求。
（4）此时网络恢复，同时s5宕机。重新选举了s1为leader，初始化所有follower对应的matchIndex为0；nextIndex为7。并发起心跳请求，以对s3发起的心跳请求为例，对其发送的心跳请求参数（prevLogIndex:6,prevLogTerm：5）
（5）follower接收到心跳请求，如s3,开始检测prevLogIndex对应位置的日志，发现不含日志，返回false，其他follower也同样。
（6）leader节点收到s3的false响应，将nextIndex-1，设置为6，重新对其发起心跳请求（prevLogIndex:5,prevLogTerm：5（leader中index== 5对应的log entry所属的term））以此类推
（7）（8）最终通过prevLogIndex== 3在follower s3中找到存在log entry的对应index，s3向leader响应true，leader s1收到响应后修改其matchIndex为3，nextIndex为4，其余follower也同样。s5由于宕机无法响应，不修改，但leader继续向其发送心跳请求。然后leader根据所有follower的matchIndex情况追加log entry。
论文中在这种情况说到一种优化，就是请求响应false时，直接将follower节点的commitIndex一同响应回leader，但论文又提到，由于宕机的情况很少，该优化不太必要。个人以为这个优化还是很有必要的，尤其可以大大缩短故障恢复时间。
（9）问题还没完。此时s5重启，而且还发起vote请求，并收到多数赞同票成为了leader（因为其最后一条日志的所属term大于其他任何节点最后一条日志的所属term）
（10）leader s5为所有的节点设置matchIndex为0，nextIndex为5，并开始检测follower的matchIndex。
（11）（12）检测的方式跟步骤（6）（7）（8）类似，但此时是prevLogIndex对应位置有log entry，但是所属任期不相等，这种也是返回false。最终确定matchIndex和NextIndex，如s3:matchIndex为3，nextIndex为4。然后开始发起日志复制请求（prevLogIndex:3,prevLogTerm：5，entry[]中包含matchIndex之后的所有log entry）；
（13）follower节点接收到日志复制请求后，发现prevLogIndex+1的位置有日志（matchIndex不是这个位置，说明这个位置的logentry肯定是冲突的，即所属的任期不一样）则删除该位置及后面的所有log entry，然后在该位置追加请求中带过来的entry[]内容。
这里就演示了，即便大多数复制的内容也可能被覆盖。如果在步骤（9）中s1在完成多数节点复制后提交了往期的日志并执行到状态机，但是还没将提交状态同步到其他节点，或者已经同步了状态。此时S5发起的vote请求依然能成为leader，顺利完成（9）之后的流程，这样就覆盖了已提交的log,与状态机的状态不一致了。
那为什么当期提交就没问题呢？
当期的leader能保证提交当期的日志时最新的，往期的日志leader不能保证是最新的（比如s5的第四个log entry才是整个集群最新的日志记录）。
那么只有在多数复制后，又有新的当期日志（肯定是所有节点中最新的）提交，才能顺带往往期的一起提交：
这个图就不再解析了，上面的流程都讲到过相关的内容
很明确的一点：已经提交应用到状态机的日志，不能被覆盖修改，这是数据一致性安全的要求。
3、leader的完整性（Leader Completeness Properties）验证
论文中对leader的完整性（Leader Completeness Properties）用了一个很啰嗦的反证。其实就是只要是leader能确认提交的日志肯定是多数复制了，且当前任期号的日志肯定是最新的日志，那么下一任期选举，一定会有包含该条最新日志的节点参与选举才能有节点得到多数选票，且一定是包含最新日志的节点得到多数选票。
可以想象存不存在s2中index为3，任期为5的日志。答案是肯定不存在的，任意一个任期的某条日志（如任期4时，s1在index3的日志），这条日志肯定是当前最新的，如果该条日志被提交那么肯定这条日志被复制到大多数节点，那么在下一次选举中，剩下的少数节点中的任意一个肯定不会被选举为leader（能得到的票数最多为n/2 -1,此例中肯定不会超过2票，如上图在任期5的选举，s4或者s2如果成为candidate发起vote请求，最多只能得到两票），由此保证了下一任期的leader的日志完整性。
后面的成员配置边和日志压缩等就先不玩了。。。
参考：
http://thesecretlivesofdata.com/raft/
https://raft.github.io/raftscope/index.html
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md#51-raft-基础
Raft算法详解
Paxos算法详解一文讲述了晦涩难懂的Paxos算法，以可理解性和易于实现为目标的Raft算法极大的帮助了我们的理解，推动了分布式一致性算法的工程应用，本文试图以通俗易懂的语言讲述Raft算法。一、Raft算法概述不同于…
一文搞懂Raft算法 - xybaby - 博客园
raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上，因为在学术理论界，最耀眼的还是大名鼎鼎的Paxos。但Paxos是：少数真正理解的