Lab2 汉化

前言

仅供学习，转载请标明出处。

有任何翻译上的问题欢迎评论和私聊。具体的实现思路会发布在另一篇文章中，本篇文章仅讨论翻译问题。

原文：http://nil.csail.mit.edu/6.824/2020/labs/lab-raft.html

课程详情：http://nil.csail.mit.edu/6.824/2020/schedule.html

6.824 实验 2： Raft

---

介绍

这是一系列实验中的第一个实验，您将在这一系列实验中构建具有容错能力的key/value存储系统。首先，您将此实验中实现 Raft（一种复制的状态机协议）。在下一个实验中，您将基于Raft构建key/value服务。然后为了实现更好的性能表现，您将把服务分发到多台冗余的服务器上。

冗余的服务器通过将状态（即数据）完整的副本存储在多个服务器上来实现容错。这种复制能够使部分服务器遇到故障（崩溃或网络损坏或片断）时，依旧提供服务。但这其中的挑战在于，部分错误可能会使冗余服务器保存不同的数据副本。

Raft 将客户端请求组织成一个序列（称为日志），并确保所有的服务器都看到相同的日志。每个服务器按日志顺序，在本地的数据副本上执行客户端请求。因为所有在线的服务器都看到相同的日志，因此它们都按相同的顺序执行相同的请求，所以所有的在线服务器继续具有相同的状态。如果服务器短暂出现故障，Raft 会负责将它的日志更新到最新的状态。只要大多数服务器处于在线状态并且可以相互通信，Raft 将继续运行，否则Raft将不会继续运行。但只要多数服务器能够再次通信，Raft就会从它停止工作的地方继续开始。

在此实验中，您将通过 Go 实现Raft ，使其成为一个大型服务的模块。一组 Raft 实例通过 RPC 互相通信，维护日志。您的 Raft 将会收到一系列不确定的命令，也称为日志条目。这些日志条目按照他们的索引号排序。这些带索引号的日志条目将会被确定下来。此时，您的 Raft 应将日志条目发送到所有其他服务，以便其执行。

您应该遵循 extended Raft paper 中的设计，并特别注意Figure 2。您将实现本文中大部分功能，包括持久化、在节点发生故障后重启并加载数据。您不会实现群集成员身份更改（第 6 节）。您将在以后的实验中实现日志压缩/快照（第 7 节）。

您可能会需要这份指南，以及有关锁和并发结构的建议。您还可以通过这些来扩展思路：Paxos, Chubby, Paxos Made Live, Spanner, Zookeeper, Harp, Viewstamped Replication, 和 Bolosky et al.

这个实验室分三部分进行。您必须在相应的到期日期提交每个部分。

协作策略

您必须为 6.824 编写并上交的所有代码，其中一部分由我们为您提供。不允许查看其他人的解决方案，不允许查看前几年的代码，也不允许查看其他 Raft 实现。您可以与其他学生讨论作业，但不得查看或复制其他人的代码，或允许其他人查看您的代码。

请不要发布您的代码或将其提供给当前或将来的 学习 6.824 的学生。github.com是公开的，所以请不要将代码放在上面，除非您将仓库设为私有。您可能会喜欢使用 MIT 的GitHub，但请务必创建一个私有存储库。

开始

如果您已经完成了实验 1，则已有实验源代码的副本。如果没有，您可以在实验 1 指南中通过 git获取到资源。

我们提供骨架代码src/raft/raft.go。我们还提供一组测试，您应该使用这些测试来驱动实现，我们将用这些测试对提交的实验进行评分。测试在src/raft/test_test.go中。

若要启动并运行，请执行以下命令。不要忘了 git pull得到最新的代码。

$ cd ~/6.824
$ git pull
...
$ cd src/raft
$ go test
Test (2A): initial election ...
--- FAIL: TestInitialElection2A (5.04s)
        config.go:326: expected one leader, got none
Test (2A): election after network failure ...
--- FAIL: TestReElection2A (5.03s)
        config.go:326: expected one leader, got none
...
$

代码

完善raft/raft.go来实现Raft。在该文件中，您将找到骨架代码，以及如何发送和接收 RPC 的示例。

您的实现必须包含以下接口，测试和key/value服务器（最终）将使用该接口。您可以通过raft.go了解更多。

// create a new Raft server instance:
rf := Make(peers, me, persister, applyCh)

// start agreement on a new log entry:
rf.Start(command interface{}) (index, term, isleader)

// ask a Raft for its current term, and whether it thinks it is leader
rf.GetState() (term, isLeader)

// each time a new entry is committed to the log, each Raft peer
// should send an ApplyMsg to the service (or tester).
type ApplyMsg

服务调用Make(peers, me, ...)创建一个 Raft peer。peers 参数是所有 Raft peers（包括这一个）的网络标识符数组，用于 RPC。me参数是网络标识符数组中，属于这个peer的网络标识符的的下标。Start(command) 要求 Raft 启动处理，将命令追加到日志副本中。Start()应立即返回，无需等待日志追加完成。该服务希望你将每个新的日志条目，封装为ApplyMsg，发送给Make函数中的applyCh参数（这是一个channel）。

raft.go包含发送 RPCsendRequestVote()和处理传入 RPC（RequestVote（）的样例代码。您的 Raft peers 应该使用 labrpc Go 包（源代码在 src/labrpc）交换 RPC。测试人员可以告诉labrpc延迟 RPC请求，重新排列它们，并丢弃它们以模拟各种网络故障。虽然您可以暂时修改labrpc，但请确保您的 Raft 与原始labrpc一起使用，因为我们将使用labrpc来测试和评价您的实验。您的 Raft 实例必须仅与 RPC 交互;例如，不允许它们使用共享的 Go 变量或文件进行通信。

后续的实验在此实验上构建，因此给自己足够的时间编写可靠的代码非常重要。

第 2A 部分

实现 Raft Leader选举和心跳检测（通过发送AppendEntriesRPC请求但不带日志条目）。第 2A 部分的目标是选举单个领导者，在没有失败时让 Leader 继续担任;如果旧 Leader 失败或旧 Leader 的数据包丢失，则新 Leader 可以接管。运行go test -run 2A以测试 2A 代码。

• 您无法轻松地直接运行 Raft 实例;相反，你应该通过测试运行它，即go test -run 2A。
• 按照论文的Figure 2。此时您只需要关心发送和接收 RequestVote RPC、与选举相关的服务器规则以及相关的情况，
• 将 Leader 选举的Figure 2 状态添加到raft.go上的 Raft结构中。您还需要定义一个结构体来保存有关每个日志条目的信息。
• 填写RequestVoteArgs和RequestVoteReply结构。修改Make()以创建一个后台 go 协程，该协程将在一段时间未从其他 peers 那里听到请求投票 RPC 时，发送RequestVote RPC 来定期启动 Leader 选举。这样，如果已经有一个 Leader，或者其成为 Leader，其他 peers 就会知道谁是Leader。实现RequestVote() RPC 函数，以便服务器投票给别人。
• 为了实现心跳检测，请提前定义AppendEntries RPC 结构（尽管您可能还不需要所有参数），并让 Leader 定期发送它们。AppendEntries RPC 函数需要重置选举超时时间，以便其他服务器已当选时，该不会以 Leader 的身份继续运行。
• 确保不同 Peers 不会在同一时间选举超时，否则所有 Peers 将只为自己投票，没有人会成为 Leader。
• 测试要求 Leader 发送心跳检测 RPC 的频率不超过 10 次/ 秒。
• 测试要求您的 Raft 在旧 Leader 失败后五秒内选出新 Leader（如果大多数同行仍然可以沟通）。但是，请记住，在发生分裂投票的情况下（如果数据包丢失或候选人不幸地选择相同的随机回票时间，则可能发生），*选举可能需要多轮投票。您必须选择足够短的选举超时（心跳间隔也是如此），确保即使选举需要多次轮断，也能在五秒内完成。
• 论文第 5.2 节提到选举超时应该在 150 到 300 毫秒范围内。只有当 Leader 发送一次心跳包的远小于 150 毫秒，这种范围才有意义。由于测试将您发送心跳包的频率限制在 10 次/秒内（译者注：也就是大于 100 毫秒），因此您必须使用比论文 150 到 300 毫秒更大的选举超时时间，但请不要太大，因为那可能导致无法在 5 秒内选出 Leader。
• 你可能会发现 Go 的 rand 很有用。
• 您将需要定期执行某些操作，或在一段时间后做些什么。最简单的方法是新起一个协程，在协程的循环中调用time.Sleep()。不要使用time.Timer或time.Ticker，这两个并不好用，容易出错（译者注：见仁见智）。
• 阅读有关锁和并发结构的建议。
• 如果代码在通过测试时遇到问题，请再次阅读论文的 Figure 2 ；Leader 选举的逻辑分布在Figure 2 的多个部分。
• 别忘了实现GetState()。
• 测试调用您的 Raft 的rf.Kill()时，您可以先调用rf.killed()再决定是否rf.Kill。您可能希望在所有循环中执行此功能，以避免已经死亡的 Raft 实例打印令人困惑的信息。
• 调试代码的一个好方法，就是在 Peer 发送或收到消息时打印自己的状态，并在测试时运行go test -run 2A > out，将日志收集到文件中。然后，通过研究 out 文件，可以确定实现中不正确的地方。您可能会喜欢用util. go中的Dprintf函数来调试，其可以在不同情况下打开和关闭日志。
• Go RPC 仅发送以大写字母为首的结构体字段（译者注：可导出的字段）。子结构体还必须具有大写字段名称（例如数组中的日志记录字段）。labgob包会警告您这一点，不要忽略警告。
• 用go test -race测试你的代码，并修复它报告的任何问题。

在提交第 2A 部分之前，请确保通过 2A 测试，以便看到类似这样的测试：

$ go test -run 2A
Test (2A): initial election ...
  ... Passed --   4.0  3   32    9170    0
Test (2A): election after network failure ...
  ... Passed --   6.1  3   70   13895    0
PASS
ok      raft    10.187s
$

每一个“通过”的测试用例会输出五个数字;他们分别是

1. 测试所用的时间（单位：秒）

2. Raft Peer 的数量（通常为 3 或 5）

3. 测试期间发送 RPC 的次数

4. RPC 消息中的字节总数

5. Raft 确定并提交的日志条目数。

您的数字将不同于这里示范的数字。您可以忽略数字（如果您想），但它们可以帮助您彻查发送的 RPC 数量。对于实验 2、3 和 4，如果评分脚本（go test）运行总共超过 600 秒，或者任何单个测试超过 120 秒，则会无法通过测试。

提交实验 2A 的程序

首先，请最后一次运行 2A 测试。然后，运行make lab2a将代码上载到提交站点。

您可以使用 MIT 证书或通过电子邮件请求 API **首次登录。您的 API ** （XXX） 将在您登录后显示，并可用于从控制台上载实验室，如下所示。

$ cd ~/6.824
$ echo "XXX" > api.key
$ make lab2a

检查提交网站，以确保它看到您的提交。

您可以多次提交。我们将使用您最后一次提交计算迟到日期。您的成绩取决于您的解决方案在正确运行测试时所达到的分数。

第 2B 部分

完善 Leader 和 Follow 的代码，是他们可以追加新的日志条目，并通过 go test -run 2B。

• 运行git pull获取最新的实验代码。
• 你的第一个目标应该是通过TestBasicAgree2B()。首先实现Start()，然后按照 Figure 2，实现 RPC函数 AppendEntries来收发新的日志条目。
• 您需要实现选举限制（论文第 5.4.1 节）。
• 在早期的 2B 实验中，测试中未能达成协议的解决办法是：即使*还活着，也举行重复的选举。在选举计时器中找到并修复这个 bug ，或在赢得选举后立即发送心跳包。
• 您的代码可能需要循环检测变量。不要让这些循环不间断连续执行，这将使您的服务运行变慢，最终导致测试失败。使用 Go的条件变量 或在循环中插入time.Sleep(10 * time.Millisecond)。
• 为了避免给之后的实验造成麻烦，请编写（或干脆重构）简洁明了的代码。您可以重新访问我们的并发结构，锁和指导页面来获得一些灵感。

如果运行太慢，可能会没法通过接下来的测试。您可以使用time命令检查您的解决方案使用了多少实时时间和CPU时间。这是典型的输出

$ time go test -run 2B
Test (2B): basic agreement ...
  ... Passed --   1.6  3   18    5158    3
Test (2B): RPC byte count ...
  ... Passed --   3.3  3   50  115122   11
Test (2B): agreement despite follower disconnection ...
  ... Passed --   6.3  3   64   17489    7
Test (2B): no agreement if too many followers disconnect ...
  ... Passed --   4.9  5  116   27838    3
Test (2B): concurrent Start()s ...
  ... Passed --   2.1  3   16    4648    6
Test (2B): rejoin of partitioned leader ...
  ... Passed --   8.1  3  111   26996    4
Test (2B): leader backs up quickly over incorrect follower logs ...
  ... Passed --  28.6  5 1342  953354  102
Test (2B): RPC counts aren't too high ...
  ... Passed --   3.4  3   30    9050   12
PASS
ok      raft    58.142s

real    0m58.475s
user    0m2.477s
sys     0m1.406s
$

"ok raft 58.142s"意味着 Go 运行 2B 的测试所用的实时时间为 58.142 秒。"user 0m2.477s"表示代码运行了 2.477 秒的 CPU 时间，或实际运行（而不是等待或睡眠）所花费的时间。如果测试 2B 使用超过 1 分钟的实时时间，或超过 5 秒的 CPU 时间，则以后的实验可能会遇到麻烦。检查睡眠时间、等待 RPC 超时所花费的时间、没有睡眠或等待地检查条件或channel信息的循环、或发送大量 RPC 的地方。

提交实验 2B 的程序

首先，仔细检查代码通过 2B 测试，并且仍然通过 2A 测试。然后运行make lab2b将代码上载到提交站点。

您可以使用 MIT 证书或通过电子邮件请求 API **首次登录。登录后将显示API** （ XXX ），可用于从控制台上传实验室，如下所示。

$ cd ~/6.824
$ echo "XXX" > api.key
$ make lab2b

第 2C 部分

如果基于 Raft 的服务器重新启动，它应该在中断的地方恢复服务。这要求 Raft 在重启后，依旧能确保数据持久化。本文的Figure 2 提到的那些状态应该被持久化（译者注：这些需要持久化的状态原文为persistent state，后文不再翻译）。

真正的实现会在每次 persistent state 被修改时写磁盘，并在重新启动后从磁盘读取状态。您不需要使用磁盘，取而代之，应该通过 Persister 对象保存和恢复 persistent state （请参阅persister.go）。调用Raft. make()时会提供一个Persister， 其可能会包含 Raft 最近的 persistent state（也可能没有） 。Raft 应从 Persister 初始化其状态（对应方法ReadRaftState()），并在每次 president state 更改后使用Persister 保存（对应方法SaveRaftState()）。

完善raft.go中的persist()和readPerisit()函数，实现保存和读取 persistent state。你可能需要使用labgob encoder 来编码（或者说序列化）persistent state，让Persister来存储二进制流。欢迎查看persist()和readPerisit()的注释了解更多。labgob很像 go 的 gob，只是会在序列化非导出字段时报错。

实现完“ 在每次 persistent state 改变时调用presist()”后，应通过其余测试。

为了避免内存不足，Raft 必须定期丢弃旧的日志条目，但在下一个实验室之前，您不必担心这一点。

• 运行git pull获取最新的实验代码。
• 许多 2C 测试涉及服务器故障和网络丢失 RPC 请求或答复。
• 您可能想优化为一次性保存多条日志。查看论文第七页的顶部到第 8 页顶部（用灰色线标记的地方）。文件没有描述清楚细节，你需要自己多考虑一下。 6.824 Raft 的讲座或许也能提供一些帮助。
• 对于完整的实验 2 测试集（2A+2B+2C），合理的时间是 4 分钟的实时时间和 1 分钟的 CPU 时间。

您的代码应通过所有 2C 测试（如下所示），以及 2A 和 2B 测试。

$ go test -run 2C
Test (2C): basic persistence ...
  ... Passed --   7.2  3  206   42208    6
Test (2C): more persistence ...
  ... Passed --  23.2  5 1194  198270   16
Test (2C): partitioned leader and one follower crash, leader restarts ...
  ... Passed --   3.2  3   46   10638    4
Test (2C): Figure 8 ...
  ... Passed --  35.1  5 9395 1939183   25
Test (2C): unreliable agreement ...
  ... Passed --   4.2  5  244   85259  246
Test (2C): Figure 8 (unreliable) ...
  ... Passed --  36.3  5 1948 4175577  216
Test (2C): churn ...
  ... Passed --  16.6  5 4402 2220926 1766
Test (2C): unreliable churn ...
  ... Passed --  16.5  5  781  539084  221
PASS
ok      raft    142.357s
$ 

提交实验 2C 的程序

首先，仔细检查代码通过所有 2A、2B 和 2C 测试。然后，运行make lab2c将代码上载到提交站点。

您可以使用 MIT 证书或通过电子邮件请求 API **首次登录。登录后将显示API** （ XXX ），可用于从控制台上传实验室，如下所示。

$ cd ~/6.824
$ echo "XXX" > api.key
$ make lab2c