0%

Raft算法(解决分布式一致性问题)

发表于 分类于 ，

Raft算法

转载 10分钟弄懂Raft算法

分布式系统在极大提高可用性、容错性的同时，带来了一致性问题（CAP理论）。Raft算法能够解决分布式系统环境下的一致性问题。我们熟悉的ETCD注册中心就采用了这个算法。

见CAP理论

过去，Paxos一直是分布式协议的标准，但是Paxos难于理解，更难以实现，Google的分布式锁系统Chubby作为Paxos实现曾经遭遇到很多坑。后来斯坦福大学提出了Raft算法。

Raft是用于管理复制日志的一致性算法。它的效果相当于(multi-)Paxos，跟Paxos一样高效，但结构与Paxos不同。这使得Raft比Paxos更容易理解，也为构建实用系统提供了更好的基础。

基础知识

Raft集群包含多个服务器，5个服务器是比较典型的，允许系统容忍两个故障。在任何给定时间，每个服务器都处于以下三种状态之一，领导者（Leader），追随者（Follower）或候选人（Candidate）。 这几个状态见可以相互转换。

  1. leader: 处理所有客户端交互，日志复制等，一般一次只有一个Leader
  2. Follower：类似选民，完全被动
  3. Candidate：类似Proposer律师，可以被选为一个新的领导人

选择领导者

Raft使用心跳机制来触发领导者选举。 当服务器启动时，它们以Follower的身份开始。 只要服务器从Leader或Candidate接收到有效的RPC请求，服务器就会保持Follower状态。 Leader向所有Follower发送定期心跳（不带日志条目的AppendEntries RPC）以保持其权限。 如果一个Follower在称为选举超时的一段时间内没有接到任何通信，该Follower认为没有可行的领导者并开始选举新的Leader。

日志复制

一旦Leader当选，它就开始为客户请求提供服务。每个客户端请求包含由复制状态机执行的命令。Leader将命令作为新条目附加到其日志，然后并行地向每个其他服务器发出AppendEntries RPC以复制条目。当条目被安全地复制时，Leader将条目应用于其状态机并将该执行的结果返回给客户端。如果Follower崩溃或运行缓慢，或者网络数据包丢失，Leader将无限期地重试AppendEntries RPC（即使它已经响应客户端），直到所有Follower最终存储所有日志条目。

过程分析

参考Llinjing动画 , 英文版(http://thesecretlivesofdata.com/raft/)
[英文版原文](Understandable Distributed Consensus)

选举投票:

  1. 假设存在多个节点,初始都为跟随者状态
  2. 一段时间跟随者未收到领导者发来的信息,那么自己更改为候选人,并向其他节点发送一次选举投票请求
  3. 接受到的其他节点响应这次投票,如果大多数赞同,则该候选人成为领导者,之后所有的变化指令都由领导者决定

日志复制(2PC,两次提交):

  1. 每次发起的更改先记录到领导者的日志里
  2. 在未提交之前就将该变更指令同步到跟随者节点日志中
  3. 随后领导者进入等待状态,直到大多数节点记录成功响应
  4. 然后领导者提交这条记录,并通知所有跟随者提交记录,最终达成一致

选举投票补充说明:

  1. 在Raft算法中,会有两个超时时间控制选举过程
  2. 首先是竞选超时: 跟随者成为候选人的时间,一般是150~300毫秒的随机数.当竞选超时时间后,跟随者转变为候选人角色,并进入到选举周期,为自己发起投票
  3. 此时候选人发送投票请求给其它节点,如果收到请求的节点在当前选举周期还没有投过票,则会投给这个候选人,然后这个节点重置它的选举周期时间,重新计时(第二个时间?不确定这个时间是否就是竞选超时)
  4. 一旦候选人获取半数以上赞成投票,则成为领导者,
  5. 之后发送附加日志指令给跟随者,这些消息周期性发送,也叫心跳包.跟随者响应附加日志消息,选举周期将一直持续到某个跟随者没有收到心跳包并成为候选人.

多数投票能保证只有一个领导者当选,如果同一时间有两个候选人,则会出现投票分裂的情况:

  1. 在同一个周期里有两个节点同时发出竞选请求
  2. 如果两个节点都收到同样数量的投票请求,并且无法获得更多选票,那么将等待一轮竞选超时后,开始下一轮的竞选请求

网络分区:

  1. 假设存在两个分区, A和B一组, C,D,E一组,A和C均为各自分区的领导者
  2. 新增两个客户端请求修改两个分区(领导者)的数据,其中一个客户端修改节点A的值为3,但该节点无法同步大多数,所以日志记录未提交
  3. 另一个客户端修改节点C的值为8,因为可以同步大多数,所以该操作成功.
  4. 随后修复了网络分区问题,节点A会发现存在”更高领导人”,所以会选择下台
  5. 此时节点A和B回滚他们未提交的记录,并同步新领导人的日志,最终达成一致(所有节点值都为8,修改值3操作丢失)

总结

Raft算法具备强一致、高可靠、高可用等优点，具体体现在：

  1. 强一致性：虽然所有节点的数据并非实时一致，但Raft算法保证Leader节点的数据最全，同时所有请求都由Leader处理，所以在客户端角度看是强一致性的。
  2. 高可靠性：Raft算法保证了Committed的日志不会被修改，State Matchine只应用Committed的日志，所以当客户端收到请求成功即代表数据不再改变。Committed日志在大多数节点上冗余存储，少于一半的磁盘故障数据不会丢失。
  3. 高可用性：从Raft算法原理可以看出，选举和日志同步都只需要大多数的节点正常互联即可，所以少量节点故障或网络异常不会影响系统的可用性。即使Leader故障，在选举超时到期后，集群自发选举新Leader，无需人工干预，不可用时间极小。但Leader故障时存在重复数据问题，需要业务去重或幂等性保证。
  4. 高性能：与必须将数据写到所有节点才能返回客户端成功的算法相比，Raft算法只需要大多数节点成功即可，少量节点处理缓慢不会延缓整体系统运行。
您的支持是对我最大的动力 (●'◡'●)