CMU 15-445 | Project 1 - Buffer Pool

• 官网链接：https://15445.courses.cs.cmu.edu/fall2023/project1/
• 耗时：11 天
• Leaderboard：40 (2024-10-16)

这个 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

前段时间做了一些简单的优化，让 Leaderboard 从原先的 497 跳到了现在的 40，这里记录一下我在优化时都做了什么：

• 2024-07-21 #Rank 497 - 未优化
• 2024-08-14 #Rank 267 - optim evict: 原先的 LRUKLNode 虽然能够记录历史信息，但是没有固定大小，所以我添加了一个 AddHistory 方法，在添加历史记录时，如果已有记录大于 k_，则将最后一个先 pop_back 掉。这样在找第 k 条历史记录时，直接用 node.hostory_.back() 就好了
• 2024-08-31 #Rank 35 - add multiple io queue: 原先在 DiskScheduler 中，只有一个 request_queue_ 队列，这会导致一个问题，消费者是单线程，每次处理完一个请求都要堵塞队列（取下一个请求）。所以我将 request_queue_ 拆成 bucket 个队列，对应 k 个锁，每个请求入队时，对应的队列和锁的索引是 page_id % bucket。通过减小锁的粒度，排名大幅提高