分布式一致性协议之Raft(一)

setse 2019-09-08

  Raft算法解决的核心问题是在分布式环境下如何保持集群状态的一致性,简而言之就是一组服务,给定一组操作,最后得到一致的结果。
  Raft算法通过选举领导人(leader),由领导人复制日志(log)跟随者(follower),跟随者执行日志指令来达到最后集群状态的一致,整个算法也分成了两部分,领导人如何选举和跟随者如何安全的执行日志指令。

领导人选举

  Raft算法中一个节点在任意时刻只能处在领导人(leader)候选人(candidate)跟随者(follower),同时强调强领导来简化整个流程,所以他的日志数据流只能从领导人复制到跟随者,跟随者之间也不能传递日志。

通常情况下,系统中只有一个领导人并且其他节点全部都是跟随者,跟随者都是被动的,他们不会发送任何请求,只是简单的响应来自领导者或者候选人的请求

  下面是三个状态的状态转换图;
图片描述
  节点启动的时候,都是跟随者状态,在一段时间没有收到来自领导者的心跳,就从跟随者转变为候选人,发起选举;如果收到含自己的多数选票则转换到领导者;如果发现其他节点比自己更新,则切换到跟随者状态。为了确定其他节点比自己更新,Raft又引入了任期(term)的概念。

  算法起始,任期是0,当有节点当选领导者时,任期号为1,新领导人选出后,任期在之前的任期号加1。当节点从跟随者转化为候选人的时候,任期号也要增加1

任期起到逻辑时钟的作用
选举流程

  当一个跟随者节点长时间没有收到领导者心跳包,猜测领导者节点可能挂了,发起新领导者节点选举。

  • 增加自己当前的任期,转换状态到`候选人
  • 投自己一票,并且给其他节点发送请求给自己投票的请求;
  • 等待其他节点回复,在等待过程中又可能发生下面的情况

    1. 赢得选举,成为领导者;
    2. 被告知其他节点当选领导者,自己退回跟随者状态;
    3. 超时时间没有收到足够多的选票,则重复整个选举过程;

下面的这个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),不定期分享一些区块链底层技术文章,博客排版好一点(ㄟ( ▔, ▔ )ㄏ)。

相关推荐