RAFT && 6.824_lab2

设计

Raft是著名的状态机类型的协议，他通过在多个服务器之间确定leader,保证了服务器之间对于一对key-value的consensus，可以通过这个可视化动画来理解raft

在6.824要求阅读的论文中，有一个关于raft服务器的状态机图：

lab2要求我们实现一个raft.具体编码工作在./src/raft/raft.go里面

lab2a要求我们实现raft里面的leader election。显然，我们需要着重于以下几点：

1. 状态机的实现
2. 心跳机制

Debug技巧

在编写代码之前，需要先学习debug的一些技巧。

对于多线程应用，断点调试是几乎不可能的。我们应该将重点放在log的输出上。然而过多的log不利于我们查看并追踪，在Students' Guide to Raft以及Debugging by Pretty Printing有介绍一些可能用到的技巧以及可能犯下的错误。

十分建议直接使用Debugging by Pretty Printing里面的代码，里面提到的技巧如下：

• 切换输出详细程度
• 输出log时标注相关主体
• 打印项目内部需要的重要信息，如调用print的函数

初次之外，TA还使用python根据log的类别，VERBOSE=1更改了log的颜色，使之更容易阅读

在你阅读完上述材料后，你的代码目录里至少多了TA提供的两个python文件，并且更改了src/raft/util.go

具体使用效果类似下方：

代码实现

首先， 完全参照 论文，实现对应的结构体

Lab2A

Lab2A要求实现leader的election机制。我们先来看raft结构体，要实现论文中的选举机制，我们至少需要保存以下信息：

• Leaderid
• 当前term id
• 心跳时间以及选举时间
• 日志中已经提交确定的最大一个id号
• 状态机的最大日志id
• 将要发送的下一个日志id
• 已经匹配的最大日志id
• 当前raft的状态，即figure 4里面的三种状态

这些都对应于上图中state部分的内容。与之对应的，我们需要实现以下几类函数：

• 与选举时间、心跳时间对应的设置函数（需要为随机值，否则会出现永远无法选举出leader的情况）
• 论文中提到的AppendEntries以及RequestVote RPC方法
• 检测term是否对应的函数
• 选举、心跳机制

时间相关

先来看时间相关的函数。

我们有两个需要进行倒计时的时间要素，其中倒计时时间需要满足election time>heartbeat time,同时两个时间需要是随机化的。至少有三个函数，分别能够返回随机化的election time,heartbeat time以及用于提示raft这两个时间是否超时的函数。

AppendEntries RPC && RequestVote RPC

这一部分仍需要参照论文，具体内容不再解释

Term相关

在figure 4里面，和term相关的内容有：

• 假如leader发现一个服务器有更高的term（更高的term意味着这个leader本身由于partition等原因落后于raft集群当前选举出来的leader）,就将自己转为follower,选举倒计时结束后变为candidate开始选举
• 假如candidate发现了leader或者新的term,就转为leader的follower.

选举、心跳机制

这一部分需要注意各种条件的判断，其他的按照流程实现即可

成功通过后，我们将看到console输出如下信息一个：

LAB 2B&&Lab2C

最近太忙了，没动力写了

lab2B要求我们实现appendentries,这里需要提示的是，如果你的lab2A已经通过而lab2B/2C始终无法通过，那么很有可能是你的lab2A某些地方的判断条件写错了，这里建议仔细检查lab2A的每一个判断条件。

首先审视raft.go找到需要我们完成的函数，首先是start,这个函数注释已经把条件写的很清楚了，照着注释写即可。

其次是由于我们需要将日志里面的内容应用到机器上，因此我们需要一个能够处理appendlog并将其应用的函数applylogs，这个函数需要在传入的raft结构体未被杀死的情况下，一直访问该结构体的日志，并将其应用，同时，我们可以想到两点，一个是访问日志时需要加锁，另一个则是官网上也给出的提示：在每次应用完日志后等待一段时间。

lab2C要求我们实现持久化。实验代码里面已经给出了可以直接实现持久化的persister.go,里面通过状态机和快照机制实现持久化，我们编写代码时直接调用即可。我们需要做的就是处理好持久化（恢复）的时机、序列化以及反序列化。

先看序列化以及反序列化，实验代码提供了labgob编码器以供使用，直接对需要（反）序列化的数据使用labgob.NewDecoder/NewEncoder即可

按照论文里面的内容，我们需要对log,currentTrem,votedFor这三个变量进行持久化操作，仔细检查之前的代码，这三个变量有更改操作时进行持久化即可。而在机器重启时，我们进行持久化恢复操作即可。

除此之外，在Hint里面提到，

• You will probably need the optimization that backs up nextIndex by more than one entry at a time. Look at the extended Raft paper starting at the bottom of page 7 and top of page 8 (marked by a gray line). The paper is vague about the details; you will need to fill in the gaps, perhaps with the help of the 6.824 Raft lectures.

这个就是为了防止一条条回退太慢。同步时，

1. leader发现冲突位置的term自己有，就从该term的最后一个日志开始同步，
2. 冲突位置term没有，就从该term第一个日志开始同步
3. 同步的位置不存在，leader就回退到被同步节点的尾部开始同步