Wandai Blog 共被围观 1,640,335 次

目标

本次lab的目标是实现基本的Raft共识算法。

设计与实现

Raft算法的原理已经由Raft论文给出，具体实现时需要结合各个章节的内容，此外还有一些工程细节需要在本次lab中解决。

Lab 2A以及2B

本次lab的实现共分为如下9个处理方法：

• RequestVote RPC请求处理方法
• RequestVote RPC响应处理方法
• AppendEntries RPC请求处理方法
• AppendEntries RPC响应处理方法
• 选举超时定时器
• 心跳定时器
• AppendEntries超时重试定时器
• 提交器（Committer）
• 上层应用接口Start

其中，四个RPC处理方法当收到RPC请求或响应时触发，它们是幂等的，即收到重复的RPC消息不会影响安全性（safety）；三个定时器处理方法由相应的定时器触发；提交器由一个下文描述的条件变量触发；上层应用接口由上层应用直接调用。接下来对这几个部分逐一进行说明。

RequestVote RPC请求处理方法

当接收者收到一个RequestVote请求时，其首先判断发送方的term是否已落后（小于接收者的term），若已落后，则直接拒绝这次请求，并将目前的term返回给发送方。另一方面，若接收者发现发送方的term更新（更大），则会更新自己的term（这意味着清除VotedFor），并将自己的状态设置为Follower，并继续处理该请求。

发送方（Candidate）利用该请求从其他节点获得选票。当如下条件都得到满足时，接收者会将选票投给发送方：

• 接收者本term还未投过票，或本term给相同的发送方投过票；
• 并且，发送方的日志至少和接收者一样新。

投票给发送方后，接收者会记录发送方（VotedFor），防止下次将选票投给不同的Candidate，从而导致本term选出多个不同的Leader。此外，投票给发送方后，接收者还会重置选举超时定时器（通过向下文描述的channel发送数据来实现）。

RequestVote RPC响应处理方法

当接收者收到了RequestVote响应时，其首先判断发送方的term是否已落后，若已落后，则直接丢弃该响应。类似地，若接收者发现发送方的term更新，则会更新自己的term，并将自己的状态设置为Follower，然后放弃后续操作。

如果发送方将选票投给了接收者，并且接收者当前还未当选Leader，接收者会继续检查当前收集到的选票是否超过了半数。若选票很幸运地超过了半数，那么该接收者当选Leader，其会将自己的状态设置为Leader，并初始化nextIndex以及matchIndex，便于之后向Follower同步日志。接收者当选Leader后，还会向其他每个节点发送初始的心跳请求（不含日志，但含其他字段的AppendEntries RPC请求）来通知其他节点自己当选了新Leader。

AppendEntries RPC请求处理方法

与RequestVote请求类似，当接收者收到一个AppendEntries请求时，其首先判断发送方的term是否已落后，若已落后，则直接拒绝这次请求，并将目前的term返回给发送方。另一方面，若接收者发现发送方的term更新，则会更新自己的term，并将自己的状态设置为Follower，并继续处理该请求。

至此，若该请求通过了上述检查，则说明当前term存在一个活跃的Leader。若接收者当前状态为Candidate，这说明，该接收者在本term不幸地没有被选为Leader，接收者会将状态设置为Follower，并继续后续处理。

该请求中含有一条日志的序号和term（PrevLogIndex和PrevLogTerm），以及该日志之后的所有日志的内容和term。接收者首先检查自己的PrevLogIndex对应的日志的term是否与PrevLogTerm相符，若不相符则日志不一致，向发送者返回失败信息。特别地，若PrevLogIndex对应的日志不存在，则认为不相符。根据Raft论文第7至8页提出的优化，在term不相符时，接收者还会向发送者返回PrevLogIndex对应的日志的term（ConflictTerm），以及该term中首个日志的序号（ConflictIndex）。特别地，若PrevLogIndex对应的日志不存在，ConflictTerm取-1，ConflictIndex取日志序号最大值加一。这两个信息提示Leader，其ConflictIndex至PrevLogIndex的所有日志的term为ConflictTerm，方便Leader尽快了解接收者当前的日志情况。

若上述检查相符，接收者会将该请求携带的日志信息与PrevLogIndex之后的日志进行比较，并将第一个序号或term不匹配的日志及之后的日志删除，最后将该请求中携带的所有本地不存在的新日志添加到本地的日志中。至此，接收者可以断定请求携带的最后一条日志对应的本地日志及之前的本地日志与当前Leader一致了。

最后，该请求中还包含Leader最新提交（commit）的日志的序号（LeaderCommit），接收者可以用此信息以及上述“断定”来安全地更新自己的提交序号（commitIndex）。

AppendEntries RPC响应处理方法

当接收者收到了AppendEntries响应时，其首先判断发送方的term是否已落后，若已落后，则直接丢弃该响应。类似地，若接收者发现发送方的term更新，则会更新自己的term，并将自己的状态设置为Follower，然后放弃后续操作。

Leader对于每一个节点存储了nextIndex值以及matchIndex值。由于一些原因，某些节点的日志与Leader的日志不完全一致，此时，nextIndex就是Leader对相应节点的首个不一致的日志的序号的乐观估计，真实值会更小。matchIndex含义与此不同，对于每一个节点，Leader确信matchIndex对应的日志及之前的日志与该节点一致。

若响应者返回成功，说明PrevLogIndex对应的日志以及发送请求时传输的日志信息均已被响应者同步，接收者（此时应为Leader）可以用这一信息来更新nextIndex值以及matchIndex值。更新后，若存在一个大于当前提交序号（commitIndex）的N，使得超过半数的matchIndex值至少为N，并且N对应的日志的term为当前term，则更新接收者自己的提交序号为N。事实上，其中满足条件的N为所有matchIndex值的某种“中位数”。接收者自己的matchIndex取其最新一个日志的序号。

若响应者返回失败，原因可能有两点。原因之一是，该响应对应的请求的term已落后，对此，响应的接收者不做继续处理。否则，失败的原因是PrevLogIndex对应的响应者的日志的term与PrevLogTerm不相符，接收者在下一次发送AppendEntries请求前，需要重新估计nextIndex值。根据AppendEntries RPC请求处理方法中描述，该响应中包含了ConflictTerm以及ConflictIndex，这两个信息提示接收者，响应者的ConflictIndex至PrevLogIndex的所有日志的term为ConflictTerm。如果对于接收者，ConflictIndex对应的本地日志的term与ConflictTerm不符，则可以估计nextIndex值为ConflictIndex，跳过整个term。如果ConflictIndex对应的本地日志的term与ConflictTerm相符，则从ConflictIndex之后第一个日志开始，到PrevLogIndex之前的一个日志，寻找首个term不为ConflictTerm的日志，将其序号作为nextIndex的估计值。对于这种情况，新的估计值是精确的。

接收者更新nextIndex后，不立即重试，而是等待后文提到的AppendEntries超时重试定时器触发，届时由其发送新的AppendEntries请求。

选举超时定时器

该定时器每隔一段随机的时间触发一次，触发前可以被重置，并重新开始等待一段新的随机的时间。该定时器的goroutine在等待定时器超时的同时等待一个channel输入，因此其他组件可以通过向该channel发送数据来重置这个定时器。

当该定时器触发时，若当前节点不是Leader，则对于当前节点而言，目前不存在活跃的Leader，或本term的选举失败了。对于这样的情况，当前节点启动一次新的选举过程，其首先将当前状态设置为Candidate，然后增加term值，接着为自己投一票（同时将VotedFor设置为当前节点），最后向其他每个节点发送一个RequestVote请求。请求除基本信息外还会包含自己最新一条日志的序号以及term，便于接收者检查选举发起者的日志是否足够新。当这些请求的响应到来时，前述的RequestVote RPC响应处理方法将对其进行处理。

当发送完上述请求后，当前节点会重置该定时器，以等待选举超时。选举超时会导致定时器再次触发，届时该节点会重复上述流程。

心跳定时器

该定时器每隔一段确定的时间触发一次。当该定时器触发时，若当前节点是Leader，其会向其他每个节点发送一个心跳请求来告知所有节点自己仍然存活。心跳请求是一个AppendEntries RPC请求，该请求中不含日志，但含其他字段。

AppendEntries超时重试定时器

该定时器每隔一段确定的时间触发一次。当该定时器触发时，若当前节点是Leader，其会对每个节点，利用nextIndex的信息，产生AppendEntries RPC请求来向其他节点尝试同步nextIndex之后的所有日志。

提交器（Committer）

每当提交序号（commitIndex）被更新时，相应的代码片段还会将所有新被提交的日志加入一个队列，并通过条件变量向提交器发送信号，提交器接收到这一信号后，将该队列中的日志通过applyCh逐一交付上层应用、作用到状态机。

上层应用接口Start

每当收到一个上层应用的命令，如果当前节点是Leader，则将命令加入日志，以便AppendEntries超时重试定时器触发时将日志同步给其他节点。如果当前节点不是Leader，则返回错误信息，上层应用会继续向其他节点发起请求。

Lab 2C

对于最后一个任务（Lab 2C），只需要在每一个修改持久状态的地方加入persist()操作即可。

致谢

开始之前，我阅读了这个guide。这个guide非常有帮助，让我潜在地少踩了不少坑。特此记录以表示感谢。

代码根据规定不予直接公开，可以与我联系，进行讨论。