Raft 算法Raft 算法是一种分布式共识算法官方动画演示复制状态机相同的初始状态 相同的输入 相同的结束状态Raft 中 leader 将请求封装到 logEntry 中并将 logEntry 复制到所有的 follower 节点每个 follower 节点按照相同顺序执行 logEntry 中的指令从而保证每个节点的状态是一致的状态转化raft 中只有三个状态每个节点都必定处于三个状态中的一种分别是follower跟随主节点的从节点candidate参与选举的节点leader主节点任期每一任期都是从选举开始如果一次选举没有选出主节点不久便会开始新的任期raft 保证每一任期里最多只会选出一个主节点节点之间每次通信都会携带任期号如果某个节点的当前任期号小于其他节点该节点会更新自己的任期号candidate 和 leader 发现自己的任期号过期了会退回到 follower如果一个节点收到了过期任期的请求该节点会拒绝这个请求通信Raft 算法中每个服务器节点都通过 RPC 进行通信节点之间一般只有两种 RPC请求投票由 candidate 节点在选举期间发起追加条目由 leader 节点发起用于复制日志以及发送心跳领导者选举选举开始leader 会定期给所有 follower 发送心跳请求如下图中的 S5如果 follower 中有一段时间没有收到 leader 心跳会认为 leader 宕机然后开始重新选举选举开始follower 首先会增加本机的任期并转换为 candidate 状态然后投票给自己并向其他节点发送投票请求没有转换为 candidate 的 follower 对于同一个任期会按照先来先得的原则将票投给第一个发起请求的节点其他的投票请求将会不投票选举结果candidate 节点获得了超半数的票数成为 leader 并开始发送心跳candidate 收到了来自其他节点的心跳并且任期大于本机节点的任期candidate 退回 follower 状态没有选举出新 leader每个节点都会在选举时间超时后增加任期然后开始新一轮选举日志复制过程leader 接收到客户端指令后会把指令作为一个新条目追加到日志当中并将日志内容发送给所有节点让他们复制该条日志当超过半数的节点复制后leader 就会在本地执行该指令并将结果返回给客户端日志构成一条日志信息会包含三个信息日志号唯一标识一条日志任期号状态机指令表示要执行的操作故障转移leader 和 follower 在日志复制过程中随时都有宕机风险raft 必须在有宕机的情况下支持日志复制并且每个副本日志顺序的一致如果 follower 没有回应 leader 的日志复制请求leader 会不停的重发即使 leader 已经执行了本次操作如果有 follower 崩溃后恢复这时 raft 的追加条目一致性检查会生效保证 follower 能按顺序恢复崩溃后缺失的日志如果 leader 崩溃崩溃的 leader 可能已经复制了日志到部分 follower 但还没有执行操作选出的新 leader 又没有这部分日志这就导致 follower 与新 leader 的日志不一致这种情况下新 leader 会强制 follower 同步新 leader 的日志raft 的一致性检查leader 在每一个发往 follower 的追加请求中都会携带前一个日志的日志号与任期如果 follwer 找不到前一个日志则会拒绝该请求leader 收到拒绝后会发送前一个日志条目从而逐渐向前定位到 follower 缺失的日志安全性选举限制leader 宕机后参与选举的 candidate 必须同步了之前所有任期的已提交日志条目避免选举出的新 leader 缺少日志从而造成节点之间的状态不一致发起投票请求时candidate 会携带自己最后一条日志的日志号与任期收到请求的 follower 会进行比较如果 candidate 的日志号与任期小于自己则拒绝投票follower 执行操作限制leader 在执行客户端操作完成后宕机此时其他 follower 还只是将日志复制到了本机并没有执行对应操作选举出新 leader 后 follower 怎么判断老 leader 宕机前的最后一次操作应不应该执行leader 每次发送心跳/日志复制请求时会携带 leader 已提交的最大日志号follower 通过这个参数判断是否应该执行leader 执行操作限制只有 leader 当前任期内的日志条目才通过计算副本数目的方式提交新 leader 当选后不会立即执行之前 leader 已经执行过的操作而是要等到下一次请求到来后将新请求与之前 leader 的请求一起执行
