写在前面

对于还未完全实现的同学们，切忌直接面向测试编程！在着手实现前，一定要想好需要实现的函数的框架，以及其需要满足的功能。有一些功能的实现是需要对buffer pool有一定的理解，而不是简单地根据注释中的guideline就上手做，对于需要实现的功能有一定的理解再去实现能大大减少debug的时间。（说来都是泪呀…）
此外，Project 1需要实现下面三个task：

  1. Extendible Hash Table：可扩展哈希表
  2. LRU-K Replacement Policy：基于LRU-K的页替换策略
  3. Buffer Pool Manager Instance：管理上面所实现的1、2，实现buffer pool的基础操作

Extendible Hash Table

定义

先明确可扩展哈希表的定义，首先它是一个可以存储key-value键值对的数据结构，由一个可延长的链表加上对应的Bucket实现。可见Extendible Hashing (Dynamic approach to DBMS) - GeeksforGeeks中的详细解释。

为什么用？

了解了可扩展哈希表的定义后，知道为什么使用可扩展哈希表也是很重要的。对于普通的使用拉链法实现的哈希表，如果对于某一哈希值其链出的Bucket数目很多，这种情况下的检索效率最坏是线性的，即_O_(_n_)的时间复杂度。
此时Extendible Hash Table从天而降，通过引入“全局深度”(global depth)和“局部深度”(local depth)的概念解决了这种问题，它通过对Bucket的长度和“平衡度”进行设定，在扩展时只需对需要分裂的Bucket操作即可。

实现细节

根据注释，可以先将对应的Bucket中的增删改查部分实现，方便后续外部实现。
对于整个部分比较tricky的地方在于，当对于新插入Bucket中的key-value，需要先检查Bucket是否已经满了，满的话则需要比较global depth和local depth的关系进而看是否需要扩展哈希表的directory（满的话Bucket是必分裂的，这个无序讨论）。如果需要扩展directory的话，对于新的directory中如何指向Bucket又是一个问题。
因此出现了以下问题：

  1. 插入时Bucket满时global depth和local depth相等于否带来的directory扩展问题
  2. 插入时Bucket满且directory扩展后的指向问题
  3. Bucket分裂后directory的指向问题

对于1，直接判断两者大小然后看扩展与否即可，可以使用vector中的reserve函数来预定原大小的一倍
对于2，由于directory的指向是与global depth有之间关联的（看IndexOf函数可以得出），因此对于未扩展之前的directory其最低global depth个位应当是一一对应的，扩展后directory大小翻了一倍，即新出现的directory与原directory中对应的最低global depth位应是相等的，变化的只有前面的一个最高位0/1，因此新扩展后的directory直接按需指向前面对应directory的Bucket即可
对于3，分裂时可以新建两个Bucket，比较两者不同的思路与2基本相同，只是将global depth换成了local depth，之后分配directory指针即可

LRU-K Replacement Policy

定义

在基础的LRU算法中，每次都是对最近最久未使用页面进行替换出去。但倘若一个短时间内有一个很长的访问序列到来且使用这一次，将原本可能会常用的缓存给替换了出去，进而会影响到后面的缓存击中率，这就是缓存污染问题。
为了解决这一问题，LRU-K出现了，它的思想是对于最近最久第K次未使用页面替换。感觉解释起来有点抽象，其实其本质就是对于未访问到K次的元素，有替换需求时直接用**FIFO**换出去；达到K次的元素缓存起来，根据**LRU**换出去。

实现细节

本来我打算使用优先队列对其进行实现，但过程中我发现C++中的优先队列尤其难用，遂使用一个历史队列（存未到达K次的元素）和一个缓存队列（存到达K次的元素）来实现，其中为了避免每次找对应frame_id时都需要对两个队列进行遍历，这里定义了一个map用来映射frame_id到frame之间的关系：

1
2
3
4
5
6
7
8
9
10
struct FrameEntry {
	size_t access_history_{0};
    bool is_evictable_{true};
    std::list<frame_id_t>::iterator pos_;
	FrameEntry() = default;
};

std::list<frame_id_t> history_queue_;
std::list<frame_id_t> cached_queue_;
std::unordered_map<frame_id_t, FrameEntry> entry_map_;

这里比较坑的应该是抛出异常时，如果直接throw加字符串异常信息的话，autograder里面会报”Subprocess aborted Exception”，我这里使用了std::invalid_argument来处理异常。
此外，当使用iterator遍历时，如果需要删除对应的iterator，记得使用std::next或者it++以防止出现use after free这种低级错误。（唉，留下了不熟悉C++的眼泪）

Buffer Pool Manager Instance

定义

关于buffer pool的定义，其可以简单理解为一个管理内存和磁盘之间数据流动的媒介。这里我更倾向于关注为什么要使用buffer pool而不是mmap，Andy在课上狂喷mmap并且在2022年出了一篇paper详细讲述为什么不要使用mmap的原因，后面抽空读一下再写（给自己挖坑- -!）

实现细节

这一节的实现主要是将上面实现后的两部分结合起来，因此在写这个部分之前我强烈建议先去autograder把前面两个完全通过再写（因为本地测试案例实在是太少了！而且测试用例还不开放>_<）
理解其中一部分变量的定义会更方便实现，free_list_是保存buffer_pool中可用的frame_id；pages_是实际存放frame的地方（不懂的话见之前buffer pool笔记）；page_table_保存了page_id到frame_id的映射，方便通过page_id找到对应的frame。
这一部分在实现过程中有小坑，比如：

  • NewPgImp中，如果失败要记得给page_id返回nullptr
  • 调用replacer时先RecordAccess再SetEvictable（可能是我实现方式的问题？这个地方我debug了好久）
  • UnPinPgImg中，如果page原先是dirty的话是不能将其变成非dirty的
  • DeletePgImg中，如果page是脏的则需要先写到disk上再进行metadata的重新设置

感受

相比于Project 0，Project 1的难度和复杂度立马上来了。不同于网上2-3天做完的大佬，我个人大概花了4-5天的时间完成，又花了3-4天debug，一度让我想放弃，不过最终还是磨了下来。听说接下来的B+树更是噩梦，那就走着瞧吧～

[参考资料]