MIT 6.830 数据库实验 Lab 1 实验报告

发表于 2022-11-16 更新于 2022-11-29 分类于后端，数据库阅读次数：本文字数： 2.8k 阅读时长 ≈ 5 分钟

摘要

最近开始学数据库了，找到了 MIT 6.830 的 Lab，感觉质量还挺高的。打算从实现上了解下数据库的细节。MIT 6.830 的实验要求使用 JAVA 语言实现一个简易的关系数据库，支持常用的增删改查操作、事务、B + 树索引、恢复等功能。这次我分享下 Lab 1 的一些总结。我把课程资料也附在了后面，有兴趣一起学习的一起来学习讨论～

整体架构

代码主要分为以下几个目录：

common: 定义公用的类：Database、Catalog，其中 Database 提供了静态方法访问 Bufferpool、Catalog 的单例
execution: 定义了数据库操作符的 OpItertor 接口，支持 scan、filter、aggregate、join 等操作
index: B + 树索引
optimizer: 查询优化
storage: 数据库的存储，定义了 Tuple、Record、Field 等基础概念类，以及 Heap File 存储
transaction: 事务

后面的 6 个 lab 会逐渐地实现这些功能，在第一个 lab，只需要实现一些存储逻辑。

Exercises

Field & Tuple

这部分要求实现基础的 Field、Tuple 类的功能，具体包含 TupleDesc 和 Tuple 两个类。

先介绍一下 Field，SimpleDB 支持两种数据类型：整数与定长字符串，两种类型定义在枚举类 Type 中，对应的 IntField 和 StringField 实现了 Field 接口，可以同种 Field 相互比较。仅有定长类型简化了数据库模型。

TupleDesc 是每个数据库表的元组描述，包含若干个字段，简单来说，就是一个 (Type, Name) 的数组，记录了每个字段的类型和可为字段的域名。这个类中主要要实现构造函数和一些 get 方法，比较简单。值得注意的是这里要实现一个静态的 Merge 方法，用于将两个 TupleDesc 对象合并，在后面的 join 操作时会用到。

Tuple 是一条元组，由一个 TupleDesc 构造而成，包含了一个 Field 的数组存储各个字段的值。其中，每个 Tuple 关联一个 RecordId，为该元组在表的索引 id，由页号 + 页内偏移完成，这里只需要实现 get、set 方法，recordId 后面会用到。

Catalog

Catalog 用于追踪数据库中的所有表，提供了方法用于新建和删除表。正常来说，Catalog 应该从磁盘加载，但是在这个 lab 不需要考虑序列化和加载的逻辑，只需要实现启动后的数据库表的管理逻辑。每个数据库表包含以下几个信息：

表名：一个字符串
文件：一个实现了 DbFile 的文件对象
表的 id：由文件对象唯一对应，一般是绝对路径的 hashcode
主键：一个字符串，SimpleDB 只考虑单一主键
元组描述，一个 TupleDesc 对象

Catalog 类还提供了一个已经实现的 loadSchema 方法，用于从文件中读取数据库的模式并新建表。

BufferPool

BufferPool 类定义了一个统一的、具有缓存的页面读取方法。一般来说，操作一个页面需要先将其从磁盘加载到内存中，然后才能操作。BufferPool 定义了一个缓存区，当页面已经被加载到内存后，就无需再次加载了。这里后续需要实现一个类似 LRU 的页面调度算法，在本次 lab 中尚不需要。

本 lab 中，BufferPool 需要实现一个 get 页面的方法，当缓存区满时，只需要抛出 DbException 异常即可。这里需要根据 PageId 获取 table id，进而通过 Catalog 获取表进而读取。

HeapPage

这个 Exercise 要实现 HeapFile 的读取方法，包含 HeapPage, HeapPageId, RecordId 三个类。其中，RecordId 类的功能已经在上面介绍，是每个元组在表中的唯一的记录 id，包含 PageId 和在页内的编号。HeapPageId 实现了 PageId 接口，包含一个表 id 以及页面号，与 RecordId 类似。这两个类都比较简单，只需要实现一些 get、equals, hashcode 方法即可。

HeapPage 是 HeapFile 的页面类，实现了 Page 接口，需要支持获取页面数据、脏位标记等功能。这里先简单介绍下 HeapFile，这是一种无序的存储格式，记录以乱序的方式存储在页面中。每个页面由若干个插槽（slot）组成，每个 slot 可用于存储一条记录，页面首部包含一个 bitmap 记录每个 slot 是否包含记录。在插入记录的时候，找到一个空的插槽插入即可。

对于定长记录的表，这里就已经很圆满了。而对于非定长的表，页面内的 slot 数量是可变的，slot 的大小也是可变的。这时，需要在页面尾部记录插槽的位置、大小、数量，还要保存已经有的记录的位置和大小。放在尾部，是因为这样可以方便地增长 slot 数量，当尾部和正向的记录重合时，就意味着页面满了。这种页面还需要周期性地重排一下，避免过多的碎片。当然，这些是题外话，SimpleDB 中不需要考虑这种复杂情况。

本次 lab 中，HeapPage 类需要实现查询槽位状态、计算空槽数量等功能，还要实现一个元组的迭代器。在按上面捋顺了 HeapFile 的原理之后，就很简单了。

HeapFile

这个类主要实现两个功能：

读取指定页面。值得注意的是，数据库文件可能很大，因此不能直接把整个文件加载到内存中，需要使用支持随机读写的 RandomAccessFile，移动指针到指定页面的位置，再进行读取。
返回一个可以迭代访问数据库所有元组的 DbFileIterator。值得注意的是，这个 DbFileIterator 需要支持重用，因此其不是一个传统的 Iterator，需要额外的代码来实现一个 DbFileIterator。我建议新建一个类继承自 AbstractDbFileIterator，其对接口的逻辑进行了一定简化。更好的方式是实现一个通用的适配器，把传统的 Iterator 转换成需要的格式。

SeqScan

最后一个 Exercise，实现表的遍历操作。这里包装一下上面的 HeapFile 的 Iterator 逻辑，实现 OpIterator 接口即可。这个新的 OpIterator 也需要支持重用，后面也会比较麻烦。这里还不需要担心，写完，通过单元测试就收工啦！

总结

这个 lab 主要是先熟悉了数据库的整体架构以及相互间的关联。之后，在底层实现 HeapFile 这一经典的文件存储方法，对于页面的读取和元组的存储有了更深的理解。最后，实现了一个数据库的遍历操作，简单了解数据库操作符的规范和接口，剩下的操作符需要在后面实现。

摘要