一、前言
共识算法的目的是确保集群内的任意节点在某种状态转换上保持一致。
相比于 Paxos，Raft 最大的特性就是易于理解。为了达到这个目标，Raft 主要做了两方面的事情：
1、问题分解：把共识算法分为三个子问题，分别是领导者选举（leader election）、日志复制（log replication）、安全性（safety）
2、状态简化：对算法做出一些限制，减少状态数量和可能产生的变动。
二、复制状态机
在学习 Raft 之前要先了解一下复制状态机。
复制状态机（Replicate state machine）：相同的初始状态 + 相同的输入 = 相同的结束状态
可以理解为在多个节点上，从相同的初始状态开始，执行相同的一串命令，会产生相同的最终状态。
在 Raft 中，leader 会将客户端请求封装到一个个 log entry 中，将这些 log entries 复制到所有的 follower 节点，然后大家按相同顺序应用 log entries 中的 command，根据复制状态机的理论，大家的结束状态肯定时一致的。
可以说，使用共识算法就是为了实现复制状态机。一个分布式场景下的各节点间，就是通过共识算法来保证命令序列的一致，从而始终保持他们的状态一致，从而实现高可用。
二、状态简化
在任何时刻，每个服务器节点都处于 leader，follower 或 cnadidate 这三个状态之一。
相比于 Paxos，这一点极大地简化了算法的实现，因为 Raft 只需要考虑状态的切换，而不用想 Paxos 那样考虑状态之间的共存和相互影响。
如上图，每个节点在起始状态都是 follower，当节点发现集群中没有 leader 时，就会切换成 candidate。
candidate 经过一次或者多次选举，最终根据选举结果决定自己切换到 leader 状态还是 follower 状态。
Raft 把时间分割为任意长度地任期，任期用连续的整数标记。
每一段任期从一次选举开始。在某些情况下，一次选举无法选出 leader，这一任期就会以没有 leader 结束，一个新的任期就会很快重新开始。Raft 保证任意一个任期内最多只有一个 leader。
可以通过比较任期来确认一台服务器历史的状态，比如说查看一台服务器在 t2 任期内的日志就可以判断它是否宕机。
Raft 算法中服务器节点之间使用 RPC 进行通信，并且 Raft 中只有两种主要的 RPC：
RequestVote RPC（请求投票）：由 candidate 在选举期间发起。
AppendEntries RPC（追加条目）：由 leader 发起，用来复制日志和提供一种心跳机制。
在 Raft 中，服务器之间通信的时候会交换当前任期号；如果一台服务器上的当前任期号比其他的小，该服务器会将自己的任期号更新为较大的那个值。
如果一个 candidate 或者 leader 发现自己的任期号过期了，它就会立即回到 follower 状态。
如果一个几点接收到一个包含过期的任期号的请求，它会直接拒绝这个请求。
三、领导者选举
Raft 内部有一种心跳机制，如果存在 leader，那么它就会周期性地向所有 follower 发送心跳，来维持自己的地位。如果 follower 一段时间没有收到心跳，那么它就会任务系统中没有可用的 leader了，它就会开始进行选举。
开始一个选举过程中，follower 会先增加自己的当前任期号，并切换到 candidate 状态。然后投票给自己，并且并行地向集群中所有的服务器节点发送投票请求。
如果 candidate 收到其他 candidate 的投票请求、并且投票请求的任期编号大于等于自己的任期编号就会自动落选，成为 follower，并投票给对方。
每个服务器在每个任期只会投一票，固定投给最早拉票的服务器（拉票的任期编号要大于等于自己），并且修改自己的任期编号为投票请求的任期编号。
一次选举可能会有三种结果：
1、它获得超过半数选票赢得了选举 -> 它成为 leader 并开始向其他服务器发送心跳
2、其他节点赢得了选举 -> 收到了新 leader 的心跳后，如果新 leader 的任期号大于等于自己当前的任期号，那么它就会从 candidate 切换回 follower 状态。
3、一段时间之后没有任何获胜者 -> 每个 candidate 都在一个随机选举超过时间后增加自己的任期号开始新一轮投票。
为什么会没有获胜者？如果有多个 candidate 出现就会导致得票太过分散，没有任何一个 candidate 得票超过半数。
随机选举超过时间范围在论文中给定的是 150 ~ 300 ms，不同的需求可以做一些调整。
下面是请求投票的请求和响应 RPC。
四、日志复制
日志复制是 Raft 最核心的功能。
Leader 被选举出来后开始为客户端请求提供服务，但是客户端如何直到新 leader 是哪个节点呢？
客户端请求可以分三种情况进行讨论：
1、客户端发送的请求的节点就是 leader -> 这种情况就可以直接进行服务
2、客户端发送的请求的节点是 follower -> follower 可以通过心跳来获得 leader 的 ID 然后告知客户端
3、客户端发送的请求的节点正好宕机了 -> 客户端可以再找另外一个节点
leader 收到一条客户端的指令之后会作为一个新的条目追加到日志中去。
一条日志需要三个信息：
- 状态机指令
- leader 的任期号
- 日志号（日志索引）
Leader 将新条目追加到日志之后会把新条目并行地发送 AppendEntries RPC 给所有 follower，并让他们复制该条目。如果有 follower 没有反应，leader 会不断地重发指令直到所有 follower 都成功记录这个新条目。
但是 leader 不会等待所有 follower 确认写入新条目，当 leader 收到超半数 follower 确认写入的消息之后，就会把指令视为提交（committed）。当 follower 发现指令状态变为已提交就会执行该指令。
如下图，成功提交的日志编号为 7。
在 Raft 中常见的故障有三种：
1、follower 缓慢：leader 会不断重发追加条目请求，即便是指令已经提交
2、follower 宕机：Raft 追加条目的一致性检查生效，保证 follower 能顺序恢复崩溃后确实的日志
3、leader 宕机：如果新 leader 缺少一些未提交的新日志，客户端会认为新日志失败，但是不影响客户端工作。但是如果原来的 leader 恢复之后就会出现老 leader 的日志比新 leader 的日志更多的情况。这时候新 leader 就会强制老 leader 复制新 leader 的日志来解决不一致的问题。
通过这种机制，leader 当选之后不需要任何特殊操作来使日志恢复到一致状态。leader 只需要正常的操作，当追加条目请求被拒绝时才进行一致性检查，一致性检查失败的时候再进行操作保持一致性。
一致性检查就是 leader 在每一个发往 follower 的追加条目 RPC 中会放入前一个日志条目的索引位置和任期号。如果 follower 在它的日志中找不到前一个日志，follower 就会拒绝此日志。leader 收到拒绝之后就会发送前一个日志，依次类推来补全所有的日志。如果某个 follower 并不是缺失日志条目，而是日志条目与 leader 冲突，leader 就会覆盖掉冲突的条目。Raft 会通过选举限制来保证已经提交的日志不会被覆盖。
下面是追加条目的请求和响应 RPC。
五、安全性
日志复制可以解决大部分故障情况，但是还有一些问题仍然未被解决，Raft 为了解决这些问题补充了以下规则：
1、leader 宕机处理：选举限制
如果一个 follower 落后了 leader 若干条日志(但没有漏一整个任期)，那么下次选举中按照领导者选举里的规则，它依旧有可能当选leader。它在当选新leader后就永远也无法补上之前缺失的那部分日志，从而造成状态机之间的不一致。
所以需要对领导者选举增加一个限制，保证被选出来的leader一定包含了之前各任期的所有被提交的日志条目。
这一规则需要通过拉票请求的 RPC 来完成，拉票的 RPC 中包含拉票者自己的最后一个日志索引号和自己最后一个日志的任期号，被拉票的 follower 如果发现自己的日志比拉票者的日志新就会拒绝投票（日志新表示日志的任期号更大或者任期号相同索引号更大）。
2、leader 宕机处理：新 leader 是否提交之前任期内的日志条目
如果 leader 当前任期内的某个日志条目已经存储到过半的节点上之后，leader 就会提交该日志条目。那么 leader 如何通知 follower 提交这个日志条目呢？
leader 可以通过追加条目 RPC来通知 follower 提交，并且 leader 的心跳也是一种特殊的追加条目 RPC。Raft 没有考虑 leader 提交，但是 follower 未提交的情况。如果需要考虑这种情况可以使用两阶段提交确认的方法。
如果 leader 未提交的时候恰好宕机了，新 leader 不会直接提交之前任期内的日志条目（日志条目任期号和自己当前的任期号不同时，无法通过半数的日志确认来提交日志）。新 leader 只会继续进行正常操作，直到当前任期中下一个指令满足提交条件就会把日志中所有条目进行提交。
3、follower 和 candidate 宕机处理
如果 follower 和 candidate 宕机，leader 会无限重试来处理这种失败。如果一个节点完成了一个 RPC，但是还没有响应的时候宕机，那么它重启之后仍会收到同样的请求。（Raft 的 RPC 都是幂等的）
4、时间和可用性限制
Raft 算法整体不依赖客观时间，也就是说 Raft 不会因为网络或者其他因素造成后发的 RPC 先到而影响 Raft 的正确性。
只要整个系统满足下面的时间要求，Raft 就可以选举出并维持一个稳定的 leader：
广播时间（broadcastTime） « 选举超时时间（electionTimeout） « 平均故障时间（MTBF）
广播时间就是一个 RPC 来回的时间。
六、集群成员变更
在需要改变集群配置的时候(如增减节点、替换宕机的机器或者改变复制的程度)，Raft可以进行配置变更自动化。
在分布式系统中是不可能在所有机器上同一时间应用变更的，所以自动化配置变更机制最大的难点是保证转换过程中不会出现同一任期的两个leader，因为转换期间整个集群可能划分为两个独立的大多数。
单节点变更
单步成员变更理论虽然简单，但却埋了很多坑，比如当同时满足以下情况会出现脑裂问题：
- 集群个数是偶数
- 并发的配置变更
- Leader丢失领导权
作者给出的解决方法是，新leader在他的任期内提交一条日志前，不能开始配置变更。利用 raft 现有的 no-op 日志就可以实现，将leader日志中为提交的配置变更提交，未复制到leader的配置变更截断。如果leader提交了一条日志他任期内的日志，那么他就知道它的配置现在是最新的，就不存在还未提交的来自先前任期配置日志。
多节点变更
多节点变更使用的是联合共识（Joint Consensus）方法，大概步骤有下：
第一阶段：leader 发起 $c_{old,new}$（可以当作一个日志条目），使整个集群进入联合一致状态。这时，所有 RPC 都要在新旧两个配置中达到大多数才可以选举或者追加成功。
第二阶段：leader 发起 $c_{new}$，使整个集群进入新配置状态，这时，所有 RPC 只要在新配置下能达到大多数就算成功。
出现脑裂的场景有以下几种可能：
1、leader 在 $c_{old,new}$ 未提交时宕机
2、leader 在 $c_{old,new}$ 已提交但 $c_{new}$ 未发起时宕机
3、leader 在 $c_{new}$ 已发起时宕机
集群成员变更还有三个补充规则需要说明一下 1、新增节点时，需要等新增的节点完成日志同步再开始集群成员变更。这点是防止集群在新增节点还未同步日志时就进入联合一致状态或新配置状态，影响正常命令日志提交。 2、缩减节点时，leader 本身可能就是要缩减的节点，这时它会在完成 $c_{new}$ 的提交后自动退位。在发起 $c_{new}$ 后，要退出集群的leader就会处在操纵一个不包含它本身的 Raft 集群的状态下。这时它可以发送 $c_{new}$ 日志，但是日志计数时不计自身。
3.为了避免下线的节点超时选举而影响集群运行，服务器会在它确信集群中有leader存在时拒绝 Request Vote RPC。 因为 $c_{new}$ 的新 leader 不会再发送心跳给要退出的节点，如果这些节点没有及时下线，它们会超时增加任期号后发送 Request Vote RPC。虽然它们不可能当选leader，但会导致 Raft 集群进入投票选举阶段，影响集群的正常运行。 为了解决这个问题，Raft 在 Request Vote RPC 上补充了一个规则:一个节点如果在最小超时时间之内收到了Request Vote RPC，那么它会拒绝此 RPC。
这样，只要 follower 连续收到 leader 的心跳，那么退出集群节点的 Request Vote RPC 就不会影响到 Raft 集群的正常运行了。
官网：https://raft.github.io/
