Raft 笔记
5.3 Log replication
要保证：
-
如果不同日志中两个entry有同样的index和term, 那么储存的是同一个指令
Leader 一次只创建一entry
-
如果两个不同日志中两个entry有同样的index和term， 那么两个entries之前的记录都是一样的
通过Leader发送AppendEntries给各个follower来检查是否和Leader的log一致，如果不一致，Follower就拒绝(拒绝后操作：Leader处理不一致)
理想情况，Leader和Follower的状态是一样的，但是可能遇到上一个Leader没有复制所有的entries到日志中,或者Leader崩溃,没来得及commit log
Leader处理不一致:
当Follower和Leader的日志不一致时，Leader强制抹除Follower的日志内容并将自己的日志内容复制给Follower（Leader's log == Fowllower's log).
缺失entries，例如（a) (b）
多余的uncommitted entries，例如(c) (d)
两者都有,例如(e) (f)
Leader发送AppendEntries 给 Follower 来找到最新的已经committed了的entry，然后少了entries的添上，多了的entries删除.
对于每个Follower，Leader会维护一个 nextIndex ：index of next log entry the leader will send to that follower
当Leader第一次启动(包括更换leader），所有的nextIndex设置为Leader log 的下一个index. 上面图中是 11
如果Follower's log和leader不一致，那么下一个AppendEntry就会失败。Follower返回rejection，nextIndex--
上图b和leader的情况：
1.nextIndex是11，sendAppendEntries到b， 发现index 11没有指令，nextIndex减一并返回false，一直减到5然后发现index=4 term = 4匹配Leader的index=4，term=4， 返回true， matchIndex is 4，nextIndex是5。
2.Leader此时知道4是对的，将5的指令发送给b， b index = 5 填上4.
5.4 Safety
前面的一些机制并不能完全保证每个状态机执行的是相同的指令。比如，当Leader提交的时候，其中一个follower可能不能用了，就会commit失败，然后它被选成了新的Leader，这时候之前应该提交的entries可能被新的entries取代。结果就是，不同的状态机执行了不同的command sequence.
5.4.1 Election restriction
Raft在选取新的Leader的时候会检查candidate是不是拥有所有的committed entries，如果没有就阻止它成为Leader: 通过RequestVote RPC实现： RPC拥有candidate的log信息。
当Follower投票时， 它会拒绝投票如果它的log比candidate的更新（拥有的committed entries更多）
5.4.2 Committing entries from previous terms
不能简单的通过count大多数entries的方式提交之前term的entry。例如：在（c）中，index2 中的2是大多数，但是（c）不能因为这个就commit 2. 可能出现（d）和 （e）两种情况
（d）中，S5成为Leader后，由于自己的值3拥有比2更大的term，导致用值3将已经commit的2覆盖,所以之前2是不能commit的
下图描述了当一个old entry储存在大部分servers上 依然存在被未来新的Leader重写的可能。
解决上述问题：
因此Raft限制只能通过判断大多数的方式提交当前term的entry，进而对之前的entry间接提交，如过程e所示
