【CMU15-445 Fall2023】Project1 Buffer Pool 小结

发表于 分类于 标签 , Disqus： 本文字数： 2.2k 阅读时长 ≈ 8 分钟

该系列博客只是为了记录自己在写Lab时的思路，按照课程要求不会在Github和博客中公开源代码。欢迎与我一起讨论交流！

这个Project需要我们实现一个缓存池，减少对于磁盘的频繁IO。开始慢慢上强度了，细节拉满！

Task1 - LRU-K Replacement Policy

什么是LRU算法？LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

LRU-K是一种增强型的LRU，其主要思想是利用历史访问模式来进行页面置换决策，具体过程如下：

  1. 访问记录：每个页面维护一个访问时间戳列表，记录其最近的k次访问时间。这个列表用于计算向后k距离。
  2. 向后k距离：当一个页面被访问时，算法会更新其时间戳列表，并计算向后k距离。向后k距离是当前时间戳与列表中第k个时间戳之间的差值。如果列表中没有k个时间戳，该页面的向后k距离被赋值为正无穷。
  3. 页面替换：
    • 在需要替换页面时，算法会遍历所有页面，找到具有最大向后k距离的页面进行替换。
    • 如果存在多个页面的向后k距离为正无穷，算法将选择这些页面中最早的访问时间戳进行替换。
  4. 优点：LRU-K相较于传统的LRU算法更为智能，它能更好地适应不同的访问模式，减少不必要的页面置换。通过考虑历史访问，它能够识别出哪些页面可能会被频繁使用，从而提高缓存的命中率。

在BusTub的实现中，LRU-K有着每个frame id与LRUKNode的映射。

1
2
3
4
5
6
7
class LRUKNode {
 private:
  [[maybe_unused]] std::list<size_t> history_;
  [[maybe_unused]] size_t k_;
  [[maybe_unused]] frame_id_t fid_;
  [[maybe_unused]] bool is_evictable_{false};
};

一个node记录了一个frame的id，还有这个frame在最近使用k次的时间戳。

  • Evict(frame_id_t* frame_id) : 与所有其他可删除的frame相比，删除具有最大向后k距离的frame。将frame id存储在输出参数中并返回True。如果没有可替换的frame，则返回False。具有少于k个访问记录的frame被给定“无穷”作为其向后k距离。如果多个帧具有inf向后k距离，则根据LRU驱逐具有最早时间戳的帧。成功删除帧应减小替换器的大小并删除帧的访问历史记录。
  • RecordAccess(frame_id_t frame_id) : 每次调用RecordAccess，内置的时间戳就要+1，并且根据frame_id是否在LRU缓存中来决定是更新对应的node还是添加一个新node。
    • Add：新建一个node，并且初始化，再把node插入缓存
    • Update：通过frame id找到对应的node，并修改node的历史访问时间戳，更新它在缓存中的访问位置
  • Remove(frame_id_t frame_id) : 从LRU缓存中删除frame id以及对应的node。要注意删除后对当前“可替换的frame数量”-1。
  • SetEvictable(frame_id_t frame_id, bool set_evictable) : 控制frame是否可逐出。它还控制着LRUKReplacer的size。
  • Size() : 返回LRUKReplacer中当前可替换的frame数量。

总的来说，把这个task当成力扣上的一道数据结构设计题来完成就好了。

Task2 - Disk Scheduler

比较简单，实现两个函数的功能：

  • Schedule(DiskRequest r)：调度DiskManager执行的请求。DiskRequest结构体指定请求是否为读/写，数据应写入/从何处写入，以及操作的页面ID。DiskRequest还包括一个std::promise，一旦请求被处理，其值应设置为true。
  • StartWorkerThread()：启动处理请求的后台工作线程。在DiskScheduler构造函数中创建工作线程并调用此方法。此方法负责获取排队的请求并将其分派给DiskManager。记住设置DiskRequest回调的值，以向请求发出者发出请求已完成的信号。在调用DiskScheduler的析构函数之前，这不应该返回。

Task3 - Buffer Pool Manager

BufferPoolManager内部采用一个原始数组来存放Page的指针。初始时，每个page都在free list中。

同一个块，在内存中称作“帧（frame）”，在硬盘中称作“页（page）”。缓冲池中会存储pool_size个Page，这些个Page包含硬盘上的数据和一些元信息。

BufferPoolManager中的page_table_采用page_id作为键，frame_id作为值。如果有某个frame被使用了，那么page_table_中就会插入相应的键值对。BufferPoolManager中的pages_的下标即代表了frame id，我们通过page id可以找到对应的frame id，再通过frame id就可以找到在pages_中的Page了。

下图来源：https://www.qtmuniao.com/2021/02/10/cmu15445-project1-buffer-pool/

我们可以从freelist或者replacer中找到frame（优先从freelist中找）。如果free list中有空闲的frame，则使用它；否则从replacer中选出需要换出的frame（replacer的size与buffer pool的size相同）。

要实现的每个函数在代码头文件中都有较为详细的实现过程，需要注意很多细节。

需要注意:

  • 每次执行FetchPage时相当于要使用到某一个页面，既然如此，也要在LRU-K缓存中更新历史访问序列（通过调用RecordAccess）；
  • 需要新的frame时，优先从free list中找，其次通过replacer的Evict来获取；
  • 对于页面的pin_count_，只有当某个函数返回的是Page*时，说明这个页是需要使用的，此时其pin_count_ + 1；而只有在Unpin中，才会对pin_count_ - 1；
  • 如果需要替换或新建或删除某个页面时，其脏位位true，则要及时写回磁盘；

错误记录

错误点1：没有保证LRU-K中的原子性

对于当前可替换的frame数量的操作应该是原子性的，可以用atomic_size_t来取代size_t，或者使用锁。

错误点2：最大向前K距离的计算错误

The LRU-K algorithm evicts a frame whose backward k-distance is maximum of all frames in the replacer. Backward k-distance is computed as the difference in time between current timestamp and the timestamp of kth previous access. A frame with fewer than k historical accesses is given +inf as its backward k-distance. When multiple frames have +inf backward k-distance, the replacer evicts the frame with the earliest overall timestamp (i.e., the frame whose least-recent recorded access is the overall least recent access, overall, out of all frames).

主要是对这段话的理解不到位，之前是这样：

1
2
3
4
5
6
7
8
9
// 计算最大向后K距离
int k_dist =
  node.history_.size() < k_ ? std::numeric_limits<int>::max() : (current_timestamp_ - node.history_[k_ - 1]);
if (k_dist > max_k_dist) {
  evict_frame_id = fid;
  max_k_dist = k_dist;
} else if (k_dist == max_k_dist && node.history_.back() < node_store_[evict_frame_id].history_.back()) {
  evict_frame_id = fid;
}

但实际应该为：

1
2
3
4
5
6
7
8
9
// 计算最大向后K距离
int k_dist =
  node.history_.size() < k_ ? std::numeric_limits<int>::max() : (current_timestamp_ - node.history_[k_ - 1]);
if (k_dist > max_k_dist) {
  evict_frame_id = fid;
  max_k_dist = k_dist;
} else if (k_dist == max_k_dist && node.history_.back() < node_store_[evict_frame_id].history_.back()) {
  evict_frame_id = fid;
}

当有多个距离为无穷大的frame时，应该选择其历史记录中具有最小时间戳的那个frame！

错误3：FetchPage找到直接返回时没有pin一下

这里卡了几个测试是因为FetchPage在page_id在缓冲池中时会直接返回，但是我没有在这种情况中对这个page的pin_count_进行+1操作。

错误4：Unpin中的is_dirty参数的设置

在Unpin中，不能直接将page.is_dirty_设置成参数is_dirty，而是应该用或操作：page.is_dirty_ |= is_dirty;。如果不这样做，那么当原先page.is_dirty_为true时，如果我们通过Unpin设置了false，其is_dirty_就变为了false，但是这个页面仍然是脏页面。

错误5：FetchPage没有RecordAccess

在FetchPage中，如果缓冲池中有 page id 直接返回时，replacer_也应该执行RecordAccess。因为这时相当于使用了Page，当然要记录更新。

最终提交

然后Leaderboard的排名有点低了，因为之前都是使用的大锁，希望之后能优化一下。

小结

这个Project差不多搞了四五天，主体代码用了两天左右，然后就是漫长的修Bug。由于从这个Project开始，就不会在本地给出完整的测试集了，所以在评测平台上也是提交了很多次来检测。通过Discord中的频道，也是找到了一些解决Bug的办法，很多时候是一些细节处自己没有考虑到（错误记录）。好在最后也基本上是自己独立完成的，有点小小的成就感！