raft协议小结

作者：李小翠

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

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