RAFT算法简述

星期四, 4月 18, 2019 | 5分钟阅读 | 更新于 星期六, 9月 7, 2019

@

什么是RAFT算法

一致性(共识)算法用于解决分布式环境下多副本之间数据一致性的问题。RAFT正是通过管理复制日志的方式来达成一致的共识算法。Raft阶段分为两个,首先是选举过程,然后是日志(一个状态机指令或者是节点配置变更)同步过程,即追随者在选举出来的领导人带领下进行日志复制操作。

如何达成一致

所有一致性算法都会涉及到状态机,而状态机保证系统从一个一致的状态开始,以相同的顺序执行一些列指令最终会达到另一个一致的状态。所有的节点以相同的顺序处理日志,那么最终状态机在多个节点中都是一致的。

节点角色

在Raft中,任何时候一个服务器可以扮演下面角色之一,且同一时刻只能是一种:
Leader领导者: 处理所有客户端交互,负责日志同步,一个时刻只有一个Leader。
Follower追随者: 类似选民,完全被动,听从leader的,与leader保持同步。
Candidate候选人: 可以被选为一个新的领导人,这是一个中间态,不可长期存在。

任期

Raft把时间切割为任意长度的任期,每个任期都有一个任期号,采用连续的整数。每个任期都由一次选举开始,若选举失败则这个任期内没有Leader;如果选举出了Leader则这个任期内有Leader负责集群状态管理。

选举过程

raft初始状态时所有节点都处于Follower状态,并且随机睡眠一段时间。最先醒来的节点进入Candidate状态,向其它所有节点发出投票请求。当其它节点收到投票请求后,如果同意(请求节点的任期日志比自己的新)将自己仅有的一票投给请求节点。当节点收到超过半数节点的投票后,就进入Leader状态,成为系统中仅有的Leader。raft系统中只有Leader才有权利接收并处理client请求,并向其它节点发出同步请求。

日志复制过程

Leader选举出来后,就可以开始处理客户端请求。Leader收到客户端请求后,将请求内容作为一条日志添加到自己的日志记录中,并向其它节点发送添加日志请求。其它节点收到请求后,判断该请求满足接收条件,如果满足条件就将其添加到本地的日志中,并给Leader发送添加成功的回复。Leader在收到大多数节点添加成功的回复后,就将该条日志正式提交。提交后的日志日志就意味着已经被raft系统接受,并能应用到状态机中了。

节点状态

  1. currentTerm:节点当前任期,初始为0,递增
  2. votedFor:在当前获得选票的候选人的 Id
  3. log[]:日志条目集;每一个条目包含一个用户状态机执行的指令,和收到时的任期号
  4. commitIndex:最大的已经被commit的日志的index
  5. appliedIndex:最大的已经被应用到状态机的index

节点响应规则

所有节点

  • 如果commitIndex > appliedIndex,应用log[appliedIndex]到状态机,增加appliedIndex
  • 如果请求或者响应包含的任期T > currentTerm,将currentTerm设置为T并转换为Follower

Followers

  • 响应来自Leader和Candidate的请求
  • 如果在选举超时周期内没有收到添加日志的请求或者给Candidate投票,转换为Candidate角色

Candidates

  • 转换为candidate角色,开始选举:

  • 递增currentTerm

  • 给自己投票

  • 重置选举时间

  • 发送投票请求给其他所有节点

  • 如果收到了大多数节点的选票,转换为Leader节点

  • 如果收到Leader节点的添加日志请求,转换为Follower节点

  • 如果选举超时,重新开始新一轮的选举

Leaders

  • 一旦选举完成:发送心跳给所有节点;在空闲的周期内不断发送心跳保持Leader身份和阻止跟随者超时,
  • 如果收到客户端的请求,将日志追加到本地日志中,在日志被应用到状态机后响应给客户端

异常情况

  1. leader节点挂了:每一个追随者节点都有一个随机时间的超时任务:转变状态至候选者,在收到leader心跳时会重置,如果leader挂了,将在超时时间之内收不到心跳,超时转化为候选者发起重新选举过程。
  2. 两个节点同时发起投票请求,由于在一次选举过程中,一个节点一个任期只能投一票,这就保证了两个节点不可能同时得到大多数(一半以上)的投票。如果A和B可能刚好都得到一半的投票,两者都成为不了Leader。这时A和B继续保持Candidate状态,并且随机睡眠一段时间,等待进入到下一个选举周期。由于所有节点都是随机选择睡眠时间,所以连续出现多个节点竞选的概率很低。
  3. 向raft系统中添加新机器时,由于配置信息不可能在各个节点上同时达到同步状态,总会有某些节点先得到新机器的信息,有些节点后得到新机器的信息。解决办法是将添加机器这个动作当成一个提议,当leader提交这个提议后新的配置生效。

优势与局限

  • 优势:在达成一致的过程中,避免所有节点争抢提议权,直接由leader节点负责提议,大大加快了共识的速度;整个集群由leader节点作为代表,对外处理客户端的提议,对内管理不同节点的日志一致,模型简单可靠,节点通信效率高(一对多)。
  • 局限性:raft算法假设每个节点都是忠诚的、节点间的信道是安全的,如果存在作恶节点(即使只有一个)或者信道不安全则整个集群就完全失效。

© 2026 我的博客

🌱 Powered by Hugo with theme Dream.

关于这个博客

关于博客

记录软件开发过程的一些知识和技巧,提升自我

关于博主

除了才华一无所有~~ 薪尽自然凉~~ 强迫症患者~~ 热爱古风~~