[TOC]

一. Raft 算法

Raft 算法属于 Multi-Paxos 算法，它是在兰伯特 Multi-Paxos 思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多 。

除此之外，Raft 算法是现在分布式系统开发首选的共识算法。 绝大多数选用 Paxos 算法的系统（比如 Cubby、Spanner）都是在 Raft 算法发布前开发的，当时没得选；而全新的系统大多选择了 Raft 算法（比如 Etcd、Consul、CockroachDB）。

如果要用一句话概括 Raft 算法：从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

二. 领导者选举

基础概念

Raft 算法支持领导者（Leader）、跟随者（Follower）和候选人（Candidate） 3 种状态。在任何时候，每一个服务器节点都处于这 3 个状态中的 1 个

跟随者：就相当于普通群众，默默地接收和处理来自领导者的消息，当等待领导者心跳 信息超时的时候，就主动站出来，推荐自己当候选人。

候选人：候选人将向其他节点发送请求投票（RequestVote）RPC 消息，通知其他节点 来投票，如果赢得了大多数选票，就晋升当领导者。

领导者：蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活 着，你们现在不要发起新的选举，找个新领导者来替代我。”

需要注意的是，Raft 算法是强领导者模型，集群中只能有一个领导者

选举过程

首先，在初始状态下，集群中所有的节点都是跟随者的状态

Raft 算法实现了随机超时时间的特性。也就是说，每个节点等待领导者节点心跳信息的超 时时间间隔是随机的。通过上面的图片你可以看到，集群中没有领导者，而节点 A 的等待 超时时间最小（150ms），它会最先因为没有等到领导者的心跳信息，发生超时。 这个时候，节点 A 就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选 票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者。

如果其他节点接收到候选人 A 的请求投票 RPC 消息，在编号为 1 的这届任期内，也还没有 进行过投票，那么它将把选票投给节点 A，并增加自己的任期编号。

如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内新的领导者。

节点 A 当选领导者后，他将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举，篡权

选举过程四连问

节点间如何通讯？

在 Raft 算法中，服务器节点间的沟通联络采用的是远程过程调用（RPC），在领导者选举 中，需要用到这样两类的 RPC：

1. 请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票；
2. 日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息。 我想强调的是，日志复制 RPC 只能由领导者发起，这是实现强领导者模型的关键之一，希 望你能注意这一点，后续能更好地理解日志复制，理解日志的一致是怎么实现的。

什么是任期？

我们知道，议会选举中的领导者是有任期的，领导者任命到期后，要重新开会再次选举。 Raft 算法中的领导者也是有任期的，每个任期由单调递增的数字（任期编号）标识，比如 节点 A 的任期编号是 1,任期编号是随着选举的举行而变化的，这是在说下面几点。

1. 跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号，比 如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加为 1。
2. 如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如节点 B 的任期编号是 0，当收到来自节点 A 的请求投票 RPC 消息时，因为消息中包含了节点 A 的任期编号，且编号为 1，那么节点 B 将把自己的任期编 号更新为 1。

我想强调的是，与现实议会选举中的领导者的任期不同，Raft 算法中的任期不只是时间段，而且任期编号的大小，会影响领导者选举和请求的处理。

1. 在 Raft 算法中约定，如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为 3 的领导者节点 B，收到来自新领导者的，包含任期编号为 4 的心跳消息，那么节点 B 将立即恢复成跟 随者状态。
2. 还约定如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。比如节点 C 的任期编号为 4，收到包含任期编号为 3 的请求投票 RPC 消息，那么它会直接拒绝这个请求

在这里，你可以看到，Raft 算法中的任期比议会选举中的任期要复杂。同样，在 Raft 算法 中，选举规则的内容也会比较多。

选举有哪些规则

在议会选举中，比成员的身份、领导者的任期还要重要的就是选举的规则，比如一人一票、 弹劾制度等。“无规矩不成方圆”，在 Raft 算法中，也约定了选举规则，主要有这样几 点。

1. 领导者周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制 RPC 消息）， 通知大家我是领导者，阻止跟随者发起新的选举。
2. 如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导 者，推举自己为候选人，发起领导者选举。
3. 在一次选举中，赢得大多数选票的候选人，将晋升为领导者。
4. 在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因 为网络延迟，其他节点发起一轮新的选举。
5. 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。比如节点 C 的任期编号为 3，先收到了 1 个包含任期编号 为 4 的投票请求（来自节点 A），然后又收到了 1 个包含任期编号为 4 的投票请求（来 自节点 B）。那么节点 C 将会把唯一一张选票投给节点 A，当再收到节点 B 的投票请求 RPC 消息时，对于编号为 4 的任期，已没有选票可投了。

如何理解随机超时时间

在 Raft 算法中，随机超时时间是有 2 种含义的

1. 跟随者等待领导者心跳信息超时的时间间隔，是随机的；
2. 当没有候选人赢得过半票数，选举无效了，这时需要等待一个随机时间间隔，也就是说，等待选举超时的时间间隔，是随机的

三. 日志复制

基础概念

在 Raft 算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和提交日志项的过程

副本数据是以日志的形式存在的，日志是由日志项组成 ,日志项是一种数据格式，它主要包含用户指定的数据，也就是指令（Command）， 还包含一些附加信息，比如索引值（Log index）、任期编号（Term）

指令：一条由客户端请求指定的、状态机需要执行的指令。你可以将指令理解成客户端 指定的数据

索引值：日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单调递增的整数号码。

任期编号：创建这条日志项的领导者的任期编号

如何复制日志？

可以把 Raft 的日志复制理解成一个优化后的二阶段提交（将二阶段优化成了一阶段），减少了一半的往返消息，也就是降低了一半的消息延迟

首先，领导者进入第一阶段，通过日志复制（AppendEntries）RPC 消息，将日志项复制到集群其他节点上。

接着，如果领导者接收到大多数的“复制成功”响应后，它将日志项提交到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的“复制成功”响应，那么就返回错误给客户端

领导者不直接发送消息通知其他节点提交指定日志项。因为领导者的日志复制 RPC 消息或心跳消息，包含了当前最大的，将会被提交的日志项索引值。所 以通过日志复制 RPC 消息或心跳消息，跟随者就可以知道领导者的日志提交位置信息。 因此，当其他节点接受领导者的心跳消息，或者新的日志复制 RPC 消息后，就会将这条日 志项提交到它的状态机。而这个优化，降低了处理客户端请求的延迟，将二阶段提交优化为 了一段提交，降低了一半的消息延迟。

1. 接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
2. 领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。
3. 当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项提交到它的状态机中。
4. 领导者将执行的结果返回给客户端。
5. 当跟随者接收到心跳信息，或者新的日志复制RPC消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没提交，那么跟随者就将这条日志项提交到本地的状态机中

如何实现日志的一致？

在 Raft 算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是 说，Raft 是通过以领导者的日志为准，来实现各节点日志的一致的。具体有 2 个步骤。

1. 首先，领导者通过日志复制 RPC 的一致性检查，找到跟随者节点上，与自己相同日志项 的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。
2. 然后，领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致

PrevLogEntry：表示当前要复制的日志项，前面一条日志项的索引值。比如在图中，如果领导者将索引值为 8 的日志项发送给跟随者，那么此时 PrevLogEntry 值为 7。

PrevLogTerm：表示当前要复制的日志项，前面一条日志项的任期编号，比如在图中， 如果领导者将索引值为 8 的日志项发送给跟随者，那么此时 PrevLogTerm 值为 4。

1. 领导者通过日志复制 RPC 消息，发送当前最新日志项到跟随者（为了演示方便，假设当前需要复制的日志项是最新的），这个消息的 PrevLogEntry 值为 7，PrevLogTerm 值 为 4。
2. 如果跟随者在它的日志中，找不到与 PrevLogEntry 值为 7、PrevLogTerm 值为 4 的日 志项，也就是说它的日志和领导者的不一致了，那么跟随者就会拒绝接收新的日志项， 并返回失败信息给领导者。
3. 这时，领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者，这个消息 的 PrevLogEntry 值为 6，PrevLogTerm 值为 3。
4. 如果跟随者在它的日志中，找到了 PrevLogEntry 值为 6、PrevLogTerm 值为 3 的日志 项，那么日志复制 RPC 返回成功，这样一来，领导者就知道在 PrevLogEntry 值为 6、 PrevLogTerm 值为 3 的位置，跟随者的日志项与自己相同。
5. 领导者通过日志复制RPC，复制并更新覆盖该索引值之后的日志项（也就是不一致的日志项），最终实现了集群各节点日志的一致

四、成员变更

成员变更的问题

在集群中进行成员变更的最大风险是，可能会同时出现 2 个领导者。比如在进行成员变更时，节点 A、B 和 C 之间发生了分区错误，节点 A、B 组成旧配置中的“大多数”，也就是变更前的 3 节点集群中的“大多数”，那么这时的领导者（节点 A）依旧是 领导者。

另一方面，节点 C 和新节点 D、E 组成了新配置的“大多数”，也就是变更后的 5 节点集 群中的“大多数”，它们可能会选举出新的领导者（比如节点 C）。那么这时，就出现了同时存在 2个领导者的情况。

单节点变更

单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，那你需要 执行多次单节点变更。比如将 3 节点集群扩容为 5 节点集群，这时你需要执行 2 次单节点 变更，先将 3 节点集群变更为 4 节点集群，然后再将 4 节点集群变更为 5 节点集群

在正常情况下，不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配 置的“大多数”都会有一个节点是重叠的。 也就是说，不会同时存在旧配置和新配置 2 个“大多数”：

从上图中你可以看到，不管集群是偶数节点，还是奇数节点，不管是增加节点，还是移除节 点，新旧配置的“大多数”都会存在重叠（图中的橙色节点）

需要你注意的是，在分区错误、节点故障等情况下，如果我们并发执行单节点变更，那么就可能出现一次单节点变更尚未完成，新的单节点变更又在执行，导致集群出现 2 个领导者 的情况。

如果遇到这种情况，可以在领导者启动时，创建一个 NO_OP 日志项（也就是空日志 项），只有当领导者将 NO_OP 日志项提交后，再执行成员变更请求。

成员变更的问题和单节点变更的重点

1. 成员变更的问题，主要在于进行成员变更时，可能存在新旧配置的 2 个“大多数”，导 致集群中同时出现两个领导者，破坏了 Raft 的领导者的唯一性原则，影响了集群的稳定 运行。
2. 单节点变更是利用“一次变更一个节点，不会同时存在旧配置和新配置 2 个‘大多 数’”的特性，实现成员变更。
3. 因为联合共识实现起来复杂，不好实现，所以绝大多数 Raft 算法的实现，采用的都是单 节点变更的方法（比如 Etcd、Hashicorp Raft）。其中，Hashicorp Raft 单节点变更的 实现，是由 Raft 算法的作者迭戈·安加罗（Diego Ongaro）设计的，很有参考价值