raft协议

2021-05-15

一、Raft一致性算法

  Eureka:Peer To Peer,每个节点的地位都是均等的,每个节点都可以接收写入请求,每个节点接收请求之后,进行请求打包处理,异步化延迟一点时间,将数据同步给 Eureka 集群当中的其他节点。任何一台节点宕机之后,理论上应该是不影响集群运行的,都可以从其他节点获取注册表信息。
  Etcd、Consul,Zookeeper, Nacos,其中的 CP 模式也是基于 Raft 协议 来实现分布式一致性算法的。当然 Zookeeper 在 Raft 协议基础上做了一些改良,使用的 ZAB 分布式一致性协议来实现的。
  1. 基本概念
1. leader选举:当已有的leader故障时必须选出一个新的leader。
2. 日志复制:leader接受来自客户端的命令,记录为日志,并 复制给集群中的其他服务器,并强制其他节点的日志与leader保持一致。
3. 安全safety措施:通过一些措施确保系统的安全性,如 确保所有状态机按照相同顺序执行相同命令的措施。
服务器三种角色:leader、candidate、follower
1. follower只会响应leader和candidate的请求,
2. 客户端的请求则全部由leader处理,
3. 有客户端请求了一个follower也会将请求重定向到leader。
 
    集群刚启动时,所有节点都是follower,之后在time out信号的驱使下,follower会转变成candidate去拉取选票,获得大多数选票后就会成为leader,这时候如果其他候选人发现了新的leader已经诞生,就会自动转变为follower;而如果另一个time out信号发出时,还没有选举出leader,将会重新开始一次新的选举。
  Raft协议中,将时间分成了一些任意长度的时间片,称为term,term使用连续递增的编号的进行识别。
每一个term都从新的选举开始,candidate们会努力争取称为leader。一旦获胜,它就会在剩余的term时间内保持leader状态,在某些情况下(如term3)选票可能被多个candidate瓜分,形不成多数派,因此term可能直至结束都没有leader,下一个term很快就会到来重新发起选举。
 
  term也起到了系统中逻辑时钟的作用,每一个server都存储了当前term编号,在server之间进行交流的时候就会带有该编号,如果一个server的编号小于另一个的,那么它会将自己的编号更新为较大的那一个;如果leader或者candidate发现自己的编号不是最新的了,就会自动转变为follower;如果接收到的请求的term编号小于自己的当前term将会拒绝执行。
 
server之间的交流是通过RPC进行的。只需要实现两种RPC就能构建一个基本的Raft集群:
* RequestVote RPC:它由选举过程中的candidate发起,用于拉取选票
* AppendEntries RPC:它由leader发起,用于复制日志或者发送心跳信号。

2. leader选举

  Raft通过 心跳机制发起leader选举。节点都是从follower状态开始的, 如果收到了来自leader或candidate的RPC,那它就 保持follower状态,避免争抢成为candidate。Leader会发送空的AppendEntries RPC作为心跳信号来确立自己的地位,如果 follower一段时间(election timeout)没有收到心跳,它就会认为leader已经挂了, 发起新的一轮选举。选举发起后,一个follower会增加自己的当前term编号并转变为candidate。它会首先投自己一票,然后向其他所有节点并行发起RequestVote RPC。
candidate状态将可能发生如下三种变化:
  1. 赢得选举,成为leader(如果它在一个term内收到了大多数的选票,将会在接下的剩余term时间内称为leader,然后就可以通过发送心跳确立自己的地位。每一个server在一个term内只能投一张选票,并且按照先到先得的原则投出)
  2.  其他server成为leader(在等待投票时,可能会收到其他server发出AppendEntries RPC心跳信号,说明其他leader已经产生了。这时通过比较自己的term编号和RPC过来的term编号,如果比对方大,说明leader的term过期了,就会拒绝该RPC,并继续保持候选人身份; 如果对方编号不比自己小,则承认对方的地位,转为follower.)
  3.  选票被瓜分,选举失败(如果没有candidate获取大多数选票, 则没有leader产生, candidate们等待超时后发起另一轮选举. 为了防止下一次选票还被瓜分,必须采取一些额外的措施, raft采用随机election timeout的机制防止选票被持续瓜分。通过将timeout随机设为一段区间上的某个值, 因此很大概率会有某个candidate率先超时然后赢得大部分选票.)
  1. 日志复制过程
  客户端提交每一条命令都会被按顺序记录到leader的日志中,每一条命令都包含term编号和顺序索引,然后向其他节点并行发送AppendEntries RPC用以复制命令(如果命令丢失会不断重发), 当复制成功也就是大多数节点成功复制后,leader就会提交命令,即执行该命令并且将执行结果返回客户端,raft保证已经提交的命令最终也会被其他节点成功执行。leader会保存有当前已经提交的最高日志编号。顺序性确保了相同日志索引处的命令是相同的,而且之前的命令也是相同的。当发送AppendEntries RPC时,会包含leader上一条刚处理过的命令,接收节点如果发现上一条命令不匹配,就会拒绝执行。
  特殊故障:如果leader崩溃了,它所记录的日志没有完全被复制,会造成日志不一致的情况,follower相比于当前的leader可能会丢失几条日志,也可能会额外多出几条日志,这种情况可能会持续几个term。
    在上图中,框内的数字是term编号,a、b丢失了一些命令,c、d多出来了一些命令,e、f既有丢失也有增多,这些情况都有可能发生。比如f可能发生在这样的情况下:f节点在term2时是leader,在此期间写入了几条命令,然后在提交之前崩溃了,在之后的term3中它很快重启并再次成为leader,又写入了几条日志,在提交之前又崩溃了,等他苏醒过来时新的leader来了,就形成了上图情形。在Raft中,leader通过强制follower复制自己的日志来解决上述日志不一致的情形,那么冲突的日志将会被重写。为了让日志一致,先找到最新的一致的那条日志(如f中索引为3的日志条目),然后把follower之后的日志全部删除,leader再把自己在那之后的日志一股脑推送给follower,这样就实现了一致。而寻找该条日志,可以通过AppendEntries RPC,该RPC中包含着下一次要执行的命令索引,如果能和follower的当前索引对上,那就执行,否则拒绝,然后leader将会逐次递减索引,直到找到相同的那条日志。
    然而这样也还是会有问题,比如某个follower在leader提交时宕机了,也就是少了几条命令,然后它又经过选举成了新的leader,这样它就会强制其他follower跟自己一样,使得其他节点上刚刚提交的命令被删除,导致客户端提交的一些命令被丢失了
Raft通过为选举过程添加一个限制条件,解决了上面提出的问题,该限制确保leader包含之前term已经提交过的所有命令。Raft通过投票过程确保 只有拥有全部已提交日志的candidate能成为leader。由于candidate为了拉选票需要通过RequestVote RPC联系其他节点,而之前提交的命令至少会存在于其中某一个节点上,因此只要candidate的日志至少和其他大部分节点的一样新就可以了, follower如果收到了不如自己新的candidate的RPC,就会将其丢弃.
    还可能会出现另外一个问题, 如果命令已经被复制到了大部分节点上,但是还没来的及提交就崩溃了,这样后来的leader应该完成之前term未完成的提交. Raft通过让leader统计当前term内还未提交的命令已经被复制的数量是否半数以上, 然后进行提交.
  1. 日志压缩
  随着日志大小的增长,会占用更多的内存空间,处理起来也会耗费更多的时间,对系统的可用性造成影响,因此必须想办法压缩日志大小。Snapshotting是最简单的压缩方法,系统的全部状态会写入一个snapshot保存起来,然后丢弃截止到snapshot时间点之前的所有日志。
  每一个server都有自己的snapshot,它只保存当前状态,如上图中的当前状态为x=0,y=9,而last included index和last included term代表snapshot之前最新的命令,用于AppendEntries的状态检查。
  虽然每一个server都保存有自己的snapshot,但是当follower严重落后于leader时,leader需要把自己的snapshot发送给follower加快同步,此时用到了一个新的RPC:InstallSnapshot RPC。follower收到snapshot时,需要决定如何处理自己的日志,如果收到的snapshot包含有更新的信息,它将丢弃自己已有的日志,按snapshot更新自己的状态,如果snapshot包含的信息更少,那么它会丢弃snapshot中的内容,但是自己之后的内容会保存下来。

二、zab对比raft

1. 上一轮次的leader的残留的数据:
  Raft:对于之前term的过半或未过半复制的日志采取的是保守的策略,全部判定为未提交,只有当当前term的日志过半了,才会顺便将之前term的日志进行提交
  ZooKeeper:采取激进的策略,对于所有过半还是未过半的日志都判定为提交,都将其应用到状态机中
2. 怎么阻止上一轮次的leader假死的问题
  Raft的copycat实现为:每个follower开通一个复制数据的RPC接口,谁都可以连接并调用该接口,所以Raft需要来阻止上一轮次的leader的调用。每一轮次都会有对应的轮次号,用来进行区分,Raft的轮次号就是term,一旦旧leader对follower发送请求,follower会发现当前请求term小于自己的term,则直接忽略掉该请求,自然就解决了旧leader的干扰问题
  ZooKeeper:一旦server进入leader选举状态则该follower会关闭与leader之间的连接,所以旧leader就无法发送复制数据的请求到新的follower了,也就无法造成干扰了
3. raft流程
1. client连接follower或者leader,如果连接的是follower则,follower会把client的请求(写请求,读请求则自身就可以直接处理)转发到leader
2. leader接收到client的请求,将该请求转换成entry,写入到自己的日志中,得到在日志中的index,会将该entry发送给所有的follower(实际上是批量的entries)
3. follower接收到leader的AppendEntries RPC请求之后,会将leader传过来的批量entries写入到文件中(通常并没有立即刷新到磁盘),然后向leader回复OK
4. leader收到过半的OK回复之后,就认为可以提交了,然后应用到leader自己的状态机中,leader更新commitIndex,应用完毕后回复客户端
5. 在下一次leader发给follower的心跳中,会将leader的commitIndex传递给follower,follower发现commitIndex更新了则也将commitIndex之前的日志都进行提交和应用到状态机中
4. zab流程
1. client连接follower或者leader,如果连接的是follower则,follower会把client的请求(写请求,读请求则自身就可以直接处理)转发到leader
2. leader接收到client的请求,将该请求转换成一个议案,写入到自己的日志中,会将该议案发送给所有的follower(这里只是单个发送)
3. follower接收到leader的议案请求之后,会将该议案写入到文件中(通常并没有立即刷新到磁盘),然后向leader回复OK
4. leader收到过半的OK回复之后,就认为可以提交了,leader会向所有的follower发送一个提交上述议案的请求,同时leader自己也会提交该议案,应用到自己的状态机中,完毕后回复客户端
5. follower在接收到leader传过来的提交议案请求之后,对该议案进行提交,应用到状态机中
5. 连续性日志:
  如果是连续性日志,则leader在分发给各个follower的时候,只需要记录每个follower目前已经同步的index即可,如Raft
  如果是非连续性日志,如ZooKeeper,则leader需要为每个follower单独保存一个队列,用于存放所有的改动,如ZooKeeper,一旦是队列就引入了一个问题即顺序性问题,即follower在和leader进行同步的时候,需要阻塞leader处理写请求,先将follower和leader之间的差异数据先放入队列,完成之后,解除阻塞,允许leader处理写请求,即允许往该队列中放入新的写请求,从而来保证顺序性
  • 正常情况下:
  Raft对请求先转换成entry,复制时,也是按照leader中log的顺序复制给follower的,对entry的提交是按index进行顺序提交的,是可以保证顺序的。
  ZooKeeper在提交议案的时候也是按顺序写入各个follower对应在leader中的队列,然后follower必然是按照顺序来接收到议案的,对于议案的过半提交也都是一个个来进行的。
  • 异常情况:follower挂掉又重启的过程:
  Raft:重启之后,由于leader的AppendEntries RPC调用,识别到leader,leader仍然会按照leader的log进行顺序复制,也不用关心在复制期间新的添加的日志,在下一次同步中自动会同步。
  ZooKeeper:重启之后,需要和当前leader数据之间进行差异的确定,同时期间又有新的请求到来,所以需要暂时获取leader数据的读锁,禁止此期间的数据更改,先将差异的数据先放入队列,差异确定完毕之后,还需要将leader中已提交的议案和未提交的议案也全部放入队列,即ZooKeeper的2个集合数据,读写锁。
 
  • 会不会有乱序的问题?
  Raft:Raft对于之前term的entry被过半复制暂不提交,只有当本term的数据提交了才能将之前term的数据一起提交,也是能保证顺序的
  ZooKeeper:ZooKeeper每次leader选举之后都会进行数据同步,不会有乱序问题
总结:2PC (两阶段提交) + 集群过半节点写机制

三、分区

  目前ZooKeeper和Raft都是过半即可,所以对于分区是容忍的。如5台机器,分区发生后分成2部分,一部分3台,另一部分2台,这2部分之间无法相互通信
  其中,含有3台的那部分,仍然可以凑成一个过半,仍然可以对外提供服务,但是它不允许有server再挂了,一旦再挂一台则就全部不可用了。
含有2台的那部分,则无法提供服务,即只要连接的是这2台机器,都无法执行相关请求。
 
参考: