分布式一致性协议之Raft(一)
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),不定期分享一些区块链底层技术文章,博客排版好一点(ㄟ( ▔, ▔ )ㄏ)。