文档分享类网站建设,深圳龙霸网站建设,wordpress 无法注册,微信怎么建立公众号Raft算法
概述
Raft算法属于Multi-Paxos算法#xff0c;它在兰伯特Multi-Paxos思想的基础上做了一些简化和限制#xff0c;比如日志必须是连续的#xff0c;只支持领导者(Leader)、跟随者(Follwer)和候选人(Candidate)3种状态。在理解和算法实现上#xff0c;Raft算法相对…Raft算法
概述
Raft算法属于Multi-Paxos算法它在兰伯特Multi-Paxos思想的基础上做了一些简化和限制比如日志必须是连续的只支持领导者(Leader)、跟随者(Follwer)和候选人(Candidate)3种状态。在理解和算法实现上Raft算法相对容易许多。 除此之外Raft算法是现在分布式系统首选的共识算法。绝大多数选用Paxos算法的系统(比如Chubby、Spanner)都是在Raft算法发布前开发的当时没有其他选择;而全新的系统大多选择了Raft算法(比如Etcd、Consul、CockroachDB)。 掌握了Raft算法我们就可以得心应手地满足绝大部分场景的容错和一致性需求比如分布式配置系统、分布式NoSQL存储等轻松突破系统的单机限制。 如果要用一句话概括Raft算法我觉得是这样的:从本质上说Raft算法是通过一切以领导者为准的方式实现一系列值得共识和个节点日志的一致。这句话比较抽象做个比喻:领导者就是Raft算法中的霸道总裁,通过霸道的一切以我为准的方式。决定了日志中命令的值也实现了个节点日志的一致。后面会以领导者选举、日志赋值、成员变更为核心讲解Raft算法的原理。
在正式介绍之前我们先来看一道思考题。 假设我们有一个由节点A、B、C组成的Raft集群(如图所示)因为Raft算法是一切以领导者为准所以如果集群中出现了多个领导者就会出现不知道谁来做主的问题。在这样一个有多个节点的集群中在节点故障、分区容错等异常情况下Raft算法应该如何保证在同一个时间内集群中只有一个领导者呢?
Raft是如何选举领导者的
既然要选举领导者要从哪些成员中选举呢除了领导者Raft算法还支持哪些成员身份呢这是需要掌握的最基础的背景知识。
有哪些成员身份 成员身份又叫作服务器节点状态。Raft算法支持跟随者、候选人和领导者3种状态。为了方便理解 我们使用不同的图形表示不同的状态如图u宋史在任何时候每一个服务器节点都处于这3个状态中的其中1个 1.跟随者:相当于普通群众默默地接收和处理来自领导者的消息当领导者心跳信息超时的时候它会主动站出来推荐自己当候选人 2.候选人:候选人将向其他节点发送请求投票(RequestVote) RPC消息通知其他节点来投票如果它赢得了大多数选票那么它将晋升为领导者 3.领导者:一切以我为准平常的主要工作包含三部分处理写请求、管理日志复制和不断发送心跳信息通知其他节点我是领导者你们现在不要发起新的选举找个新领导者来替代我 需要注意的是Raft算法是强领导者模型集群中只能有一个霸道总裁。
选举领导者的过程
那么如何从3个成员中选出领导者呢? 首先在初始状态下集群中所有的节点都处于跟随者的状态如图所示。
Raft算法实现了随机超时时间的特性。也就是说每个节点等待领导者节点心跳信息的超时时间间隔是随机的。 通过上图可以看到集群中没有领导者而节点A的等待超时时间最小(150ms)所以它会最先因为没有等到领导者的心跳信息而超时。 这个时候节点A会增加自己的任期编号并推荐自己为候选人先给自己投一张选票然后先其他阶段发送请求投票RPC消息请他们选举自己为领导者如图所示
如果其他节点接收到候选人A的请求投票RPC消息且在编号为1的这届任期内它也还没有投过票那么它将把选票投给节点A,并增加自己的任期编号如图所示。
如果候选人在选举超时时间内赢得了大多数选票那么它就会成为本届任期内新的领导者如图所示。
节点A当选领导者后将周期性的发送心跳消息通知其他服务器我是领导者,阻止跟随者发起新的选举、篡权。
如图所示看到这里你是不是发现领导者选举很容易理解?它与现实中地议会选举也很类似当然你可能还是会对一些细节产生疑问比如:
1.节点间是如何通信地?2.什么是任期?3.选举有哪些规则4.随机超时时间又是什么
选举过程四连问
老话说细节是魔鬼。这些细节也是大家在学习Raft算法时比较难掌握地所以这里有必要具体分析一下。一步步来
节点间如何通信
在Raft算法中服务器节点采用地沟通方式是远程过程调用(RPC)在领导者选举中我们需要用到这样两类RPC:
1.请求投票(RequestVote)RPC时由候选人在选举期间发起通知各节点进行投票2.日志复制(AppendEntries)RPC是由领导者发起地用来复制日志和提供心跳消息
需要注意的是日志复制RPC只能由领导者发起这是实现强领导者模型的关键之一理解这一点有助于后续更好地理解日志复制以及如何实现日志的一致
