CMU15-445 PROJECT #1 - BUFFER POOL

前言

终于来到了Project #1 了，这次是要实现三个组件，分别是 Extendible Hash Table, LRU-K Replacement Policy, Buffer Pool Manager Instance。个人感觉，LRU-K Replacement Policy 的实现比较自由，需要自己编写一些额外的内容。另外两个组件的大致框架以及内置的一些变量都已经写好了，只需要实现对应的函数即可。三个组件中，分别都有一个比较细节或者不那么trival的地方（至少我感觉是这样的）。第一个哈希表比较卡壳的地方就是Insert，第二个替换策略比较细节或者说自由的地方就是如何记录时间戳。第三个缓冲池管理组件中，就是按照函数的brief中的内容按部就班写了。由于再写这篇博客的时候gradescope中non cmu课程的对应lab还没开放测评，因此我这里只过了本地评测，可能并不是完全正确，特别是在并发这方面。对于并发，我直接一把大锁保平安了，遇事不决，一把大锁。至于如果之后在线评测的时候TLE了的话，那就只能拆分锁了。

工业革命

这次debug用上了船新的lldb+vscode，体验是真的不错，比自己手动debug效率提高了好多好多。具体看博文：https://www.cnblogs.com/alyjay/p/16709127.html

Extendible Hash Table

实现细节以及一些思考

1. 对于key是从高位取比特还是从地位开始作为dir的index

   在已经实现的IndexOf函数中，取的是地位比特作为index。为什么取低位而不是高位呢？比如有一批key，范围从0到1000，那么其高位全为0，低位不相同，所以这里取低位比特更容易将所有key分散到不同的bucket中，而不是挤在一个bucket中从而导致全局深度以指数级速度爆涨。但是key如果不是整数，而是某种特殊的编码，比如身份证号，高位表示省份等信息，低位表示个人信息，在这种情况下说不清是取高位还是低位，各有优劣吧。奇思妙想一下，是否有可能将高位和低位组合起来。

2. insert，bucket分裂以及global深度增加细节

   • 对于bucket分裂，我们迫切需要的就是找到其兄弟索引。在这里，兄弟索引指的是在全局深度的限制下，仅最高位bit与自身不同的index即为兄弟。比如索引001011101的兄弟就是索引101011101。也就是0的兄弟是1，1的兄弟是0。这就呼之欲出了，直接上异或即可，mask的最高位为1，其余位为0。公式如下。分裂之后将新的索引项指向新创建出来的bucket即可。

     idx ^ (1 << (global_depth_ - 1))
     

   • 对于全局深度的增加，也就是索引项增加了一倍。假设增加后的索引数量为2n，那么我们只需要将n到2n-1对应的索引指向其兄弟索引指向的bucket即可。
   • 对于插入，使用while循环不断尝试插入，直到插入成功为止。由于重新hash也要使用插入函数，因此这里存在一个递归的操作，这比较影响并发。我在这里分别实现了一个带lacth和不带latch的Insert函数，带latch的调用不带latch的实现递归。

测评结果

LRU-K Replacement Policy

实现细节以及一些思考

1. 如何记录Frame的metadata、

   在LRUKReplacer类中创建了一个辅助类FrameMeta。

2. 用什么来保存key到value的映射信息

   其实是可以用咱们上面自己实现的hash表的，但是因为上面的哈希表没有实现收缩功能，因此对内存压力比较大。因此我用的unordered_map。在这里也有trade off。我觉得access的次数坑定是要远远大于换页的操作的。原本我想采用优先队列实现，因为优先队列在换页的情况下O(1)的时间复杂度就能找到需要换出的页，但是要更新页时间戳的话需要O(N)去遍历查询。由于查询更新操作数量必定远远大于换页操作，因此在这种wordload下，采用unordered_map我觉得是非常好的。

3. 用什么来存储时间戳信息

   我使用了一个循环数组（或者说循环vecotr）来存储时间戳。数组大小为K。如果数组元素小于k，那么表示这个还没达到k次access，直接返回timestamps[0]即第一次访问的时间戳即可。如果大小超过或者与k相同，那么返回timestamps[(cur+1)%k]即可。其中cur为上一次访问的时间戳索引。(cur+1)%k必定为前K次的访问时间戳的索引。

评测结果

Buffer Pool Manager Instance

实现细节以及一些思考

• 没啥细节，细节就是建议画个流程图。步骤有点复杂，不画流程图可能会漏情况。（我就因为没画，debug了1小时）。

评测结果

总结

这次lab内容确实是比lab0要多了一些，但是难度可能还稍微有点下降了。毕竟lab0还有一些c++11标准的相关特性以及标准。不过也有可能是因为在线测评没开放，我只过了local test，可能还有没踩到的坑。后续在线测试更新了再来跟新这篇博客吧。（感觉并发要杀我，我全用的大锁保平安大法）