谈谈raftfig8——迷惑的提交条件和选举条件
谈谈raft fig8 —— 迷惑的提交条件和选举条件
前⾔
这篇⽂章的思路其实在两个⽉前就已经成型了，但由于实习太累了，⼀直没来得及写出来。⼤概⼀个⽉前在群⾥和群友争论fig8的⼀些问题时，发现很多群友对fig 8是充满了迷惑的。我个⼈在做lab的时候也对fig 8的问题感到⾮常头疼，真正⼤概理解这个问题的来龙去脉（⼤概？）的时间⼤概是两个⽉前复习raft的时候，⽽此时距离我做完lab已经⾜⾜⼀年有余了......这个问题难于理解，其实raft的作者要⾄少背⼀部分锅的——2014年的论⽂⾥，对于这个问题的讨论不是很充⾜，很多该回扣的点并没有回扣到。我这⾥尝试按照我⾃⼰的理解，梳理⼀下fig 8问题的原因。如果你想要看懂这篇⽂章，请⾄少把raft的论⽂完整的读⼏遍，如果懂basic paxos再好不过了，因为理解了ba罗技鼠标宏设置
sic paxos对于理解fig 8的问题⾮常有帮助。
迷惑的提交条件
如果⼀个操作得到了提交，那么相当于系统给出了⼀个保证：只要是这个系统是能推进的，那么这个操作⽇志迟早会被apply。如果⽇志能够提交，这条⽇志必须要满⾜某些条件，在满⾜了所有的条件的瞬间，这条⽇志的状态就是已提交的，即使它的index⾼于commitIndex。
那么细化来说，这些条件是什么呢？对于数据库中的事务，提交条件是该事务所有的WAL Log均已落盘；对于Percolator式的分布式事务，提交条件是Primary成功提交；但是对于Raft中的⽇志呢？如果回顾论⽂你可能会⽐较惊讶，直到讨论fig 8的问题之前，作者似乎都回避了这个问题，只是⼀味的说，⽇志只要成功备份到了Majority上，就提交它。初次阅读论⽂时，我们潜意识中便隐隐约约的埋藏了这样⼀个先⼊为主的错误认知——只要⽇志备份到了Majority上，就可以提交它，连带着提交这条⽇志之前的所有⽇志。然后论⽂来到了5.4，作者开始打我们的脸，告诉了我们⽇志的真正提交条件：要么被连带提交，要么只能提交⼀条term == 的⽇志。
读到这⼀部分，你只需要知道，在raft算法中，⽇志真正的提交条件为，要么被连带提交，要么只能提交⼀条term == 的⽇志，就可以了。如果⽇志不满⾜这个提交条件，那么它被截断是合理的。
迷惑的选举条件
现在让我们先忘掉raft⽇志的提交条件，先梳理⼀下raft算法的部分基本规则：
1. 采⽤逻辑时钟term，⼀个term内⾄多有⼀个leader，candidate之间通过选举算法竞选leader；
2. ⽇志流是单向的，只允许⽇志从leader流向follower；
3. 对于⽇志冲突的场景，直接截断follower不匹配的⽇志，替代以leader的⽇志；
综合2和3，我们不难发现，leader必须要拥有所有commitable的⽇志；根据2，leader是⽆法从其他机器上学习到它缺失的commitable的⽇志的，根据3，leader可能截断那些commitable的⽇志。⽽根据1我们可以知道，leader当选的充分必要条件为它在那个term内得到了Majority的选票。
现在让我们来审视选举算法。论⽂中定义了candidate与follower间⽐较⽇志新旧的⽅法：
Raft determines which of two logs is more up-to-date by comparing the index and term of the last entries in the logs. If the logs
have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up-to-date.
⽐较最后⼀条⽇志，到底谁最up-to-date。如果candidate更加up-to-date，且其他更优先的条件均已满⾜（term不超过leader，尚未投出票等等），那么follower会投票给candidate。
算法看似很⾃然直观，但你会发现，这和我们之前所强调的，当选的leader必须拥有所有commitable的⽇志这⼀条件，似乎并不存在⼀个包含关系，假设存在⼀个Majority认定candidate的⽇志更加up-to-date，那个这个candidate真的拥有所有的commitable的⽇志吗？
既然我们提到了commitable的⽇志，那么肯定要讨论commitable的条件是什么。现在让我们成为那个当开始读论⽂的初学者，根据论⽂前⽂，理所应当的认定那个先⼊为主的条件吧（也就是说，令⽇志的commitable的条件为⽇志“已经备份到Majority上”），看⼀看fig 8的场景（终于到fig 8了，泪⽬）：
在fig管的成语
8的c阶段，s1是term = 4的leader，它先将(index = 2, term = 2)的⽇志备份到了{s1, s2, s3}上。根据我们所认定的那个commitable条件，既然(index = 2, term = 2)的⽇志成功备份到了Majority上，那么这条⽇志就是commitable的，当前⽇志的commitable集合为{1, 2}。到了d阶段，s5的⽇志相⽐于{s2, s3, s4}来说都是more up-to-date的，因此它能得到多数派的投票，成为term 5的leader，但当它成为了term = 5的leader的那⼀刻它开始了背刺⾏为：它截断了index = 2的⽇志，⽽这条⽇志是commitable的。究其原因，是因为在d阶段中，commitable 的⽇志集合为{1, 2}，⽽s5并不持有2，因此s5并不持有全部的commitable的⽇志。
总的来说，在commitable条件设定为“备份到了Majority上”的场景下，我们的选举算法⽆法满⾜最核⼼的那个约束：当选的leader必须持有全部commitable的⽇志，这正是5.4 safty所讨论的安全性问题。
两个⽉前当终于想到了这些东西时，我的第⼀反应就是去谴责那个该死的选举算法，选leader这么重要的算法居然⽆法满⾜这么重要的约束条件，那么这个算法就未免太寒颤了。但我很快发现这还真的不是个我⾏我上的问题：在⼀轮拉票的过程中仅涉及到了candidate和follower，这两个rver间的交
互，⼀次交互你还能指望candidate得到多少的信息呢？⽽在完全异步的⽹络环境下，即使是能和⼀个Majority
进⾏交流，⼜能做到多少的事情呢？
补⽇志or加强提交约束？
补⽇志
我们⽤精确的语⾔描述⼀下fig 8的错误场景：
在commitable的条件为“备份到了Majority上”的场景下，使⽤现存的选举算法，⽆法保证当选的leader持有所有commitable的⽇志，导致commitable的⽇志存在被截断的风险。
我们不妨先把思维发散⼀下：既然当选的leader不保证持有全部commitable的⽇志，那缺啥补啥呗！先把所有commitable的⽇志补全，再去ReplicateLogs，不就可以了吗？既然现在commitable的⽇志已经备份到了Majority上，那我只要和任意⼀个Majority取得联系就肯定能获得commitable的⽇志！诶等等这样的话选举算法的more-up-to-date貌似意义不⼤了，反正⽇志会补全，那保证单主就可以了吧！诶等等如果我们把这个联络Majority的过程普及化，任意⼀个index处的⽇志，都要先联络到Majority协商好这个index处写什么⽇志，再去写下这个⽇志，这样的话单主的约束也可以去掉，因为
每个主都要先和Majority取得联系，那么它们必定会有交集，获悉到其他主想写的⽇志！
恭喜你，你已经进⼊了basic paxos的⼤门。basic paxos解决的是多个机器对单个Value的共识问题。basic paxos中，也存在⼀个全局单增的逻辑时钟propoId。propor们不能随便的提议Value，在提议Value之前，它们必须要和Majority取得联系，要求它们拒绝⼀切propoId < myPropoId的提案，同时，如果Majority中有部分机器已经accept了⼀个Value（这个Value可能就是已提交的结果），这个propor就要考虑⾃⼰是否需要将⾃⼰的提案改成那个Value。这个过程被称为basic paxos的Prepare阶段（basic paxos的第⼆个阶段为Accept阶段，这⾥不讨论它）。现在将Value改成单条⽇志，对单条⽇志进⾏Prepare阶段，如果这条⽇志已经被提交了，那么propor就可以学到这条⽇志！对所有的⽇志均⾛⼀遍basic paxos流程，就可以保证所有的⽇志是⼀致的，这就是最朴素的multi paxos思想，实际的multi paxos⽅法会复杂很多，存在着⼤量的优化。
虽然提到了paxos，但你完全不必去担忧上述那段⽂字你⽆法理解。我这⾥仅仅是想表达⼀个观点，解决fig 8⾥的问题，⽅法不⽌⼀种，⽽raft采⽤了⾮常精彩的办法。在raft的⼀些变种中，也存在着融合paxos思想的⽅案，例如说PolarFS的Parallel Raft，不需要leader持有全部commitable的⽇志，只需要lea林志玲图片
der有最新的checkpoint就可以了，leader上任后，通过merge阶段补全所有⽇志，这个merge阶段其实就⾮常类似于paxos的perpare阶段。
不管怎样，先补全commitable的⽇志，再去ReplicateLogs是⼀个解决fig 8中所描述问题的⽅法。值得注意的是，这种⽅案下，⽇志commitable的条件仍然是“备份到Majority”上就可以了。如果有⼈问你，为什么paxos将⽇志备份到Majority上就可以提交，⽽raft这样深奥反义词
做就要在fig 8上吃瘪，你就可以告诉他，因为paxos的propor可以通过prepare阶段补全⽇志。关于paxos算法此处不再讨论，如果想要更详细的了解paxos算法务必阅读《paxos made simple》这篇论⽂。
加强提交约束
再次回顾⼀下fig 8中的错误场景：
在commitable的条件为“备份到了Majority上”的场景下，使⽤现存的选举算法，⽆法保证当选的leader持有所有commitable的⽇志。
raft的办法是，将commitbale的条件进⾏加强：⽇志要么被连带提交，要么只能提交term = 的⽇志。如果leader能够提交⼀条⾃⼰term内的⽇志，毫⽆疑问，这条⽇志之前的所有⽇志均是⼀致的。
现在再看⼀下fig 8：
将commitable的条件强化为“⽇志要么被连带提交，要么只能提交term = 的⽇志”之后，⽆
论是d还是e，均是允许的，因为index = 2的⽇志并不满⾜commitable的条件，所以这条⽇志不会被c中的s1提交，客户也收不到ok的结果，会⼀直等待，所以在图d中截断它是允许的。但这个个例并不是重点，真正的重点是，在这样的commitable条件下，“leader必须持有全部的commitable的⽇志”这⼀约束条件是满⾜的！我个⼈尝试着做了⼀下证明，放在了⽂章的末尾。
nop entry的引⼊
原论⽂中提到了nop entry。raft作者建议任何leader在上台后，先不要急着响应客户请求⽣成操作⽇志，⽽是先提交⼀条⾃⼰term内的nop-entry，成功提交后，nop entry之前的所有⽇志就保持了主从⼀致了，此时再响应客户服务。
nop entry的引⼊其实还解决了⼀个更加棘⼿的问题：在提交条件被强化后，如果新的leader上台后，迟迟不⽣成新的⽇志，那么leader就⽆法提交那些它已经成功备份到Majority，但term < 的⽇志。
尽管如此，我个⼈强烈不建议在6.824⾥引⼊nop。因为nop也是要占据logIndex的，后台的测试代码会对每个index的⽇志进⾏校验。nop并不是测试代码添加的，因此测试代码在匹配index时会报错。在6.82万开头的四字成语
4⾥，⽆需考虑也不能考虑leader⽆法显⽰提交⽇志导致进度得不到推进的场景。
总结
关于fig8的讨论就到这⾥了。我们再次梳理⼀下原论⽂中的⼀些⽐较坑的点。⾸先是fig 8中场景d的正确性。在commitable的条件为"备份到Majority上即可"时，a → b → c → d是错误的，因为c中index = 2的⽇志成功备份到了Majority上，commitable的集合为index = {1, 2}，index = 2的⽇志不允许被截断。当commitable的条件为“⽇志要么被连带提交，要么只能提交term = 的⽇志”时，a → b → c → d是正确
的，因为在c中，index = 2 的⽇志term不等于高压锅蛋糕
s1的term，因此s1并不会提交它，所以到了d时，commitable的集合仍然是index = {1}，所以d 可以截断index = 2的⽇志。
为什么我们要强化提交条件？因为我们在raft算法的设定下，我们必须要保证leader必须持有全部的commitable的⽇志"这⼀条件，⽽选举算法⽆法保证这样的leader当选，为此，要么让leader在ReplicateLogs前补全所有commitable的⽇志，要么另辟蹊径。raft的解决办法是强化了提交条件，在这个提交条件下，选举算法所选出的leader必定持有全部的commitable的⽇志。
前⽂中我提到“raft作者要为fig 8难以理解背⼀部分锅”，也很⼤程度上是因为作者没有对fig 8出现的根本原因进⾏讨论，在提出加强提交条件后也没有⽤⽂墨去回扣到选举条件上。
关于提⾼约束条件后算法正确性的证明
证明算法正确，等价于证明将c螃蟹和什么东西不能一起吃
ommitable的约束条件提升⾄"⽇志要么被连带提交，要么只能提交term = 的⽇志"，后，当选的leader必定持有全部的commitable的⽇志。可以⽤反证法，下⽂是我⾃⼰的证明，个⼈不保证证明是正确的，毕竟⼈菜瘾⼤(反证法
(1) 令TL是最后⼀次保持约束条件且成功commit了⽇志的leader，TL的最后⼀条commitable的⽇志index为c_index，term为
c_term，假设在TL之后的第⼀个错误leader为FL，即第⼀个不持有全部的commitable的⽇志，但仍然成功当选的leader。
(TL.term, FL.term)间可能存在0个或者多个leader，这些leader进⾏过ReplicateLog，但没能成功commit任何新的⽇志，也正是因此，在这期间c_term和c_index是不变的。
(2) 根据假设可知FL ∉ Majority_1。根据TL的定义可知she组合
，集群中必定有⼀个Majority_1，它们都持有这些commitable的⽇志。令
TL的最后⼀次提交时，TL的term为commit_term。根据当前的commitable条件，有commit_term == c_term。
(3) 根据投票算法我们可知，存在⼀个Majority_2认为FL的⽇志是more up-to-date的。这只有两种可能：
要么FL. ==
c_term，但index更⾼，要么虽然FL.last_log.index < c.index，但FL. > c_term。第⼀种情景是不可能的，因为这样的机器只能出现在Majority_1中，这与我们的假设⽭盾，
(4) 考虑第⼆种场景，如果FL. == FL.term，那么这条⽇志是FL⾃⼰添加的，因此它不可能靠这个⽇志去赢得选举，
这条⽇志只能是来⾃于之前term的leader。因此到了这⾥我们得到了⼀个恒等式：TL.term == commit_term == c_term <
FL. < FL.term。
(5) 根据这个不等式可知，存在⼀个before_leader，它是term为 FL.时刻的leader，它给⾃⼰添加了⼀条/⼏条⽇志，
还没来得及commit就step down了。根据(4) 中FL. > c_term == commit_term == TL.term可知，before_leader 的当选时刻是在TL成功的commit之后；⼜根据我们对TL的定义可知，before_leader肯定是⼀个持有全部commitable⽇志的leader(但它并没有成功commit更多的⽇志，否则要将它归于TL)，因此before_leader在⽣成⽇志(FL., FL.last_log.idx)时，必定是持有所
有的commitable的⽇志的，且FL.last_log.index > c.index (新⽇志是append进来的)。对应的，既然FL.last_log之前的⽇志来⾃于before_leader（复制条件文章欣赏
），那么它们的⽇志在这之前应该⼀致，因此FL必须有这些commitable的⽇志，这与我们的假设相⽭盾。综上所述，我们的假设均被否定，结论得证。
