RAFT

RAFT

写在前面

RAFT是比PAXOS更容易理解的一致性算法,即使容易理解,依然细节很多。建议有英语基础的初学者还是要看论文。本篇文章主要列举RAFT中的异常场景,对比论文看可以达到更好的学习效果。

选举

选举阶段,主要解决两个问题:

  1. 每个节点都把票投给了自己。
  2. leader宕机。

每个节点都把选票投给自己

解决方案是随机的election timeout。election timeout用来控制一个follower合适变成candidate。假定三个节点的情况:

由于随机election timeout是随机值,假定A先成为candidate:

此时A开始发起term 1的投票,此时A成为leader:

平分投票的情况,此时节点C和D同时成为candidate并发起投票:

此时A和B分别投票给D和C。

产生了平分选票的情况。即此term没有leader产生,此时candidtate会等待下一个election timeout周期,然后开始继续投票。

注意,当follower收到选票后或者leader的append log消息时,需要重置自己的election timeout。这个机制让我们可以更快的选出一个leader。

leader宕机

leader宕机时,由于没有append log消息来重置follower的election timeout,所以follower会成为candidate,并且开始新一轮选举。具体过程与第一个问题一致,不多赘述。

日志复制

这个过程会存在多种异常情况:

  1. follower存在leader不存在的日志。
  2. follower缺失了leader的日志。
  3. 提交之前任期内的日志条目。
  4. 脑裂,出现多主问题。

下文我们以[index, term]的方式表示一条log。

具体的follower接受到append log的逻辑如下,详细的可以看论文:

  1. 如果term < currentTerm就返回false
  2. 如果日志在prevLogIndex位置处的日志条目的任期号和prevLogTerm不匹配,则返回false
  3. 如果已经存在的日志条目和新的产生冲突(索引值相同但是任期号不同),删除这一条和之后所有的附加日志中尚未存在的任何新条目。
  4. 如果leaderCommit > commitIndex,令commitIndex等于leaderCommit新日志条目索引值中较小的一个

follower存在leader不存在的日志

此时集群的状态如下:

此时leader的最新一条为[10, 6]。我们挑选follower e和follower f看看RAFT如何处理这种情况。

对于follower e,log [6, 4][7, 4]与leader的日志不匹配。
对于follower f,log [4, 2]之后的日志全都不匹配。

RAFT会记录每个follower的位点,这个位点用来记录需要发送给他的下一个日志条目的索引值,初始化为leader的最后索引值+1,这个例子中,leader最新的位点为10,则follower的复制位点被初始化为11。

follower e:

RAFT开始向follower e发送消息,RAFT复制方式是从后向前复制,此时复制[10, 6](以每次复制一条看更容易理解)给follower e,由于follower在index=10位置不存在消息,返回false。此时leader会继续向前尝试,知道找到匹配的日志。当leader尝试将[7, 5]发送给follower e的时候,e会发现index=7位置的term与leader不符合,此时删除index=7和之后所有的日志。

按照这个规则,follower e会删除[6, 4][7, 4]两条日志,当leader继续发送[5, 4]的时候,follower e返回true。此时leader记录follower e的复制位点为index=6,后续将[6, 5]和之后的log一条条复制给e。

了解了follower e的思路之后,可以对照论文的规则即可推断出follower f的复制逻辑。

follower缺失了leader的日志

选取follower b,follower b此时缺失了[5, 4]和之后所有的日志。此时leader会按照上述的逻辑找到index=5,并尝试把之后所有的日志复制给follower b。

提交之前任期内的日志条目

RAFT规定,不能删除已经提交到状态机的条目,但是按照我们之前的逻辑不能规避这个问题,所以RAFT规定,leader只能提交当前任期内的log到状态机。具体看看:

  • 图(a)中,S1是leader,部分的复制了index=2的日志条目,此时[2, 2]未被commit。
  • 图(b)中,S1宕机,然后S5在任期3里通过S3、S4和自己的选票赢得选举,然后从客户端接收了一条不一样的日志条目放在了索引2处。
  • 图(c)中,S5又崩溃了,S1重新启动,选举成功,开始复制日志。在这时,来自任期2的那条日志已经被复制到了集群中的大多数机器上。按照之前的规则,2已经被leader commit(满足大多数)。
  • 图(d)中,S1又宕机了,此时S5可以成为leader,因为S5满足成为主的条件,term=3 > 2,且最新的日志index=2,比大多数节点(如S2/S3/S4)的日志都新。此时,按照复制规则,S5会把自己的[2, 3]覆盖到其他机器,并且删除已经commit的[2, 2]这条log。这是致命的错误。

解决方式就是我们说过的,leader只能提交任期内的日志条目。

继续以上述的场景为例,假定此时整个集群的状态进行到图(c)。由于我们规定leader只能提交任期内的日志条目,此时term=4,所以即使[2, 2]已经被复制到大多数的follower上,但是当前term=4,所以leader不能提交index=2的这条log,此时commitIndex仍然等于1。

此时存在两个情况,第一种就是S1挂掉,第二种就是S1并没有挂掉。

  1. S1并没有挂掉,则S1会继续给其他follower复制log,当走到图(e)时,[3, 4]这条日志被大多数收到,且term=4符合leader只能提交任期内的日志条目这个要求,此时commitIndex=3,提交index=3的这条log到状态机。那么如果提交完了S1挂了呢?此时S5不会成为主,由于S5最多只能收到S4和自己的投票,不满足大多数。新的leader只会在S2和S3中产生。
  2. S1挂掉,假定S5成为leader,此时假定S5一直存活,那么整个集群的状态会继续来到图(d),注意!由于此时[2, 2]未被交道状态机,所以即使S5的[2, 3]这条log覆盖到S1、S2和S3的[2, 2],也不会产生任何问题,因为[2, 2]的log未被提交。

考虑更极端的情况,假定整个集群状态在在图(e),S1刚刚提交了[3, 4](当然[2, 2]也被一起提交了),但是还没来得及通知S2和S3提交[3, 4]就挂了,此时仍然不会导致删除已经提交的log。因为即使S1挂了,S5和S4也不会成为主,由于S2和S3的日志都比他们新,新的leader只会出现在S2和S3中。

脑裂,出现多主问题

RAFT保证即使出现了网络隔离,依然能够保证数据强一致性。

假定此时集群状态如下:

此时节点B和A被隔离,B仍然是主:

C、D和E由于超时没有收到leader的心跳,重新选主,此时假定C成为主,term+1后为2(这里仍然保证了每个term只有1个leader):

client分别发送SET 8和SET 3到两个leader上。由于B和A独立的分区不满足大多数,所以不能提交。而SET 8落到了上半区中,此时上半区满足大多数,可以提交:

后续当A和B的隔离被解除时,C的term=2高于B和A的1,此时B和A直接退化成follower,并且会把SET 8复制到自己的日志中,保证整个集群的状态一致。

集群拓扑变化

我们用CO表示旧集群配置,新集群配置用CN表示。CO和CN共存我们用CO并CN表示。具体集群变更流程如下:

  1. 当集群成员配置改变时,leader收到重配置命令从CO切成CN。
  2. leader在本地生成一条新的log,其内容是CO并CN,代表当前时刻新旧拓扑配置共存,写入本地日志,同时将该log推送至其他follower。
  3. follower收到log后更新本地日志,并且此时就以该配置作为自己了解的全局拓扑结构。
  4. 多数follower确认了C0并CN这条日志的时候,leader就commit这条log。
  5. 接下来leader生成一条新的log,其内容是全新的配置CN,同样将该log写入本地,同时推送到follower。
  6. follower收到新的配置CN后,将其写入日志,并且从此刻起,就以新的配置作为系统拓扑,并且如果发现自己不在Cnew这个配置中会自动退出。
  7. leader收到多数follower的确认消息以后,向客户端发起命令执行成功的消息。

异常分析:

  1. 如果leader的CO并CN尚未推送到follower,leader就挂了,此时选出的新的leader并不包含这条日志,此时新的leader依然使用CO作为全局拓扑配置。
  2. 如果leader的CO并CN推送到大部分的follower后就挂了,此时选出的新的leader可能是CO也可能是CN中的某个follower。
  3. 如果leader在推送CN配置的过程中挂了,那么和2一样,新选出来的leader可能是CO也可能是CN中的某一个,那么此时客户端继续执行一次改变配置的命令即可。
  4. 如果大多数的follower确认了CN这个消息后,那么接下来即使leader挂了,新选出来的leader也肯定是位于CN这个配置中的。

另外,为什么不能直接从CO切换成CN呢?因为可能产生多主。

解决方案RAFT论文中也提到了,有两种,比较推荐第一种:

  1. 每次只允许增加或移除一个节点。
  2. join consensus。(两阶段提交)

除了成员变更的实现,成员变更还带来一系列问题:

  1. 新节点如何追赶。
  2. 删除的节点是当前leader。
  3. 为什么要有PRE-VOTE。
  4. 被移除的节点破坏当前集群的选举。

多主

假设拓扑关系如下,S1为leader:

此时变更了系统配置,将集群范围扩大为5个,新增了S4和S5两个节点,这个消息被分别推送至S1、S2和S3,但是假如只有S3收到了消息并处理,S1和S2尚未得到该消息:

这时在S1和S2的眼里,拓扑依然是[S1, S2, S3],而在S3的眼里拓扑则变成了[S1, S2, S3, S4, S5]。假如此时由于某种原因触发了一次新的选主,S2和S3分别发起选主的请求:

最终,候选者S2获得了S1和S2自己的投票,那么在它眼里,它就变成了leader。而S3获得了S4、S5和S3自己的投票,在它眼里自己也变成了leader。

这张图很好的说明了问题的关键,即在红色箭头所示的时间点,出现了两个多数派:

  1. Server1、2组成的,以CO为拓扑关系的多数派,此时Server1和Server2可以根据CO的配置选择出来一个leader。
  2. Server3、4、5组成的,以CN为拓扑关系的多数派,此时Server3、4、5可以根据CN的配置选择出来一个leader。

每次只允许增加或移除一个节点

具体步骤:

  1. 由于每次增减一个节点方式无论如何CO和CN都会相交,所以RAFT采用了直接提交一个特殊的replicated LogEntry的方式来进行集群关系变更。
  2. 跟普通的LogEntry提交的不同点,该LogEntry不需要commit就生效,只需要append到log中即可。(“The New configuration takes effect on each server as soon as it is added to the server’s log”)。
  3. 后一轮MemberShip Change的开始必须在前一轮MemberShip Change Commit之后进行,以避免出现多个leader的问题。

这个解决方案是最常用的,实现简单。解决方案的核心为增删一个节点的时候,新旧配置中的大多数必定有部分重叠

每次只增删一个节点

我们以三个节点变化到四个节点为例。

  • 图(a)中,三个节点分别是S1、S2和S3,此时S1为主。
  • 图(b)中,新增节点S4,S4由于是新节点,所以S4是知道集群拓扑全貌的。作为leader的S1收到请求,准备开始推送,此时按照上述规则,S1的该条config log还未被commit,但是也已经知道集群拓扑全貌了。
  • 图(c)中,S1宕机,此时S4仍然以S1、S2、S3和S4作为集群拓扑全貌,但是S2和S3依然是旧配置。此时,S2、S3和S4都可能成为leader。其中S2和S3由于不知道S4的存在,S2只要收到自己和S3的投票,就会成为leader。S4主动发起投票的情况下,会收到S2、S3和自己的投票,所以也可能成为主。
  • 图(d)中,此时假定S2成为主,S1恢复,此时S2不知道S4的存在,所以不会给他发送心跳,此时S4被孤立。并且此时,这次membership变更会被认为失败,因为只有当大多数commit了config log,leader才会响应客户端,而当前的场景中,append S4这条config log最终会被S2上的日志给删除掉,此时集群恢复图(a)的旧配置的情况(仅仅相当于leader变成了S2)。
  • 假定图(b)中,S1没有宕机,并且把消息赋值给了S2,此时就满足了集群中大多数已经收到消息,可以commit并且返回给client表示此次membership变更成功。但是提交之后S1宕机,来到图(e)。
  • 图(e)中,S3不会成为leader,因为S2和S4有比S2更新的日志(append S4这条config log也是一条log,但是S3没有这条log,所以S3的index一定小于S2和S4),此时leader只可能在S2和S4中选出。
  • 假定S4选举成为新leader,来到图(f)。后面S4会把append S4这条config log复制给S3,此时所有集群的拓扑关系均为最新的配置。

这里引入另外一个问题,即图(d)中,S4被孤立,此时S2还不知道S4的存在,当然也不会给S4发送心跳,此时S4会超时并且成为candidate开始发起新一轮投票,此时如何处理这种情况?这个我们后面会继续讨论。先看可能出现的问题。

为什么后一轮membership change必须在前一轮membership change完成之后(完成即commit之后)进行

这个图很好的说明了这个问题,如果这样操作此时可能出现多主问题。

为什么Single MemberShip Change LogEntry只需要append持久化到log(而不需要 commit)就可以应用

如图所示:leader S1接收到集群变更请求将集群状态从[S1、S2、S3、S4]变更为[S2、S3、S4],提交到所有节点之后commit之后,返回客户端集群状态变更完成(如图a),S1退出(如图b);S1 退出之后,S1、S2、S3由于没有接收到leader S1的心跳,导致进行选举,但是不幸的是S4故障退出。假设这个时候S2、S3由于Single MemberShip Change LogEntry没有commit还是以[S1、S2、S3、S4]作为集群状态,那么集群没法继续工作。但是实质上在图(b)中S1返回客户端集群状态变更请求完成之后,实质上是认为可独立进入正常状态。

join consensus

这是一种类似两阶段提交的思想:

这种实现比较复杂,我们需要保证我们的CO并CN被提交到了CO中的大部分和CN中的大部分。温习一下脑裂现象并阐述一下join consensus如何解决这个问题。这里假定我们的新旧配置如下图所示:

注意这个场景中,我们就配置是X2、Y1和Z2,而新配置是X1、Y1和Z2,与我们之前提到的单纯的新增节点不同,我们这里的场景是变更节点(X2替换为X1)。

看看为什么会产生脑裂现象,第一张图为初始状态,C1表示旧配置[X2, Y1, Z2],C2表示新配置[X1, Y1, Z2]

推送C2到leader:

Y1立刻切换到了C2配置,此时认为集群中存在[X1, Y1, Z2],Y1将这条日志推送给X1,所以X1也更新配置为最新(图中的C1和C2表示两条配置变更日志):

此时就形成了两个多数派,分别是X1、Y1组成的新配置下的多数派和X2、Z2组成的旧配置下的多数派,此时两个多数派可以同时开始工作(图中的x表示X1和Y1组成的多数派收到了一条log,而y表示X2和Z2组成的多数派收到了另外一条log):

如何解决这个问题,上面也已经说过了,我们需要先推送CO并CN的配置(CO=C1,CN=C2)到新集群中的多数派和旧集群的多数派,而CO并CN的配置如下所示:

拥有CO并CN的机器做任何决定,需要CO和CN下的大多数都同意才可以,比如提交。按照这个规定,Y1和X1就不能成为大多数,当然就不能commit log。

我们继续推演下去:

此时如果产生了分区,即Y1和X1单独一个分区,X2和Z2单独一个分区(这样分区导致CO并CN永远无法推送到X2和Y2上面,对于客户端来说,这次membership变更会被认为失败,需要再次进行成员变更)。此时X2和Z2的分区可以独立做决定(比如选主和commit log)。而X1和Y1形成的分区,再假定两种情况:

  1. 如果Y1这个leader宕机,重新启动后,由于持有CO并CN这个配置,所以Y1和X1都无法通过竞选成为leader(无法得到CO的大多数同意)。而X2和Z2可以,此时X2和Z2由于进行了一次竞选,所以term一定大于Y1的term,当网络恢复的时候,Y1会自动成为follower。
  2. 如果Y1这个leader不宕机,也没什么问题,因为Y1虽然是leader,但是不能commit log。同样的,当网络恢复后,由于X2和Z2成为leader后的term一定大于Y1,所以Y1和新的X1在网络恢复后都会成为follower。

而一旦CO并CN的配置被推送到了CO的大多数和CN的大多数的时候,就可以给客户端返回membership变更成功了,此时不管怎么分区,我们都可以保证整个集群正常运行,具体的逻辑这里不再进行推演。

新节点如何追赶

这两张图展示了为什么追赶会引发可用性问题。

  • 图(a)中,新增S4已经成功,但是S3宕机。此时任何一条消息需要大多数(3个)节点收到消息才可以commit,由于S4的日志是空的,追赶需要很长时间,此时整个集群出在不可用状态,因为所有的新日志的commit都会等待非常久。
  • 图(b)中,新增S4-S6三个节点,同样的,由于一条消息需要大多数(4个)节点收到消息才可以commit,由于达到大多数一定包含S4-S6中的一台,所以会出现与图(a)一样的问题。

解决问题的方式这里以ETCD为例,ETCD引入了learner角色,新加入的节点设置为learner状态,该状态的节点不计在majority,也就不参与投票和commit,当learner追上集群的进度时,提升为正常的节点,完成config change

RAFT论文中也提到了多轮复制的方案:

这里不具体展开,可以阅读论文获取更多细节。

删除的节点是当前leader

有可能需要移除的节点是leader,按照RAFT论文的做法会比较奇怪,leader需要管理不包含自己的集群,直到提交之后再退出。论文中提到可以通过leadership transfer将leadership转移到其他节点,然后再移除原先的leader。leadership transfer还有其他的用途,比如leader所在机器的负载比较高,要转移到低负载机器上;leader要改变机房实现就近等,同时还能降低选举的影响。

leadership transfer的流程

  1. leader 停止接收新的请求。
  2. 通过log replication使leader和transferee的log相同,确保transferee能够赢得选举。
  3. leader发送消息给transferee,让transferee立即发起选举。leader收到transferee的消息会退出。

仍有几个问题需要处理:

  1. transferee挂了: 当leadership transferelection timeout时间内未完成,则终止并恢复接收客户端请求。
  2. transferee有大概率成为下一个leader,若失败,再次发起leader transfer即可。
  3. check quorum会使节点忽略RequestVote,需要强制投票。

为什么要有PRE-VOTE

假定此时节点S1、S2和S3,S2是leader,S1被隔绝。此时S1由于收不到心跳,会不断成为candidate,增加term并且发起投票。虽然不能成为主(网络隔绝,只能收到自己的一票),但是加入term增大到一定程度的时候(比S2更大),网络恢复,那么S1就会赢得选举。

PRE-VOTE

partitioned节点的log一般会落后于其他节点,不会收到majority的投票,基于此,增加了PRE-VOTE阶段:

  • 只有收到majority的投票,才会增加term进行正常的选举过程。
  • 若PRE-VOTE失败,当网络恢复后,该节点收到leader的消息重新成为follower,避免了disrupt集群。

PRE-VOTE只解决了log落后的节点不会自增term 导致集群disrupt,但是仍有可能节点log没有落后但仍发起PRE-VOTE。下一个小节会继续讨论。

被移除的节点破坏当前集群的选举

当我们移除S1的时候,S4是当前新集群的leader,此时S4会断开与S1的心跳(已经创建了CN配置),此时S1、S2和S3还没有收到新的配置,此时会导致S1自增版本号开始进行选举(可以收到S1、S2和S3的选票)。

PRE-VOTE也并不能解决上述问题,同样的还有下面这个场景:

  1. 有S1、S2、S3三个节点,S1为leader且三个节点log相同。
  2. 发生网络分区,其中S1和S3互通,S2和S3互通,S1和S2不通。
  3. S2发起PRE-VOTE,收到S3投票后,进行正常election,成为新的leader。

解决方式是通过Leader lease。核心思想是:节点不应该在集群正常工作的情况下给其他节点投票。

当节点在最小election timeout时间内接收到了leader的消息,就不会改变自己的term,也不会给其他节点投票。(“if a server receives a RequestVote request within the minimum election timeout of hearing from a current leader, it does not update its term or grant its vote.”)

论文中也提到了,这个改变与leadership transfer存在冲突,因为leadership transfer的第三步是:

leader发送消息给transferee,让transferee立即发起选举。leader收到transferee的消息会退出。,需要注意的是,此时leader仍然存在,如果leader lease机制存在,会导致transferee发出的投票被其他follower拒绝掉,此时我们需要增加一个标志位,表示这次发起的投票可以强制移除leader。

leader lease是从follower视角确保leader是合法的。

这里又出现了一个新的问题,leader如何确保自己合法?这需要另外一个机制,即check quorum机制。看看如果只有leader lease会出现什么问题:

只有leaderlease

  • 图(a)其中共五个节点,S1位leader,S1与S2通,S2、S3和S3互相通,S5被隔离,此时S1是leader。
  • 图(b)中,由于S3和S4都收不到leader的心跳,两者会成为candidate并且开始投票,假定此时S4成为candidate。它只能收到自己喝S3的投票,因为S2与S1互通,一直有来自leader的消息,所以触发leader lease机制,S2会认为现在leader是正常的而拒绝掉S4的投票。此时S3和S4永远无法达到大多数,导致这两个节点认为整个集群是不可用的。

这个情况并不合理,S2、S3和S4都是互通的,其实我们的集群中是有一个大多数的,并且我们认为其实是可以进行服务的,只要leader在S2、S3和S4之间选出来就可以了。这里我们引入一个新的机制,即CHECK-QUORUM。

leader每隔election timeout检查其他节点的活跃情况,若少于majority活跃,则自动step down为 follower

即leader隔一段时间就去检查自己是不是属于大多数中,如果不是,就自动退出成为follower。在我们上面的图中,由于S1只与S2相连,不满足集群中的大多数,所以S1自动退化成为follower。然后当进行到图(b)中时,S4成为candidate,就可以收到S2(S1已经退化成follower了,leader lease对于S2不再生效)、S3和自己的投票成为leader,整个集群又可以正确的工作了。

写在后面

RAFT的论文被熟知的是这一篇,但是RAFT的作者的博士毕业论文对RAFT做了更详细的阐述。要在分布式场景下达到强一致性是非常困难的,即使是相对容易理解的RAFT依然有一定的门槛。

本文更多的笔墨都花在成员变更这个模块,这个模块也许是RAFT中最复杂的模块,后面还有关于快照和日志压缩的相关部分,这里就不再阐述了。