Raft 算法是一个共识的算法，在集群的分布式状态中，保证每个节点都处于一致的状态。
Raft 算法主要可以分为两个阶段：
- 领导者选举阶段
- 日志复制(数据同步)阶段
Raft 算法中的服务器节点只有 3 种状态，Leader（领导人），Follower（跟随者），Candidate（候选人）。
- Leader（领导者）：接受客户端的读、写请求，协调整个日志的持久化和推进
- Follower（跟随者）：系统启动时默认的角色，一般来说不参与客户端读、写请求，接受 Leader 发送过来的心跳追加日志，在 Leader 挂了之后转变为 Candidate
- Candidate（候选者）：如果当前没有 Leader，Follower 就转变为这个角色，这个角色会向其它节点发起投票请求，如果多数节点同意投票，则晋升为 Leader
Leader 负责管理集群中的日志复制，在大多数时候 Candidate 这个状态是不存在的，只有当集群中没有 Leader 的时候其他节点才会产生 Candidate，然后 Candidate 会要求其他节点进行投票，获得大多数票数的节点就变为新的 Leader，其他所有节点的状态变为 Follower。
当客户端有请求进来，Leader 负责接收和处理，并且也只有 Leader 有资格进行这种操作，每一个服务器节点都在维护一个日志。假设客户端发送过来的是一个 add 请求，往服务器添加了一个数据，Leader 会更新它的日志，然后通过 AppendEntries 消息让 Follower 同步这个更新，Leader 会记录 Follower 返回成功的数目，如果超过半数的节点都成功了，Leader 才会通知客户端已经成功 add 了，并且 Leader 会进行日志提交的操作，并且让其他的服务器节点也进行提交。
Leader 选举机制
可以看出所有节点启动时都是 Follower 状态；在一段时间内如果没有收到来自 Leader 的心跳，从 Follower 切换到 Candidate，发起选举；如果收到超过一半的赞同票（含自己的一票）则切换到 Leader 状态；如果发现其他节点比自己更新，则主动切换到 Follower。
总之，系统中最多只有一个 Leader，如果在一段时间里发现没有 Leader，则大家通过选举-投票选出 Leader。Leader 会不停的给 Follower 发心跳消息，表明自己的存活状态。如果 Leader 故障，那么 Follower 会转换成 Candidate，重新选出 Leader。
任期 - Term
从上面可以看出，Leader 是大家投票选举出来的，每个 Leader 工作一段时间，然后选出新的 Leader 继续负责。在raft协议中，对应的术语叫 term（任期）。
term（任期）以选举（election）开始，然后就是一段或长或短的稳定工作期（normal Operation）。从上图可以看到，任期是递增的，这就充当了逻辑时钟的作用；另外，term 3 任期期间没有 Leader，就是说没有选举出 Leader 就结束了，然后会发起新的选举，后面会解释这种 split vote 的情况。
选举过程详解
每个节点会维护一个 Term 值，即为当前是第几任领导，初始启动时是第 0 任，每个节点都会随机给一个 TIMEOUT 值，一般在 150ms 到 300ms 之间。当 TIMEOUT 值到达后，还没有收到 Leader 的心跳检测。首先变成 Candidate 的是 TIMEOUT 值先结束的节点，上图为节点 A（TIMEOUT 值是随机的），然后变成 Candidate 后首先会先将自己的 Term + 1，并且先给自己投一票，然后向其他节点发送信息，要求他们进行投票，其他节点会对比自己的 Term 值和被选举者的 Term ，如果小于 被选举者传过来的 Term，则同意其成为 Leader，并将自己的 Term 更新。投票的数量占据所有节点总数一半以上即变为 Leader，如果 A 节点成功变为了 Leader，那么它会向其他节点按一定频率发送心跳检测，如果其他节点发现发送心跳检测的 A 节点的 Term 是大于或者等于当前它节点维护的 Term 的，他就会更新 Term 并且成为 A 的追随者。
上面已经说过，如果 Follower 在 election timeout 内没有收到来自 Leader 的心跳（也许此时还没有选出 Leader；也许leader挂了；也许 Leader 与该 Follower 之间网络故障），则会主动发起选举。步骤如下：
- 增加节点本地的 current term ，切换到candidate状态
- 投自己一票
- 并行给其他节点发送 RequestVote RPCs
- 等待其他节点的回复
在这个过程中，根据来自其他节点的消息，可能出现三种结果
- 收到大多数的同意投票（含自己的一票），则赢得选举，成为 Leader
- 被告知别人已当选，那么自行切换到 Follower
- 一段时间内没有收到大多数的同意投票，则保持 Candidate 状态，重新发出选举
第一种情况，赢得了选举之后，新的 Leader 会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举。在这里，先回到投票者的视角，投票者如何决定是否给一个选举请求投票，有以下约束：
- 在任一任期内，单个节点最多只能投一票
- 候选人知道的信息不能比自己的少
- first-come-first-served 先来先得
第二种情况，比如有三个节点A B C。A B 同时发起选举，而 A 的选举消息先到达 C，C 给 A 投了一票，当 B 的消息到达 C 时，已经不能满足上面提到的第一个约束，即 C 不会给 B 投票，而 A 和 B 显然都不会给对方投票。A 胜出之后，会给 B,C 发心跳消息，节点 B 发现节点 A 的 term 不低于自己的 term，知道有已经有 Leader 了，于是转换成 Follower。
第三种情况，没有任何节点获得大多数节点投票，比如下图这种情况：
总共有四个节点，Node C、Node D 同时成为了 Candidate，进入了term 4，但 Node A 投了 Node D 一票，Node B 投了 Node C 一票，这就出现了平票 split vote 的情况。这个时候所有节点会一直等，直到超时后重新发起选举。如果出现平票的情况，那么就延长了系统不可用的时间（没有 Leader 是不能处理客户端写请求的），因此 raft 引入了 randomized election timeouts 来尽量避免平票情况。同时，leader-based 共识算法中，节点的数目都是奇数个，尽量保证大多数节点的出现。
关于选举还有其它一些规则：
- 针对 Follower
如果在超过选举超时时间的情况之前都没有收到 Leader 的心跳，或者是 Candidate 请求投票的，就自己变成 Candidate;
- 针对 Candidate
开始选举后的动作如下：自增当前的任期号（current Term）; 给自己投票; 重置选举超时计时器;发送请求投票的 RPC 给其他所有服务器;
收到响应后的规则：如果接收到大多数服务器的选票，那么就变成 Leader；如果接收到来自新的 Leader 的心跳信息，则转变成 Leader；如果选举过程超时，再次发起一轮选举;
- 针对 Leader
一旦成为 Leader：发送空的附加日志 RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以阻止跟随者超时。
日志复制
当有了 Leader，系统应该进入对外工作期了。客户端的一切请求来发送到 Leader，Leader 来调度这些并发请求的顺序，并且保证 Leader 与 Followers 状态的一致性。raft 中的做法是，将这些请求以及执行顺序告知 Followers。Leader 和 Followers 以相同的顺序来执行这些请求，保证状态一致。
复制状态机
请求完整流程
当系统（Leader）收到一个来自客户端的写请求，到返回给客户端，整个过程从 Leader 的视角来看会经历以下步骤：
- leader append log entry
- leader issue AppendEntries RPC in parallel
- leader wait for majority response
- leader apply entry to state machine
- leader reply to client
- leader notify follower apply log
可以看到日志的提交过程有点类似两阶段提交 (2PC)，不过与 2PC 的区别在于，Leader 只需要大多数（majority）节点的回复即可，这样只要超过一半节点处于工作状态则系统就是可用的。
日志在每个节点上是状态如下图：
特殊状态下的复制
正常来说客户端一个请求过来，领导者接收，更新日志，然后通知其他节点进行更新，接收到大多数成功的信息后，就告诉客户端成功，提交日志，让其他节点也提交日志。再看看比较特殊或者极端的情况。
特殊情况1：假设现在有A,B,C三个节点，领导者A接收了一个add请求，现在自己日志add了，然后发送信息让节点B和C也add到日志了。这个时候领导者A宕机了，也就是说接收不到其他节点的成功信息，不能进行commit操作，那咋办？这个add操作还有效吗？现在B的TIMEOUT时间为150ms，C的TIMEOUT时间为160ms，所以B先变成候选人发起投票，C给B投票（如果在请求达到C之前，C也变成候选人，就等待下一次选举呗，先TIMEOUT的再次Term + 1，这里假设C还没有变为候选人），B变为了领导者，这个时候B和C都存在有下标未更新的日志8（如上图），但是Raft算法要求领导者不能删除或者覆盖自己的日志文件，所以新领导者B是不会删除下标未更新的日志8，并且会履行原来A的职责让追随者们更新日志8，但不会进行commit操作，只有在下一次客户端请求进来对日志进行操作时，让追随者们更新日志9，领导者B得到大多数的成功信息后，才会把两个日志都进行一个commit操作。
特殊情况2：现在有A,B,C三个节点，领导者A接收了一个add请求，现在自己日志add了，然后发送信息让节点B进行更新，还没对节点C发送，这个时候领导者A挂了咋办？如果这时候还是C先到了过期时间，C向B发送了投票请求会发生什么？因为Raft算法要求新的领导者需要更具有完整性的日志，所以会拒绝向C进行投票，会等待下一次B自己选举的时候向C发送投票请求。
特殊情况3：如果有A,B,C,D,E五个节点，A为领导者，接收了一个请求，让B更新了，还没有让C,D,E更新就宕机了，这个时候还是C先TIMEOUT了，会发生什么？这个和特殊情况2有什么不同？特殊情况2的时候A和B是已经存在有日志更新了，占据了绝大多数；但是在特殊情况3更新日志的情况只是占据少数，如果这个时候让没有更新日志的C来发起投票，那么C,D,E都会投给C，而B会拒绝投给C，但是C也拿到了绝大多数的票数，所以当选领导者，并且会检查其他节点的日志是否是最新的了，发现B存在它没有的日志，领导者首先不会去理会，在下一次进行更新的时候，因为会维护一个日志的index，并且是按照领导者index来执行，所以B更新的日志会被覆盖。
