etcd-3-2-7源码解析-Raft实现(臆想篇)

Posted by AlstonWilliams on February 17, 2019

这篇文章实际上并不是我在阅读etcd中跟Raft相关的部分之后得出的,而是我在读了ZooKeeper中Zab的实现以及重新读«IN Search of an Understandable Consensus Algorithm(Extended Version)»这篇论文而得到的.虽然可能跟实际的实现有一点差距,但是应该不大.后面我会读etcd源码中的Raft部分,然后再写一篇文章介绍.

文末的参考资料中,有一个动画版的对Raft算法的解析,各位可以看一下.当然,很多细节方面的内容,它并没有说的很明确.

Raft算法中,各个Server具有的属性

  • currentTerm:这个是Server当前的term.如果Server处于Follower状态,则其表示的是Server认为的leader的当前的term.
  • votedFor:表示Server为谁投过票,也就是Server认为谁更有资格成为Leader.在一个term中,只能给一个Server投票.
  • log[]:log entries.每个Log Entry都包含状态机要执行的命令,以及其term.
  • commitIndex:已知的要被提交的Log的最大的index
  • lastApplied:已应用Log的index

Leader还有两个特殊的属性:

  • nextIndex[]:代表下次要发送给各个Server的log entry.开始时是Leader的最后一个log的index + 1
  • matchIndex[]:代表Leader的log和各个Server的log匹配的位置

Raft算法的三个阶段

跟Zab算法一样,可以将Raft算法分成三个阶段,分别是Election,Synchronization,Broadcast

Election阶段

在这个阶段,顾名思义,就是选择一个Leader.

那么什么时候需要选择一个Leader呢?有这么三种情况:

  • 当集群刚开始启动时
  • 当一台新的Server想要加入到集群时
  • 当一台Server经过分区或者故障后,想要重新加入集群时

下面我们会拿第一种情况,即集群刚开始启动时举例说明:

  • Server会先进入到Follower状态,并设置一个超时时间
  • 如果过了超时时间,那么Server进入到Candidate状态
    • 增加Server的currentTerm
    • 为它自己投票
    • 设置选举超时时间
    • 给集群中的其他机器发送RequestVote RPC
    • 如果从半数以上的Servers中收到Ok,则进入到Leader状态
    • 如果收到来自Leader的AppendEntries RPC,则进入到Follower状态
    • 如果收到其他Server的RequestVote RPC,并且当前Server的voteFor为null或者那台Server,并且那台Server的log比这台Server的log更新,则为那台Server投票
    • 如果收到的RequestVote RPC的响应中,term比当前Server的term大,则重置当前Server的term为来自RequestVote RPC的term,并进入到Follower状态
    • 如果在过了选举超时时间之后,还未确认自己就是Leader或者来自Leader的Append Entries RPC,则将当前Server的term+1并开始新的一轮选举
  • 如果在超时时间内收到了来自Candidate的RequestVote RPC:
    • 如果RequestVote RPC中的term比当前Server的更大,那么更新当前Server的term.同时,判断一下voteFor是否为null或者发送RequestVote RPC的Server,以及Candidate的log是否比当前Server的更新,如果是,那么就返回true和当前Server的term.同时,在当前term中,不能再为其他具有相同term的Server投票.
    • 如果RequestVote RPC中的term没有当前Server的大,那么返回false以及当前的term
  • 如果在超时时间内收到了来自Leader的AppendEntries RPC:
    • 如果leader的term比当前Server的term大,那么就重置当前Server的term
    • 如果leader的term比当前Server的term小,那么返回false以及当前Server的term
    • 如果当前Server的log和Leader的log在prevLogIndex处的日志冲突,删除当前Server对应位置以及往后位置的log,并返回false
    • 如果Leader包含当前Server没有的log,那么就将这些Log追加到当前Server的log的末尾
    • 如果leaderCommit > commitIndex,则更新commitIndex为min(leaderCommit,当前Server的最后一个log entry的位置)

Synchronization阶段

在一个Server成为Leader之后,它需要将其日志同步给Follower.

Leader会做下面的操作,将其log同步给Follower:

  • 向Follower发送AppendEntries RPC,其中prevLogIndex为其最后一条log的index,prevLogTerm为其最后一条log的term
  • 如果收到的AppendEntries RPC的响应为true,则更新nextIndex[]matchIndex
  • 如果收到的AppendEntries RPC的响应为false并且其中的term比Leader当前的term大,那么更新Leader的term并进入到Follower状态
  • 否则的话,如果只是响应为false,那么就减小nextIndex[]的值并且重试

Broadcast阶段

在这一阶段,Leader将接收客户端请求并应用到状态机.

Leader会这样做:

  • 接收来自Client的请求,将其封装成一个log,保存到log[],并且将其发送给Follower
  • Follower在收到AppendEntries RPC之后,会将其添加到本地log[]并应用到状态机,然后给Leader回复Ok.
  • Leader在收到半数以上的Follower的OK之后,就将这个log应用到本地状态机,更新commitIndex以及lastApplied,同时给Client回复OK.

AppendEntries RPC和RequestVote RPC

上面我们反复提到这两种RPC,却并没有深入介绍.这里介绍一下这两种RPC的请求数据以及响应数据,关于Leader和Follower以及Candidate对于这两种RPC会作何反应,上面已经介绍过.

AppendEntries RPC

请求数据:

  • term:leader的term
  • leaderId:有了这个leaderId,follower才能接收到客户端请求时,将其重定向到leader
  • prevLogIndex:要发送给follower的log entry的index
  • prevLogTerm:要发送给follower的log entry的term
  • entries[]:要存储的log entries

响应数据:

  • term:Follower或Candidate的当前的term
  • success:是否更新成功,当其为true时,表明Follower已经成功的将log entries保存了下来

RequestVote RPC

请求数据:

  • term:Candidate的term
  • candidateId:Candidate的Id
  • lastLogIndex:Candidate的最后一个log entry的index
  • lastLogTerm:Candidate的最后一个log entry的term

响应数据:

  • term:接受者当前的term
  • voteGranted:接受者是否为这个Candidate投票.如果为true,则表明此接受者愿意为这个Candidate投票.

实例

上面说了那么多,都是比较理论的东西,下面我们来讨论几个场景,以及一些难题.

当一个集群刚刚启动时,此时集群中的Server均处于Follower状态.此时它们都接收不到来自Leader的Append Entries RPC,因为此时集群中压根就没有Leader.

Server在初始化时,除了会初始化为Follower状态,还会为其设置一个固定的超时时间.

假设集群中有三台Server,分别是Server A,Server B以及Server C,它们的超时时间均为300ms.

在这300ms过去后,Server A,B和C均进入到Candidate状态,此时Server A,B和C会获得一个随机分配的选举超时时间,假设这三台Server获得的超时时间为50ms,100ms,150ms.

Server A, B和C在第一轮选举中,分别为自己投票.由于在每个term中,一台Server只能投一次票,所以在第一轮选举中,无Server成为Leader.

50ms过去以后,Server A会将它的term+1,并通知其他Server为自己投票,Server B和C收到Server A的RequestVote RPC以后,由于开始时他们的term都相同,此时RequestVote RPC中的term更大,所以Server B和C会更新自己的term为从RequestVote RPC中收到的term,然后比较一下Server A中的log是否比自己的新,如果是,则为Server A投票.

那么Server A的log在满足什么条件下比其他Server的log更新呢?

  • ①Server A中的log的term比其他Server的term更大
  • ②Server A中log的term跟其他Server的log的term相同,但是Server A中log的index更大,即Server A的log更长

在这两种情况下,我们认为Server A的log比其他Server的log更新.

这两条还可以保证选出的leader一定包含全部已提交的log.

为什么呢?

因为当一台Server收到半数以上的Server的赞同时,才会被选为leader,而leader提交一个log时,也需要半数以上Server的同意.所以它们之间至少有一台Server相交.

注意已提交Log和已应用的Log的区别.

当Leader收到来自客户端的请求时,它会将其添加到本地log[]中,然后发送给全部Followers,当收到半数以上的Followers回复Ok的时候,它会提交这个log entry,这时Log称为已提交Log,然后,它会回复给客户端一个Ok,同时,将这个log entry应用到本地状态机,然后在下次给Follower发送AppendEntries RPC的时候,将其commitIndex发送给Followers,Follower在收到AppendEntries RPC的时候,会将commitIndex位置上及之前位置上的log entry应用到本地状态机.此时log entry被称为已应用Log

我们可以看到,已应用Log就是已经成功应用到集群的Log,而已提交Log则是Leader收到半数以上Followers的回复但是并没有被应用到集群上的Log.

Leader并不会记录是否多半的Followers已成功应用此Log,实际上,这也完全没有意义,因为已经告诉Client成功了.所以,如果一个log已提交,它就必须应用到Followers.

所以,如果leader崩溃了,新选出的Leader必须将这些已提交log应用到集群中.

那么新的leader要在何时应用上一个leader所在的term的log呢?

最简单也最容易想到的就是,在新的leader选择出来之后,计算上个term留下的log在集群中的数量,如果过半则认为它已经被应用到集群了呗.

但是在Raft论文中,专门强调了这样做是不行的,有数据被覆盖的风险.

在解释这一点之前,我们需要明白,Raft必须满足下面的条件:

  • 已经给Client请求成功的响应的log,必须被应用到状态机中.

记住这一点,我们再来解释为何不能通过计算上个term留下的log在集群中的数量来判断它是否已经应用.

这幅图是Raft论文中用来解释这样做不行的原因的例子.

在这幅图中,每个方框代表一个Log Entry,方框中的数字代表Log Entry的term,最上面的数字表示的是Log Entry的index.

在(a)时刻,S1是Leader,它的term是2,此时,它接受了一个客户端请求并成功发送给了S2,S2也保存在logs[]中了.

在(b)时刻,S1崩溃了,S5通过给S3和S4发送RequestVoteRPC并收到了成功的回复,成为了Leader,其term为3.此时S5收到了客户端请求并加到了log中,但是还未来得及向其他Server发送就崩溃了.

在(c)时刻,S5崩溃以后,S3和S4由于选举超时时间还未到,还是Candidate状态(其实处于Follower状态也无妨),此时S1再次选举成为Leader,在S1的Synchronization阶段,会将index为2以及term为2的Log Entry复制到S2和S3,加上S1正好达到了半数以上的条件,所以这个log就被认为成功应用到了集群.

在(d)时刻,如果S1再次崩溃了,则S5必定会成为leader.那么此时,它会在Synchronization阶段,用index为2而term为3的entry覆盖掉s2,S3,S4上index为2,term为2的entry.

我们可以看到,S1认为已被集群应用的log却被S5覆盖掉了.

那么如何解决这个问题呢?

我们首先考虑一下这个问题产生的原因,就是因为在(d)时刻,S5的log确实比S2,S3,S4的更新,所以才能成为Leader并将Log覆盖掉.

那么,我们如果能够阻止S5在(d)时刻成为leader,即让其他的Server的Log比S5的更新,不就可以防止这种情况了吗?

在Raft论文中,便是通过这种方式解决的.

即,Server在将当前term的entry应用到状态机时,才顺带着应用之前的term的entry,正如前面那幅图中(e)时刻所做的那样.

其实这里数据是否被覆盖,我感觉没有那么重要,因为我们前面介绍过,选举得出的Leader一定是含有全部已提交Log的Server,所以,即使被覆盖,也只是覆盖一些未提交的log,也就是并未给Client回复Ok的log.而且,在实现中,当一台Leader宕机后,它跟客户端之间的连接肯定就会被关闭了,客户端收到的肯定是一个错误.所以,客户端如果需要的话,肯定会再次发起请求.

那么,这样的话,又有一个难点,即对于非幂等性的操作,如果Leader已经成功引用到集群,却对Client响应了一个错误,客户端再次发送一个请求,该怎么办呢?

对于幂等性的操作,这里并不重要,在发送一次就再发送一次呗,无所谓.

而对于非幂等性的操作,再发送一次就可能造成数据错误.

那么如何处理这个问题呢?

Raft论文中并没有给出明确的方案,但我在其他文章中看到过一个方案.

我们可以在客户端动一些手脚,客户端每次发送请求时,都为这个请求生成一个唯一的ID,Leader在收到请求之后,同样在Broadcast阶段将这个ID随着AppendEntries RPC发送给Followers.当客户端重试时,还是发送这个ID,Leader检查一下,如果发现该ID的请求已被处理过,则直接返回给客户端OK.

由于这个ID是随着AppendEntries RPC发送给Followers的,所以Leader上的ID的记录必然能够正确地反映出此集群已经处理的请求.

这样便能解决上面提到的非幂等性操作的问题.

总结

我们可以看到,Raft实现的是强一致性,因为全部的请求,不管是读请求还是写请求,都是先到Leader的.

同时,它也实现了CAP中的CP.

其实这些都是可以打破的.比如说,我们不想要强一致性,而只想要最终一致性,那么我们完全可以让Follower接收客户端的读请求,而不是重定向给Leader.如果我们想要实现AP,那么完全可以让分区的Server继续接受读请求.

参考资料

Raft动画解释 Raft算法解析-乒乓狂魔