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元组

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方便进行数据表元信息的查询：

public class Catalog {
    private ConcurrentHashMap<Integer, DbFile> tableMap;
    private ConcurrentHashMap<Integer, String> idMap;
    private ConcurrentHashMap<String, Integer> nameMap;
    private ConcurrentHashMap<Integer, String> keyMap;
}

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

public Page getPage(TransactionId tid, PageId pid, Permissions perm)
       throws TransactionAbortedException, DbException {
       // some code goes here
       if (!this.buffer.containsKey(pid.hashCode())) {
           // find the right page in DBFiles
           DbFile dbFile = Database.getCatalog().getDatabaseFile(pid.getTableId());
           Page page = dbFile.readPage(pid);
           if (buffer.size() > numPages) {
               evictPage();
           }
           buffer.put(pid.hashCode(), page);
       }
       return this.buffer.get(pid.hashCode());
   }

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方法的实现代码如下：

public Page readPage(PageId pid) {
       // some code goes here
       byte[] data = new byte[BufferPool.getPageSize()];
       int startPosition = pid.getPageNumber() * BufferPool.getPageSize();
       try {
           RandomAccessFile randomAccessFile = new RandomAccessFile(this.file, "r");
           randomAccessFile.seek(startPosition);
           randomAccessFile.read(data, 0, data.length);
           return new HeapPage((HeapPageId) pid, data                                               );
       } catch (FileNotFoundException e) {
           e.printStackTrace();
       } catch (IOException e) {
           e.printStackTrace();
       }
       return null;
   }