分布式-一致性算法raft

一致性算法解决的问题

• 简单说：数据存在多副本时，不丢数据的问题。
• 专业一点：一个集群的所有状态机之间，对一条数据达成共识。

为什么需要超过半数达成共识？

• 选举时，超过半数达成共识，可以保证leader唯一，不会同时选出两个leader。
  
• 日志复制时，可以由任意数量节点达成共识(Quorum机制)。解释一下：假设，client向leader发送一条命令，只要有2个follower成功存储该命令，leader即告知client命令被成功存储。随后leader失效，如果，刚好存储命令的2个follower也失效，此时就会丢数据。因此，这种情况下，集群可以容忍2个节点失效，否则进入不可用状态。日志复制时，不必超过半数才算提交。
  

关键：1.leader必须唯一，2.leader必须包含所有已提交的log

• leader唯一：由超过半数达成共识保证。
  
• leader一定包含所有提交的log（leader中一个log Entry已提交蕴含着：这个log Entry，以及之前所有的log Entry已复制到多数节点上），接下来证明一下，raft算法选出的leader一定包含所有提交的log:
  • 第一个问题，为什么不选CommitIdex最大的节点，作为leader？因为，日志被复制到多数节点后，leader才能更新CommitIdex，然后leader把CommitIndex发给follower。存在日志已经提交，但是follower的CommitIndex还没有更新的间隙，此时，可能会选出一个错误的leader。
    
  • 第二个问题，为什么超过半数节点认为candidate log比自己的log新，那么candidate一定包含所有提交的Log？因为，假设candidate不包含所有提交的log，那么它的log就滞后于包含所有提交log的节点，这些节点就不会投票给他。
    

日志复制

• 最简单的办法，就是把leader的所有log，全部拷贝到follower，但是效率不高。
  
• 论文中给出的方法，不难证明，这里略过。
  

为什么需要持久化

• 如果不持久化，当所有处于正确状态的server挂掉后，重启之后，所有的正确状态都消失，此时造成丢数据。因此必须持久化。
  

值得注意的异常问题

• 日志被复制到大多数节点，是否等价于被提交？
  答案不是。被提交的含义：一条日志被提交，意味着状态机可以执行该日志，所以被提交的日志不能被覆盖或丢弃。一条日志被复制到大多数节点，是否意味这条日志不会被覆盖或丢弃？绝大部分情况是的，但是有一种特殊情况，会导致存在于大多数节点的日志被覆盖或丢弃，参见论文中的Figure 8。
  解决方法是：新选出的leader，之前leader的log拷贝给follower成功后，不能提交这些log。直到新写入的log成功复制后，之前leader写入的log才能一起被提交。
  
• Raft算法，底层的传输层协议，可以是tcp或udp
  tcp协议是流式的，保证先发先到；但是udp协议可能存在后发先到的问题，接收到网络数据时，需要对数据是否过时做检测。（无论是leader选取，还是日志复制）。
  
• 当follower的日志落后leader很多时，按照每次心跳nextIndex--的方式匹配follower日志，太慢了（例如，心跳间隔T，落后了N个日志项，则需要T*N时间才能匹配上，如果T=50ms，N=1000，匹配时间=50s），其实nextIndex一次可以向前移动更多。