vlambda博客
学习文章列表

raft协议的一些要点

raft 协议是一致性协议中相对容易理解的一个实现,类似的还有zab,paxos等一致性算法。etcd是基于raft协议的,k8s依赖于etcd,下面介绍下raft协议的一些要点


1,Raft算法的节点数量问题

Raft协议中主节点心跳失效后follower成为candidate并且在n/2个节点投票成为主节点,在RAFT协议集群中如何确认n是多少?动态增加机器如何变化n,超时多久应该认为节点为n-1?n固定好是动态调整好?


领导人选举、日志复制、安全性的讨论都是基于Raft集群成员恒定不变的,然而在很多时候,集群的节点可能需要进行维护,或者是因为需要扩容,那么就难以避免的需要向Raft集群中添加和删除节点。最简单的方式就是停止整个集群,更改集群的静态配置,然后重新启动集群,但是这样就丧失了集群的可用性,往往是不可取的,所以Raft提供了两种在不停机的情况下,动态的更改集群成员的方式:


单节点成员变更:One Server ConfChange

多节点联合共识:Joint Consensus

从Cold迁移到Cnew的过程中,因为各个节点收到最新配置的实际不一样,那么肯能导致在同一任期下多个Leader同时存在。


为了解决上面的问题,在集群成员变更的时候需要作出一些限定。


单节点成员变更

所谓单节点成员变更,就是每次只想集群中添加或移除一个节点。比如说以前集群中存在三个节点,现在需要将集群拓展为五个节点,那么就需要一个一个节点的添加,而不是一次添加两个节点。


这个为什么安全呢?很容易枚举出所有情况,原有集群奇偶数节点情况下,分别添加和删除一个节点。在下图中可以看出,如果每次只增加和删除一个节点,那么Cold的Majority和Cnew的Majority之间一定存在交集,也就说是在同一个Term中,Cold和Cnew中交集的那一个节点只会进行一次投票,要么投票给Cold,要么投票给Cnew,这样就避免了同一Term下出现两个Leader。


变更的流程如下:


Leader在收到请求以后,回向日志中追加一条ConfChange的日志,其中包含了Cnew,后续这些日志会随着AppendEntries的RPC同步所有的Follower节点中

当ConfChange的日志被添加到日志中是立即生效(注意:不是等到提交以后才生效)

当ConfChange的日志被复制到Cnew的Majority服务器上时,那么就可以对日志进行提交了

以上就是整个单节点的变更流程,在日志被提交以后,那么就可以:


马上响应客户端,变更已经完成

如果变更过程中移除了服务器,那么服务器可以关机了

可以开始下一轮的成员变更了,注意在上一次变更没有结束之前,是不允许开始下一次变更的

可用性

可用性问题

在我们向集群添加或者删除一个节点以后,可能会导致服务的不可用,比如向一个有三个节点的集群中添加一个干净的,没有任何日志的新节点,在添加节点以后,原集群中的一个Follower宕机了,那么此时集群中还有三个节点可用,满足Majority,但是因为其中新加入的节点是干净的,没有任何日志的节点,需要花时间追赶最新的日志,所以在新节点追赶日志期间,整个服务是不可用的。


2,客户端交互

包括客户端如何发现领导人和 Raft 是如何支持线性化语义的


我们 Raft 的目标是要实现线性化语义(每一次操作立即执行,只执行一次,在他调用和收到回复之间)。但是,如上述,Raft 是可以执行同一条命令多次的:例如,如果领导人在提交了这条日志之后,但是在响应客户端之前崩溃了,那么客户端会和新的领导人重试这条指令,导致这条命令就被再次执行了。解决方案就是客户端对于每一条指令都赋予一个唯一的序列号。然后,状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令,它的序列号已经被执行了,那么就立即返回结果,而不重新执行指令。


3,领导人选举

Raft中的节点有三种状态:


领导人状态:Leader

跟随者状态:Follower

候选人状态:Candidate

每一个节点都是一个状态机,Raft会根据当前的心跳,任期等状态来进行状态的迁移转化


首先,在Raft节点启动的时候,所有任务都是Follower状态, 因为此时没有Leader,所有Follower都在固定的超时时间内都收不到来自Leader的心跳,从而变成了Candidate状态,开始选举Leader


当节点处于Candidate状态的时候,会并发的向所有的节点发出请求投票请求RequestVote(后面章节会向详细介绍),在Candidate状态下,节点可能会发生三种状态的迁移变化:


开始下一轮新的选举:发出的投票请求在固定时间内没有收到其他节点的响应,或者是收到响应(或者同意投票)的节点数量没有达到 N/2+1,那么选取超时,进入下一轮选举

选举成功,成为新的Leader:如果选举过程中收到大于N/2+1数量的节点的投票,那么选举成功,当前的节点成为新的Leader

成为Follower:如果选举过程中收到来及其他节点的Leader心跳,或者是请求投票响应的Term大于当前的节点Term,那么说明有新任期的Leader

如果节点选举成功,成为了Leader,那么Leader将会在固定周期内发送心跳到所有的节点,但是如果心跳请求收到的响应的Term大于当前节点的Term,那么当前节点的就会成为Follower。比如Leader节点的网络不稳定,掉线了一段时间,网络恢复的时候,肯定有其他节点被选为了新的Leader,但是当前节点在掉线的时候并没有发现其他节点选为Leader,仍然发送心跳给其他节点,其他节点就会把当前的新的Term响应给已经过时的Leader,从而转变成Follower


4,日志复制

领导人必须从客户端接收日志然后复制到集群中的其他节点,并且强制要求其他节点的日志保持和自己相同。


复制状态机通常都是基于复制日志实现的,每一个服务器存储一个包含一系列指令的日志,并且按照日志的顺序进行执行。


客户端请求服务器,请求的信息就是一系列的指明,比如PUT KEY VALUE

服务器在收到请求以后,将操作指令同步到所有的服务器中

服务器收到同步的指令以后,就将指令应用到状态机中

最后响应客户端操作成功


5,节点超时机制

每个节点都有150~300ms的随机超时,如果收到leader的心跳包,会重新计时,否则将自己状态设置为candidate,发起投票。由于时间是随机的,减少了同时发起投票的可能性。follower是通过节点超时机制知道leader存活的,否则可能认为leader已经死亡。