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 的请求一起执行
