6.824 实验总结

2018-05-10

概述

花了小半年的时间,断断续续终于将 6.824 2018 的 lab 做完了,代码详见 mit-6.824-2018。 下面总结下 lab 2,lab 3 和 lab 4

lab 2

对于 lab 2来说,关键在于理解 Raft 论文 中的 Figure 2。另外,6.824 的助教写了篇博客 Students’ Guide to Raft 对于实现很有帮助。

在实现时,逛 google group 碰到一个有趣的问题即选举时为什么发送的是最后一项日志的 index 和 term,而不是最后一次 commit 日志的 index 和 term,详见 Leader election… why last log entry, not last committed log entry?

实现 lab2 主要需要注意的就是网络请求乱序、延迟等情况。比如 leader 发送给 follower 的 appendEntries 调用可能会乱序到达。还有就是 golang 的 Timer 不好理解,可以参考文档:Reset

lab2 的实现必须可靠,因为 lab 3 和 lab 4 的实现都基于 lab 2,要用 go test -race 运行多次保证没有错误。

lab 3

lab 3 基于 lab 2 构建一个简单分布式的 key-value 存储。每一个 kvserver 都有一个 raft 实例,可以通过 raft.GetState() 判断自己是否是 leader。为了保持一致性,只有 leader 才可以接受客户端请求;同时所有的请求必须经过 raft 复制(replicate)、提交(commit)后才可以返回给客户端。

实现中碰到了下面的坑:

  1. 等待 commit 的日志。leader 收到 Get/PutAppend RPC 调用后,需要将请求提交给 raft,由 raft 完成复制和提交才可以将请求结果返回 client。那么中间需要阻塞等待直到收到了 commit 的日志。这里我使用 channel 来通知,详见代码
  2. 幂等性。client 可能会多次提交同一个请求,所以实现时保证幂等性。这里我使用当前系统时间的纳秒数作为请求的 id(在实际中不要这么做),同时每次请求会带上上一次请求的 id。这可以保证 server 不会处理冗余请求,又能快速释放内存
  3. 线性一致性。2018 年的 lab 加上线性一致性(linearizability)的检查。具体做法是返回最新请求的结果

lab 4

lab 4 在 lab 3 的基础上增加了分片(Sharding)的功能。实现了 lab 3 后,我们有了一个分布式的 key-value 存储系统,但是这样的系统性能不会高。因为所有的读写请求都需要发送给 leader,通过 raft 复制给其他服务器,然后才能返回结果。所以我们需要分片的策略,提供系统性能。

lab 4 架构类似下面:

每一个集群(group)由固定数量的 server 组成,会持有一定数量的分片,并使用 raft 协议保证分片数据高可用。shard master 会记录集群和分片归属信息;当发生配置变更(有集群加入,离开等),那么就会产生新的配置项,重新分配分片。client 向 shard master 查询最新配置信息,确定应该将请求发送给哪个集群;同理,server 也需要定期查询 shard master 获得新的配置信息。当发生分片变动时,server 就不再响应不属于自己集群的分片请求并进行分片迁移。

这个 lab 首先需要实现 shard master。shard master 实现不难,可以参考 lab3 的实现。需要注意的 Move,Join 和 Leave 应该将所有的分片均匀给所有集群,并尽可能少的移动分片。

有了 shard master,就可以考虑 shardkv 的实现了。shardkv 最大的挑战就是配置切换和分片迁移了。如果还想通过挑战测试,还需要考虑垃圾回收和并发迁移。

配置切换需要按序处理,上一个配置没有完成就不能处理下一个配置。

分片迁移时需要考虑 push 还是 pull。原来我也纠结了很久,最后选择了 pull 方式,这样子只要集群拉取到了所需的分片就可以切换到下一个配置。

结语

感谢 MIT 6.824 的老师开放出实验源码,让我能学习这门非常棒的课程~