MIT 6.824 Lab2 Raft实现总结

前言

本文的局限性在于，本文不完全按照论文(raft extended)实现，并以通过所有测试和自我满足为目的。在部分与论文不一致，或论文没有详细讨论的地方，我将以引用的格式来说明。

文本并不详细论证Raft，即不按照领导选取（leader election）、日志复制（log replication）、安全（safety）展开，并且（暂时-2020/10/4）不讨论成员变化（membership changes）。本文将把这些部分融合起来，全面展示各个部分的状态变化。

在实现Raft的时候，加锁是个难题，鄙人亦有所总结，才疏学浅，望不吝赐教。文本将不讨论所有加锁的细节。

所有持久化的状态

• currentTerm 当前的Term id
• votedFor 当前任期我投票给谁了
• log[] 日志的顺序列表；每个日志包括了给状态机执行的命令，所在term id

非持久化状态

• commitIndex 已收到的日志
• lastApplied 已投喂给状态机的日志

Leader非持久化的状态

• nextIndex 对于Leader来说，每个Follower的下一个提交位置
• isSynchronizing 是否正在和某个Follower同步信息，一般当Follower日志对不上时启动一下

这里并没有使用matchIndex。因为我不理解这nextIndex和matchIndex的区别：matchIndex+1不就是nextIndex吗？

isSynchronizing 是用来同步大量数据的时候，标记一下Leader正在和谁同步大量数据，避免重复通信大量数据。一般的心跳包和日志传输用不到。这个是自己实现时考虑到而加上的。

---

Raft在运行过程中，主要由这三个死循环来驱动：检查心跳并发动选举、发送日志、投喂状态机。

持久化并不是难点，找到每个修改持久化状态的地方，保存一下就好。所以这文篇章也不会讨论持久化。

检查心跳并发动选举

跟随者 Follower

Follower的所有行为都依靠以下三件事来驱动：

1. 收到了AppendEntries（被动）
2. 收到了RequestVote（被动）
3. 心跳超时（主动）

两个被动触发的事件相互相对独立，但是都会影响到心跳超时。

收到了AppendEntries

如果收到了AppendEntries，则：

1. 检查args.Term，如果args.Term比currentTerm，更新currentTerm，如果Term更低，返回false
2. 将自己的commitIndex添加到reply之中
3. 刷新心跳倒计时，并把自己设为Follower
4. 判断是否接受日志条目

1. 将commitIndex添加到reply之中，是我自作主张的优化。当出现一个有一大段记录与Leader不同的Follower，Leader可以直接通过commitIndex来确定nextIndex，这样会多传输一些日志，但避免了多次通信来寻找匹配的点。
2. 虽然说这是Follower的行为表，但是事实上是，我认可了某个AppendEntries，我就是Follower，这就是我的行为表。所以第3点的后半段是必要的。
3. 第4点这里不详细说，将在发送日志详细介绍；需要提醒一点的是，AppendEntries这个接口一半的功能是与选举有关的，我们这里只提这一半，另一半发送日志的功能，会在后面说到。实现的时候，这两个功能的区分也需要注意一下：接受了心跳不一定接受日志条目。接受了日志条目则一定会接受心跳。

收到了RequestVote

如果收到了RequestVote，则按照下面的规则投票和刷新心跳：

1. 只投票给Term大于等于自己的currentTerm的Candidate
2. 只投票给那些最后一条日志up-to-date（更新或者一样新）的Candidate，新的定义包括两个方面：
   1. 如果日志的Term更大，则是up-to-date的
   2. 如果日志的Term一样且日志的id（槽位的编号）更大，则是up-to-date的
3. 如果不是Pre-Vote且VoteGranted，则更新自己的Term，刷新心跳计时，使自己成为Follower

这里没有提到“一个Term只投票给一个Candidate”，是因为，“每次投票，只投票给自己Term更大的Candidate”这个条件，隐性地保证了“一个Term只投票给一个Candidate”。如果Term一样，那么则不会发生投票。

刷新心跳计时，使自己成为Follower，这点和收到心跳包很像。

心跳超时

如果心跳超时了，则成为Candidate，如下

候选者 Candidate

Candidate的所有行为都依靠以下三件事来驱动：

1. 收到了AppendEntries -> 成为Follower（被动）
2. 收到了RequestVote -> 成为Follower（被动）
3. 选举（主动）

Candidate竞选Leader，是协议中最复杂的状态机，不仅要考虑两轮投票的情况，还要考虑其他Candidate的投票和其他Leader的心跳。我建议每个Peer在主循环中执行这一部分逻辑，防止自己同时发起多次选举。

1. 设置随机的超时时间，且每次超时之后都设置新的随机超时时间。每次超时之后，检查自己的身份，如果不是Candidate（一般来是因为自己成为Follower了），则退出
2. 发起Pre-Vote，使用currentTerm+1作为args.Term，currentTerm暂时不改变
3. 如果Pre-Vote成功，则currentTerm++，进入下一步；如果失败/超时，等待一定时间之后回到第2步
4. 以currentTerm作为args.Term发起Vote
5. 如果Vote成功，进入下一步；如果失败/超时，currentTerm++，重新开始第4步
6. 成为Leader，开始发送心跳/日志

为了方便理解，下面是描述更加详细的状态变化。上述的实现将收到心跳包 -> 成为follower这一类变化，融合进了超时检查之中。

首先发起一轮pre-vote(用于确认自己是否有权力进行选举)，直到

1. 获得的票数大于半数 -> 进入vote
2. 选举超时 -> 稍微等待之后发起新一轮pre-vote
3. 收到有效心跳包 -> 成为follower
4. 承认team更大RequestVote -> 成为follower

之后将自己的current team + +，发起一轮vote，直到

1. 获得的投票大于半数 -> 进入Leader
2. 选举超时 -> 将自己的current team + +，发起一轮vote
3. 收到有效心跳包 -> 成为follower
4. 承认team更大的RequestVote -> 成为follower

复制日志

Leader

Leader的所有行为都依靠以下四件事来驱动：

1. 收到了AppendEntries -> 成为Follower（被动）
2. 收到了RequestVote -> 成为Follower（被动）
3. 收到了Client的请求（被动）
4. 分发日志/心跳（主动）

分发日志 / 心跳

1. Leader将Client的所有请求，包装成log，存入自己的logs。存完之后等待（先不响应Client）
2. Leader从Sleep中醒来，取logs的长度作为end，取nextIndex[i]作为start，将logs[start:end]发给Follower，达成共识之后响应对应的Client。

这算是一种将多条日志，打包分发的方式吧。因为要响应Client，所以这个Sleep的时间间隔不能太长，所以第2点会成为事实上的心跳包，不需要再去写额外的心跳包函数。

我有看到（在哪看到忘记了）收到Client的请求，先分发，达成共识之后再加入到logs队列。这么做是为了避免在logs中插入了一个本应该失败（Client看到了失败）的log。但是后来发现，Raft在很多地方都不能保证失败，而且这样处理的话，log index很难分发，因此这种做法并不可取。

3. 如果end=commitIndex，则说明此次并没有分发任何实际上的日志。不需要关心是否达成共识
4. 如果当前最后一条日志不是自己任期内的日志，则Leader只能分发日志，不能修改commitIndex，则也不需要关心是否达成共识
5. 虽然Leader有时候并不关心是否达成共识，但是依旧要关心每个Follower是否接受自己的日志
6. 如果某个Follower不接受日志，则以reply.commitIndex作为nextIndex[i]和start，再发送一次日志

Follower

接受日志

6. ……（接检查心跳并发送选举中的第6点）
7. 如果目前的日志长度小于args.PreLogIndex，则退出；否则进入下一步
8. 如果logs[args.PreLogIndex].Term与args.PreLogTerm不一致，则退出，否则进入下一步
9. 以args.PreLogIndex为结尾，接上args.Entries
10. 更新CommitIndex并提交记录。

在做实验的时候，可以同步按照CommitIndex来提交记录。另一种更好的方式是，再起一个协程，专门检查CommitIndex并提交记录。

Tips

这些和大的方向与状态转换无关，只是分享一下在某些细节上，这么实现可能会很方便。

更新心跳包

// 将nextTimeOut更新到now + HeartBeatTimeOut，返回这个时间
func (rf *Raft) updateHeartBeatTimeOut() time.Duration {
   rf.nextTimeOut = Now() + HeartbeatTimeout + RandTime(HeartbeatTimeout)
   return rf.nextTimeOut
}

func (rf *Raft) waitHeartBeatTimeOut() {
	for true {
		time.Sleep(rf.getNextTimeOut() - Now())
		if rf.getIdentity() == Follower && Now() >= rf.getNextTimeOut() { // follower超时了，这里不可能是candidate
			DPrintf("[%d] start leader election", rf.me)
			rf.leaderElection()
			rf.updateHeartBeatTimeOut()
		}
	}
}

使用Select和time.Ticker来实现状态转换

助教说不要使用time.Ticker，很容易出错。但是我个人认为通过Select配合time.Ticker，能非常清晰地表达如果A，则。。。如果B，则。。。如果超时，则。。。这种语义。

如果担心Ticker用错，我的建议是，不要去重启一个Stop掉的Ticker，而去重新创建一个Ticker。