分布式系统选举算法剖析详解大数据
我们在了解分布式选举算法之前,我们需要这样一种算法产生的背景。在一个分布式系统中,因为各种意外的因素,有的服务器可能会崩溃或变得不可靠,它就不能和其他服务器达成一致状态。因而这样就需要一种Consensus协议,来确保服务器的容错性,也就是说即使系统中有一两个服务器节点Crash,也不会影响其处理过程。为了让容错方式达成一致,我们不可能要求所有的服务器节点100%都达成Consensus状态,只要超过半数的大多数服务器节点Consensus即可,假设有N台服务器节点,(N/2)+1 就超过半数,即可代表大多数了。那么,今天笔者给大家分享的就是Raft分布式选举算法。
Raft为了实现Consensus这个目标,这个过程如果选举一样,参选者需要说服大多数服务器节点投票给他,一旦选定后就跟随其操作。在Raft中,任何时候一个服务器节点可以扮演下面角色之一:
Leader:处理所有客户端交互,日志复制等操作,一般一次只有一个Leader。 Follower:类似选民,处于被动状态。 Candidate:类似Proposer,可以被选为一个新的Leader。Raft阶段分为两个,首先是选举过程,然后在选举出来的Leader带领下进行相关正常的操作,比如复制等。下面有相关示意图来展示该过程:
2.1 选举请求任何一个服务器节点都可以成为一个Candidate,它向其他服务器节点Follower发出要求选举自己的请求,如下图所示:
2.2 应答其他服务器应答同意,发出OK。如下图所示:
需要注意的是,如果在这个过程当中,有一个FollowerCrash掉,没有收到请求选举的要求,因此候选者可以自己选举自己,只要达到 (N/2)+1 的大多数票,候选人还是可以成为Leader的。
2.3 发送指令在候选者成为Leader后,它可以向其他Follower节点发送指令,比如进行日志复制,如下图所示:
2.4 Heartbeats之后,通过心跳进行日志复制等通知,如下所示:
2.5 Crash在运行的过程当中,一旦该集群的Leader当场Crash了,那么Follower中有一个成为候选者,发出投票选举邀请,如下图所示:
2.6 New Leader在Follower同意后,其成为Leader,继续承担日志复制等操作动作,如下图所示:
这里需要注意的是,在整个选举过程当中是有一个时间限制的,如下图所示:
出现在Split Note的情况,是因为如果同时有两个候选人向其他节点发出投票邀请,这时通过类似的加时赛来解决,两个候选者在一段Timeout,比如100ms互相不服气的等待后,因为双方得到的票数是一样的,一半对一半,那么在100ms后,再由这两个候选者发出投票邀请,这时同时的概率大大降低,那么首先发出邀请投票的候选者得到大多数同意票后,成为Leader,而另外的一个候选者后来发出投票邀请,那些Follower选民已经投票给了第一个候选者,此时不能再投票给它,它就成为落选者了,最后这个落选者也就成为一名普通的Follower了。
3.日志复制案例下面通过以日志复制为例子来说明Raft分布式选举算法,假设这里Leader已经选出,这时候客户端发出一个新增的请求,比如日志内容是 smartloli ,如下所图所示:
3.1 Append在Leader发送的指令下,Follower需要遵循它的指令,都将这个新的日志内容追加到他们各自的日志中:
3.2 Commit大多数Follower服务器节点日志写入磁盘文件后,确认追加成功,发出Commited OK,如下图所示:
再下一个心跳Heartbeats中,Leader会通知所有的Follower更新Commited。对于每个新的日志记录,重复上述操作过程。如果在这个过程当中,发生了网络通信故障,使得Leader不能访问大多数Followers了,那么Leader只能正常更新它能访问的那些Follower服务器节点,而大多数的服务器Follower因为没有了Leader,他们重新选择一个候选者作为Leader,然后这个新的Leader作为代表与外界进行交互,如果外界发送新的请求操作,比如添加新的日志,这个新的Leader就按照上述步骤通知大多数Followers服务器节点,如果这时网络故障修复了,那么原先的Leader就要降级成为Follower,在失联阶段这个老Leader的任何更新都不能算Commit,都要Roll Back,接受新的Leader的新的更新操作。
目前,几乎所有的语言都已经支持Raft分布式选举算法的库了。这里我们通过对分布式选举算法的学习与分析,可以对分布式系统底层选举机制有更好的理解。大家可以去阅读一下Raft算法作者写的论文。另外,Raft的作者有将论文进行整理成了大纲,阅读地址:《Raft论文大纲》
5.结束语这篇博客就和大家分享到这里,如果大家在研究学习的过程当中有什么问题,可以加群进行讨论或发送邮件给我,我会尽我所能为您解答,与君共勉。
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/9888.html
分布式文件系统,分布式数据库区块链并行处理(MPP)数据库,数据挖掘开源大数据平台数据中台数据分析数据开发数据治理数据湖数据采集相关文章
- 数据透视表上线!如何在纯前端实现这个强大的数据分析功能?
- 浙大发布「数据混合增强」框架AutoMix,还顺手开源了众多mixup算法
- 智驾车技术栈 | Apollo规划模块详解(二):算法实现-数据检查及更新
- 【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享|附代码数据
- 什么是高维数据可视化的降维方法_数据降维具体算法有哪几种
- etl算法详解_数据拉链处理什么意思
- MATLAB、R用改进Fuzzy C-means模糊C均值聚类算法的微博用户特征调研数据聚类研究
- MATLAB数据挖掘用改进的K-Means(K-均值)聚类算法分析高校学生的期末考试成绩数据
- [洗牌算法] - 从长度为m的int数组中随机取出n个元素,每次取的元素都是之前未取过的
- [Nucleic Acids Research | 论文简读] 基于大规模数据整合的单细胞基因调控网络推理算法
- A.机器学习入门算法(六)基于天气数据集的XGBoost分类预测
- 【计算机网络】网络层 : 总结 ( 功能 | 数据交换 | IP 数据报 | IPv4 地址 | IPv6 地址 | 路由选择协议 | 路由算法 )★★★
- 【数据挖掘】数据挖掘总结 ( K-Means 聚类算法 | 二维数据的 K-Means 聚类 ) ★
- 机器学习算法之降维详解大数据
- H2O中的随机森林算法介绍及其项目实战(python实现)详解大数据
- Spark MLlib回归算法——线性回归、逻辑回归、SVM和ALS详解大数据
- sparkMlib实现协同过滤算法详解大数据
- Python 调度算法 死锁 静动态链接(七)详解编程语言
- 算法-翻转单词顺序列详解编程语言
- 完美校验:Linux采用CRC算法防止数据丢失(linuxcrc校验)
- 只训练一次数据就能识别出物体,谷歌全新 AI 算法“单次学习”
- 宜远智能CEO吴博:医学影像的数据标注、算法方法与算力优化
- MySQL的中位数算法,快速准确计算数据集中间的值(mysql 中位数算法)
- Oracle中大数据按小到大排序算法(oracle从大到小排序)
- Redis集群中的选举算法与机制研究(redis选举算法和机制)