ZonePG

CMU 15-445/645 PROJECT #1 - Buffer Pool

Posted on Aug 6, 2021

记录一下完成 Project #1 的主要思路及踩过的坑。

遵循Andy Pavlo要求，代码存放在私有仓库。

LRU Replacement Policy

做过leetcode-146. LRU 缓存机制，可以直接用 hash_map 与 双链表实现，保证操作 O(1) 时间复杂度。 不过这里这里我们可以借用标准库 std::unorder_map, std::list 实现即可。

Victim, Pin, Unpin操作，直接面向测试用例编程，上传 gradescope 一遍过。

需要注意的是，LRU存放的都是 Unpin 的 frame_id，同时 Unpin 并不会更新 frame_id 在 LRU 中的位置，

LRU 供 Buffer Pool 调用，当 Buffer Pool 的 free_list_ 为空时，LRU Vicitm 驱除出来一个 frame_id，这样就可以写入 page 了。

Pin 直接将 frame_id 从 LRU 删除，说明有线程正在使用 frame_id 上的 page，直接将 frame_id 删除可以保证不会获取到 frame_id 上的 page，这样也就无法对该 page 进行操作了，达到了 Pin 的目的。

Buffer Pool

首先对 Buffer Pool 中的一些成员进行解释。

  • page_table_ 是 frame_id 与 磁盘页 page_id 的映射。
  • pages_ 是 Buffer Pool 中的内存，跟据 page_table[page_id] 就得到 frame_id，pages[frame_id] 用来存放磁盘页 page_id 的数据。
  • replacer_ 就是我们的 LRU，LRU 中存放的都是 frame_id，该 frame_id 的 pages_[frame_id] 都是 Unpin 的，也就是 pin_count 为0，表示该页可被替换。
  • free_list_ 是可用的 frame_id，当 Buffer Pool 要存放磁盘页时，优先从 free_list_ 分配 frame_id，并将该 frame_id 与 page_id 磁盘页建立映射。 如果 free_list_ 没有可用的 frame_id 时，也就是 free_list_ 为空，则从我们的 LRU 查找是否有可替换的 frame_id，拿来重新映射磁盘页，并写入到pages_[frame_id]内存中。

以下是实现过程的细节描述。

  • NewPageImpl 将分配的磁盘页与空闲的frame_id建立映射关系，frame_id 从 free_list_ 中获取，如果 free_list_ 为空，则从 LRU 中驱除一个 frame_id 出来供使用。 如果 LRU 也为空，则说明所有 frame_id 都进行了 pin 操作。要注意驱除 frame_id 时，原来 frame_id 上的 pages_ 是否为脏页，如果是脏页，应当将原来 frame_id 对应的 pages_ 写回到磁盘中。 最后将获取的 frame_id 与 分配的磁盘页建立映射，并更新 pages_[frame_id] 相应字段/成员变量。
  • UnpinPageImpl 跟传入的 page_id 可以指导对应的 frame_id，这里有两个坑点。 首先是不能直接将该 frame_id Unpin 到LRU中，应该对 pages_ 的 pin_count 进行判断，如果 pin_count减 1 后是 0 的话，则说明该页没有被使用了，就可以可以 Unpin 到 LRU 中了，保证 LRU 中的 frame_id 都是没有被使用的页。 第二个坑点是，传入的 is_dirty 参数，如果原先页本来就是脏的，即使 is_dirty 是 false，该页仍然是脏的。
  • FetchPageImpl 如果根据 page_id 可以找到对应的 frame_id，直接返回 pages_[frame_id] 即可，同时 pin_count++，也要对 frame_id 进行 Pin() 操作，保证 frame_id 不会在 LRU 中出现 （如果frame_id不在LRU中，Pin()不会对LRU有任何影响；在LRU中，则说明该页之前的pin_count为0，将frame_id在LRU中移除，两种情况都要对pin_count加1） 如果 page_id 找不到对应的 frame_id，找到一个可替代的 frame_id 与 page_id 建立联系，操作类似 NewPageImpl，优先从 free_list_ 中找，最后将磁盘上 page_id 内容读入到 pages_[frame_id] 中。
  • DeletePageImpl 根据 page_id 找到 frame_id，如果该pages_[frame_id] pin_count 不为 0，则不能释放 pages_[frame_id]； 如果为0，则删除 frame_id 与 page 的映射关系，保证 LRU 与 page_table_ 都没有 frame_id，同时设置 page_id 为 INVALID_PAGE_ID，就可以将 frame_id 添加到 free_list_ 中了，表示该frame_id现在可以分配page了。
  • FlushPageImpl 将 Buffer Pool 中的 pages_ 数据写到磁盘页 page_id 中。
  • FlushAllPages 直接遍历 page_table_，获取 page_id, frame_id，将所有 pages_[frame_id] 的内容写到磁盘页 page_id 上。

心得与总结

本来想着对着 ppt 与 它给的课堂笔记，就直接撸实验一了，对着实验指导文档看，什么 Unpin 与 Pin，pin_count 处理，看得云里雾里的，实现 LRU 的时候 Unpin 不更新 LRU 也很反直觉。

LRU 直接面向测试用例编程，虽然过的挺顺利的，但是在实现 Buffer Pool 时，LRU 为 Buffer 提供的是一个什么角色也是云里雾里。

后面又去重新撸网课了，只能说 Andy Pavlo 老师课讲的真好啊（语速也是真的快，英语菜鸡落泪），然后到现在已经彻底清楚 Buffer Pool 原理了。

上面提到的 Unpin 不更新 frame_id 在 LRU 中的位置，现在看来是显然易见的，Unpin 只是将 pin_count 中为 0 的 pages[frame_id] 中保证在 LRU 中存在就行了，由于 pin_count 为0，说明并没有线程又重新获取过 pages[frame_id]，那就不用更新在 LRU 中的位置。

最后，真想说国外的 lab 设计得真心 NB 啊，proj2 B+ 树很难，还是看老师课弄懂原理再开始肝实验吧，避免云里雾里面向测试用例编程。