Raft算法系列教程1:Leader选举

1、服务器的三种角色

Raft算法中服务器主要分为三种角色: LeaderFollowerCandidate ,并且三种角色相互独立,也就是服务器在同一时间内只可能扮演其中一种角色。

Leader :用于对所有用户的请求进行处理以及日志的复制等等。

Follower :不会主动发送消息,只响应来自 LeaderCandidate 的请求。

Candidate :用于选举新的Leader。

2、任期介绍

Raft 算法将时间划分成为任意不同长度的任期( term )。任期用连续的数字进行表示。每一个任期的开始都是一次选举( election ),一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举,它就会在该任期的剩余时间担任领导人。在某些情况下,选票会被瓜分,有可能没有选出领导人,那么,将会开始另一个任期,并且立刻开始下一次选举。Raft 算法保证在给定的一个任期最多只有一个领导人。

3、网络状态

网络状态分为两种情况:选举阶段,正常运行阶段。 备注:网络状态还可能会有成员变化阶段,暂时先不考虑。

每一个任期都是以选举阶段开始。但不一定以正常运行阶段结束。在某些情况下一个完整的任期可能全部为选举阶段。如下图:

4、选举阶段->正常运行阶段

在网络初始化时,网络中所有的服务器都以 Follower 的角色启动。由于 Follower 只被动接收消息,所以全网中所有服务器都处于等待状态。同时每一个服务器都在本地维护一个计时器。计时器的作用很简单,就是判断当前阶段(选举阶段或正常运行阶段)是否超时,而当计时器超时后,任期将会加1。

总之,在网络启动后所有服务器等待指定长度的一段时间之后,计时器将会超时。这时候计时器超时的服务器将转换自己的角色为 Candidate ,从而进入选举阶段。进入选举阶段的 Candidate 将会做以下几件事:

(1)将自己的任期号加1。

(2)为自己投一票用以选举出新的Leader。

(3)将本地的计时器重置。

(4)发送投票请求到网络中的其他所有的服务器。

(5)等待下一次的计时器超时。

同时,投票选举 Leader 具有以下几点要求:

(1)每个服务器在一个任期内只能投一票,并且只能投先到者(即投票给自己收到的第一个请求)。
如果没有先到者,只能投票选自己了。

(2)请求投票的消息中需要带有请求者所处的当前任期号。

(3)投票者只会投票给任期号大于等于自己当前任期号的服务器。

在选举状态会出现三种结果:

(1)自己成功当选Leader

(2)网络中其他服务器当选Leader

(3)网络中没有服务器当选Leader

当网络中某一个 Candidate 接收到网络中大多数成员的投票后,即可将自己的身份转换为 Leader 。在当选 Leader 后,该服务器将周期性地发送心跳信息(心跳信息包含成功当选 Leader 的服务器的当前任期号)到网络中其他服务器。在网络中其他的服务器收到心跳信息后检查心跳消息中的任期号是否大于等于自己的任期号。如果满足该条件的话 Candidate 将会转换为 Follower 状态,并重置计时器。而如果任期号小于自己的任期号,服务器将拒绝该心跳消息并继续处于 Candidate 状态。

第三种情况为网络中没有服务器成功当选 Leader 。这种情况在有很多 Follower 同时成为 Candidate 时会发生。因为当角色转换为 Candidate 后将会将选票投给自己,从而导致选票被分散开来,没有 Candidate 可以得到网络中大部分节点的选票,从而没有节点可以成为 Leader 。这种情况下计时器将再次超时,网络状态将从选举阶段进入下一个选举阶段,同时 Candidate 将会再次执行上面说明的几件事。

Raft算法采用了随机选举超时机制来避免出现这种情况。即当计时器超时后,服务器将随机延迟指定的时间后才进入选举阶段。

由于随机延迟的原因,将降低服务器在同一时间选举超时的情况,可以有效避免选票分散的情况。

5、正常运行阶段->选举阶段

Leader 成功选举之后,将周期性发送心跳消息到网络中其他服务器。同时其他服务器将转换自己的角色为 Follower ,并且每次收到心跳消息后都会重置自己的计时器,防止超时再次进入选举阶段。

如果 Leader 因为特殊情况崩溃时,网络中的其他服务器将不再接收到心跳消息,在等待指定时间后计时器将会超时,从而再次进入选举阶段。

如果 Leader 崩溃时间较短,可以在其他服务器计时器超时之间恢复,并发送心跳消息,网络仍然可以恢复为 Leader 崩溃之前的状态。

如果 Leader 崩溃时间较长,在网络中已有新的 Leader 选举产生后恢复,由于旧的 Leader 任期号将小于新的 Leader ,在旧的 Leader 接收到新的 Leader 发送的心跳消息后则会变为 Follower 状态。

6、参考

http://www.mybatis.cn/archives/1147.html

博客园精华区
我还没有学会写个人说明!
上一篇

ClickHouse MaterializeMySQL实时同步MySQL汇总

你也可能喜欢

评论已经被关闭。

插入图片