cmu15445 2022fall lab1 Buffer Pool

此project实现一个buffer pool，缓存住磁盘查询的数据。

Task1

这部分需要我们实现一个可扩展的哈希表，这部分的难点在于插入操作时的分裂，由于Remove不需要我们将目录和桶收缩回去，所以它也很简单。

先分析清楚目录和桶的结构。

我们可以先实现简单的部分，Find，Remove，以及对桶的Find、Remove、Insert，这几个函数都非常简单，查看一下对应类的成员变量就行了，需要注意的是对桶的insert，如果满了直接返回false即可。

然后就是Insert函数。

1. 首先根据索引找目录项对应的桶，插入成功直接返回，插入失败进入下一步
2. while循环判断应该插入的桶是否满，因为有可能分裂并重分配节点后还是满的，需要再次分裂
3. 如果桶的深度不等于全局深度时，可以不需要分裂，而是增加一个目录项，这个我们后面再说，先说分裂的步骤
   • 全局深度加1
   • 目录翻倍，即复制一份到目录的后面
4. 记录一下之前插入桶的深度（用于后面寻找兄弟目录），并将深度加1，再创建一个深度一样的桶
5. 寻找兄弟目录（它们是指向同一个桶的目录，他们的低位是一样的，低位的长度就是之前记录的深度），因为深度增加之后它们的更高的一位就会不一样，把高一位为1的那个目录指针指向新的桶。
6. 之后重新分配之前插入桶中的节点，重分配的方法就是把每个值删掉，重新插入，因为目录项已被我们修改，所以插入之后就会得到想要的结果。
7. 之后再尝试插入节点，失败的话就会到第二步，需要再次分裂

• 我们再讲一下刚刚第3步说的不需要分裂的情况，上述过程我们发现复制出来的目录指针，每次只会重新添加一个桶，所以还有很多指针是指向同一个桶的，那门当我们插入那种桶满时，可以不要分裂，而是只添加一个桶即可。

• 步骤有点复杂，我们梳理一下，插入桶->分裂/不分裂->创建新桶->重新分配目录项->重新分配桶内节点->再次尝试插入，基本就是这样，处理好细节即可。

Task2

这部分需要我们实现一个LRU-K算法的替换器，用于buffer满时替换frame。

面试常见的LRU算法一般使用双链表+哈希的写法，这里的LRU-K需要维护两个序列，虽然也可以使用双链表+哈希，只需要在中建添加一个哨兵节点即可，效率肯定更高，但为了写代码方便，我直接使用一个哈希表来实现，创建一个FrameInfo多记录一些信息即可，偷个懒。

LRU-K 算法相比 LRU 算法的优势在于它考虑了元素的使用频率，从而更加精细地选择淘汰缓存中的元素。

这部分实现非常简单。

Task3

NewPgImp

1. 判断是否有freelist
   • 如果有：则拿出freelist中的新的frameid
   • 如果没有：则判断是否可以将Pages腾出一页
     • 如果可腾出：则判断腾出的页是否为脏页
       • 如果是脏页：则写回数据至磁盘，置dirty为false，清空页memory，将页的<pageid,frameid>从哈希表中移除，将页的lru记录清除
       • 如果不是脏页：则清空页memory，将页的<pageid,frameid>从哈希表中移除，将页的lru记录清除
     • 如果不能腾出：返回nullptr
2. 记录这个新页的访问记录，置framei的evict位为false
3. 分配新的页id，将映射关系插入哈希表
4. 设置新页的元数据（pgid,pin_count,id_dirty,memory）

FetchPgImp

1. 先寻找页，找到了的话，设置一下replacer_的信息，还有page的pin_count
2. 判断是否还有空闲页，如果没有，换出一个页并刷脏，清除page_table_和 replacer_的记录，进入下一步；有空闲时拿出空闲页id进入下一步
3. 设置新的replacer_和page_table_记录，同时调用disk_manager从磁盘读出一个所需页。

FlushPgImp， FlushAllPgsImp，UnpinPgImp

这三个比较简单，unpin时记得当pin_count为0时设置页状态为Evictable。

DeletePgImp

• pin_count >0时不能删除
• 脏页记得刷脏
• replacer_和page_table_记录删除
• 调用DeallocatePage

Summary

project1在很久之前就做完了，当时忘记写博客了，重新回忆并记录一下。