MIT6.830-lab1：SimpleDB Overview

这是MIT6.830Database Systems课程的Project实现记录，这门课的内容和常见的数据系统课程基本一致，而课程Project是用Java实现一个名为SimpleDB的简单数据库系统，一共有6个lab

Overview

和CMU15-445类似，MIT6.830也有一个课程Project需要自己实现一个数据库系统SimpleDB中的关键部分，和15-445的Bustub类似，SimpleDB也被分成了若干个模块，包括

  • 通用的数据库管理模块，如Catalog和Database，复杂管理整个数据库中的信息
  • 数据的存储模块，从底层开始实现了数据库的基本单位tuple的存储
  • 查询的执行模块和优化模块
  • 索引模块，主要实现了B+树索引来加速查询
  • 事务处理模块，实现了数据库的事务的抽象

而我们要在6个lab中实现的东西有：

  • lab1，对整个SimpleDB有大致的了解，并且实现其中数据存储相关的类，然后还有一些其他东西比如Catalog和SeqScan
  • lab2，实现查询处理中的各种算子
  • lab3，实现查询的优化相关的功能
  • lab4，实现事务处理的相关功能
  • lab5，实现B+树索引
  • lab6，实现回滚和恢复等功能

下面我们就要正式开始lab1的内容

SimpleDB存储模块的架构

lab1的前几个任务需要我们实现SimpleDB中存储模块的关键内容，我们可以先根据实验指导和源代码来分析一下SimpleDB存储模块的结构。我们知道数据库中的数据表是用页(Page)为单位进行存储的，每个页中包含了若干个元组(Tuple)，同一个数据表中的元组具有相同的定义(即一条数据包括哪些属性)，我们先来分析一下SimpleDB里的元组是什么设计的。

Tuple元组

MIT6.830-lab1：SimpleDB Overview - 图1

SimpleDB中的一个元组主要有三个部分组成，TupleDesc负责描述元组每一栏数据的名称和类型，RecordId是元组的ID，通过页号PageId和元组在页内的偏移量TupleNum生成，Field数组负责存储具体的数据，顺着这个思路，我们可以实现下面几个文件中的内容

  • src/java/simpledb/storage/TupleDesc.java
  • src/java/simpledb/storage/Tuple.java
  • src/java/simpledb/storage/RecordId.java

比较简单就不贴代码了。

Catalog/Buffer目录和缓冲区

Catalog类起到的作用相当于数据库的目录，记录了数据库中有哪些数据表，每个数据表对应的ID、数据文件、主键是什么东西，并定义了一系列增删查的方法，同时Database类中会有一个Database.getCatalog()的静态方法来访问整个数据库的Catalog，一个数据表要加入Catalog的时候，参数包括数据表的文件(可以获得数据表的id)，表名以及主键的名字，因此可以设置下面这样4个HashMap方便进行数据表元信息的查询：

  1. public class Catalog {
  2.     private ConcurrentHashMap<Integer, DbFile> tableMap;
  3.     private ConcurrentHashMap<Integer, String> idMap;
  4.     private ConcurrentHashMap<String, Integer> nameMap;
  5.     private ConcurrentHashMap<Integer, String> keyMap;
  6. }

另一个很重要的类是BufferPool，它负责管理SimpleDB保存在内存中的页的信息，因为内存不可能无限大，所以我们需要在一个指定大小的Buffer中保存一定数量的数据页，并在Buffer容量达到上限的时候进行页的置换，不过lab1不需要我们管这些，我们要做的就是实现一个方法getPage()，它的实现逻辑也非常简单，就是根据输入的页号在buffer存储页的HashMap中进行查询，如果这个页不存在就调用Database.getCatalog().getDatabaseFile这个方法把对应的页去读出来，这一段的代码如下：

  1.     public Page getPage(TransactionId tid, PageId pid, Permissions perm)
  2.         throws TransactionAbortedException, DbException {
  3.         // some code goes here
  4.         if (!this.buffer.containsKey(pid.hashCode())) {
  5.             // find the right page in DBFiles
  6.             DbFile dbFile = Database.getCatalog().getDatabaseFile(pid.getTableId());
  7.             Page page = dbFile.readPage(pid);
  8.             if (buffer.size() > numPages) {
  9.                 evictPage();
  10.             }
  11.             buffer.put(pid.hashCode(), page);
  12.         }
  13.         return this.buffer.get(pid.hashCode());
  14.     }

HeapFile堆文件

SimpleDB中的数据有两种组织方式，一种是堆文件Heap File，即无序存放，另一种是B+树，是有序的索引，我们首先要来实现Heap File的存放方式，在SimpleDB中，一个Heap File包括了一系列页，称为Heap Page，而每个页能存储的数据量是固定的(默认设定为4096KB)，在磁盘中这些Heap File就以无顺序的方式存放，需要用的时候以页为单位读入内存中就行。

同时Heap Page中除了要正常存放元组的数据，还要用一些位置来标注每一条记录是不是有效的，这种方式称为Bit Map，每个元组对应1bit的位置，因此1B的位置可以标注8个元组，因此每个Heap Page中能存放的页的数量需要通过下面的方式计算：

  • tuples per page = floor((page size * 8) / (tuple size * 8 + 1))

同时用来标记页中每条记录是否有效的Bit Map被称为页的头部，因此页头需要的字节数量就是ceiling(tups per page/8) ，我们可以根据这些要求来实现下面三个文件中的代码：

  • src/java/simpledb/storage/HeapPageId.java
  • src/java/simpledb/storage/RecordId.java
  • src/java/simpledb/storage/HeapPage.java

其中HeapPage有个方法isSlotUsed()要根据给定的下标判断一个元组是否有效，这时候就要通过位运算取出页头中对应位置的标记，然后判断是不是1(通过和1作And操作可以实现)

在实现了Heap Page的结构之后，我们进一步需要实现Heap File的结构，Heap File中直接保存了File形式的数据文件和元组的元信息TupleDesc，其中一个关键的方法就是根据给定的页号来读取File中对应的Page，这需要通过Java提供的文件随机访问API实现

  • 补充一点操作系统的知识，文件的两种访问方式是随机访问和顺序访问，随机访问就是可以从文件的任何一个字节开始向下读取，而顺序访问就是必须从文件头开始读
  • 这里的readPage方法的实现代码如下：
  1.     public Page readPage(PageId pid) {
  2.         // some code goes here
  3.         byte[] data = new byte[BufferPool.getPageSize()];
  4.         int startPosition = pid.getPageNumber() * BufferPool.getPageSize();
  5.         try {
  6.             RandomAccessFile randomAccessFile = new RandomAccessFile(this.file, "r");
  7.             randomAccessFile.seek(startPosition);
  8.             randomAccessFile.read(data, 0, data.length);
  9.             return new HeapPage((HeapPageId) pid, data                                               );
  10.         } catch (FileNotFoundException e) {
  11.             e.printStackTrace();
  12.         } catch (IOException e) {
  13.             e.printStackTrace();
  14.         }
  15.         return null;
  16.     }

另一个很重要的需要我们实现的东西叫做Heap File的迭代器，我们在实现Heap Page的时候就已经实现了Heap Page的迭代器，这个迭代器会遍历页内的每一个元组，而Heap File的迭代器需要能够遍历整个数据表文件中所有的页的所有元组，我们的实现策略是：

  • 对于每一个特定的页，调用Heap Page的迭代器来完成任务
  • Heap File中维护的迭代器会在访问完一整个页之后自动切换到下一个页，这样就可以实现一页一页的访问

因此在实现的时候，我定义了一个方法getTupleIterator来实现Page Iterator的更新。

SeqScan

lab1的最后，我们要实现一个顺序扫描的运算符，实际上就是要实现一个能够实现顺序扫描的迭代器，我们上面实现的Heap File迭代器就可以直接调用，在SeqScan这个类中再封装一层就行，其他的没什么东西，无非就是多加了一些其他的属性以及get方法。