安全性
在raft论文学习-raft basics & leader election和raft论文学习-log replication文章中已经介绍了raft算法的领导人选举和日志复制，然而它们并不能充分的保证每个节点会按照相同的顺序执行相同的指令，所以需要一些约束条件来保证节点执行顺序的安全性。例如，当一个follower节点挂掉后，leader节点可能提交了很多条的日志条目，挂掉的follower节点很快重启后可能被选举为新的leader节点，新的leader节点接收日志条目后会复制给其他follower节点，会导致follower中的日志条目被覆盖，这会导致不同的节点执行的不同的指令序列。对于上述情况，raft算法通过增加约束限制来保证对给定的任意任期号，leader都包含了之前各个任期所有被提交的日志条目。
选举约束
任何基于leader的一致性算法，leader最终都必须存储所有已经提交的日志条目。在viewstamped replication一致性算法中，一开始时并没有包含所有已经提交的日志条目的节点也可能被选为leader,这种算法会用一些额外的机制来识别丢失的日志条目并将它们传送给新的leader,不过这种方法会导致比较大的复杂性。raft使用了一种简单的方法，可以保证新的leader在当选时就包含了之前所有任期号中已经提交的日志条目，所以不需要再传送日志条目给新leader.这样保证了日志条目传送的单向性，只能从leader传给follower，并且leader从不会覆盖本地日志中已经存在的条目。
那raft是如何保证新的leader在当选时就包含了之前所有任期号中的已经提交的日志呢？raft做法是新的leader选出有约束限制，一个candidate并不是获得大多数节点的投票就能当选。除非该candidate节点包含了所有已经提交的日志条目。candidate节点为了赢得选举必须与集群中的过半的节点通信，而已提交的日志条目肯定存储到了过半的节点上，那么与candidate进行通信的节点中至少有一个节点包含有所有已经提交的日志。
在requestVote RPC中raft限制了如果投票者自己的日志比candidate的还新，它会拒绝掉该投票请求。这里比较日志哪个更新的定义是：
- 如果两个日志的任期号不同，任期号大的日志更新
- 如果两个日志的任期号相同，日志较长的日志更新
有了这里的约束，一个candidate要想成为leader，必须赢得过半节点的投票，而这过半节点中至少有一个拥有所有已经提交的日志，所以这个candidate也拥有所有已经提交的日志，当它成为leader时已经有所有已经提交的日志了。
提交之前任期内的日志条目
对应「当前任期内」的日志条目如果已经存储到过半的节点上，leader就知道该日志条目已经被提交了。然而，如果是之前任期内的日志条目已经存储到过半的节点上，leader也无法立即断定该日志条目已经被提交了。下图（来自raft论文）展示了这种情况，一个已经被存储到过半节点上的旧日志条目，任然有可能被将来的leader覆盖掉。
上图中的S1到S5是集群中的5个节点，方框表示日志条目，方框中的数字表示任期term, 最上面一行的数字表示日志索引index.
- 在(a)中，S1是leader节点，部分地复制了index为2的日志条目到S2节点中。
- 在(b)中，S1崩溃了，然后S5在任期3通过节点S3、S4和自己赢得选举，然后从客户端接收了一条新的日志条目放在了索引2处。这里在分析下为什么S5可以当选为leader节点，根据前一小节的约束，S5的term为3，S3和S4的term为1，所以当S3和S4收到S5的 requestVote RPC时，是满足S5的日志比S3和S4新的，因为term较大，会投票给S5.
- 在(c)中，S5崩溃了，S1重新启动，选举成功，继续复制日志，来自任期2的日志已经被复制到了集群中的大多数节点上，但是还没有提交。这里继续分析下为啥S1又又可以成为leader节点，因为它的term为4，比S2、S3、S4和S5的term都大，所以是满足前一小节约束条件的，可以成为leader节点。
- 在(d)中，S1又崩溃了，S5通过来自S2、S3和S4的投票重新成为leader节点，然后覆盖了S2和S3中index为2处的日志。
现在我们来思考场景(d)是正确的还是错误的？答案是正确的，是不是有点出乎意料。因为从客户端的角度看，在场景(b)的时候，S1作为leader崩溃，term为2的日志返回给客户端肯定是超时或者出错的。也就是说对于term为2的日志，在(d)中被覆盖(丢弃)，还是节点存储下来，都是正确的。
但是从raft规则的角度来看，「这不满足raft规则：一条日志一旦被复制到了多数节点上，就认为这条日志是commit状态，这条日志是不能被覆盖的」，但是现在却被覆盖了!!! 那怎么办呢？修改commit的规则定义。新的规则为：新的leder被选举出来后，对之前任期内的日志，即使已经被复制到了多数节点，任然不认为是commit的。只有等到新的leader在自己的任期内commit了日志，之前任期内的日志才算commit了。
也就是说raft不会通过计算副本数目的方式来提交「之前任期内」的日志条目。只有leader「当前任期内」的日志条目才通过计算副本的方式来提交。对应到上图中的(e),在崩溃之前，如果S1在自己的任期(term=4)里复制了日志条目（term=4,index=3)到大多数节点上，然后这个日志条目就会被提交（S5不可能选举成功，因为它的日志没有S1、S2和S3新，这三个节点拒绝为S5投票，S5不可能获得大多数选票)，在这种情况下,之前的(term=2,index=2)的日志也被提交了。不会出现term为2被覆盖的情况，S5老老实实成为follower节点，让term为2的日志覆盖它的term为3的日志。
场景(d)和(e)从客户端角度来看，都是正确的。场景(d)之所以出现日志被覆盖的情况，是因为term为2的日志不是一次性被复制到多数节点，而是跨越了多个任期，断续地被复制到多数节点。新选举出来的leader不能认为这种日志是commit的，需要延迟等到新的任期里面有日志被commit后，之前任期内遗留的日志被顺便变为commit状态。
raft修改commit规则增加额外复杂性是因为新选举出来的leader在复制之前任期内的日志条目时，这些日志条目都保留的是原来的任期号。在其他的一致性算法中，如果一个新的leader要重新复制之前任期里的日志时，必须使用当前新的任期号。raft算法保持原来的term有两个好处：一是更容易追溯日志条目，因为term是不变的嘛，二是新leader只需要发送更少的日志条目，其他算法必须在它们被提交之前发送更多的冗余日志条目对日志重新编号。
安全性证明
leader的完整性证明采用了反证法，即假设leader的完整性是不满足的，然后推出矛盾。假设任期T的leader在任期内提交了一个日志条目，但是该日志条目没有被存储到将来的某些任期的leader中，并假定U是大于T的没有存储该日志条目的最小任期号。下图来自raft论文。
图中的集群有5个节点，节点S1在任期T是leader,提交了一个新的日志条目。然后S5在之后的任期U(T<U)里被选举为leader.那么肯定至少会有一个节点，比如S3，既接收了来自S1的日志条目，又给S5投票了。
- 任期为U的leader节点一定在刚成为leader的时候就没有那条被提交的日志条目了，因为leader从不会删除或者覆盖任何日志条目
- 任期为T的leader会复制日志条目给集群中过半的节点，同时任期为U的leader从集群中的过半节点赢得了选票。因此，至少有一个节点同时接受了来自leader T的日志条目并给leader U投票了
- 投票的节点在给leader U投票之前先接受了从leader T发来的已经被提交的日志条目，否则它会拒绝来自leader T的 appendEntries请求，因为它的任期号比T大
- 投票的节点在给leader U投票时依然保有这条日志条目，因为任何U、T之间的leader都包含该日志条目，leader从来不会删除日志，并且follower节点只在跟leader冲突的时候才会删除条目
- 投票的节点在把自己投票给leader U节点时，leader U的日志必须至少和投票者的一样新，这就导致了下面的两个矛盾
- 如果投票者和leader U的最后一个日志条目的任期号相同，那么leader U的日志至少和该投票者的一样长，所以leader U的日志一定包含该投票者日志中的所有日志条目。这与假设leader U不包含投票者日志是矛盾的
- 如果6不成立，那leader U的最后一个日志条目的任期号就必须比该投票者的大，此外，该任期号也比T大，因为该投票者的最后一个日志条目的任期号至少和T一样大。创建leader U最后一个日志条目的之前的leader一定已经包含了该已被提交的日志条目。根据日志匹配特性，leader U一定也包含了该已提交的日志条目，与假设矛盾
- 所以所有比T大的任期的leader一定都包含了任期T中提交的所有日志条目
- 日志匹配特性保证了将来的leader也会包含间接提交的日志条目
follower和candidate节点崩溃情况
前面分析了leader崩溃的情况，follower和candidate节点崩溃的情况要比leader简单不少，并且它们两者的处理方式是相同的。
- 如果follower或者candidate崩溃了，那发给它们的requestVote和appendEntries RPC都会失败，raft通过「无限的重试」来处理这种失败，当崩溃的机器重启后，这些RPC就会成功地完成。
- 如果一个节点在完成了一个RPC但是还没有响应的时候崩溃了，当它重启之后会再次收到相同的请求，raft的RPC是幂等的，所以重试不会有副作用。
定时和可用性
raft算法的其中一个要求是安全性不能依赖定时：整个系统不能因为某些事情运行得比预期快一点或者慢一点就产生错误的结果。但是可用性不可避免的要依赖于定时，例如当有节点崩溃的时候，消息交换的时间会比正常情况下长，没有一个稳定的leader，raft是无法工作的，所以candidate不能等待太长的时间来赢得选举。
leader选举是raft中定时最关键的要素，只要整个系统满足下面的关系，raft就可以选举并维持一个稳定的leader.
广播时间(broadcast time) << 选举超时时间(election timeout) << 平均故障间隔时间(MTBF)
广播时间：节点并行地发送RPC给集群中所有其他的节点并接收到响应的平均时间
选举超时时间：这个一般是用户设定的
平均故障间隔时间：对于一个节点来说，两次故障间隔时间的平均值
广播时间必须比选举超时时间小一个数量级，这样leader才能够可靠地发送心跳来阻止follower开始进入选举状态，再加上随机化选举超时时间的方法，使得瓜分选票的情况几乎不可能。选举超时时间需要比平均故障时间间隔小几个数量级，这样整个系统才能稳定的运行。当leader崩溃后，整个系统会有大约选举超时的时间不可用，希望这个时间只是占整个时间的很小一部分。
上面的三个时间值如何设定呢？广播时间和平均故障间隔时间是由系统决定的，我们自己设置的是选举超时时间。raft的RPC需要接收方将信息持久化的保存到稳定存储中，所以广播时间大约在[0.5,20]毫秒之间，选举超时时间在[10,500]毫秒之间，大多数的节点平均无故障间隔时间都在几个月甚至更长，很容易满足时间的要求。
