CMU15-445 - Project1 Buffer Pool
前言
我做的是 CMU15-445 2022年秋季版本，目前课程尚未完结，poject和 gradescope 也在慢慢开放中，目前我的进度到Project1 buffer pool，这篇总结一下我做这个实验的基本思路以及遇见的一些坑
首先说一下做这个实验的感受，这个实验大概拖了一个月才完成，中间半个月国庆摸鱼去了。。。大概花了40个多小时才写完，前面十几个小时其实已经写差不多了，最后20多个小时因为一个小bug导致卡了这么长时间，实验的文档和代码注释写的比较清晰了，可能就是前两个 task 涉及的知识点不熟悉的话，需要去网上找找相关资料，知道咋回事之后就没那么难
Task #1 - Extendible Hash Table
可以先参考一下这两篇文章大概弄清楚可拓展哈希的原理
后来我发现书上好像有这部分内容，刚开始没有书，只能参考博客了，后面去图书馆借了一本。因为也是最开始做的，过了好久了，具体细节也忘记了，这部分就略过吧
Task #2 - LRU-K Replacement Policy
经典的 LRU 在可以先去力扣做一下 146. LRU 缓存，基本思路就是双链表+哈希表，链表记录数据，哈希表记录数据存放在链表中对应的迭代器
LRU-K 的话，网上我看到的说法是用一个历史队列存放访问次数小于k的数据，当访问次数达到k的时候，将数据从历史队列移动到缓存队列中，缓存队列采用LRU算法进行淘汰
最开始我把历史队列也采取LRU策略进行淘汰，然后会发现有问题，仔细看看LRU-K的头文件关于 Evict 方法的描述
最后如果有较多超过 k-distance 的，替换出最早时间戳的 frame，其实就是根据入队列的先后顺序要替换，注意当一个 frame 再次被访问的时候，不需要改变 frame 在历史队列中的顺序，除非访问次数大于等于k，也就是说只需要根据 frame 第一次访问的时间进行 FIFO 替换即可
然后说一下我在这里遇见的一个bug，我是用链表+哈希表模拟队列（即上述的历史队列），这样就可以O(1) 的复杂度记录以及查找 frame 对应的位置，我遇见的问题是我用了一个迭代器从哈希表中查找 frame 的迭代器，然后在访问次数大于等于k的时候，先转移到缓存队列中，然后再删除历史队列的记录，删除的时候我先把哈希表中 frame_id 删除了，然后导致原来的迭代器失效了，我最后又去根据迭代器删除链表中的 frame，就导致删除一个未定义的位置！这个bug卡了我接近20h，开始的时候先在gradescope上面提交发现除了LRU-K通不过其他都能通过，然后我换了个方法实现LRU-K，结果buffer pool一直过不去，我又找了其他已经通过的小伙伴，把他的 buffer pool 拿了过来，发现还是不行，只能说明还是LRU-K有问题，最后回到之前提交的，一调试发现这个bug，这告诉我卡在一个地方的时候一定要进行调试，调试找到问题并解决之后再去做下一个任务，不然可能会花费大量的时间做无用功
Task #3 - Buffer Pool Manager Instance
刚开始做这个的时候没有搞清楚，page_id 和 frame_id 的关系，其实就是 page_id 对应的是磁盘中文件的下标（可以将磁盘抽象看出一个大的数组，page_id 就是数组的下标），而 frame_id 是 Buffer Pool 的下标，这两个很清楚再去看代码框架给的提示就很清晰了
可能会出问题的地方：
- Unpin 的时候，只有当 is_dirty 是 true 的时候才设置 page 的 dirty标记，如果为 false，不能直接设置，因为可能原来就是 true
- 创建一个新页和获取一个页面的时候都需要调用 replacer_ 的 RecordAccess 以及 SetEvictable 设置 frame 不可以被替换出
- 当替换出一个页面的时候如果是脏页需要将数据写回磁盘中
- LRU上锁的时候要在一开始就上锁，我写Remove的时候，把find函数写在锁外面了，导致测试时候出现data race的情况，原因是unordered_map本身也不是线程安全的，所以加锁的时候记得要加全局的
其他的感觉可能出现问题的地方比较少，前提是前面两个实现的没有问题（逃 ~）
小结
这部分前前后后加上调试总共花了41.5h，如果早点进行调试估计会少花一半的时间，不得不说调试真的很重要，另外就是多看看提示，很多可能出现问题的地方代码注释都写出来了
最后是完结证明：
写于：2022/10/12 总共实验用时大约41.5h
Data Race
Data Race是指多个线程在没有正确加锁的情况下，同时访问同一块数据，并且至少有一个线程是写操作，对数据的读取和修改产生了竞争，从而导致各种不可预计的问题。