失眠网 > 动画演绎分布式共识算法Raft

动画演绎分布式共识算法Raft

时间：2020-10-19 08:51:14

相关推荐

动画演绎分布式共识算法Raft

1. Raft 概述

Raft 算法是分布式系统开发首选的共识算法。主要在分布式集群架构下进行领导者（主节点）的确认。

比如现在流行的组件 Etcd、Consul、Nacos、RocketMQ、Redis Sentinel 底层都是采用Raft算法来确认集群中的主节点，再通过主节点向其他节点下发指令。

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

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

Raft协议概览

Raft协议基于quorum机制，即大多数同意原则，任何的变更都需超过半数的成员确认

2. Raft 角色

2.1 角色

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

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

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

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

学习者（Learner）: Raft 4.2.1引入的新角色。例如，当出现一个etcd集群需要增加节点时，新节点与

Leader的数据差异较大，需要较多数据同步才能跟

上Leader的最新的数据。

此时Leader的网络带宽很可能被用尽, 进而使得

Leader无法正常保持心跳。

进而导致Follower

重新发起投票。

进而可能引发etcd集群不可用。

Learner角色只接收数据而不参与投票，因此增加

Learner

节点时,

集群的quorum不变。

3. 单节点系统

3.1 数据库服务器

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

3.2 客户端

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

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

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

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

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

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

4. 选举领导过程

4.1 初始状态

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

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

4.2 成为候选者

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

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

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

4.3 投票

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

第一步：节点 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 先超时，先成为了候选者。这种巧妙的设计，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，减少了因选票瓜分导致选举失败的情况。

5. 领导者故障（触发新的一轮选举）

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

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

6. Etcd基于Raft的一致性

6.1 选举方法

初始启动时，节点处于follower状态并被设定一个election timeout，如果在这一时间周期内没有收到来

自leader的heartbeat，节点将发起选举：将自己切换为candidate之后，向集群中其它follower节

点发送请求，询问其是否选举自己成为 leader。当收到来自集群中过半数节点的接受投票后，节点即成为 leader，开始接收保存 client的数据并向其它

的 follower 节点同步日志。如果没有达成一致，则candidate随机选择一个等待间隔（150ms～300ms）

再次发起投票，得到集群中半数以上follower接受的candidate将成为leaderleader节点依靠定时向 follower 发送heartbeat来保持其地位。任何时候如果其它 follower 在 election timeout 期间都没有收到来自 leader 的 heartbeat, 同样会将

自己的状态切换为 candidate 并发起选举。每成功选举一次，新 leader 的任期（Term）都会比之前

leader的任期大1。

6.2 日志复制

当接Leader收到客户端的日志（事务请求）后先把该日志追加到本地的Log中，然后通过

heartbeat把该Entry同步给其他Follower，Follower接收到日志后记录日志然后向Leader发送

ACK，当Leader收到大多数（n/2+1）Follower的ACK信息后将该日志设置为已提交并追加到本

地磁盘中，通知客户端并在下个heartbeat中Leader将通知所有的Follower将该日志存储在自己

的本地磁盘中。

6.3 安全性

安全性是用于保证每个节点都执行相同序列的安全机制，如当某个Follower在当前Leader

commit Log时变得不可用了，稍后可能该Follower又会被选举为Leader，这时新Leader可能会

用新的Log覆盖先前已committed的Log，这就是导致节点执行不同序列；Safety就是用于保证

选举出来的Leader一定包含先前 committed Log的机制;

选举安全性（Election Safety）：每个任期（Term）只能选举出一个LeaderLeader完整性（Leader Completeness）：指Leader日志的完整性，当Log在任期Term1被

Commit后，那么以后任期Term2、Term3…等的Leader必须包含该Log; Raft在选举阶段就使

用Term的判断用于保证完整性：当请求投票的该Candidate的Term较大或Term相同Index更大

则投票，否则拒绝该请求。

失效处理

Leader失效：其他没有收到heartbeat的节点会发起新的选举，而当Leader恢复后由于步进数

小会自动成为follower（日志也会被新leader的日志覆盖）follower节点不可用：follower节点不可用的情况相对容易解决。因为集群中的日志内容始

终是从 leader 节点同步的，只要这一节点再次加入集群时重新从 leader 节点处复制日志即可。多个candidate：冲突后candidate将随机选择一个等待间隔（150ms～300ms）再次发起

投票，得到集群中半数以上follower接受的candidate将成为leader

6.4 wal日志(write ahead log)

wal日志是二进制的，解析出来后是以上数据结构LogEntry。

其中第一个字段type,
一种是O表示Normal, 1表示ConfChange（ConfChange表示Etcd本
身的配置变更同步，比如有新的节点加入等）。第二个字段是term，每个term代表一个主节
点的任期，每次主节点变更term就会变化。第三个字段是index，这个序号是严格有序递增的，
代表变更序号。第四个字段是二进制的data，将raft request对象的pb结构整个保存下。

etcd 源码下有个tools/etcd-dump-logs，可以将wal日志dump成文本查看，

，可以协助分析

Raft协议。

Raft协议本身不关心应用数据，也就是data中的部分，一致性都通过同步wal日志来实现，每

个节点将从主节点收到的data apply到本地的存储，Raft只关心日志的同步状态，如果本地存

储实现的有bug，比如没有正确的将data apply到本地，也可能会导致数据不一致。

7. 总结

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

任期机制：决定消息的接收或拒绝领导者心跳信息：决定领导者是否正常有效可以和其他跟随者（Follower）通信随机选举超时时间：决定同一时间不会让所有跟随者（Follower）进行投票选举先来先服务的投票原则：在同一届任期内（Term）内，先收到哪个候选人（Candidate）的请求，跟随者（Follower）就把票投给谁大多数选票原则：收到至少 N/2+1的投票，才可以成为领导者