CMU 15-445 数据库系统 实验

发表于 更新于 分类于 阅读次数： 本文字数： 759 阅读时长 ≈ 3 分钟

#Project 0 - C++ Primer

简单的 C++ 语法练习，略过。

#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(GD−LD)2^{\left(\text{GD}-\text{LD}\right)} 个 entry 指向。

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

#初始状态

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

#插入算法

#算法逻辑

  1. 根据插入元素的 hash 值；

  2. 根据Header定位到Directory，如不存在则创建；

  3. 根据Directory定位到Bucket，如不存在则创建；

  4. 遍历Bucket，如果元素已存在则直接结束；

  5. 检查Bucket是否装满，如果不满则直接插入到当前Bucket中，结束；

  6. （桶装满）比较Bucket的Local Depth (LD) 和 Global Depth (GD)；

  7. 如果LD == GD，如果Directory已经达到最大深度，结束；否则拓展Directory，GD += 1，重新定位Bucket Entry；

  8. 如果LD < GD，说明该桶包含了多个entry的元素，且元素的最后LD位是一样的：进行分裂操作，将这个Bucket拆分成两个，元素按照1<<(LD)位分散到两个桶中；然后根据entry的最后LD位，更新一半的entry指针到新的Bucket上；

  9. 如果当前Bucket仍是满的，回到第 6 步；

  10. 在当前Bucket中插入元素，结束；

#示例 1：两次目录拓展

原状态：

插入…1001，目录拓展：

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

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

#示例 2：指针更新

原状态：

插入…010：

原来的桶(...010)从...0变成...10，LD改变1->2；新创建的桶(...000)保存...00，LD=2； Entry ...000和...100被驱逐到新的桶中：

#删除算法

#坑点

计算哈希值要调用Hash()而不是hash_fn_.GetHash()。

#Project 3

#Project 4