setse 2019-09-08
Raft
算法解决的核心问题是在分布式环境下如何保持集群状态的一致性,简而言之就是一组服务,给定一组操作,最后得到一致的结果。
Raft
算法通过选举领导人(leader)
,由领导人复制日志(log)
到跟随者(follower)
,跟随者执行日志指令来达到最后集群状态的一致,整个算法也分成了两部分,领导人如何选举和跟随者如何安全的执行日志指令。
Raft
算法中一个节点在任意时刻只能处在领导人(leader)
,候选人(candidate)
,跟随者(follower)
,同时强调强领导来简化整个流程,所以他的日志数据流只能从领导人复制到跟随者,跟随者之间也不能传递日志。
通常情况下,系统中只有一个领导人并且其他节点全部都是跟随者,跟随者都是被动的,他们不会发送任何请求,只是简单的响应来自领导者或者候选人的请求
下面是三个状态的状态转换图;
图片描述
节点启动的时候,都是跟随者状态,在一段时间没有收到来自领导者的心跳,就从跟随者转变为候选人,发起选举;如果收到含自己的多数选票则转换到领导者;如果发现其他节点比自己更新,则切换到跟随者状态。为了确定其他节点比自己更新,Raft
又引入了任期(term)
的概念。
算法起始,任期是0,当有节点当选领导者
时,任期号为1
,新领导人选出后,任期在之前的任期号加1
。当节点从跟随者转化为候选人的时候,任期号也要增加1
。
任期起到逻辑时钟的作用
当一个跟随者节点长时间没有收到领导者心跳包,猜测领导者节点可能挂了,发起新领导者节点选举。
任期
,转换状态到`候选人
;等待其他节点回复,在等待过程中又可能发生下面的情况
下面的这个gif就展示了这个过程;(吐槽不支持git,博客连接http://qyuan.top/2019/07/14/r...
当选出了领导人
系统就可以对外提供服务,客户端把请求发送给集群,如果是跟随者收到则转发给领导者,由领导者统一处理,领导人会调度这些请求,顺序告知所有跟随者,保证所有节点的状态一致。
Raft
是基于复制状态机实现的,其核心思想就是相同的初始状态 + 相同的输入 = 一致的最终状态
,领导者将客户端请求打包到一个个log entry
,将这些log entries
发送到所有跟随者节点,然后大家按相同顺序应用log entry
中的命令,则状态肯定是一致的。
log entry
;log entry
到集群所有节点;log entry
的回复;log entry
里面的命令到自己的状态机中,也就是执行命令;log entry
中命令,达到和自己一致的状态机; 每个log entry
中,除了需要执行的命令之外还有领导者节点的任期号,用于处理异常情况;同时我们也可以看到,当日志被复制到大多数节点,即可向客户端返回成功的消息,一旦返回了结果,就必须保证系统在任何异常情况都不会发送回滚。
Raft
通过第一个阶段的commited
和第二个阶段的apply
,保证了状态机的一致性。
当然还有各种异常情况,我们下篇再讲,讨论细节(╹▽╹)
欢迎关注我的博客(qyuan.top),不定期分享一些区块链底层技术文章,博客排版好一点(ㄟ( ▔, ▔ )ㄏ)。