Raft协议及伪码解析

跟着Martin大神学习Raft协议，带上讲解和伪码确实给人深入浅出的感觉，英音听起来十分优雅，也是一种享受了~
视频地址：Distributed Systems 6.2: Raft
整篇主要包括了十张Slide：

节点的状态转换

首先需要明确，节点只有三种状态：

• follower
• candidate
• leader

follower

当一个节点刚启动的时候，或者刚从崩溃中恢复，它只会变成follower，等待来自其他节点的消息

candidate

当follower有一段时间没有接收到来自leader或者candidate的消息，它会开始怀疑leader已经掉线，于是准备开始发起选举，推举自己变成leader。

这段时间对于每个节点是随机设置的，否则所有节点刚启动的时候都会在同一时间发起选举。

如何选举？

概括一下：

1. candidate会增加自己的term，然后邀请其他节点进行投票。
2. 如果candidate接收到比自己更高的term(可能来自于leader或者其他candidate)，那么它会重新变成follower。
3. 如果candidate收到足够多的投票，那么它会变成leader。

下文都会使用quorum(合法的法定人数)来表示足够多的投票，表示过半数以上的节点。

4. 如果candidate没有在计时器(timer)时间范围内获得quorum票数的话，选举超时。它会再次增加term，发起投票邀请，再次进入选举。

leader

当选了leader后，一般情况下会一直保持这个状态。除非：

1. leader掉线了，那么它再次上线回重新变成follower。
2. 它接受到了来自其他节点发送的消息，而他们的term比它更高，那么它也会变成follower。

这种情况可能是由于网络分区导致其他节点无法与它连接，认为它已经掉线而重新进行了选举。

伪码部分

节点初始化(Initialazation)

初始化中需要注意的变量有：
需要持久化的四个变量(他们的值不能因为节点崩溃而丢失)

• currentTerm：节点当前处在的term值
• voteFor：节点把票投给的节点ID值
• log：可以认为是一个数组，每一个值entry包含了msg和term值。msg表示需要向其他节点广播复制的消息，而term表示该条消息所处的term的值。log通过追加新entry的方式进行增长，如果某条entry已经被quorum数量的节点复制成功，那么这条entry可以被commit，即被提交。
• commitLength：已经被提交的长度
  其他变量可以因为节点崩溃在恢复时被重置。同时假设，每个节点拥有唯一的ID，nodes变量保存了所有节点的ID，系统中的节点数量发生变化不在讨论的范畴之内。

前面提到，当follower发现不能与leader进行通信时，会使自己的currentTerm+1，然后将自己设置为candidate，发起选举。与此同时，它会将票投给自己，因此votedFor的值设置为自己的ID，votesReceived集合中也添加了自己的ID，并且初始化lastTerm。

lastTerm代表节点本地log的最后一条entry的term值。

candidate将构造好的投票信息msg(由nodeId, currentTerm, log.length, lastTerm组成)发送给其他节点，开启计时器，进行选举。

选举时其他节点的视角

当其他节点收到了投票请求后，会首先对自身的currentTerm与candidate发送过来的currentTerm(用cTerm替代)进行比较：

1. 如果自身currentTerm小于cTerm，那么自己变成follower，更改自己的currentTerm变成cTerm。
2. 如果自身存在log，取出自己最新接收到的entry的term值作为自己的lastTerm。
3. logOk的值当candidate发来的lastTerm(用cLogTerm代替) > lastTerm（candidate的最新的log的term比自己大）或者cLogTerm=lastTerm 但是candidate.log.length >= log.length(candidate虽然与当前node中的最新log的term值相同，但是candidate拥有很多msg)为true。

由3可见，logOk为true的前提是，candidate拥有更新更多的log。

4. 当且仅当currentTerm接受了candidate的cTerm，并且candidate拥有最新的log(logOk为true)，且没有给其他candidate投票的情况下，可以将自身的voteFor的值设置为candidate的ID值。这种情况下，表示准备将票投给candidate，发送一条granted为true的VoteResponse(由当前节点ID-nodeId, currentTerm, 是否投票给它的granted)消息返回给它。否则，返回一条granted为false的VoteResponse消息。

回到candidate选举时的视角

当candidate收到来自其他节点的回复时，判断：

1. 如果自己仍然还是candidate，并且其他节点的term与自己的一致，也同意投票给自己，将这个节点添加至自己的votesReceived集合中(发起投票时，里面最初只有自己投给自己)。
2. 判断votesReceived中节点的数量是否已经过半，如果已经过半了，那么将自己设置为leader，currentLeader的值为自己的节点ID，并且取消计时器。遍历nodes集合中的所有node，更改sentLength和ackLength字段，执行ReplicateLog函数。

sentLength和ackLength都可以看做是一个map，key为follower的nodeId， value是一个数值，代表长度。前者代表leader已经发送给某个follower的log长度，后者代表该follower已经确认收到的长度。显然，当sentLength的值设置为log.length，表明leader假设follower已经拥有和leader一样多的log，虽然这个假设可能是错的，但是我们会在后面进行修正。
ReplicateLog也会在后面进行解释。

3. 如果节点的term大于自身的currentTerm，表明有比自己更高term的节点存在，那么自己重新变成follower，并且更改自己的currentTerm为那个更高的term，取消定时器，终止选举。

消息如何广播复制

当应用发送消息给集群时，消息是如何被保存提交的？

1. 如果leader接收了消息，那么它可以将消息直接保存到自己的log中，然后修改自己的ackedLength，再遍历follower调用ReplicatedLog进行复制。
2. 如果是follower接收到了消息，那么它需要通过FIFO队列，将这个请求发送给leader进行处理。
   与此同时，leader会周期性地向follower复制消息，即使没有新的消息需要进行广播，这样不仅可以充当与其他节点之间的心跳链接，也可以当做复制给某个follower失败时的重传。

重要的反复出现的ReplicateLog

在这里，sentLength派上了用场。利用sentLength将log分割成两个部分：

• prefixLen：已经发送给follower的log长度
• suffix: 需要发送给follower的log的entry列表。

如果prefixLen = log.length，那么suffix为空，代表没有新数据要发送给follower。
leader构造了一个LogRequest，包括自身的ID, currentTerm，prefixLen, prefixTerm(已经发送给follower的log的最后一个值log[prefixLen-1]的term), commitLength, suffix发送给follower。

节点收到了LogRequest

这时有两种情况：

1. 节点可能正在处于candidate状态，如果接收到的term值大于currentTerm，那么它会取消选举，将自己变成follower，并设置leader，否则的话，返回一条接收失败的LogResponse给发送者。
2. 节点是个普通的follower。
   如果节点的状态是follower，那么需要判断logOk，这个值当且仅当当前节点的log长度大于等于prefixLen(当前节点的log不能小于leader认为的已经发送的长度，否则存在log的丢失)，以及如果存在prefixLen，那么leader端的prefixTerm应当与当前节点的最新log的term一致。

Raft保证，如果两个节点的log在同样的index包含同样的term，那么他们在该index以及之前的log都是相同的。

如果节点的term与leader一致，并且logOk为true，那么节点将会执行Appendentries，并且更改自己的ack为prefixLen+suffix.length，作为LogResponse的一部分返回。

节点如何追加log，Appendentries

follower需要判断的是，是否已经包含了这个消息。

1. 如果follower的log长度大于prefixLen，并且suffix的长度不为空，意味着follower中的log可能包含了以前leader的消息，于是需要找到他们重叠位置的index。
   根据这个index的值，判断当前log的term和suffix对应的term，如果不相等，意味着需要对当前的log进行截断，即丢弃prefixLen之后的log。

为什么能在这个地方截断？因为进入Appendentries的前提是logOk已经为true，此时已经保证prefixLen之前的term已经一致。

2. 将suffix的值追加到log中
3. 如果commitLength小于leader的commit的值，那么将自己没有提交的log发送给应用，然后增加自己的commitLength。

再次回到leader， 如何处理LogResponse

1. 如果leader发现返回的term大于自身的term，那么说明有新的leader，所以自身变为follower。
2. 否则，它会检查其他节点是否已经成功接收消息并且ack长度大于原来所记载的长度。
   2.1 如果是，那么更新sentLength和ackLength，并且执行Commitlogentries。
   2.2 success为false，表明sentLength需要进行修正。然后重新执行Replicatelog。

logOk不为true，可能是因为prefixLen >= log.length，也可能是因为prefixTerm != log[prefixLen-1].term。

leader提交log，Commitlogentries

leader遍历所有的log，将有超过半数以上被接收的entry，认为是已经ready的log。
找到最大下标的log，如果term与当前一直，意味着已经可以被认为commit的log长度增加了。并且这些消息已经被过半节点存储，可以发送给应用了。

总结：

1. 每一个节点在收到比自己高的term时，会变成follower。
2. leader复制到其他节点时，发送LogRequest，其他节点返回LogResponse，用来标识是否已经成功复制。
3. leader根据是否有过半的成功LogResponse来判断消息是否能够最终commit