Raft算法分析

什么是Raft算法?

筏算法是用于解决分布式系统中一致性问题的算法。在使用Raft算法之前,Lamport爷爷提出的Paxos算法过于模糊,难以实施。因此,筏算法似乎是Paxos的替代方法。与Paxos算法相比,Raft算法更易于理解且易于实现。

什么是共识?

在描述Raft算法之前,我们首先确定一致性的概念。一致性是分布式系统中的经典问题。简而言之,一致性是指多台计算机中数据的一致性。共识算法是确保多台机器可以同步数据。

请考虑以下情形。现在,我们有了仅包含一台服务器的单点服务。变量X存储在服务中。现在客户端希望将X的值设置为8。

raft协议机器台数

Client-Server.PNG

如果该服务仅在一台服务器上运行,则客户端将直接向服务器发送一个将X = 8设置的请求。如下图所示,服务器的值设置为8。

raft协议机器台数

Client-Server.PNG

但是如果服务在三台计算机的群集中运行怎么办?

raft协议机器台数

Client-Cluster.PNG

这时亚博app ,仅将节点A中的X设置为8。但是,我们不想简单地将X = 8请求发送到三个服务器A,B和C三次。我们希望外部接口服务的内容保持简单且不变。这时,它依靠共识算法来同步集群中的数据。

就严格性而言,一致性可以大致分为三类:

筏算法说明

Raft共识算法主要包括两个重要步骤:领导者选举(Leader Election)和日志复制(Log Replication)。

领导选举(Leader Election)

首先raft协议机器台数,Raft将群集中的计算机角色分为三种类型:领导者,关注者和候选者。

每台计算机的默认启动角色是“跟随者”。

如图所示,集群中的三台机器处于初始状态的“跟随者”状态:

raft协议机器台数

Follower.PNG

如果追随者在一段时间内未收到来自领导者的消息,它将自动转换为候选状态,如图所示,机器A变为候选:

raft协议机器台数

候选.PNG

计算机A成为候选者后亚博vip ,它向集群中的其他计算机发送投票请求,表明它希望成为领导者。

机器A在从集群中的其他大多数机器获得投票后自动成为领导者,如图所示:

raft协议机器台数

Leader.PNG

以上过程称为领导者选举(Leader Election)。

日志复制(日志复制)

在机器A成为领导者之后,以下示例描述了Raft协议如何同步该群集中的数据。

首先,客户端向集群发送请求,希望将X的值设置为5。

领导者收到请求后,首先将X = 5的请求写入日志。目前,该日志尚未提交,因此X的值未更改。

raft协议机器台数

log.PNG

领导将X = 5的请求发送到集群中的其他计算机。

raft协议机器台数

log.PNG

其他机器在收到请求后,还将X = 5的请求写入日志,并将成功结果返回给领导者。目前,X的值仍未更新。

raft协议机器台数

log.PNG

领导者收到一条消息,指出其他计算机已成功写入日志(大多数情况下成功),并提交X = 5的请求日志。此时,计算机A中的X值已成功更新为5。并通知其他计算机该日志已提交。

raft协议机器台数

提交日志。PNG

收到日志提交命令后,其他机器提交日志,并且X的值成功更新为5。

raft协议机器台数

提交日志。PNG

到目前为止,集群已真正达到一致状态。

领导选举(Leader Election)

上面概述了领导人选举的步骤。下面我们将解释两个主要的超时配置,它们控制着领导者选举的生命周期。

选举超时(选举超时)

选举超时是指关注者在自动转换为候选人之前的等待时间。

启动Raft算法时,默认情况下捕鱼平台 ,群集中的所有计算机都处于“关注者”状态。等待选举超时定义的时间后,它们会自动转换为候选状态。

选举超时时间基于固定值(1000ms)和150ms至300ms的随机值。

因此,群集中达到“选举超时”的第一台计算机将转换为“候选”状态并开始选举期限(“期限”)。此时,其他计算机处于“从动”状态。如下图所示,此时,机器B成为候选者辛运28 ,并且已经获得了投票权。

raft协议机器台数

候选.PNG

成为候选人之后,计算机C向其他计算机发送投票请求(请求投票)。

raft协议机器台数

候选.PNG

其他计算机收到投票请求后,如果在此期限(期限)内尚未投票,则将投票给该候选人。然后重置您的选举超时(Election Timeout)。

raft协议机器台数

Vote.PNG

在最后,谁得到了多数选票的候选人成功地成为了领导者。如图所示:

raft协议机器台数

Leader.PNG

心跳超时(心跳超时)

候选人成为领导者后,附加条目消息将定期发送给关注者。发送消息的时间间隔为“心跳超时”,默认值为100ms。

raft协议机器台数

Heartbeat.PNG

Follower在收到“添加条目”消息后重置其选举超时。

如果“关注者”在选举超时时间内未收到“追加条目”消息,它将自动转换为“候选人”并开始新一轮的领导选举(Term ++)。

raft协议机器台数

Vote.PNG

选举失败

请考虑集群中有四台计算机。此时raft协议机器台数,两台机器都成为候选人,并且都获得2票。然后,这一轮选举将失败。 Raft协议将等待群集选举时间超时,然后重新启动下一次选举,直到选举成功为止。

参考文章:

老王
地址:深圳市福田区国际电子商务产业园科技楼603-604
电话:0755-83586660、0755-83583158 传真:0755-81780330
邮箱:info@qbt8.com
地址:深圳市福田区国际电子商务产业园科技楼603-604
电话:0755-83174789 传真:0755-83170936
邮箱:info@qbt8.com
地址:天河区棠安路288号天盈建博汇创意园2楼2082
电话:020-82071951、020-82070761 传真:020-82071976
邮箱:info@qbt8.com
地址:重庆南岸区上海城嘉德中心二号1001
电话:023-62625616、023-62625617 传真:023-62625618
邮箱:info@qbt8.com
地址:贵阳市金阳新区国家高新技术开发区国家数字内容产业园5楼A区508
电话:0851-84114330、0851-84114080 传真:0851-84113779
邮箱:info@qbt8.com