raft是是consoul和etcd的核心算法

Raft介绍

• Raft提供了一种在计算系统集群中分布状态机的通用方法，确保集群中的每个节点都同意一系列相同的状态转换
• 它有许多开源参考实现，具有Go，C ++，Java和Scala中的完整规范实现
• 一个Raft集群包含若干个服务器节点，通常是5个（单数），这允许整个系统容忍2个节点的失效，每个节点处于以下三种状态之一
  • follower（跟随者） ：所有节点都以follower 的状态开始。如果没收到leader发来的消息（leader不存在或出现问题）则会变成candidate状态
  • candidate（候选人）：会向其他节点“拉选票”，如果得到大部分的票则成为leader，这个过程就叫做Leader选举(Leader Election)，当有candidate成为leader后，其他candidate变回follower
  • leader（领导者）：所有对系统的修改都会先经过leader

Raft一致性算法

• Raft通过选出一个leader来简化日志副本的管理，例如，日志项(log entry)只允许从leader流向follower
• 基于leader的方法，Raft算法可以分解成三个子问题
  • Leader election (领导选举)：原来的leader挂掉后，必须选出一个新的leader
    • 如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，然后他就会认为系统中没有可用的领导者然后开始进行选举以选出新的领导者。从跟随者到候选人时有一个超时时间，通常在150ms-300ms之间，当在这个时间段没有收到来自leader的消息时（leader挂掉了）就会转换成candidate，不设置固定值是避免同时有多个候选人出现，他们会先投自己一票，然后再去拉选票，同时成为就都只投了自己，然后又重新超时拉选票，导致死循环，系统卡死。
    • 当第一个candidate出现后，他会先给自己投一票，然后进行拉票，如果向其他candidate拉票，他会进行判断两者的任期，只有任期小才会拉取成功，否则会拒绝
    • 如果同时有两个追随者成为候选者，它们会同时拉取选票，如果有4个节点，则两个候选者都是两票，此时在两个候选者之间又会有一个随机时间，最快的先成为leader
    • Raft 使用一种心跳机制来触发领导人选举，当服务器程序启动时，节点都是 follower(跟随者) 身份
    • 候选人的状态维持直到发生以下任何一个条件发生的时候：
      • 他自己赢得了这次的选举
      • 其他的服务器成为领导者
      • 一段时间之后没有任何一个获胜的人
  • Log replication (日志复制)：leader从客户端接收日志，并复制到整个集群中
    • 当客户端发送一条信息给leader，leader收到后会存入节点的log中，此时leader是未提交的状态，它会先将信息复制给其他follower进行同步，follower存入自己的节点日志后（未提交状态）给leader一个响应，leader接受到响应进行数据提交（此时可以设置主节点提交成功后则给客户端进行响应），提交后leader再发送一个响应给follower，follower进行提交，此时leader和follower都有相同的数据了，同步成功
    • 假如网络波动，发生网络分区（脑裂），5个节点分成了三个子节点为一组，一个leader B一个子节点一组，两者不能相互通信，此时三个追随者会重新选举产生新的leader A，当网络恢复时，B会变为leader A的小弟（因为A只有一个小弟，B有两个），此时A是有4个追随者的leader，然后继续发送消息进行同步
  • Safety (安全性)：如果有任意的server将日志项回放到状态机中了，那么其他的server只会回放相同的日志项