丹穴
0%

6.830项目记录

Database|6.830 lab1

为了对数据库系统有更深层次的理解,尝试在暑期间做了6.830的Lab。

项目展图

本项目主要实现了数据库系统，包括了存储系统Storage,查询Query框架,查询的优化器Optimizer,索引的查询B+-tree实现等。整个项目的框架大致会随着项目的逐渐深入给出。

环境配置

ant环境配置下载官网上的在ant build,按照README中的教程执行即可。

Tuple/Tuple Desc

Tuple和TupleDesc类较为简单，注意好已经提供了Field的字段封装。
TupleDesc需要type和fieldname两个属性，一个用来标明数据的属性，一个用来记录数据的，将其这两属性包裹为TdItem静态类，使用ArrayList保存即可。
Tuple中包含TupleDesc,RecordId以及ArrayList<Field>,qizh其中RecordId在前几个Lab并没有作用，是在后期

1
2
3
private TupleDesc tupleDesc;
private RecordId rid;
private ArrayList<Field> fields;

Buffer Pool

buffer pool是一个缓冲存储区，就是为了能够更快访问table所设立的区域
以Page作为基本单位。使用CocurrentHashMap来进行维护。

Page

在书写的过程中可以发现，SimpleDb中实现的相应的Page和大二下写过的Lsm-tree的写法非常类似，如果做类比的话BufferPool缓冲区就类似sst_buf,而Page就类似于SsTable的写法。也就是说比起当时LSM-tree的实现，SimpleDb在页的层级进行分割，对效率有了更大的提高，减少了IO操作。

HeapFile HeapPage

在设计db的过程中，最为重要的还是Dbfile和page都是一个抽象接口，可以Dbfile是一个table在硬盘的存储接口，而一个Dbfile。而在读取的时候以Page为单位来读取，pages来存储相应的Tuples。
每个Page的结构如下，

1
2
3
4
5
final HeapPageId pid;
final TupleDesc td;
final byte[] header;
final Tuple[] tuples;
final int numSlots;

page.getId().pageno()从对应Dbfile读取的起始偏移量
Dbfile和Table的关系为一个Table对应的是一个Dbfile。
Dbfile和Page有不同的实现方式，这也是数据io的主要优化点，lab1中实现的是最为基础的HeapFile和HeapPage

RecordId

RecordId是Tuple中包含的一个元素，他的目的是为了在添加以及删除Tuple确定Tuple所在的页位置以及页中的位置，因此包含两个元素PageId以及TupleNumber，通过这两个成员来实现Database对于Tuple的删除和添加操作。

Database|6.830 lab2

Project

关系代数投影
算法是编写的新的TupleDesc来做投影,子操作元素OpIterator child,Project利用新的TupleDesc和子操作的fetchNext来形成新的Tuple

Filter

Filter中使用Predicate进行Tuple判断是否符合条件，不符合条件则在fetchNext中跳过，和Project的逻辑类似。

Join

笔者在此实现的Join方式简单的simple nest join，也就是循环嵌套联结，通过二层嵌套来进行实现表和表的连接。事实上还有不同的实现方式,有

Agg

  实现了IntegerAggregator以及StringAggregator。
  具体思路是通过给定的gbfield将Tuple的gbfield位相同的合在一起，调用mergeTupleIntoGroup函数添加入组，通过op来相应对每个group进行聚合结果进行计算。其中IntegerAggregator都是对Intfield字段符的聚合，而StringAggregator是对StringField字符段的聚合，聚合操作只有COUNT。
  笔者算法上采用HashMap存储相同的gbField和聚合结果的对应关系，IntAggregator中由于需要实现AVG聚合操作，因此既要相应的结果val，又需要相应的计数cnt，因此建立两个HashMap

1
2
3
4
5
6
if(value){
    header[i/8] |= 1<<(i%8);    //置为1
}
else {
    header[i/8] &= ~(1<<(i%8));     //置为0
}

Add and Delete

Add
加入Tuple的思路是先在HeapPage中寻找empty slot，如果有则在HeapPage的list中加入Tuple,同时修改该Tuple的RecordId；如果HeapFile内所有HeapPage都没有empty slot，则调用emptyPage创建新的HeapPage。
需要注意的是，所有的HeapFile中所有的getPage都需要调用BufferPool的getPage()方法，来获取相应的Page,原因一是通过BufferPool获取Page是可能可以减少磁盘IO操作的，二是最关键的，也是我做到Lab4才发现的，只有在这里的insertTuple和DeleteTuple中调用的是BufferPool中的getPage()方法，读和写的事务才能统一被管理，都在事务ACID协议的管辖范围内
Delete

Page Eviction

Flush Page
使用CocurrentHashMap中value的迭代器，将所有脏页写入磁盘

1
2
3
4
5
6
7
8
9
10
11
12
public synchronized void flushAllPages() throws IOException {
     Iterator<Page> it = pages.values().iterator();
     while (!it.hasNext()){
         Page page = it.next();
         //将所有脏页写入disk中
         if(page.isDirty() != null){
             DbFile dbFile = Database.getCatalog().getDatabaseFile(page.getId().getTableId());
             dbFile.writePage(page);
             page.markDirty(false,null);
         }
     }
 }

LRU缓存，实现方式类似Leetcode.146
将原先维护的CocurrentHashMap改为链表+HashMap的LRUCache类来进行维护。双链表是为了将调用的页插入队首，并且将队尾的页去除。
PS:笔者出于练手的目的造了LRUCache的轮子，事实上Java有自己的类似实现LinkedHashMap

Template Summary

完成Lab1以及Lab2后，Database基本的存储框架和增删查询的框架已经搭建完成，对于数据库的大抵架构也有所熟悉，我画了一张草图，来表示Database的大致结构。

Database|6.830 Lab3

Lab3主要是查询的优化，对查询语句
Lab3的Optimizer架构如下图所示,可以看到


而Optimizer中干的是两件事情：

  • 第一阶段：收集表的统计信息，有了统计信息才可以进行，也就是Ex1,2做的是
  • 第二阶段：根据统计信息进行估计，找出最优的执行方案。
    通过创建直方图来解决filter selectivity estimation
    估计相应的

TableStat.Java

TableStat主要是用来统计表中的信息，使用实现的IntHisgram对进行相应的实现。TableStat通过ConcurrentMap存储了表的名称和表的对应的关系。
算法思路如下：调用LAB2实现的SeqScan遍历，通过第一次遍历构建Field相应的Histogram，如果是IntField类则计算他的最大值和最小值，如果是StringField类则创建StringHistogram。
随后SeqScan.rewind(),进行第二次遍历，
TableStat中实现以下3个Estimate:

  • estimateSelectivity
  • estimateScanCost
  • estimateTableCardinality
    计算
    1
    2
    joincost(t1 join t2) = scancost(t1) + ntups(t1) x scancost(t2) //IO cost
    					+ ntups(t1) x ntups(t2) //CPU cost
    这些代码都是基于SeqScan来进行相对应的书写

    基数估计

    Cardinality是指表中唯一值的行数，即是选择出来的行中该字段符应当不重复，对于有唯一约束的列，“基数”等于表的总行数。而选择性指的（Selectivity）的意思就是字段可取值相对于总行数的比值，公式如下：

    选择性 = 基数 / 总行数 * 100%

Join优化

根据相应的知识查询抗压发现，Join优化有两种，也就是先Filter再Join，会相应减少Cpu的操作
并且JoinOptimizer会相应的
computeCostAndCardOfSubplan返回了CostCard

Database|6.830 Lab4

Transacation遵守ACID原则，ACID实现的前提是严格两阶段封锁协议(Strict two-phase locking)
两阶段封锁协议将事务分为两个阶段：

  • 增长阶段：事务可以获得锁，但不能释放锁，锁的数量单调不减。
  • 缩减阶段：事务可以释放锁，但不能获得新锁。锁的数量单调不增。
    共享锁(Shared lock)以及排他锁(Exclusive lock)的区别和联系。
    注意的是，一个事务t可能会多次访问同一个Page，而他说是锁实现使用类的等待获取来做到的，类似于读写锁。
    下面有一张思维导图，很好地阐述了PageLock的工作逻辑

基于这张思维导图开始写PageLock页级别的锁和LockManager类来对BufferPool中的锁进行统一管理。

PageLock实现

首先使用枚举类型指定PageLock的两个类型EXCLUSIVE和SHARED，并且按照上面的思维图对应PageId的Page

Database|6.830 Lab5

未完待续……