CMU 15-445 数据库系统实验

发表于 2024-05-03 分类于 learning-notes ， database-system 阅读次数：本文字数： 749 阅读时长 ≈ 3 分钟

#Project 0 - C++ Primer

#Project 1 - Buffer Pool Manager

#基础知识

关于future，promise的使用参见 C++并发查漏补缺。

#优化：减小锁范围

在拿到Page之后，我们可以释放BPM自身数据结构的锁，只要保证不会有其他操作同样的Page即可。

需要注意的是，Page本身的锁是是保护Page内容用的（而不是Page的元数据），在Project 1，由于其他部分的代码没有使用它，因此可以直接复用Page本身的锁，但是到Project 2就会出问题。

因此最好在BPM里面维护单独的Page锁。

#优化：workload区分

#优化：lock-less队列

#优化：多线程读写

#优化：块缓存

每个Worker带一小块缓存，尽可能减少对OS的调用。

缓存使用LRU-K策略替换。

#Project 2 - Hash Index

任务二的目标是在前面实现的换页基础上，实现一个三级可拓展哈希表。

#可拓展哈希表结构

右侧的数字是每个Bucket的Local Depth，表示该桶内的元素最多有多少个bit是一致的。

简单推论：

如果GD = LD，则一定只有一个entry指向当前bucket；
如果GD< LD，则当前bucket被 $2^{\left(\text{GD}-\text{LD}\right)}$ 个entry指向。

Header是 Project 相对于课本增加的内容，Header按照 Most Significant Bits 预先对Directory进行一次分区，目的是增大整个系统的并发度，对主要逻辑影响不大。

#初始状态

初始状态下，Directory和Bucket均不存在：

#插入算法

#算法逻辑

根据插入元素的hash值；
根据Header定位到Directory，如不存在则创建；
根据Directory定位到Bucket，如不存在则创建；
遍历Bucket，如果元素已存在则直接结束；
检查Bucket是否装满，如果不满则直接插入到当前Bucket中，结束；
（桶装满）比较Bucket的Local Depth (LD) 和 Global Depth (GD)；
如果LD == GD，如果Directory已经达到最大深度，结束；否则拓展Directory，GD += 1，重新定位Bucket Entry；
如果LD < GD，说明该桶包含了多个entry的元素，且元素的最后LD位是一样的：进行分裂操作，将这个Bucket拆分成两个，元素按照1<<(LD)位分散到两个桶中；然后根据entry的最后LD位，更新一半的entry指针到新的Bucket上；
如果当前Bucket仍是满的，回到第6步；
在当前Bucket中插入元素，结束；

#示例1：两次目录拓展

原状态：

插入…1001，目录拓展：

桶分裂，但是仍然空间不足：

再次拓展目录，成功插入：

#示例2：指针更新