Raft 算法学习 续

log的传播
    当leader收到客户的写请求后， 它记录一个更新log， 然后把log并行的复制给其它server。在多数派完成log复制后， leader向客户回复操作成功，以确认操作被提交。如果有follower宕机或处理的速度很慢， leader会一直重试直到成功。我们先看log的组织形式。以term 和 index来标示log 如下图：
                 1                  2                3                4                5                6                7                8                       log index
  leader    1,x＝3         1,y=1          1,y=9         2,x=2          3,x=0         3,x=7         3,x=5          3,x=4                term number, operation
 follower  1,x＝3         1,y=1          1,y=9         2,x=2          3,x=0        
 follower  1,x＝3         1,y=1          1,y=9         2,x=2          3,x=0         3,x=7         3,x=5          3,x=4  
 follower  1,x＝3         1,y=1        
  follower  1,x＝3         1,y=1          1,y=9         2,x=2          3,x=0         3,x=7         3,x=5   
              |------------------------------------------提交掉的log-----------------------------------------|

    上面的示意图惨点， 不过意思到了。
    一条log什么时候被确认是提交的， 这个由leader来决定。 已经提交的log不会丢失。 ledaer把一条log复制到了多数派就可以认为这条log被提交了， 同时在leader的log中， 这条log之前的log（即便是前任leader创建的）也就被提交了。 注意， 这里的当前log应该是由当前leader创建的。 如果是前任留下来的log， 即便复制到了多数派也不能认为提交。 这个后面专门讨论。leader一直追踪着提交了的最高的log index， 并且在后续的log复制消息中带着这个信息， 这样follower就知道哪条log被认为提交了， 从而应用相应的操作到自己到状态机中。leader在一个给定的term中给定的index， 只会至多创建一条log。 这个log在log序列中的位置永远不会改变。leader在复制log给follower的时候， 总是会携带当前log的前一条log的term和index信息。 如果一个follower在自己本地信息中无法找到对应的log信息， 则拒绝这个复制log的请求。有了这个条件， 如同数学归纳法一样， leader知道只要log复制成功了， 那么follower的log序列就和自己的log序列是完全一致的。
    在正常情况下， leader和followers的log序列是一致的， 上面这种检查不会失败。 但是如果有leader宕机， 或者leader和follower交错宕机等复杂情况， 就会发生这种序列的不一致， 比如：
        1        2        3        4        5        6        7        8        9        10        11        12              log index
       
L       1        1        1        4        4        5        5        6         6        6                                     term number
a       1        1        1        4        4        5        5        6         6                   
b       1        1        1        4        
c       1        1        1        4        4        5        5        6         6        6        6                            
d       1        1        1        4        4        5        5        6         6        6        7          7
e       1        1        1        4        4        4        4
f        1        1        1        2        2       2        3        3          3        3        3

    上图中 L行是 term8 的leader， a －f 是可能的follower。 当L现在成为leader的时候， follower 有可能缺失log（a－b）， 有可能存在多出来的没提交的log（c－d）也有可能两者都有（e－f）。比如f的出现， 可能是因为在term2的时候它是leader， 然后接受三个写请求， 写了三个log。在都没有复制到其它follower的时候自己宕机， 然后迅速重启， 又成为了leader（这时term变为3）， 又接受了5个写请求。 写了5条term3的log， 然后宕机。
    在Raft中， 如果leader发现了这种不一致， 它会要求把自己的log复制给follower从而让follower跟自己达到一致。 这就是说， follower的log可能被覆写（leader的从来不会被覆写）。因为leader在选举的时候是有限制条件的（包含所有的已经提交的log）， 所以这样的同步是安全的。leader要找到follower跟自己一致的log， 然后删除follower后面的log把自己的同步给follower。 leader是通过这种方式来做的： 首先， leader为每个follower保存一个next index指针。用这个指针来标记leader应该发给follower的下一条log。 当一个server成为leader的时候， 它初始化所有follower的这个指针为自己最后一条log的下一条， 然后跟follower核对（在复制log的消息中），如果不符合则前移指针， 直到找到符合的为止。在找到并且同步好log之后， follower的log序列就应该跟leader完全一致了， 并且一直保持下去。
 
提交前任的log：
    前面提到， 一个leader一旦把本term里的一个log复制给了多数派就可以认为这个log被提交了。当一个leader在完成多数派复制之前就宕掉， 下任leader会尝试完成上一任的复制， 这时候复制到多数派后， leader不能确认这个log是提交的。 只有自己本term内又一个新的log复制到多数派后才能确认本term的log和之前的所有log（包括上任那个）是提交的。看下面的演示：

                    1       2               1       2                 1     2      3                1     2     3              1    2    3
                  －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
          s1      1       2    ｜        1       2       ｜       1     2      4    ｜         1     3          ｜        1    2    4
          s2      1       2    ｜        1       2       ｜       1     2            ｜          1     3         ｜        1    2    4
          s3      1             ｜        1                ｜       1     2            ｜          1     3         ｜        1    2    4
          s4      1             ｜        1                ｜       1                   ｜          1     3         ｜        1
          s5      1             ｜        1        3       ｜       1     3            ｜          1     3        ｜         1    3
                        a        ｜             b            ｜              c             ｜             d           ｜                e
        解释一下上面的图。 s1是leader的时候， 将term2复制到s2就宕机了（a列的状况）。  然后S5成为candidate进入term3， 并且收到了S3，S4和它自己的投票，从而成为term3的leader。它在index为2的位置写了一个不同的内容， 还没复制出去就宕机（列b）。s1重启， 并且被选为leader。在成为leader的过程中， 经过多数派投票， 所以S1知道term2 term3都是过时的了， 所以它的term是4， 这个时候S1继续前面2的复制， 把2的log复制给了S3从而达到了多数派（列c），但是这个时候是不能认为term2的log是提交了的， 因为如果这个时候S1宕机， S5重启并成为leader（因为S5当前term是3， 在S1宕机后， 它的term最大也就是log最新， 可以被选为leader）， S5会把自己的index 2位置term3的log复制给S2-S4， 从而覆盖掉了term2的log（列d）。但是， 
如果S1（列c状态）完成了本term， 也就是term4的一条log到多数派到复制， 则可以认为term2， term4都被提交了。 因为这时s1再宕机， s5是无法被选成leader的（列e）因为 s5不满足必须包含所有提交log的约束（见leader选举时， leader的log不能比任何其它server的旧的要求）。
   
    log传播完了， 最核心的部分也就都介绍完了。 其余比如集群成员变化， log压缩等都不在这里细说。感兴趣都同学自行阅读原文。