您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

Paxos算法难理解?来看看大家都在用的Raft算法

时间:2021-06-04 14:09:31  来源:今日头条  作者:微说互联网

分布式共识系列文章:

前面几篇文章介绍了Paxos算法,一直是分布式协议的标准,但Paxos算法难于理解,更难以实现。即使google的分布式锁系统Chubby以Paxos算法实现,也遇到了很多坑。为了简化分布一致性算法,斯坦福大学提出了一种Raft算法。

Raft 算法在2013年发表,就是建立在希望得到一个更易于理解的 Paxos 算法的替代品。论文题目《In Search of an Understandable Consensus Algorithm》就可以看出来,可理解性是Raft算法的主要目标之一。到现在已经有了十多种语言的Raft算法的实现框架,最为出名的就是Etcd。

Etcd是CoreOS团队于2013年6月发起的开源项目,它的目标是构建一个高可用的分布式键值(key-value)数据库。

Leader选举(Leader Election)

在一个由 Raft 协议组织的集群中有三类角色:Leader(领袖)、Follower(群众)、Candidate(候选人)。

Paxos算法难理解?来看看大家都在用的Raft算法

Raft三类角色的状态转换

  • Leader:处理所有客户端交互,日志复制等。集群一般只能有一个领导,领导在位期间就是一个任期(Term)。Leader定期向Follower发送心跳,宣示自己的存在。
  • Follower:如果Follower在election timeout内没有收到来自Leader的心跳,那么会认为Leader挂掉了。Follower会更新自己的当前任期(Current Term)并成为Candidate,并开始选举新的Leader。
  • Candidate:候选人,有可能被选为一个新的领导人。如果收到了多数的投票就当选为Leader。如果超过一定时间没有收到选票,就重新发起选举。

一个最小的 Raft集群需要三个参与者,这样才可能投出多数票。如下图所示,初始状态下 ABC三个节点开始选举Leader。

Paxos算法难理解?来看看大家都在用的Raft算法

Raft协议Leader选举

Leader选举过程中有三种可能的情形发生:

  • A节点要投自己一票,并把提议(拉票请求)发给B和C,B和C接受了A的提议,也投票给A。A成为Leader。
  • A节点投了自己一票,B节点也投了自己一票,C节点支持A节点的提议,少数服从多数。A成为Leader。
  • A节点、B节点、C节点都各自投了自己一票。没有节点获得多数票。

以上前二种情况都能选出 Leader,第三种情况本轮投票无效,出现了平票(Split Votes)。因为没有任何一方获得多数票,所以要发起新的一轮投票。

Raft协议为了不让选举机制反复出现平票,定义了一个随机超时机制(randomized election timeouts)。一旦发生平票,平票的节点会各自再来一次随机timeout倒数,然后重新拉票。先发起拉票的节点就可以优先获得了多数节点的投票。

数据同步(Log Replication)

Raft 协议强依赖 Leader 节点的可用性来确保集群数据的一致性。数据的流向只能从 Leader节点向 Follower 节点转移。

  1. 当 Client 向集群 Leader 节点提交数据(v=3)后,Leader 节点接收到的数据处于未提交状态(Uncommitted)。
  2. 接着 Leader 节点会并发向所有的 Follower 节点复制数据并等待接收响应。
  3. Leader节点确保至少集群中超过半数节点确认接收到数据。
  4. Leader向 Client 发送Ack确认数据已接收,表明此时数据状态进入已提交(Committed)状态。Leader 节点向Follower 节点发通知告知该数据状态(v=3)已提交。
Paxos算法难理解?来看看大家都在用的Raft算法

数据从Leader向Follower转移过程

Leader挂掉对一致性的影响

接下来我们看一下,如果在数据转移过程中,Leader挂掉,对数据一致性会造成什么影响。

1. 在数据到达 Leader 节点前,这个阶段 Leader 挂掉。显然不影响一致性。

Paxos算法难理解?来看看大家都在用的Raft算法

数据到达Leader前,Leader挂掉

2. 当数据到达 Leader 节点,但未复制给 Follower 节点。这个阶段 Leader 挂掉,数据属于未提交状态。Client 没有收到 Ack确认会认为超时失败,于是发起重试。

Follower 节点重新选主,新的Leader上没有该数据。Client 重新提交数据到新Leader可以成功。原来的 Leader 节点恢复后作为 Follower 加入集群,从当前任期的新 Leader 同步数据,保持和 Leader 数据一致。

Paxos算法难理解?来看看大家都在用的Raft算法

数据到达Leader,处于未提交状态

3 当数据到达 Leader 节点,并成功复制给所有Follower节点,但Follower节点尚未向 Leader 响应接收。此时 Leader 挂掉。

虽然数据在 Follower 节点处于未提交状态(Uncommitted),但已经保持一致。重新选出 Leader 后可完成数据提交。此时 Client 由于不知到底提交成功没有,会重试提交。针对这种情况 Raft 要求 RPC 请求实现幂等性,也就是要实现内部去重机制。

Paxos算法难理解?来看看大家都在用的Raft算法

当数据到达 Leader 节点,并成功复制给所有Follower节点,但尚未提交

4. 数据到达 Leader 节点,并成功复制给 Follower 部分节点,但还未向 Leader 响应接收。在这个阶段 Leader 挂掉,数据在 Follower 节点处于未提交状态(Uncommitted)且数据不一致。

Raft 协议要求投票只能投给拥有最新数据的节点。这样拥有最新数据的节点会被选为 Leader,再同步数据到 Follower,数据不会丢失并实现最终一致。

5 数据到达 Leader 节点,并成功复制给 Follower 所有或多数节点,数据在 Leader 处于已提交状态,但在 Follower 处于未提交状态。这个阶段 Leader 挂掉,重新选出新 Leader 后的处理流程和上面第3种情况一样。

Paxos算法难理解?来看看大家都在用的Raft算法

数据在Leader 节点处于已提交,在Follower处于未提交状态

6 数据到达 Leader 节点,成功复制到 Follower 所有或多数节点,数据在所有节点都处于已提交状态,但由于某种原因,Client未收到Ack响应。这个阶段 Leader 挂掉,集群内部数据其实已经是一致的,Client 重新提交数据,基于幂等策略对一致性无影响。

Paxos算法难理解?来看看大家都在用的Raft算法

集群内数据已达成一致

从上面的讨论可知,在Leader向Follower进行数据同步的不同阶段,Leader挂掉也不会影响数据的最终一致性。那么如果由于网络分区,导致双Leader出现,即所谓脑裂的情况,那么对数据一致性会有影响吗?

脑裂的情况

所谓脑裂,就是集群中出现了双 Leader,这种情况通常是由于网络分区导致。一山不容二虎,一个集群也不能有二主。我们来看一下这种情况下,Raft协议如何将集群恢复到正常。

  1. 网络分区将原先的 Leader 节点和 Follower 节点分隔开,由于Follower 收不到 Leader 的心跳将发起选举产生新的 Leader。
  2. 这时就产生了双 Leader,原先的 Leader 独自在一个区,向它提交数据不可能复制到多数节点,所以永远提交不成功。
  3. 向新的 Leader 提交数据可以提交成功,网络恢复后旧的Leader 发现集群中有了新 Leader,于是自己主动降级为 Follower,并从新 Leader 那里同步数据,最终达成集群数据一致。
Paxos算法难理解?来看看大家都在用的Raft算法

脑裂最终达成一致

总结

设计Raft算法的目的是实现一种可理解性较好的Multi Paxos算法。看了上面的讲解,大家是否也觉得Raft算法理解起来非常容易呢?

我会持续更新关于物联网、云原生以及数字科技方面的文章,用简单的语言描述复杂的技术,也会偶尔发表一下对IT产业的看法,请大家多多关注,欢迎留言和转发,希望与大家互动交流,谢谢。



Tags:Raft算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
分布式共识系列文章: 《解决分布式一致性问题,不得不了解的Paxos算法》 《基本Paxos协议是如何实现分布式数据一致性的?》 《可用于实际应用场景中的Multi Paxos实用算法》前面...【详细内容】
2021-06-04  Tags: Raft算法  点击:(172)  评论:(0)  加入收藏
Raft,分布式共识算法,是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。如redis-sentinel,etcd等都使用Raft协议解决分布式一致性的问题。Nacos注册中心是阿里...【详细内容】
2020-08-31  Tags: Raft算法  点击:(408)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条