分布式系统必须知道的一个共识算法：Raft

ゞ浴缸里的玫瑰 2023-10-13 18:39 18阅读 0赞

## 一、Raft 概述 ##

`Raft 算法`是分布式系统开发首选的`共识算法`。比如现在流行 Etcd、Consul。

如果`掌握`了这个算法，就可以较容易地处理绝大部分场景的`容错`和`一致性`需求。比如分布式配置系统、分布式 NoSQL 存储等等，轻松突破系统的单机限制。

**Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。**

## 二、Raft 角色 ##

### 2.1 角色 ###

**跟随者（Follower）**：`普通群众`，默默接收和来自领导者的消息，当领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。

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

**领导者（Leader）**：`霸道总裁`，一切以我为准。处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们不要”发起新的选举，不用找新领导来替代我。

如下图所示，分别用三种图代表跟随者、候选人和领导者。

![图片][61a7402ff9c7526ec083904434a6c201.png]

角色

## 三、单节点系统 ##

### 3.1 数据库服务器 ###

现在我们想象一下，有一个单节点系统，这个节点作为数据库服务器，且存储了一个值为 X。

![图片][cbda0e5f92a5f778063ba20b20127883.png]

数据库服务器

### 3.2 客户端 ###

左边绿色的实心圈就是客户端，右边的蓝色实心圈就是节点 a（Node a）。Term 代表任期，后面会讲到。

![图片][e84c01426e0f778db9220c0cef82017b.png]

客户端

### 3.3 客户端向服务器发送数据 ###

客户端向单节点服务器发送了一条更新操作，设置数据库中存的值为 8。单机环境下（单个服务器节点），客户端从服务器拿到的值也是 8。一致性非常容易保证。

![图片][ce36ac00d89a6d20531bb7c192a34f22.gif]

客户端向服务器发送数据

### 3.4 多节点如何保证一致性？ ###

但如果有多个服务器节点，怎么保证一致性呢？比如有三个节点：a，b，c。如下图所示。这三个节点组成一个数据库集群。客户端对这三个节点进行更新操作，如何保证三个节点中存的值一致？这个就是分布式一致性问题。Raft 算法就是来解决这个问题的。当然还有其他协议也可以保证，本篇只针对 Raft 算法。

![图片][82409ba9c9d7aa47c7d1d906a4a3a90d.gif]

在多节点集群中，在节点故障、分区错误等异常情况下，Raft 算法如何保证在同一个时间，集群中只有一个领导者呢？下面就开始讲解 Raft 算法选举领导者的过程。

## 四、选举领导过程 ##

### 4.1 初始状态 ###

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

如下图所示，有三个节点(Node) a、b、c，任期（Term）都为 0。

![图片][0e651ad304068083b83575f6739ac777.png]

初始状态

### 4.2 成为候选者 ###

Raft 算法实现了随机超时时间的特性，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。比如 A 节点等待超时的时间间隔 150 ms，B 节点 200 ms，C 节点 300 ms。那么 a 先超时，最先因为没有等到领导者的心跳信息，发生超时。如下图所示，三个节点的超时计时器开始运行。

![图片][2d036f7d1183c313abc0a533e44f4768.gif]

超时时间

当 A 节点的超时时间到了后，A 节点成为候选者，并增加自己的任期编号，Term 值从 0 更新为 1，并给自己投了一票。

*  Node A：Term = 1, Vote Count = 1。
 *  Node B：Term = 0。
 *  Node C：Term = 0。

![图片][ed8b9b9d239501685494d65278e6052c.gif]

成为候选者

### 4.3 投票 ###

我们来看下候选者如何成为领导者的。

![图片][3db02ce8f97dd993db8f725924fb5929.gif]

Leader 选举

*  **第一步**：节点 A 成为候选者后，向其他节点发送请求投票 RPC 信息，请它们选举自己为领导者。
 *  **第二步**：节点 B 和 节点 C 接收到节点 A 发送的请求投票信息后，在编号为 1 的这届任期内，还没有进行过投票，就把选票投给节点 A，并增加自己的任期编号。
 *  **第三步**：节点 A 收到 3 次投票，得到了大多数节点的投票，从候选者成为本届任期内的新的领导者。
 *  **第四步**：节点 A 作为领导者，固定的时间间隔给 节点 B 和节点 C 发送心跳信息，告诉节点 B 和 C，我是领导者，组织其他跟随者发起新的选举。
 *  **第五步**：节点 B 和节点 C 发送响应信息给节点 A，告诉节点 A 我是正常的。

### 4.4 任期 ###

英文单词是 term，领导者是有任期的。

*  **自动增加**：跟随者在等待领导者心跳信息超时后，推荐自己为候选人，会增加自己的任期号，如上图所示，节点 A 任期为 0，推举自己为候选人时，任期编号增加为 1。
 *  **更新为较大值**：当节点发现自己的任期编号比其他节点小时，会更新到较大的编号值。比如节点 A 的任期为 1，请求投票，投票消息中包含了节点 A 的任期编号，且编号为 1，节点 B 收到消息后，会将自己的任期编号更新为 1。
 *  **恢复为跟随者**：如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。这种场景出现在分区错误恢复后，任期为 3 的领导者受到任期编号为 4 的心跳消息，那么前者将立即恢复成跟随者状态。
 *  **拒绝消息**：如果一个节点接收到较小的任期编号值的请求，那么它会直接拒绝这个请求，比如任期编号为 6 的节点 A，收到任期编号为 5 的节点 B 的请求投票 RPC 消息，那么节点 A 会拒绝这个消息。

### 4.5 选举规则 ###

*  一个任期内，领导者一直都会领导者，直到自身出现问题（如宕机），或者网络问题（延迟），其他节点发起一轮新的选举。
 *  在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，投完了就没了。

### 4.6 大多数 ###

假设一个集群由 N 个节点组成，那么大多数就是至少 N/2+1。例如：3 个节点的集群，大多数就是 2。

### 4.7 心跳超时 ###

为了防止多个节点同时发起投票，会给每个节点分配一个随机的选举超时时间。这个时间内，节点不能成为候选者，只能等到超时。比如上述例子，节点 A 先超时，先成为了候选者。这种巧妙的设计，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，减少了因选票瓜分导致选举失败的情况。

![图片][ed8b9b9d239501685494d65278e6052c.gif]

成为候选者

## 五、领导者故障 ##

如果领导者节点出现故障，则会触发新的一轮选举。如下图所示，领导者节点 A 发生故障，节点 B 和 节点 C 就会重新选举 Leader。

![图片][e8aff4960f4c7553371a2a75a8ef2d1a.gif]

领导者故障

*  **第一步** ：节点 A 发生故障，节点 B 和节点 C 没有收到领导者节点 A 的心跳信息，等待超时。
 *  **第二步**：节点 C 先发生超时，节点 C 成为候选人。
 *  **第三步**：节点 C 向节点 A 和节点 B 发起请求投票信息。
 *  **第四步**：节点 C 响应投票，将票投给了 C，而节点 A 因为发生故障了，无法响应 C 的投票请求。
 *  **第五步**：节点 C 收到两票（大多数票数），成为领导者。
 *  **第六步**：节点 C 向节点 A 和 B 发送心跳信息，节点 B 响应心跳信息，节点 A 不响应心跳信息，因为 A 故障了。

## 总结 ##

Raft 算法通过以下几种方式来进行领导选举，保证了一个任期只有一位领导，极大减少了选举失败的情况。

*  任期
 *  领导者心跳信息
 *  随机选举超时时间
 *  先来先服务的投票原则
 *  大多数选票原则

本篇通过动图的方式来讲解 Raft 算法如何选举领导者，更容易理解和消化。

[61a7402ff9c7526ec083904434a6c201.png]: https://img-blog.csdnimg.cn/img_convert/61a7402ff9c7526ec083904434a6c201.png
[cbda0e5f92a5f778063ba20b20127883.png]: https://img-blog.csdnimg.cn/img_convert/cbda0e5f92a5f778063ba20b20127883.png
[e84c01426e0f778db9220c0cef82017b.png]: https://img-blog.csdnimg.cn/img_convert/e84c01426e0f778db9220c0cef82017b.png
[ce36ac00d89a6d20531bb7c192a34f22.gif]: https://img-blog.csdnimg.cn/img_convert/ce36ac00d89a6d20531bb7c192a34f22.gif
[82409ba9c9d7aa47c7d1d906a4a3a90d.gif]: https://img-blog.csdnimg.cn/img_convert/82409ba9c9d7aa47c7d1d906a4a3a90d.gif
[0e651ad304068083b83575f6739ac777.png]: https://img-blog.csdnimg.cn/img_convert/0e651ad304068083b83575f6739ac777.png
[2d036f7d1183c313abc0a533e44f4768.gif]: https://img-blog.csdnimg.cn/img_convert/2d036f7d1183c313abc0a533e44f4768.gif
[ed8b9b9d239501685494d65278e6052c.gif]: https://img-blog.csdnimg.cn/img_convert/ed8b9b9d239501685494d65278e6052c.gif
[3db02ce8f97dd993db8f725924fb5929.gif]: https://img-blog.csdnimg.cn/img_convert/3db02ce8f97dd993db8f725924fb5929.gif
[e8aff4960f4c7553371a2a75a8ef2d1a.gif]: https://img-blog.csdnimg.cn/img_convert/e8aff4960f4c7553371a2a75a8ef2d1a.gif