Raft学习笔记

Published: by Creative Commons Licence

  • Tags:

Raft算法

通常用复制状态机来实现分布式环境的容错。只要大多数状态机的状态相同,那么即使少量状态机宕机也不会响应系统的可用性和一致性。

而复制状态机的实现原理一般都是复制日志的方式,每条日志对应一个命令,日志有序排放。

而保持日志一致就是一致性算法的工作。每个一致性模块接受客户端命令,并将命令加入到日志尾部。每个一致性模块还需要和其它一致性模块交流保证最终所有一致性模块以相同顺序包含所有的日志(就是最终日志相同了)。

Raft是一种用于管理复制日志的一致性算法,它与multi-paxos拥有相同的效果,且同样高效,但是比paxos更加易于理解。

Raft通过选举Leader来处理客户端命令。之后客户命令如果发送到其它模块,则都会被转发到Leader中进行处理。Leader全权负责客户命令是否成功,它会将日志发送给所有机器,如果得到了半数以上的成功回复,则会通知所有机器执行提交日志操作。

通过Leader的方式,Raft算法可以分解为解决三个子问题:

  • 选主:如果Leader失败了,必须有新的Leader被选举出来
  • 复制日志:Leader必须保证大部分节点的日志与自己的日志相同。
  • 安全性:如果某个节点提交了某个日志,那么所有其它节点的相同偏移量处,不能存在不同的命令。

Raft的节点器三种角色,leader、follower和candidate。通常,集群会有一个leader,其余节点器全部是follower。

Raft将时间切分为若干长度任意的任期,每个任期都用一个递增的整数来编号。每个任期开始时,所有的candidate会竞选成为leader,如果某个candidate拿到半数以上的选票,则在任期的之后时间中将作为leader。当然如果没有一个candidate拿到超过半数的选票,则这个任期就没有leader。Raft保证了所有的任期最多有一个candidate(当然可能一个都没有)。

不同的节点观察到的同一个任期的开始和结束时间是不同的。任期以逻辑时钟的方式运行,从而能帮助节点发现过期的信息。每个节点都保存了当前任期的编号,它随时间的流逝而递增。当两个节点交流的时候,会交换彼此任期的编号。如果当前节点的任期较小,则会将自己的任期更新为另一方较大的任期,并且将自己的角色更新为follower;如果对方的任期较小,则丢弃它们的信息。

Raft中节点的交流方式是通过RPC实现的,Raft需要节点支持两类RPC操作:

  • RequestVote:调用方要求获得被调用方的选票。
  • AppendEntries:调用方将自己的日志项复制到被调用方中去(如果日志项为空,则表示是用于实现心跳)。

如果在规定时间内没有得到被调用方的回复,则调用方会进行重试。

初始时,所有的Raft节点都是follower身份。如果某个节点长时间(这个时长称为election timeout)没有从leader和candidate处收到RPC请求,就会将自己的角色切换为candidate。Leader会周期性地向所有follower发送心跳(AppendEntries不带日志)来防止follower升级为candidate。一旦一个follower称为candidate,它会立即增大节点的任期编号,开启下一个任期。

candidate角色的节点器,会在任期开始的时候进行竞选,首先它会给自己投票,之后会调用其它节点的RequestVote方法,要求获得它们的选票。如果在同一个任期中,一个candidate获得了集群中超过半数的选票,则它在这个任期中将称为leader。一旦称为leader,它首先要向所有节点发送心跳,通知它们自己称为leader的信息,并让它们重新称为follower(避免下一个任期有人竞选)。

如果节点每次竞选失败就立即开始下一个任期,那么很可能会一直都没有任何一个节点能成功得到半数以上的选票。我们需要加入一个失败重试的一个等待时间,即竞选失败后需要等待一个固定周期(从150ms到300ms之间随机选择),这样就能避免candidate无休止的竞选。

当节点器成为leader之后,就开始接收并处理客户端的命令。leader在自己的日志中追加这条命令,之后并行地将这条日志通过AppendEntries发布到集群中的其它机器。当日志被复制到超过半数节点的日志中,leader会认为日志项提交成功,同时leader会执行提交成功的日志项中的命令,并通知客户端处理成功。如果有部分节点的RPC调用失败,则会之后重试。

日志信息中会包含如下信息:

  • 客户端命令
  • 任期编号
  • 日志偏移量

当leader提交一条日志的时候,之前所有没有提交的日志项也会被一并提交了(这里面可能包含了上一个leader没有提交的日志),同时被提交的日志项中的命令也会被一并执行。具体实现是leader会记录最后提交的日志的偏移,所以提交实际上就是修改这个偏移量而已。如果一个follower从leader那里学习到某个日志项被提交,它就会执行这个命令。

Raft会维护下面的性质(日志匹配性质的部分):

  • 如果两个日志中存在下标和任期相同的日志项,则两个日志项中的命令也相同。(任期和下标能完全确定日志项)
  • 如果两个日志中存在下标均为$k$且任期相同的日志项,则两个日志中下标不超过$k$的日志项中的任期和命令都相同。(如果某个日志项提交成功,则前面的所有日志项都会被提交)

第一个性质很容易证明,因为我们保证了一个任期中只有一个leader,而同一个leader发布的日志项,自然能保证下标能唯一确定命令。

第二个性质需要leader在调用AppendEntries的时候,将新日志项的前一项的任期和下标也带上。如果被调用的follower没有在自己的日志中找到匹配新日志项前一项的日志项,则会拒绝执行,之后leader需要负责将这个follower的日志更新成和自己相同的内容。根据归纳法可以证明,当AppendEntries被调用成功的时候,这个follower和leader前面的所有日志项都是一致的。如果半数以上的节点同意了新日志项的追加,则相当于前面的日志项存在于多于半数的节点中,因此也处于可以被提交的状态。

由于存在宕机或网络问题,并不能保证所有的follower和leader拥有相同的日志。可能存在follower拥有额外的日志或leader拥有额外的日志。Raft中会强制用leader的日志覆盖冲突的follower的日志。实现方法可以通过找到leader和follower的最后一次相同的日志项,之后删除follower后面的日志项,并将leader后面的日志项拷贝到follower中去。

但是上面所讨论的内容还存在一个问题,比如某个日志已经提交了,但是还没有同步到某个follower中,之后leader下线了,这个拥有较少日志项的follower被推举为新的leader,那之前提交的日志不就都作废了嘛。要解决这个问题,我们需要修改选举部分的内容,要求只有拥有之前所有任期提交的所有日志项的节点才能被选举为leader。其具体实现就是在调用RequestVote的时候需要带上自己的最后一项日志的任期和下标。被调用方如果发现自己的最后一项日志比调用方的新(按任期作为第一关键字,下标作为第二关键字进行比较),则会拒绝投票。由于candidate需要获得半数以上的投票,而其中至少会存在一个节点包含所有被提交的日志,因此这意味着成为leader的节点拥有所有之前任期中被提交的日志。被重新选举出来的leader无法确定未提交的日志项是否能被提交,raft中leader不会尝试立即提交这些日志项,而是在提交自己的任期中的日志项的时候会将之前的日志项一并提交。

除了Leader会下线外,candidate和follower也有可能会下线。这时候发送给下线节点的请求会失败,之后发送方会不定时时地进行重试。这里有一个特殊的情况就是AppendEntries在响应前follower下线,那么在上线后leader会重新RPC操作,这时候follower会检查日志项是否已经存在,如果存在则会直接返回成功,从而实现幂等性。

超时时间应该满足下面不等式:

\[broadcastTime\ll electionTimeout\ll MeanTimeBetweenFailure\]

即electionTimeout一定要远大于调用RPC花费的时间,而electionTimeout一定远小于两次节点下线的平均时间。

动态增加移除节点

Raft算法支持动态(无需下线)增加和移除节点。考虑原来的节点集合为old,新的节点集合为new。

为了保证一致性,raft算法使用了两阶段协议。

首先leader会处理一条配置指令(处理流程和之前处理客户端的相同),这个指令中包含old和new中的所有节点(这个配置叫做joint consensus)。

这里需要特别注意的是当遇到配置指令的时候,不需要等待日志提交,节点就应该直接更新配置(因此此时leader需要同时将配置发送给new中的节点)。new中的一些节点可能是没有日志的,因此leader会将自己的日志同步给它们。

通过处理这条指令,保证集群(new和old)中大多数节点包含joint consensus后。

配置成功切换为joint consensus后,leader会处理另外一条配置指令,将配置切换到new。

可以发现上面我们实际上仅处理了两个指令,速度会远远快于停机后,修改配置重启,对服务可用性的影响也几乎是0。

但是这里还需要解决三个问题。

第一个问题,就是新加入的节点和leader的日志可能相差非常多,这样就需要leader长时间进行同步,如果新加入的节点占集群大小比重很大,甚至可能导致leader短时间内不可用。解决方案就是在配置切换前,先让新加入的节点同步leader的日志,这段期间的这些处于学习阶段的新节点不进行投票(也不计入集群总数)。这样就不会影响集群的可用性了。

第二个问题,在切换到joint consensus配置之后,此时leader可能不包含在new中。之后发布切换到new的配置指令,切换的过程中,leader继续复制日志,但是在投票的时候不将自己计算在内。等到new配置切换成功后,leader就会将自己切换为follower,之后new中的机器可以选出新的leader。

第三个问题,被移除的节点可能会影响新的集群。这些被移除的节点没有了leader进行管理,会晋升为candidate,并进行竞选。这样会导致新集群中的leader被迫退位(任期不断自增)。解决方法就是如果一个节点如果依旧认为leader在线,则会无视收到的RequestVote请求。

日志压缩

由于节点会长时间运行,导致日志也会越来越大。这样势必最终会耗尽资源。下面提几种解决方案。

最简单的方式就是使用快照。可以注意到任意节点提交的日志是不会被修改的,而提交的日志恰好对应的就是当前的状态机状态。我们将状态机以快照的方式进行持久化,快照生成成功后,就可以将已经提交的日志删除。这样日志的大小就能保证不会太大。

参考资料