Raft算法

 Raft是一个用于管理日志一致性的协议。它将分布式一致性分解为多个子问题：Leader选举（Leader election）、日志复制（Log replication）、安全性（Safety）、日志压缩（Log compaction）等。同时，Raft算法使用了更强的假设来减少了需要考虑的状态，使之变的易于理解和实现。Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选者（Candidate）：

  • Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
  • Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
  • Candidate：Leader选举过程中的临时角色。

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

选举过程：
Raft 使用心跳（heartbeat）触发Leader选举。当服务器启动时，初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。
  每一个follower都有一个时钟，是一个随机的值，表示的是follower等待成为leader的时间，谁的时钟先跑完，则发起leader选举。
  Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC。结果有以下三种情况：

  • 赢得了多数的选票，成功选举为Leader；
  • 收到了Leader的消息，表示有其它服务器已经抢先当选了Leader；
  • 没有服务器赢得多数的选票，Leader选举失败，等待选举时间超时后发起下一次选举。

在Raft协议中，所有的日志条目都只会从Leader节点往Follower节点写入，且Leader节点上的日志只会增加，绝对不会删除或者覆盖。
能被选举成为Leader的节点，一定包含了所有已经提交的日志条目。

日志复制的过程

Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

  • 客户端的每一个请求都包含被复制状态机执行的指令。
  • leader把这个指令作为一条新的日志条目添加到日志中，然后并行发起 RPC 给其他的服务器，让他们复制这条信息。
  • 假如这条日志被安全的复制，领导人就应用这条日志到自己的状态机中，并返回给客户端。
  • 如果 follower 宕机或者运行缓慢或者丢包，leader会不断的重试，直到所有的 follower 最终都复制了所有的日志条目。

1、Raft分为哪几个部分？

  主要是分为leader选举、日志复制、日志压缩、成员变更等。

2、Raft中任何节点都可以发起选举吗？

  Raft发起选举的情况有如下几种：

  • 刚启动时，所有节点都是follower，这个时候发起选举，选出一个leader；
  • 当leader挂掉后，时钟最先跑完的follower发起重新选举操作，选出一个新的leader。

  • 成员变更的时候会发起选举操作。

    3、Raft中选举中给候选人投票的前提？

      Raft确保新当选的Leader包含所有已提交（集群中大多数成员中已提交）的日志条目。这个保证是在RequestVoteRPC阶段做的，candidate在发送RequestVoteRPC时，会带上自己的last log entry的term_id和index，follower在接收到RequestVoteRPC消息时，如果发现自己的日志比RPC中的更新，就拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term id更大，则更新，如果term id一样大，则日志更多的更大(index更大)。

    4、Raft网络分区下的数据一致性怎么解决？

      发生了网络分区或者网络通信故障，使得Leader不能访问大多数Follwer了，那么Leader只能正常更新它能访问的那些Follower，而大多数的Follower因为没有了Leader，他们重新选出一个Leader，然后这个 Leader来接受客户端的请求，如果客户端要求其添加新的日志，这个新的Leader会通知大多数Follower。如果这时网络故障修复 了，那么原先的Leader就变成Follower，在失联阶段这个老Leader的任何更新都不能算commit，都回滚，接受新的Leader的新的更新（递减查询匹配日志）。
    分布式原理 - 图1

    5、Raft数据一致性如何实现？

      主要是通过日志复制实现数据一致性，leader将请求指令作为一条新的日志条目添加到日志中，然后发起RPC 给所有的follower，进行日志复制，进而同步数据。

    6、Raft的日志有什么特点？

      日志由有序编号（log index）的日志条目组成，每个日志条目包含它被创建时的任期号（term）和用于状态机执行的命令。

    7、Raft和Paxos的区别和优缺点？

  • Raft的leader有限制，拥有最新日志的节点才能成为leader，multi-paxos中对成为Leader的限制比较低，任何节点都可以成为leader。

  • Raft中Leader在每一个任期都有Term号。

    8、Raft prevote机制？

    分布式原理 - 图2
    Prevote（预投票）是一个类似于两阶段提交的协议，第一阶段先征求其他节点是否同意选举，如果同意选举则发起真正的选举操作，否则降为Follower角色。这样就避免了网络分区节点重新加入集群，触发不必要的选举操作。

    9、Raft里面怎么保证数据被commit，leader宕机了会怎样，之前的没提交的数据会怎样？

      leader会通过RPC向follower发出日志复制，等待所有的follower复制完成，这个过程是阻塞的。
      老的leader里面没提交的数据会回滚，然后同步新leader的数据。

    10、Raft日志压缩是怎么实现的？增加或删除节点呢？？

      在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃（以前的数据已经落盘了）。
      snapshot里面主要记录的是日志元数据，即最后一条已提交的 log entry的 log index和term。

    11、Raft里面的lease机制是什么，有什么作用？

      租约机制确保了一个时刻最多只有一个leader，避免只使用心跳机制产生双主的问题。中心思想是每次租约时长内只有一个节点获得租约、到期后必须重新颁发租约。
    分布式原理 - 图3