猪小花1号

个人签名

282篇博客

raft协议小结

猪小花1号2018-09-03 09:44

作者:李小翠


1、raft协议是什么?

容错性。

  • 备份(backup)。一个系统的工作模是:接受客户端的command,系统进行处理,将处理的结果返回给客户端。由此可见,系统里的数据可能会因为command而变化。

    复制状态机(Repilcated State Machine,RSM),它有一个很重要的性质——确定性(deterministic)

    • 如何实现呢?如下图所示(来自raft协议):                

      每个server上Log的一致性!

      • raft就是Consensus Module的一个实现

        因此,raft是一致性协议,是用来保障servers上副本一致性的一种算法。

      遵循的性质

      • Election Safty 

        • 每一个任期内只能有一个领导人
      • leader只能追加日志条目,不能重写或者删除日志条目
    • 如果两个日志条目的index和term都相同,则两个如果日志中,两个条目及它们之前的日志条目也完全相同
  • 如果一条日志被commited过,那么大于该日志条目任期的日志都应该包含这个点
  • 如果一个server将某个特定index的日志条目交由状态机处理了,那么对于其他server,交由状态及处理的log中相同index的日志条目应该相同
  • 2.1 如何保证Election Safty

  • 不会总是出现票被瓜分的情况?raft使用了一个比较优雅的实现方式,随机选举超时(randomize election timeouts)。这就使得每个server的timeout不一样,发起新一轮选举的时候,有些server还不是voter;或者一些符合条件的candidate还没有参加下一轮。这种做法使得单个leader会很快被选举出来。 

    2.2 如何保证Log Matching

    preLogIndex和preLogTerm这两个信息,follower收到消息的时候, 首先判断它最新日志条目的index和term是否和rpc中的一样 (不是最新的,新的leader被选举可能会发生overwrite的情况)首先找到与preLogIndex相同index处的entry是否和preLogTerm相同,如果一样,才会append.

    2.3 如何保证Leader Completeness

      这个在raft协议中是有完整证明的,这个证明比较简短,用反正法,我在看的时候加了一些标注。

    第一个没有包含leaderT中commitT点(T<U)

    • 否则会因为index小而被拒绝投票),那么leaderU肯定包含了voter的所有信息(这个是由Log Matching的属性决定的,它们包含有相同的term,因此相同index的日志条目肯定相同),leaderU中肯定包含commit点,这与假设矛盾
    • 这是因为leaderU的leader的term>leaderU的term>voter的term,而leaderU是的一个不符合条件的任期,所以leaderU的leader应该是符合条件的,肯定就包含了voter的commit点),即包含commit点,根据Log Maching的原则,leaderU里面一定包含了这一点,这与假设矛盾
    • 2.4 raft协议中有一个约定,不能提交之前任期内log entry作为commit点。这是为什么?

      误解成了这个约定是用来保证之前任期内已经被复制到大多数server却没有被提交的日志在新的仍期内不会被覆盖。  实际上,论文中的figrure8的过程是一个正确的过程。


  •    在(c)中,index=2并没有被提交,在(d)中被复制了是一个正确的做法。论文想阐述的是:如果在(c)中,leader提交了这个之前任期内的entry,在(d)中依然会被覆盖,也就是说被commit的entry覆盖了,这是一个错误!因此约定“can not commit entries from previous term”

  • 从而可能会产生两个leader,如下图的情况:
  •  raft的解决方法就是two phase approch,引入一个过度配置,称为共同一致状态。具体的做法和图示:

    • 如果顺利commit,从而完成新配置的生成

     考虑上述过程:

    • 因为此时,拥有(old,new)entry的server并不是大多数
    • 如果说,已经复制给大多数server,只是未提交,那么(old,new)是有可能被选为leader,不过这没有什么太大的影响,因为新的leader在被选之后,会发送一条no-op的rpc,这个时候(old,new)就会被提交。重要的是,此时也仅有可能一个leader被选出,old不肯那个被选举为leader.
  • 3,4,5阶段,大多数情况(old,new)成为leader,例外与上条类似
  • 2.6 log过长或日志回放时间过长怎么办?

      此时就需要做log compaction

    写时复制的snapshot(写是复制在linux中可以通过fork来完成)

    • 写时复制主要是处于性能考虑的,如果state machine数据太多,snapshot将会耗费大量的时间,也许会导致系统可用性大大降低

     

  • 网易云大礼包:https://www.163yun.com/gift

    本文来自网易实践者社区,经作者李小翠授权发布。