什么是 RAFT 算法

一致性（共识）算法用于解决分布式环境下多副本之间数据一致性的问题。RAFT 正是通过管理复制日志的方式来达成一致的共识算法。Raft 阶段分为两个，首先是选举过程，然后是日志（一个状态机指令或者是节点配置变更）同步过程，即追随者在选举出来的领导人带领下进行日志复制操作。

如何达成一致

所有一致性算法都会涉及到状态机，而状态机保证系统从一个一致的状态开始，以相同的顺序执行一些列指令最终会达到另一个一致的状态。所有的节点以相同的顺序处理日志，那么最终状态机在多个节点中都是一致的。

节点角色

在 Raft 中，任何时候一个服务器可以扮演下面角色之一，且同一时刻只能是一种：
Leader领导者: 处理所有客户端交互，负责日志同步，一个时刻只有一个 Leader。
Follower追随者: 类似选民，完全被动，听从 leader 的，与 leader 保持同步。
Candidate候选人: 可以被选为一个新的领导人，这是一个中间态，不可长期存在。

任期

Raft 把时间切割为任意长度的任期，每个任期都有一个任期号，采用连续的整数。每个任期都由一次选举开始，若选举失败则这个任期内没有 Leader；如果选举出了 Leader 则这个任期内有 Leader 负责集群状态管理。

选举过程

raft 初始状态时所有节点都处于 Follower 状态，并且随机睡眠一段时间。最先醒来的节点进入 Candidate 状态，向其它所有节点发出投票请求。当其它节点收到投票请求后，如果同意（请求节点的任期日志比自己的新）将自己仅有的一票投给请求节点。当节点收到超过半数节点的投票后，就进入 Leader 状态，成为系统中仅有的 Leader。raft 系统中只有 Leader 才有权利接收并处理 client 请求，并向其它节点发出同步请求。

日志复制过程

Leader 选举出来后，就可以开始处理客户端请求。Leader 收到客户端请求后，将请求内容作为一条日志添加到自己的日志记录中，并向其它节点发送添加日志请求。其它节点收到请求后，判断该请求满足接收条件，如果满足条件就将其添加到本地的日志中，并给 Leader 发送添加成功的回复。Leader 在收到大多数节点添加成功的回复后，就将该条日志正式提交。提交后的日志日志就意味着已经被 raft 系统接受，并能应用到状态机中了。

节点状态

1. currentTerm：节点当前任期，初始为 0，递增
2. votedFor：在当前获得选票的候选人的 Id
3. log[]：日志条目集；每一个条目包含一个用户状态机执行的指令，和收到时的任期号
4. commitIndex：最大的已经被 commit 的日志的 index
5. appliedIndex：最大的已经被应用到状态机的 index

节点响应规则

所有节点

• 如果 commitIndex > appliedIndex，应用 log[appliedIndex]到状态机，增加 appliedIndex
• 如果请求或者响应包含的任期 T > currentTerm，将 currentTerm 设置为 T 并转换为 Follower

Followers

• 响应来自 Leader 和 Candidate 的请求
• 如果在选举超时周期内没有收到添加日志的请求或者给 Candidate 投票，转换为 Candidate 角色

Candidates

• 转换为 candidate 角色，开始选举：

• 递增 currentTerm

  • 给自己投票
  • 重置选举时间
  • 发送投票请求给其他所有节点
• 如果收到了大多数节点的选票，转换为 Leader 节点
• 如果收到 Leader 节点的添加日志请求，转换为 Follower 节点
• 如果选举超时，重新开始新一轮的选举

Leaders

• 一旦选举完成：发送心跳给所有节点；在空闲的周期内不断发送心跳保持 Leader 身份和阻止跟随者超时，
• 如果收到客户端的请求，将日志追加到本地日志中，在日志被应用到状态机后响应给客户端

异常情况

1. leader 节点挂了：每一个追随者节点都有一个随机时间的超时任务：转变状态至候选者，在收到 leader 心跳时会重置，如果 leader 挂了，将在超时时间之内收不到心跳，超时转化为候选者发起重新选举过程。
2. 两个节点同时发起投票请求，由于在一次选举过程中，一个节点一个任期只能投一票，这就保证了两个节点不可能同时得到大多数（一半以上）的投票。如果 A 和 B 可能刚好都得到一半的投票，两者都成为不了 Leader。这时 A 和 B 继续保持 Candidate 状态，并且随机睡眠一段时间，等待进入到下一个选举周期。由于所有节点都是随机选择睡眠时间，所以连续出现多个节点竞选的概率很低。
3. 向 raft 系统中添加新机器时，由于配置信息不可能在各个节点上同时达到同步状态，总会有某些节点先得到新机器的信息，有些节点后得到新机器的信息。解决办法是将添加机器这个动作当成一个提议，当 leader 提交这个提议后新的配置生效。

优势与局限

• 优势：在达成一致的过程中，避免所有节点争抢提议权，直接由 leader 节点负责提议，大大加快了共识的速度；整个集群由 leader 节点作为代表，对外处理客户端的提议，对内管理不同节点的日志一致，模型简单可靠，节点通信效率高（一对多）。
• 局限性：raft 算法假设每个节点都是忠诚的、节点间的信道是安全的，如果存在作恶节点（即使只有一个）或者信道不安全则整个集群就完全失效。