CMU 15-455 | 学习札记
本来是想直接去干 6.824 来着,结果在网上查了查,发现好多人都做了 CMU 15-455,于是去官网看了看。感觉这门课程还挺有意思,官网居然还有提供完整配套的课程资料,包括视频、PPT、字幕、实验、作业。略经思索,不如先把这个做了,正好复习复习数据库的知识。
请注意,我做的是 Fall2023 这一学期的版本
应课程要求,我的笔记不会包含任何实验的代码,只会提供相关思路和分析
所有的课程资料在官网上都有,我就不列出了。这里只记录一下我做的笔记。暂时计划在 3 个月内完成这门课。下面是我的笔记列表:
Lectures
TODO...
Lecture #11: Joins Algorithms
Join 的算法有如下几种:
- Nested Loop Join
- Naive
- Block
- Index
- Sort-Merge Join
- 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 打榜暂时先不考虑了,先把课程学完再说。
To be continued...