CMU 15-445 数据库系统 实验记录

发表于 更新于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 6 分钟

以下 Project 内容均基于 Fall 2023 的版本。

#Project 0 - C++ Primer

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

#Project 1 - Buffer Pool Manager

Project 1 要求实现 DBMS 最底层的组件之一 —— Buffer Pool Manager (BPM)，BPM 是对数据库所在的物理存储的抽象。在 DBMS 中，底层物理存储被抽象为一个包含巨量 4KB 大小页的持久数组，DMBS 的上层抽象，例如 B 树、哈希表结构 和数据库中实际保存的数据就持久化在这样的物理存储上。

然而，按照冯诺依曼架构，CPU 想要操作物理存储并不是一件轻松的事情，以 POSIX 文件接口为例，需要先open打开文件，然后seek移动到正确的位置，才能read/write需要的数据。更坏的是，我们想要读或者写的数据往往非常复杂，需要先加载到内存中，进行一定的计算和分析，才能真正执行读写操作。

BPM 组件就是为了简化这些细节，它提供了换入换出某个物理页的接口，能够自动管理内存和不需要的物理页，方便上层使用。

#基本实现

#Task 1 - LRU-K

LRU-K 是 LRU 算法的一种变体，与原版 LRU 算法相比，在淘汰时，LRU-K 算法会衡量每个数据条目的倒数第kk 次被访问的时间，按照这个时间去淘汰最久的元素。

Bustub 的 BPM 使用了 LRU-K 算法来管理物理页，需要注意的是，BPM 还需要允许pin住某个页面不被换出。

LRU-K 最优的算法实现之一是使用两条链表，一条链表保存访问未达到 k 次的元素，另一条保存访问 k 次的元素。记录时，正常记录元素访问历史，如果是元素是首次被访问，则插入到第一条链表尾；如果满 k 次访问，则移动到第二条链表尾。淘汰时，先从第一条链表中淘汰，若第一条链表没有元素，或者所有元素都被锁定，则再从第二条链表中选择最近 k 次访问的时间最小的元素淘汰。

#Task 2 - Disk Scheduler

由于磁盘的一些奇特性质（比如需要实际的寻道过程，顺序读写比随机读写快等），合理调度磁盘请求往往可以获得更高的性能。

Disk Scheduler 是 BPM 和实际物理存储的中间层，负责直接和磁盘打交道。 BPM 的读写硬盘请求会被发送给 Disk Scheduler 异步执行，两者通过 std::promise 交互。

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

这部分调度算法和操作系统的文件管理类似，常用的算法例如电梯算法等。

#Task 3 - Buffer Pool Manager

Task 3 基本上是把 Task 1 和 Task 2 合理地组装起来，加上一些 RAII 和锁机制，形成 BPM 的接口。

#优化：减小锁范围

在拿到 Page 之后，我们可以立即切换到 Page 级别的细粒度锁，释放 BPM 的大锁，只要保证不会有其他线程操作同样的 Page 即可。

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

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

#优化：workload 区分

BufferPoolManager::UnpinPage 接口传入了当前页访问的模式，可以是 Lookup、Scan、Index三种。 BPM 可以根据这个信息做未来页面的预测。

在 LRU-K 中，当元素被首次访问，而且访问模式是 Scan，可以把元素插入到第一条链表头而非链表尾，使之更快被淘汰。

#优化：多线程 I/O

在 Disk Scheduler 中开一个线程池，每个线程开一个单独的任务队列。收到的 IO 任务按照块号分派到任务队列中。

Bustub 中提供了 Channel 类可以使用。

#优化：块缓存

每个 Worker 带一小块页缓存，读写的时候如果缓存中的内容是有效的，就进行 memcpy，尽可能减少对 OS 的调用。

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

#Project 2 - Hash Index

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

#可拓展哈希表结构

每个 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；

  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 - Query Execution

Project 3 的目标是实现几个数据库的 Executor。

#Project 4 - Concurrency Control

Project 4 要求实现基于 MVCC 的事务并发控制。