CMU15-445数据库实验总结

简要介绍

这门课程共五个配套实验，不过关于数据库的是后面4个实验，第一个实验是检验基本C++语言能力的前菜。

实验全部都是完形填空的形式，需要我们实现声明好的函数，自己也可以增加其它成员变量或成员函数来辅助完成实验要求。

实验配套的开源项目是bustub，需要我们从github上clone下来，按照README配置环境就好。我是在VMWARE中装Ubuntu18.04虚拟机来完成实验的，一定要仔细看环境要求，免得工具链不支持折腾时间。我最开始是用Ubuntu22.04，结果回退代码版本到2021FALL的实验位置后似乎编译不了，又不得不再配环境（因为我菜，不知道怎么修改）。

另外，这门课还开放了Gradescope在线测试平台，非CMU的学生也可以使用，非常不错。因为本地的测试代码都比较简单，Gradescope上面才是严格的测试，注册时要选卡内梅隆基大学和填入口代码，每次上传代码文件时最好运行如下命令检查一下代码格式，因为代码格式检查非常严格，不合规直接0分。

1
2
3

make format
make check-lint
make check-clang-tidy

还有一个上传代码的坑点是提交时要另外多加一个文件tmp_tuple_page.h，具体修改见github issue #225。

于自己而言，实验难度大概是 proj0 < proj1 < proj3 <= proj4 << proj2。其中project2难度最大，是实现可扩展哈希索引，虽然不是2020年听着就非常难的B+树索引，但感觉也不相上下（project2前前后后提交了差不多100次，每次改bug后再提交都得需要运行十几分钟才出结果，难顶…，还好没放弃最终通过全部测试）。project0感觉做不做都没关系，简单的矩阵运算。project1是实现缓存池，其中用到LRU缓存替换策略，管理数据库页面，相对简单。project3是执行查询语句相关的，主要是调用函数，看懂代码中各个类的关联就好。project4是并发控制，实现一个锁管理器（读写锁）和事务回滚的控制。所有实验项目中注意线程安全。在每个Lab前我们需要好好理解实验要求，看懂代码中接口之前的关系，然后理解原理，想好实现思路。

下文主要记录一下各个Lab中的实现思路和遇到问题的解决方法。

Project0 C++ Primer

说明

在这个项目中，您将实现三个类：Matrix、RowMatrix、RowMatrixOperations。这些矩阵是简单的二维矩阵，必须支持加法、矩阵乘法和简化的通用矩阵乘法(GEMM) 运算。

思路

直接写就行，不过注意：

模板子类在实例化之前不知道他的模板父类是谁，所以在模板子类中调用父类成员需要加：（都可以）
1
2
3
this->var_name Parent::var_name using Parent::var_name;
const对象只能调用const成员函数；
构造函数中new了对象后，记得在析构函数delete释放掉；

抛出异常：

1	`throw Exception(ExceptionType::OUT_OF_RANGE, "index out of range");`

智能指针uni_ptr转换为普通指针使用；
1
ptr = uni_ptr.get()

Project1 Buffer Pool Manager

说明

第一个编程项目是在存储管理器中实现缓冲池。缓冲池负责将物理页面从主内存来回移动到磁盘。它允许 DBMS 支持大于系统可用内存量的数据库。

因为在BusTub中，数据库中的数据以页为单位存储在磁盘中，使用时要把页面从磁盘加载到内存，此后再使用如果命中缓存也会提高效率。但内存的容量有限，当容量不足时就需要利用合理的规则淘汰掉某些页面，把位置留给有需要的。

在缓存池中，有些页面是空闲的，存在于空闲链表中，即没有数据库页面与它对应；有些数据库页面处于PIN后的状态，它们正在被使用，不能被淘汰；还有些数据库页面处于Unpin状态，在内存容量不足时被淘汰掉。

page_id唯一标识了一个数据库页面，disk_manager 就是根据 page_id 来读取和写入磁盘页；frame_id唯一标识了内存中的一个页面的位置，代表一个内存帧位置，内存页可以存放数据库页面page，它和page_id呼应。

思路

Task #1 LRU替换策略

使用LRU缓存替换策略，lru_replacer相当于一个回收站，LRU管理的对象就是内存帧位置frame_id。

我们用unordered_map哈希表和list双向链表实现LRU算法，链表节点是一个frame_id帧位置，哈希表存每个链表节点的迭代器位置。这里链表尾部代表最近最久未使用的页面对应的 frame_id；
Pin函数：代表该帧位置对应的页面被某个线程正在使用，不能被替换出去，所以从lru_replacer（umap和list）中移除参数frame_id。从上层的视角而言就是固定某个页面，不被LRU管理；
Unpin函数：与Pin相反，表示没有线程在使用参数frame_id对应的页面，该页面可以被淘汰。所以要把frame_id加入到lru_replacer（umap和list）中，加到链表头部；
Victim函数：查看 lru_replacer 是否有可以牺牲的页面，有的话则取出帧位置 frame_id；

Task #2 缓冲池管理器实例

缓冲池管理器的作用其实就是获取在磁盘的数据库页面、创建新页面、删除页面、写回脏页。这里的一个page_id就唯一标识了一个页面，哈希表page_table_ 管理所有页面，lru_replacer管理的页面是page_table_ 中页面的子集，空闲链表free_list_中是未被使用的页面，和前两个独立。每个函数按注释的要求写就行。

每次获取新内存页位置时，优先从空闲链表free_list_中取出，没有再从lru_replacer获取牺牲页；
脏页记得写入磁盘，创建新页时不能从磁盘读，因为此时还没有该页；
NewPgImp()时，成功取得要被替换的页面后再AllocatePage()；
记得将被替换的旧页ResetMemory()，必须要清空原数据；
每次操作记得设置好pin_count_引用计数；
UnpinPgImp后，只有页面的pin_count_为0时，表示没有线程使用，才能被加到空闲链表；

Task #3 并行缓冲池管理器

ParallelBufferPoolManager是一个拥有多个缓冲池管理器实例的类。对于每个操作，ParallelBufferPoolManager选择一个BufferPoolManagerInstance并委托给该实例。

也就是系统中拥有多个缓冲池，每个缓冲池都有自己的锁，减少了一个缓存池时抢占锁的开销，负载均衡的样子。

这里维护一个 next_instance_ 变量，轮询来判断下一次page的操作分配给那个Buffer Pool Manager。该类中只需在NewPgImp()函数加锁。

其它

加锁建议利用RAII机制，如使用lock_guard、unique_lock、scoped_lock等，不然手动lock再unlock麻烦，还可能忘记加解锁而出现问题。我就忘记解锁造成死锁了，后面全部改用unique_lock；

有两种脏页的刷盘时机的策略，一种是每次 Unpin 的时候都刷，这样会刷比较频繁，但能保证异常掉电重启后内容不丢；一种是在 replacer victimized 的时候 lazily 的刷，这样能保证刷的次数最少；这是性能和可靠性的取舍。

Project2 Hash Index

说明

第二个项目是为ButsTub DBMS实现一个磁盘支持的可扩展哈希表。哈希索引包含一个directory page，该目录页包含指向bucket page的指针。哈希表将通过第一个实现中的缓冲池访问页面。目录页存储了table和bucket的所有元数据。哈希表需要支持对满/空bucket的拆分和合并，以及在全局深度必须更改时支持directory的扩展和收缩。

这里的桶页就是数据库中存储键值对数据的页面。在目录页中桶只是逻辑上的概念，就是一个索引位置，目录页中数组的索引i对应第i个桶，实际上可能有多个桶指向同一个物理桶页面（page）。

我把目录页中一个索引位置称作一个逻辑桶，一个物理桶页面称为桶页，满桶分裂时（空桶合并时）对应调整数据的桶称作镜像桶，它们互为兄弟桶。

每个哈希表的Directory或Bucket页对应于从缓冲池中获取的内存内的内容。每次尝试读写页面的时候，需要使用唯一的page_id从缓冲池中获取页面，然后将他们重新转换为Directory或Bucket页，并且要在任何读写操作之后Unpin这个页面。

建议先理解可扩展哈希索引的原理到位后再开始做此lab，要理解全局深度和局部深度，理解原桶和镜像桶之间的关系。

思路

Task #1 页面布局

哈希表目录页

一些成员变量	描述
global_depth_	目录的全局深度
local_depths_	桶的局部深度的数组（uint8_t）
bucket_page_ids_	桶页的page_id的数组

目录页的全局高度global_depth_ 初始值是0，目录页中逻辑桶的索引范围是[0, Size())，也就是存在Size()个有效的逻辑桶，Size()由全局高度计算得到，就是2^global_depth_为有效逻辑桶的个数；
1
uint32_t HashTableDirectoryPage::Size() { return (1 << global_depth_); }
根据目录页中数组大小是512，可知最多有512=2^9个桶，所以在头文件定义一个最大全局高度；
1
#define MAX_GLOBAL_DEPTH 9
关于全局高度或局部高度掩码，是使用最低有效位，掩码与键的hash值&运算得到该键对应的逻辑桶索引；
1
2
3
4
uint32_t HashTableDirectoryPage::GetGlobalDepthMask() { return (1 << global_depth_) - 1; } // 局部高度掩码类似
只有当每个桶的局部高度严格小于目录的全局高度时，才执行目录收缩；

增加全局深度要将桶数量翻倍，只是逻辑上翻倍了原来的bucket，两个兄弟桶仍然指向同一个物理桶页面；

void HashTableDirectoryPage::IncrGlobalDepth() {
  uint32_t old_size = Size();
  for (uint32_t i = 0; i < old_size; ++i) {
    bucket_page_ids_[i + old_size] = bucket_page_ids_[i];
    local_depths_[i + old_size] = local_depths_[i];
  }
  ++global_depth_;
  assert(global_depth_ <= MAX_GLOBAL_DEPTH);
}

获取镜像桶（兄弟桶）的索引，其实就是将原桶索引的最高位取反；

uint32_t HashTableDirectoryPage::GetSplitImageIndex(uint32_t bucket_idx) {
  assert(bucket_idx < Size());
  // 用异或，给待分裂桶的下标的最高位取反，得到兄弟桶下标
  uint32_t local_deep = local_depths_[bucket_idx];
  return bucket_idx ^ (1 << (local_deep - 1));
}

哈希表桶页

成员变量	描述
occupied_	若数组array_ 的第i个索引曾经被占用过，则occued_的第i位为1
readable_	若数组array_ 的第i个索引包含一个可读值，则readable_的第i位为1
array_	保存key-value键值对的数组

array_是一个0长度数组，一个桶页面类对象后面的空间都用来存储键值对数据；
插入数据时满了返回false，也不能插入重复的键值对，如下是相等判断，cmp函数等于0就是相等的键，值可以直接比较；
1
cmp(key, KeyAt(i)) == 0 && (value == ValueAt(i)
occupied_ 与readable_ 数组类型是char，一个char是8bit，可以表示8个位置，节约空间，对应的函数操作也就需要位运算了。插入数据需要将occupied_ 与readable_ 数组上对应的位置1，删除只需要将occupied_ 数组上对应的位置0。寻找对应位时，先找到所在char，再找到具体第几位。比如：
1
2
uint8_t ch = static_cast<uint8_t>(readable_[bucket_idx / 8]) 找到第几位: (1 << (bucket_idx % 8))，再进行&或|或~运算等等
求NumReadable()，一个桶页面上可读（该位是1）的键值对数量，可以使用ch &= (ch - 1)；
遍历全数组时，也就是处理每个char时，有向上取整；
1
int sz = (BUCKET_ARRAY_SIZE + 8 - 1) / 8; // 向上取整
空或满判断可以直接调用NumReadable()，看是不是等于0或BUCKET_ARRAY_SIZE；
还自定义了两个辅助函数配合桶分裂，取出桶中全部可读数据，重置桶页面（将可读位全部置0）；

Task #2 实现可扩展哈希表

构造函数中创建目录页和第一个桶页，并设置第一个桶索引为0，局部高度为0；
普通的取出、插入、删除操作基本就是先取出目录页和对应桶页，然后调用我们在桶页实现的相应函数即可；
插入前判断到桶满了就分裂桶，删除元素后判断桶为空就合并，目录页也相应调整；
分裂满桶的步骤：
- 先获取目录页和对应桶索引；
- 如果桶的局部高度已经等于MAX_GLOBAL_DEPTH，就不能再扩容；
- 因为并发问题，再取出桶页面，并再次检查是不是满了；
- 当桶页的局部高度等于目录的全局高度时，还需要增加全局高度；
- 将桶局部高度增加一个单位；
- 取出原桶的所有元素，清空原桶；
- 创建新的镜像桶页面，设置好镜像桶局部高度和对应索引；
- 将原桶中的元素重新散列到原桶和镜像桶中；
- 可能之前存在逻辑桶映射到原桶对应的桶页面，这些信息也要相应的调整；
- 最后再次尝试插入数据；
合并空桶的步骤：
- 先获取目录页和空桶和其镜像桶的索引；
- 判断桶索引是否有效，即索引（下标）小于Size()；
- 如果空桶的局部高度已经等于0，就不能再合并；
- 如果两兄弟桶的局部高度不相等，也不能再合并；
- 如果两兄弟桶指向的桶页面相同，也不合并；
- 因为并发问题，再取出桶页面，并再次检查是不是空桶；
- 删除空桶对应的桶页面；
- 进行合并，就是改变空桶指向，将空桶（逻辑桶）指向其镜像桶对应的桶页面；
- 将这两兄弟桶局部高度减一个单位；
- 遍历所有桶，将指向原空桶或镜像桶的其它桶都指向镜像桶，同时设置减小后的局部高度；
- 判断全局高度是否需要减少；
- 递归合并其它可能存在的空桶；
每次取出目录页或桶页操作后一定要Unpin，不然内存承受不了，缓存池满了；

取出目录页代码，用到了reinterpret_cast，取出桶页类似，都是将Page页面解释成相应类型；

template <typename KeyType, typename ValueType, typename KeyComparator>
HashTableDirectoryPage *HASH_TABLE_TYPE::FetchDirectoryPage() {
  Page *dir_page_raw = buffer_pool_manager_->FetchPage(directory_page_id_);
  assert(dir_page_raw != nullptr);
  return reinterpret_cast<HashTableDirectoryPage *>(dir_page_raw->GetData());
}

一些基本代码：

// 创建新页
Page *buc0_page_raw = buffer_pool_manager_->NewPage(&buc0_page_id);
// 获取目录页、桶页
HashTableDirectoryPage *dir_page = FetchDirectoryPage();
page_id_t buc_page_id = KeyToPageId(key, dir_page);
HASH_TABLE_BUCKET_TYPE *buc_page = FetchBucketPage(buc_page_id);
// unpin页面
buffer_pool_manager_->UnpinPage(directory_page_id_, false);

Task #3 并发控制

需要时就加锁，哈希表（目录页）有table_latch_，桶页用page对象原始的锁，两者都有读锁和写锁；

桶页加锁用到reinterpret_cast，将桶页类型的对象重解释成page对象；

1
2
3

Page *buc_page_raw = reinterpret_cast<Page *>(buc_page);
buc_page_raw->RLatch();  	// 加读锁
buc_page_raw->RUnlatch();  	// 解读锁

哈希表加锁使用table_latch_；

1 2	`table_latch_.WLock(); // 写锁 table_latch_.WUnlock();`

加锁思路：

GetValue对哈希表和桶页面上读锁；
Insert对哈希表上读锁，对桶页面上写锁，因为这里只对一个Bucket操作；
SplitInsert需要对哈希表和桶页面都上写锁，因为这里涉及到了Directory的操作；
Remove需要对哈希表上读锁，对桶页面上写锁；
Merge需要对哈希表上写锁，因为只是修改Directory，也并没有取出镜像桶页面；

其它

我一开始对可扩展哈希索引的概念理解得并不是很清楚，就直接做实验了，后面在桶分裂和桶合并的代码一直存在BUG，一会改这一会改那，提交始终过不了，不是这出问题就是那儿出问题，也连着折腾了好几个晚上。

后面看了些其它博客分析的思路，看了好几遍可扩展哈希索引的概念，理清了思路。也重新从实验一缓存池开始检查代码，发现BPM（缓存池）完成得有瑕疵（lru_replacer容量满了后多删了页面，以及对页面pin_count的检查），所以存在内存泄漏。也在lab2中完善了处理哈希表扩展、收缩的小细节（如忘了uppin页面，没有处理其它被分裂或合并影响的桶等等），再后面改着改着BUG就通关全部测试了；

可以使用断言assert，以快速定位不符合预期的地方，还可以结合日志模块LOG_DEBUG，打印日志排查问题；

要保证每个小功能的以及前一个实验的正确性，毕竟整个项目是自底向上构建的，会用到前一个实验的实现模块，当前实验出错可能是上一个实验的隐藏问题导致的，测试文件并非100%的完善；

全部完成Lab2后，感觉好像也没有那么难了，主要是考虑的细节比较多，关键要思路清晰；

Project3 Query Execution

说明

第三个项目中，您将实现负责获取查询计划节点并执行他们的执行器。DBMS还不支持SQL，所以您的实现将直接在手工编写的查询计划上运行。

使用迭代器模型（又称火山模型）。每个查询计划执行器中，Init方法初始化操作符的内部状态，Next方法提供迭代器的接口，该接口在每次调用时返回一个记录和一个记录标识符（Record Identifier）（也可能是执行器已经结束的标志）。记录标识符是该记录相对于其所属表的唯一标识符。

每个执行器实现一个循环，该循环继续调用其子对象的Next函数来检索记录并逐个处理他们。

9个操作分别是Sequential Scan、Insert、Update、Delete、Nested Loop Join、Hash Join、Aggregation、Limit、Distinct。

思路

该Lab感觉是让我们了解了一下常见SQL语句的执行逻辑，关键是要理解代码中各个类接口的作用；

常用代码

// 头文件定义辅助成员变量
TableInfo *table_info_;
// Init函数初始化
table_info_ = exec_ctx_->GetCatalog()->GetTable(plan_->GetTableOid());

// Predicate条件判断
bool is_valid = plan_->GetPredicate()->Evaluate(&(*iter_), &(table_info_->schema_)).GetAs<bool>();

// 取出当前符合条件行的每一列数据
std::vector<Value> values;
for (size_t i = 0; i < GetOutputSchema()->GetColumnCount(); ++i) {
    values.emplace_back(GetOutputSchema()->GetColumn(i).GetExpr()->Evaluate(&(*iter_), &(table_info_->schema_)));
}
*tuple = Tuple(values, GetOutputSchema());

// 索引变更，示例是增加索引
indexinfo->index_->InsertEntry(tuple->KeyFromTuple(table_info_->schema_, *(indexinfo->index_->GetKeySchema()), indexinfo->index_->GetKeyAttrs()), new_rid, exec_ctx_->GetTransaction());

Hash Join、Distinct需要仿造头文件中 SimpleAggregationHashTable实现哈希方法，这是我参考的博客。

Project4 Concurency Control

说明

第四个项目是在DBMS中实现一个Lock Manager，然后使用他来支持并发执行。锁管理器负责跟踪向事务发出的行级锁，并支持根据隔离级别适当的上或释放共享锁和排他锁。LM（锁管理器）的基本思想是，它维护一个关于活动事务当前持有的锁的内部数据结构（请求队列），然后事务在访问数据项之前向LM发出锁请求，LM将根据情况决定锁授予该事务、阻止该事务还是终止该事务。使用Wound-Wait策略避免死锁。

需要LM支持三个常见的隔离级别：READ_UNCOMMITED，READ_COMMITTED和REPEATABLE_READ。

任何失败的锁操作都应该导致事务终止（隐式Aborted）并抛出异常。事务管理器将进一步捕获该异常并回滚事务执行的写操作。

我把共享锁也称作读锁，排他锁也称作写锁；

二段封锁协议（2PL）：事务分为两个阶段（不考虑commit/abort），上锁阶段（GROWING）只获取锁或升级锁，不能释放锁；解锁阶段（SHINKING）只解锁，不能获取和升级锁。这样，第二次读取时，前一次读取的读锁一定还在，避免了中途被修改。

严格二段封锁协议：增加在SHRINKING阶段也不能释放锁，只有在事务 commit 或 abort 时统一释放锁的限制；

思路

Task #1 锁管理器

脏读的产生：事务1修改数据，被事务2读到，之后事务1 abort，事务2读到的是脏数据。

不可重复读的产生：事务1读数据，事务2修改数据，事务1再读数据，事务1两次读到的数据不一致。

幻读的产生：事务1统计行数，事务2插入数据，事务1再统计行数，事务1两次统计的行数不一致。

隔离级别	实现方式	可能问题
READ_UNCOMMITED	只在写操作时上写锁	脏读、不可重复读、幻读
READ_COMMITTED	读时上读锁，读完解读锁；写时上写锁，写完解写锁	不可重复读、幻读
REPEATABLE_READ	读写均需要加锁，遵守严格2PL	幻读

其它的和死锁预防预防一起写了；

Task #2 死锁预防

事务txd_id大的就是新事务，小的是老事务；
加共享锁步骤：
- 状态已经是ABORTED的事务，直接返回false；
- 隔离级别是读未提交，无需共享锁，设置事务abort，然后返回false；
- 隔离级别是可重复读，但不处于GROWING阶段，设置事务abort，然后返回false；
- 已经获得共享锁或排他锁，直接返回true；
- 遍历rid（元组）对应的请求队列，根据wound-wait原则；
- 若遇到新事务，如果新事物申请持有写锁就需要Abort这个新事务，新事务申请持有读锁则可以共存，跳过继续遍历；
- 若遇到老事务，如果老事务申请持有写锁，事务就条件变量等待获取锁cv_.wait(locker)，如果老事务申请持有读锁，可以共存，跳过继续遍历；
- 当成功获取锁后，还要循环判断事务自己在等待获取锁期间是不是被abort了；
- 构造SHARED模式的请求节点，将请求节点加入请求队列尾部，并将rid加入事务的共享锁集，设置事务状态为GROWING，返回true；
加排他锁步骤：
- 类似获取共享锁，不过排他锁和所有锁互斥；
- 遇到新事务，可以abort掉任何新事务；
- 遇到老事务，事务自己被abort，返回false；
升级锁步骤：
- 也类似获取共享锁；
- 只有共享锁才能升级成排他锁；
- 遇到新事务，可以abort掉任何新事务；
- 遇到老事务，不论老事务申请锁的类型，事务自己就条件变量等待获取锁cv_.wait(locker)；
- 成功后还要调整请求节点的模式和事务对应的锁集；
解锁步骤：
- 先判断是不是真的加有锁，不是就返回false;
- 若待解锁事务隔离级别是 REPETABLE_READ，且处于 2PL 的 GROWING 阶段，将 2PL 设置为 SHRINKING 阶段；
- 从事务对应的锁集（共享锁集或排他锁集）中移除rid；

Task #3 执行并发查询

需要我们修改部分执行器的代码，加入刚刚实现好的共享或排他锁，并且还要求支持事务的回滚。只需要修改Sequential Scan、Insert、Update、Delete这4个执行器。

顺序扫描时，如果不是READ_UNCOMMITTED，读取均需要获取共享锁。如果是 READ_COMMITTED，读完后需要立刻释放 shared lock。

增删改操作不管什么级别都需要获取排他锁（如果已经有共享锁，升级为排他锁），READ_UNCOMMITTED和READ_COMMITTED写入完成后立刻释放排他锁。REPEATABLE_READ会在整个事务commit时统一 unlock，因为READ_COMMITTED 需要等待提交后才可以被其他事务读取，不释放锁，不需要我们自己编写代码。

如下是需增加的示例代码：

// 获取锁
LockManager *locker = GetExecutorContext()->GetLockManager();
Transaction *txn = GetExecutorContext()->GetTransaction();

// 加解读锁
locker->LockShared(txn, rid);
locker->Unlock(txn, rid);

// 加写锁
if (txn->IsSharedLocked(new_rid)) {
    locker->LockUpgrade(txn, new_rid);
} else if (!txn->IsExclusiveLocked(new_rid)) {
    locker->LockExclusive(txn, new_rid);
}
// 解写锁
if (txn->GetIsolationLevel() != IsolationLevel::REPEATABLE_READ) {
    locker->Unlock(txn, new_rid);
}

// 记录事务变更，为了回滚
txn->GetIndexWriteSet()->emplace_back(IndexWriteRecord(new_rid, table_info_->oid_, WType::INSERT, *tuple,indexinfo->index_oid_, exec_ctx_->GetCatalog()));