2021 CMU 15-445 实验笔记

因为目前 cmu 15-445 的实验项目没有全部放出,本笔记会随着课程的更新而更新。

只有我的实验满分通过 gradescope 我才会分享我的心得,帮助大家少踩坑。

Project 0

Project 0 相当于一个热身项目,用于检查学员是否具备正常的 C++ 能力来进行这一门课程。

因为我学习这门课程前不会 C++,所以我没能力,因此我没做。。。

Project 1

Project 1 要我们实现一个 buffer pool,实验分为三个部分,我逐步说明。

LRU Replacement Policy

这个实验一开始主要是被方法名搞懵了,实际上其方法名是对应上层 BufferPool 来说的。LRU 管理的是 frame,存放 page 的那个 frame,而不是 page 本身。比如上层 BufferPool Pin() 了一个 page,然后上层找到该 page 的 frame,然后 LRU 需要移除这个 frame,不进行淘汰(因为上层在使用中)。反之,如果上层 BufferPool UnPin() 了一个 page,然后就要把该 page 对应的 frame 加入 LRU,等待被移除。

此外每个方法注意加锁,可以使用 std::lock_guard<std::mutex> 来进行处理,类似 go 语言的 defer ,可以优雅的解决锁释放的问题。

Buffer Pool Manager Instance

具体流程我不讲,大家自己琢磨琢磨就知道了,我就说说我几个犯了错误的地方。

NewPgImp(page_id_t *page_id) 中,不要一开始就调用 AllocatePage() 分配 pageId,只有当真的有空闲的 page 可以使用时,再调用 AllocatePage()分配一个 pageId 给它,不然你会过不去 gradescope 上面的 [RoundRobinNewPage] 这个测试点。至于为啥,你看看 AllocatePage() 的实现就知道了。

每一次获得一个新的 page,或者删除一个 page 时,请调用 page->ResetMemory() 方法将其数据重置掉,而不是放任不管,想着后面可以直接覆盖。

UnpinPgImp(page_id_t page_id, bool is_dirty) 时不要直接 page->is_dirty_ = is_dirty ,相反应该是:

1
2
3
if (is_dirty) {
page->is_dirty_ = is_dirty; // 不然会直接把之前的 is_dirty 状态给覆盖了。
}

最后注意加锁!

Parallel Buffer Pool Manager

我在 Parallel Buffer Pool Manager 中维护了一个 next_instance_ 变量,用于判断下一次分配 page 的 Buffer Pool Manager 是谁,分配 page 的 round-robin 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
Page *ParallelBufferPoolManager::NewPgImp(page_id_t *page_id) {
std::lock_guard<std::mutex> guard(latch_);
for (size_t i = 0; i < num_instances_; i++) {
BufferPoolManager *manager = *(managers_ + next_instance_);
Page *page = manager->NewPage(page_id);
next_instance_ = (next_instance_ + 1) % num_instances_;
if (page != nullptr) {
return page;
}
}
return nullptr;
}

注意,这里只有 NewPgImp(page_id_t *page_id) 方法需要加锁,别的地方加锁没必要,不然还要 parallel 干啥。

Project 2

Project 2 是让我们实现一个 Extendible Hash Table,只能说很难,难度系数是 Project 1 的两倍,中间一度有点想放弃(主要网上还没别人的代码参考)。整个项目大约花了 10 天吧。

关于 Extendible Hash Table 的算法实现,可以看我的另一篇文章:https://www.inlighting.org/archives/extendible-hash-table-algorithm ,这里我说说我遇到的一些坑。

Bucket

先从 bucket 开始说起,首先就是 IsReadable()IsOccupied() 两个函数。在这里,如果一个元素被创建了,那么他的 readable_occupied_ 均要被标记。如果被删除了,你只需要将 readable_ 的标记清除即可,occupied_ 不用管,仍然占用。

Bucket 标记元素是否被占用的是 char 数组,一个 char 是 8 bit,能表示 8 个数据,设置 readable 和 occupied 时位运算是肯定跑不了了。

关于插入和查询操作,你直接遍历查找就行了,是的,你没有听错,就是一个一个遍历。一个 bucket 只占一个 page 的大小,4 KB 的空间你也玩不出什么数据结构。虽然常规下,Extendible Hash Table 的 bucket 应该使用前缀树,但是它太占空间了。

请不要在 bucket page 中定义额外的成员变量:一开始我想为了提升性能,在 bucket 中定义了一个 NumReadable 变量,用于统计当前 bucket 有几个可读的元素,这样判断 IsFull 和 IsEmpty 可以不需要遍历。但是实际上官方给你定义的数据结构有时候会正好占满 4096 KB,如果你自己定义了某个成员变量,会使得这个 bucket 超出范围了,然后你会越界访问到 Page 里面的内容,然后就莫名其妙的报错。我被这个问题卡了很久,不然早过了。

Directory

这块其实没啥好说的,你自己实现好 Hash Table 的 grow 和 shrink 的逻辑即可。锁也不用加。

Hash Table

Hash Table 这块锁的设计就有讲究,我个人建议的是,先不加锁实现,等能过基本的 Insert,Remove 测试点时,再加锁。加锁直接用全局的 table_latch_ 加写锁,先保证测试用例都能过了,100 分了,再考虑优化性能。我一开始全局写锁,gradescope 是 100 分了,不过 leaderboard 那里没有分数。

这里讲讲我优化后的锁设计:

Insert() 时,table_latch_ 是 ReadLock,对应的 bucket 为 WriteLock。这很好理解,因为你只对一个 bucket 就行修改操作。

SplitInsert() 时,因为一个 bucket 容量不够,你需要扩容,这里会涉及到 directory 的操作,所以这里我使用 table_latch_ 的 WriteLock,锁住全局。同理,合并 directory 的操作也需要 table_latch_ 的 WriteLock 锁住全局。

GetValue() 操作不用说,table_latch_ 和 bucket lock 均使用 ReadLock。

FetchDirectoryPage() 这块我使用了一个独立的锁,因为我在这个方法里面涉及到创建 directory 的逻辑,就是当 HashTable 刚被创建的时候需要一个初始的 directory 是一个 local depth 为 0 的 bucket。当然你也可以不用这么麻烦,直接在 Hash Table 的构造方法里面创建就行了。


及时的 Unpin 不需要的 page,我就这么说吧,gradescope 中有些测试用例的 buffer pool size 只有 3,也就是 Hash Table 运行最小需要的 page 数量。(1 个给 directory,2 个给 bucket,因为 bucket 分裂的时候需要 2 个)。


善用 assert 语句,比如 Unpin 等操作时通过 assert 确定其是成功执行的。还有一些地方通过 assert 来确定数据是按照你的想法在执行。这样能帮助你更快的定位出程序的问题。

比如下面这段程序:

1
2
3
4
5
6
7
8
9
10
11
12
uint32_t mask = dir_page->GetLocalDepthMask(split_bucket_index);
for (uint32_t i = 0; i < origin_array_size; i++) {
MappingType tmp = origin_array[i];
uint32_t target_bucket_index = Hash(tmp.first) & mask;
page_id_t target_bucket_index_page = dir_page->GetBucketPageId(target_bucket_index);
assert(target_bucket_index_page == split_bucket_page_id || target_bucket_index_page == split_image_bucket_page_id);
if (target_bucket_index_page == split_bucket_page_id) {
assert(split_bucket->Insert(tmp.first, tmp.second, comparator_));
} else {
assert(split_image_bucket->Insert(tmp.first, tmp.second, comparator_));
}
}

当一个 bucket 分裂后,我们需要将这个 bucket 中原有的数据分流。按照 split 逻辑我们肯定知道,分流的数据必定落在原来的 bucket page 和 split image bucket page 两个 bucket 中(注意是 page 哦,而不是 bucket 的 index)。这里我们可以使用 assert 进行确认,提前定位 bug。

Project 3

Comming soon。。。