MIT6.830 lab1 SimpleDb

2023-10-08 19:27:34

MIT6.830 lab1 SimpleDb

整个实验一共有6个lab，通过每一个lab的代码去实现一个简单的数据库，主要有：数据库的组织架构(字段、元组、模式、buffer pool等)、CRUD的实现、查询优化、事务与并发控制、崩溃与故障恢复。

SimpleDB consists of:

Classes that represent fields, tuples, and tuple schemas;

Classes that apply predicates and conditions to tuples;

One or more access methods (e.g., heap files) that store relations on disk and provide a way to iterate through tuples of those relations;

A collection of operator classes (e.g., select, join, insert, delete, etc.) that process tuples;

A buffer pool that caches active tuples and pages in memory and handles concurrency control and transactions (neither of which you need to worry about for this lab); and,

A catalog that stores information about available tables and their schemas.

lab1主要是实现了整个数据库的整体架构,主要有这几个部分：Tuple(元组)、TupleDesc(table的metadata)、catalog(该数据库并没有过度区分catalog和schema，可以看成是一个schema)、BufferPool(缓冲池)、HeapPage(数据页)、HeapFile(disk上的文件)、SeqScan(全表顺序扫描)。

lab1要完成：
1.Tuple：元组，数据库上把一个有n列的table称作n元组，一个Tuple有多个字段。通俗来讲，一条记录就是一个元组，在该实验中体现为一个Tuple类的实例。

2.TupleDesc：TupleDesc用来表示一个元组的描述信息，更准确来说应该是一个表的描述信息；

3.Catalog：Catalog是仅次于DataBase的抽象概念，一个DataBase可以有多个Catalog，一个Catalog有多个Schema，一个Schema有多张table。

4.BufferPool：BufferPool的基本单位是Page，每次从磁盘中(这里表现为DbFile)读取数据页到BufferPool，在数据库上的crud操作都是在Buffer Pool的Page中进行的(所以有脏页、故障恢复等)。该数据库的BufferPool默认是缓冲50个Page，每个Page的默认大小是4096bytes即4kb。

5.HeapPage与HeapFile：HeapPage是Page接口的实现，是以顺序逻辑组织数据的一张数据页(后续会用b+树实现来替代)，crud操作都是在Page上进行的。HeapPage既是BuffeerPool的基本单位也是HeapFile的基本单位。HeapFile是DbFile接口的实现，与磁盘中的文件交互，该数据中一张表的所有数据就是存到DbFile的File属性中，即一个磁盘的文件就是一张表的所有数据。

6.SeqScan：全表顺序扫描的实现，相当于select * from table.

Exercise1 Fields and Tuples

Tuples in SimpleDB are quite basic. They consist of a collection of Field objects, one per field in the Tuple. Field is an interface that different data types (e.g., integer, string) implement. Tuple objects are created by the underlying access methods (e.g., heap files, or B-trees), as described in the next section. Tuples also have a type (or schema), called a tuple descriptor, represented by a TupleDesc object. This object consists of a collection of Type objects, one per field in the tuple, each of which describes the type of the corresponding field.

1.Tuple：

元组，数据库上把一个有n列的table称作n元组，一个Tuple有多个字段。通俗来讲，一条记录就是一个元组，在该实验中体现为一个Tuple类的实例。一个Tuple由以下部分组成：a.TupleDesc：该元组的描述信息；b.fields：该记录各个字段的类型与值; c.RecordId：该记录在磁盘的位置。
Tuple.java：

Tuple构造函数：创建fields数组。
getTupleDesc()：返回当前tuple的TupleDesc结构。
getRecordId()、setRecordId：获得/设置当前tuple的RecordId，RecordId代表了当前tuple在disk上的位置。
setField(int i, Field f)：为fields数组下标i处的field赋新值。
getField(int i)：获得fields数组下标i处的field值。
fields()：返回一个迭代器，迭代此tuple内fields数组的所有元素。

2.TupleDesc：

TupleDesc用来表示一个元组的描述信息，更准确来说应该是一个表的描述信息，TupleDesc就是tuple的schema

TupleDesc.java：

class TDItem ：用于组织每一列的辅助类，包含fieldType和fieldName两个属性。
TupleDesc构造函数：创建一个TDItem数组，描述一个tuple包括哪些field。
numFields()：返回TDItem数组的大小。
getFieldName(int i)：返回TDItem数组中下标i的fieldName。
getFieldType(int i)：返回TDItem数组中下标i的fieldType。
fieldNameToIndex(String name)：遍历TDItem数组找到对应fieldName的下标。getSize()：遍历TDItem数组，求每一列fieldType大小总和。
merge(TupleDesc td1, TupleDesc td2)：把两个TupleDesc合二为一。
equals(Object o)：判断两个TupleDesc的列属性是否相同。

3.Field:

SimpleDB中元组中字段值的接口。

Field.java

serialize：将表示此字段的字节写入指定的DataOutputStream。
compare：将此字段对象的值与传入的值进行比较。
getType：返回此字段的类型(参见{@link type #INT_TYPE}或{@link type #STRING_TYPE})
hashCode：哈希代码。不同的Field对象可能代表相同的值返回相同的hashCode。

4.Type

在SimpleDB中表示类型的类。类型是这个类定义的静态对象; 因此，Type构造函数是私有的。枚举类实现了INT_TYPE 和 STRING_TYPE

Type.java

getLen：存储这种类型的字段所需的字节数。
parse：一个与该对象相同类型的Field对象，该对象的内容是从指定的DataInputStream中读取的。

5.总结

元组是非常基本的由"Field"对象的集合组成，在"元组"中每个字段一个。"字段"是不同数据类型（例如，整数，字符串）实现的接口。"元组"对象由底层访问方法（例如，堆文件或 B 树）创建。元组还具有一个类型（或架构），称为_tuple descriptor_(元组描述），由"TupleDesc"对象表示。此对象由"Type"对象的集合组成，元组中每个字段一个，每个对象描述对应的类型‎‎字段。

Exercise 2 Catalog

The catalog (class Catalog in SimpleDB) consists of a list of the tables and schemas of the tables that are currently
in the database. You will need to support the ability to add a new table, as well as getting information about a
particular table. Associated with each table is a TupleDesc object that allows operators to determine the types and
number of fields in a table.

The global catalog is a single instance of Catalog that is allocated for the entire SimpleDB process. The global
catalog can be retrieved via the method Database.getCatalog(), and the same goes for the global buffer pool (
using Database.getBufferPool()).

exercise2主要是实现Catalog.java这个类，这里的关键是在Catalog里实现一个Table类，来存放一张表格的信息；然后一个CataLog有多张表格，在Catalog里我们可以用map来存储tableid与table的映射关系,一个file对应一个table。

1.Catalog.java：

Catalog跟踪数据库中所有可用的表及其关联的模式。

目前，这是一个存根目录，在使用它之前，用户程序必须用表填充它——最终，它应该转换为从磁盘读取目录表的目录

class Table：为Catalog存储的一个个表建立的辅助类，Table类的构造函数需要三个参数，第一个参数是DbFile类型，是table的内容；第二个参数是String类型，是table 的name；第三个参数是pkeyField，代表表中主键的fieldName。
Catalog构造函数：创建一个<Interger,Table>的哈希表，用于存储已经实例化的表。
addTable(DbFile file, String name, String pkeyField)：在哈希表中添加一个Table。
getTableId(String name)：遍历哈希表中的Tables，找到对应名字返回table的Id。
getTupleDesc(int tableid)：返回tableid表对应的TupleDesc表结构。
getDatabaseFile(int tableid)：返回tableid表对应的表数据DbFile。
getPrimaryKey(int tableid)：返回tableid表对应的主键名。
getTableName(int id)：返回tableid表对应的TableName。
clear()：从Catalog中删除所有的tables。
loadSchema(String catalogFile)：利用正则化从file中读取表的结构，并在数据库中创建所有合适的表。

2.总结

Catalog是仅次于DataBase的抽象概念，一个DataBase可以有多个Catalog，一个Catalog有多个Schema，一个Schema有多张table，不过该数据库没有太过区分这三个概念，而在MySQL中也是用Schema来表示整个数据库包含的多张table。该lab中实现了一个Table类，并在Catalog类中使用一个HashMap来存放table id与table的映射关系。table 中的元素为file:表文件，name:表名，pkeyField:主键名。

Exercise3 BufferPool

The buffer pool (class BufferPool in SimpleDB) is responsible for caching pages in memory that have been recently read from disk. All operators read and write pages from various files on disk through the buffer pool. It consists of a fixed number of pages, defined by the numPages parameter to the BufferPool constructor. In later labs, you will implement an eviction policy(淘汰策略). For this lab, you only need to implement the constructor and the BufferPool.getPage() method used by the SeqScan operator. The BufferPool should store up to numPages pages. For this lab, if more than numPages requests are made for different pages, then instead of implementing an eviction policy, you may throw a DbException. In future labs you will be required to implement an eviction policy.

lab1无需实现淘汰策略，主要是实现getPage方法。根据PageId来查找BufferPool中有无该数据页，如果有直接返回，如果没有就从磁盘中获取，存入BufferPool中。其中BufferPool的容器是用map来存Page的，以pid的hashcode与Page建立映射关系。

1.BufferPool.java：

class Lock：为Transaction设置锁的辅助类，Lock类的构造函数需要两个参数，第一个参数是加锁Transaction的TransactionId；第二个参数是锁的类型（0 for shared lock and 1 for exclusive lock）。
class PageLockManager：管理基于页的加锁解锁所需的辅助类，创建一个<PageId,Vector>的哈希表，保存每页上拥有的锁集合。有三个内置方法，第一个是acquireLock(PageId pid,TransactionId tid,int lockType)用来加锁；第二个是releaseLock(PageId pid,TransactionId tid)用来解锁；第三个是holdsLock(PageId pid,TransactionId tid)用来判断是否有锁。
BufferPool(int numPages)：BufferPool的构造函数，创建一个BufferPool实例缓存最大numPages数量的Pages，通过<PageId,Page>类型的pageStore哈希表管理缓存pages。
getPageSize()：获得每个Page大小，默认是4096。
getPage(TransactionId tid, PageId pid, Permissions perm)：根据pid获取Page，如果在pageStore中，返回对应Page，如果不在就添加进哈希表，如果缓存的page数量超过缓存最大numPages数量，调用evictPage()淘汰一个页。获得page时在tid代表的Transaction上加锁，perm代表锁的类型，保证使用返回Page时的安全性。
releasePage(TransactionId tid, PageId pid)：调用 lockManager.releaseLock(pid,tid) 解锁。
holdsLock(TransactionId tid, PageId p)：判断特定Transaction是否在特定Page上加了锁。
transactionComplete(TransactionId tid, boolean commit)：如果commit，则调用flushPages(tid)将缓存中的页数据写入disk。如果没有commit，则调用 restorePages(tid) 回滚commit，重置pageStore中dirty的Page。
insertTuple(TransactionId tid, int tableId, Tuple t)：在BufferPool中添加特定的tuple到tableId对应的表中，调用DbFile的insertTuple(tid, t)方法（其中有一个读写锁），并将添加了tuple的page mark dirty。
deleteTuple(TransactionId tid, Tuple t)：从BufferPool中删除特定的tuple，调用DbFile的deleteTuple(tid, t)方法（其中有一个读写锁），并将删除了tuple的page mark dirty。
discardPage(PageId pid)：从BufferPool的缓存中删除pid对应的page。
flushPage(PageId pid)：将pid对应的Page从BuffePool的缓存中写入disk。
flushPages(TransactionId tid)：将tid下所有BufferPool缓存中的Page都写入disk。
evictPage()：当缓存的page数量超过缓存最大numPages数量，调用evictPage()淘汰一个页。先维护一个<PageId,Integer>类型的哈希表pageAge，根据Page载入cache的时间排序，淘汰缓存中最老的Page，当然这是最简单的一种实现，还有其他实现方式。

2.总结

BufferPool管理将页面从磁盘读写到内存。访问方法调用它来检索页面，它从适当的位置获取页面。

BufferPool也负责锁; 当事务获取页面时，BufferPool检查该事务是否具有读/写页面的适当锁。

lab1只需要实现getpage这一个方法且后续还需要不断地重构，因此比较简单

Exercise 4 HeapFile access method

对象被排列成一组页面，每个页面由固定数量的字节组成，用于存储‎‎元组（由常量定义），包括一个标头。在 SimpleDB 中‎
‎，数据库中的每个表都有一个对象（一个HeapFile对应一张表）。中的每个页面都排列成一组槽，每个‎‎槽可以容纳一个元组（SimpleDB 中给定表的元组大小相同）。除了这些槽之外，‎每个页面都有一个标头，该标头由一个位图组成，每个元组槽有一个位。如果与特定‎‎元组对应的位为1，则表示该元组有效;如果为 0，则元组无效（例如，已被删除或从未初始化过‎
‎。对象页是实现接口的类型。‎页‎‎存储在缓冲池中，但由‎‎HeapFile‎‎类读取和写入。‎HeapFileBufferPool.DEFAULT_PAGE_SIZEHeapFileHeapFileHeapFileHeapPagePage
Exercise 4

src/java/simpledb/storage/HeapPageId.java

src/java/simpledb/storage/RecordId.java

src/java/simpledb/storage/HeapPage.java

硬盘中包含很多文件，其中有的文件就是我们的HeapFile，一个HeapFile中存储了我们这个数据库中的所有表。文件由硬盘中的许多页(Page)构成，在我们的实现中，每个Page存储一个Table，当Page被加载到内存中后它就是一个表的形式。而每个页又包含很多slot，一个slot里有一个tuple。

1.HeapPageId.java

HeapPage对象的唯一标识符。

HeapPageId的构造函数：对于特定table中的一页特定Page，设置一个page id 结构，参数为int类型的tableId和int类型的pgNo。
getTableId()：返回PageId对应的tableId。
getPageNumber()：返回tableId对应的表包含的page数量。
equals(Object o)：判断两个pageId对象是否相等。

2.RecordID

RecordId是对特定表的特定页上的特定元组的引用。

RecordId的构造函数：RecordId是对一个特定Table中特定一个Page的一个特定tuple的引用，构造时用到的参数是PageId类型的 pid 和 int类型的 tupleno，其中pid是该tuple所在的Page对应的Id，tupleno是该tuple是该Page中第几个。
getTupleNumber()：返回RecordId引用tuple的tupleno。
getPageId()：返回RecordId引用tuple的pid。
equals(Object o)：判断两个RecordId对象是否相等。

3.HeapPage.java

HeapPage中的核心是数据是怎样HeapPage中组织的，这里主要是由header和tuples两个部分组成。其中，一条tuple在HeapPage中表示为一个slot，而header以bitmap的形式来表示第i个slot是否被占用，最低位表示第一个slot是否被占用。由于header是一个byte类型数据，所以最后一个字节并不一定都表示一个slot，也可能无意义：

public class HeapPage implements Page {

    final HeapPageId pid;
    // 每个数据页存储的是同一张表格的数据，所有只需要使用TupleDesc来描述即可
    final TupleDesc td;
    // 数据页的头部，使用bitmap来保存各个slot的占用情况，从最低位开始数
    final byte header[];
    // 具体的记录，即数据
    final Tuple tuples[];
    // 一共有多少个slot，即该数据页一共有多少条记录
    final int numSlots;

    byte[] oldData;
}

class HeapPageIterator：用于迭代HeapPage，有hasNext()、next()、remove()等方法。
HeapPage的构造函数：有两个参数，第一个是HeapPageId，第二个是byte[] 类型的data。在构造函数中为data分配空间，并将空间中开始部分用于header，header中保存了此页slots的bitmap信息。
getNumTuples()：返回此页中能够存储的tuple数量，用于构造函数中分配slot。
getHeaderSize()：返回此页需要多少bytes作为header。
getBeforeImage()：在修改前返回此页的view，用于recovery。
getId()：返回此页的pid。
readNextTuple(DataInputStream dis, int slotId)：寻找到下一个被占用的slot，返回读取的tuple。
getPageData()：返回byte[] 类型的此页数据。
deleteTuple(Tuple t)：从此页中删除特定的tuple数据，同时修改header中对应的bit，指示此slot处的数据已经被删除了。（这里其实没有删除数据，只是在header处显示此处数据为空，可用其他数据替换）。
insertTuple(Tuple t)：利用getFirstNotUsedSlot()函数找到第一个空闲的slot，加入数据，同时修改header中对应的bit，指示此slot处有数据。
getFirstNotUsedSlot()：找到第一个为空的slot下标。
markDirty(boolean dirty, TransactionId tid)：标识此页的dirty/not dirty状态，同时利用tid说明是哪一个Transaction做了该标识。
TransactionId isDirty()：返回最后一个dirtied了此页的Transaction的tid，如果不dirty返回null。
getNumEmptySlots()：返回此页中为空的slot数量。
isSlotUsed(int i)：判断下标为i的slot是否被占用。
markSlotUsed(int i, boolean value)：在header中标识下标为i的slot是否被占用，true在header的bit位上标1，false则标0。

4.总结

HeapPage中各个字段的存储结构和分布，有个BitMap变量来表示各个位置有没有被使用。HeapPage中tuple数组来存储真正的一行一行数据，除此之外还有一个heapPageId和tupleDesc字段。

一个HeapPage能存多少行Tuple，取决于他要保存的一个个元组有多长且都是什么元素，元组数量的计算：floor((BufferPool.getPageSize()*8) / (tuple size * 8 + 1))。以byte为单位的header数组的长度是：ceiling(no. tuple slots / 8) 。最后要注意实验中位图标记slot是否被使用的位运算是从右往左进行的，如0000—>0011这样。

Exercise5 HeapFile

To read a page from disk, you will first need to calculate the correct offset in the file. Hint: you will need random access to the file in order to read and write pages at arbitrary offsets. You should not call BufferPool methods when reading a page from disk.

You will also need to implement the HeapFile.iterator() method, which should iterate through through the tuples of each page in the HeapFile. The iterator must use the BufferPool.getPage() method to access pages in the HeapFile. This method loads the page into the buffer pool and will eventually be used (in a later lab) to implement locking-based concurrency control and recovery. Do not load the entire table into memory on the open() call – this will cause an out of memory error for very large tables.

1.HeapFile

HeapFile是DbFile的一个实现，它以无特殊顺序存储元组集合。元组存储在页面上，每个页面都有固定的大小，文件只是这些页面的集合。 HeapFile与HeapPage紧密合作。 HeapPages的格式在HeapPage构造函数中描述。

HeapFile的构造函数：通过特定的file文件构建一个heap file，有两个参数，第一个是File类型的f，第二个是TupleDesc类型的td。
getFile()：返回磁盘中支持此HeapFile 的File类型文件。
getId()：返回唯一标识此HeapFile的ID。
getTupleDesc()：返回存储在这个DbFile中的table 的TupleDesc。
readPage(PageId pid)：读取pid对应的Page。先找到File内要读取的Page Number，读取整个Page返回。
writePage(Page page)：写pid对应的Page。先找到File内要写的Page Number，写入整个Page。
numPages()：返回这个HeapFile中包含的page数量。
insertTuple(TransactionId tid, Tuple t)：找到一个未满的page，如果不存在空闲的slot，创建新的一页存储tuple，之后添加，返回添加过的Page。
deleteTuple(TransactionId tid, Tuple t)：找到对应的page，删除tuple，标识此page为dirty。

2.总结

‎要从磁盘读取页面，首先需要计算文件中的正确偏移量。提示：您需要随机访问该文件，以便以任意偏移量读取和写入页面。从磁盘读取页时，不应调用 BufferPool 方法。‎一个HeapFile就是一张表/一个文件。HeapFile.readPage方法是核心，该方法只会被BufferPool调用，方法根据传入的pageId从磁盘中读取一个page。还有就是HeapFile的迭代挺难，HeapFileIterator相当于是对整个表中所有的元组进行了迭代操作，需要复写接口的next, hasNext, open三个方法，基本思路是对File中的每个Page进行元组迭代，需要自己维护currentPage和游标。

Exercise 6 Operators

Operators are responsible for the actual execution of the query plan. They implement the operations of the relational algebra. In SimpleDB, operators are iterator based; each operator implements the interface.DbIterator

Operators are connected together into a plan by passing lower-level operators into the constructors of higher-level operators, i.e., by ‘chaining them together.’ Special access method operators at the leaves of the plan are responsible for reading data from the disk (and hence do not have any operators below them).

At the top of the plan, the program interacting with SimpleDB simply calls on the root operator; this operator then calls on its children, and so on, until these leaf operators are called. They fetch tuples from disk and pass them up the tree (as return arguments to ); tuples propagate up the plan in this way until they are output at the root or combined or rejected by another operator in the plan.getNextgetNextgetNext

数据库Operators(操作符)负责查询语句的实际执行。在SimpleDB中，Operators是基于迭代器实现的，每种iterator实现了一个DbIterator接口。SeqScan则为顺序扫描的功能，提供表内数据的迭代。

1.SeqScan.java

SeqScan是一个顺序扫描访问方法的实现，它读取表的每个元组，没有特定的顺序(例如，当它们被放置在磁盘上时)。

SeqScan的构造函数：创建一次特定的transaction对特定table内的数据进行遍历，有三个参数，第一个参数是transaction对应的tid；第二个参数是tableId；第三个参数是表的别名，用于解析。
getTableName()：返回对应tid。
getAlias()：返回对应别名。
open()：使用DbFileIterator打开table。
getTupleDesc()：返回table 的TupleDesc类型。
close()：使用DbFileIterator关闭table。

2.总结

全表顺序扫描的实现，相当于select * from table.

实验总结

lab1实现的都是些基础的整体架构，一开始看到怼过来的代码很蒙圈，梳理了下所有类的概念才慢慢明白。

码农公寓