CMU 15-455 | 学习札记

本来是想直接去干 6.824 来着，结果在网上查了查，发现好多人都做了 CMU 15-455，于是去官网看了看。感觉这门课程还挺有意思，官网居然还有提供完整配套的课程资料，包括视频、PPT、字幕、实验、作业。略经思索，不如先把这个做了，正好复习复习数据库的知识。

所有的课程资料在官网上都有，我就不列出了。这里只记录一下我做的笔记。暂时计划在 3 个月内完成这门课。下面是我的笔记列表：

Lectures

Lecture #11: Joins Algorithms

Join 的算法有如下几种：

1. Nested Loop Join
   • Naive
   • Block
   • Index
2. Sort-Merge Join
3. Hash Join
   • Simple
   • GRACE (Externally Partitioned)
   • Hybrid

Projects

PROJECT #0 - C++ PRIMER

• 官网链接

本节实验只是一道开胃菜，如果没有 C++ 基础建议先去其它地方学习一下。这节实验主要就是实现了一个 Copy-On-Write Tire。虽然只是开胃，但还是把我小小地折磨了一下。

TireNode 和 Tire 的方法和属性到处都有 const 修饰，意味着变量不能被修改，但是在树的构建过程中，时不时得修改父节点的 children_ 属性，这里卡了半天。仔细研究了一下，发现 Clone() 方法可以返回 std::unique_ptr<TireNode>，而且已经通过继承的方式将带值的节点正确复制。这样可以节省很多代码量，而不是手动一个一个进行复制和判断。

因为实验要求每个 TireNode 都不能修改，那么如果要修改一颗树上的某一个节点，就需要将这个节点到根节点路径上的所有节点进行更新。所以就需要记录从根节点到当前节点的路径，这个其实不算复杂，用一个栈就可以解决。

其它的地方就没什么难度了。有一点需要注意，尽量使用课程推荐的 clang-14 系列工具链，避免不必要麻烦。我本来用的 clang-18，结果代码格式化的时候和 clang-14 有点不一样，导致提交的时候一直不通过。后来换成 clang-14 就好了。

PROJECT #1 - BUFFER POOL

• 官网链接：https://15445.courses.cs.cmu.edu/fall2023/project1/
• Leaderboard：497/505 (2024-07-21)

这个 Project 有三个小任务，分别是实现 LRU 算法，Disk Scheduler 和实现一个 Buffer Pool。前两个任务花了五天时间，最后一个花了五天时间。全部做下来，感觉主要的困难在于对算法和类的理解，函数的注释其实已经写得很贴心了，至少只看注释的话 SampleTest 肯定能过。

首先是 LRU-K Replacer，需要实现一个 LRU 算法，不过只需要对比在第 K 次前访问时的时间，谁最早访问淘汰谁。如果所有元素的访问次数都小于 K，则淘汰上次访问时间最早的元素。这个算法使用双向链表保存每个节点的访问记录，使用哈希表记录 frame_id 和节点的对应关系，理解了这些，实现起来还是没多少困难的。

第二个是 DiskScheduler。这个任务比较容易，DiskScheduler 使用一个 Worker Thread 对读写请求进行串行处理，使用队列保存请求，这个部分让我知道了 std::promise 的用法。

最后一个当然就是 BufferPoolManager，这个部分折磨了我好几天 🙈，原因是我没理解 Page 和 Frame 分别是啥，这个 Page* pages_; 存的是什么东西。我在完全没理解 frame_id 是什么的情况下在 Gradescore 上拿了 74 分，简直离谱 😂。首先来说 Frame，Frame 其实就是 Page 在内存中存储的位置，从代码的角度看，Page* pages_ 这个数组的元素下标就是 frame_id，就这样，没了。而 Page 的位置是不固定的，它可能在磁盘或者内存的任何位置，如果我们想将一个 Page 读到内存，就需要将其存到 pages_ 这个数组中的一个位置，换一个表述方式，在内存中选择一个 frame，将 page 存到这个 frame 中。其实在 BufferPoolManager 构造函数中初始化 free_list_ 的时候就能看出来，frame_id 的最大值就等于 pool_size_ - 1，对应 BufferPoolManager 中 pages_ 的大小。理解这些，在实现的时候再参照注释就会比较舒服。

至于 Leaderboard 打榜暂时先不考虑了，先把课程学完再说。