Project #0 - C++ Primer

资源

课程主页
Bustub Github
在线测试网站 (Entry Code: 2KJRB5)，注意用外国大学以及gmail注册。
lab0资源我的lab0实现，入门实现有困难的同学可以参考一下。

Backgroud

环境

我的是Ubuntu 9.4.0 + vscode

语法

需要了解的：

c++11: 智能指针、dynamic_cast和const_cast

c++17: string_view、optional

Task #1 - Copy-On-Write Trie

COW Trie的优势就是可以提升并发性能以及降低使并发编程更简易。
对COW Trie的更改会得到一棵新Trie，这使得读操作可以在旧Trie树上进行而不会被阻塞。
但这也会带来另一个问题，即旧节点的管理问题，我们需要回收无效节点，但主动管理比较复杂，实验模板里用了shared_ptr来管理TrieNode。当指向TrieNode的shared_ptr数量为0时，TrieNode会自动释放。

Put

当插入一个key时，从新的根节点到目标节点，都会被创建，区别是前面通过clone，后面通过make_shared。如下图所示，黄色的是复制，红色的是新创建。

在这里插入图片描述

因此，插入大致可分为3步：

从顶向下找出需要复制的节点
从后往前创建新节点
从后往前复制节点

Remove

和Put类似，区别是创建的新节点数为1（或者为0）

有几点需要注意：

边界条件，要能够处理key为空字符串，以及向一棵空树插入数据
用到的指针都是const的，对map的访问需要先find再使用at，不能直接用下标，向map插入数据时需要用const_cast去掉const属性。

Task #2 - Concurrent Key-Value Store

COW使得Trie的并发编程更简单，实验模板里只使用了两个互斥量，而不需要每个node维护互斥量。同时更新操作在获得root后，可以立刻释放root锁，在完成更新操作后，再通过root锁更新root，这样基本上不会阻塞读操作。

Task #3 - Debugging & Task #4 - SQL String Functions

都不难
task3不同环境生成的随机数可能不同，trie_debug_test.cpp的样例可以用以下代码替换

  auto trie = Trie();trie = trie.Put<uint32_t>("65", 25);trie = trie.Put<uint32_t>("61", 65);trie = trie.Put<uint32_t>("82", 84);trie = trie.Put<uint32_t>("2", 42);trie = trie.Put<uint32_t>("16", 67);trie = trie.Put<uint32_t>("94", 53);trie = trie.Put<uint32_t>("20", 35);trie = trie.Put<uint32_t>("3", 57);trie = trie.Put<uint32_t>("93", 30);trie = trie.Put<uint32_t>("75", 29);

评测

cmu15445课程主页FAQ里有如何使用评测网站说明，注意要用gmail和外国大学注册。
在这里插入图片描述

Project #1 - Buffer Pool

Task #1 - LRU-K Replacement Policy

本实验的LRU-K和笔者理解的LRU-K略有不同。笔者之前了解的LRU-K是维护两个队列：历史访问队列+LRU队列，在历史访问队列达到k次的数据将缓存到LRU队列中。而此实验的LRU-K更像一个普通的LRU队列，只不过它的替换策略不是根据最近一次访问，而是最近k次访问。

在计算k-distance上，笔者计算的是各个访问时间戳之和，所有节点中时间戳之和最小值就是k-distance最大值，对于访问次数不足k次的，返回一个标志。笔者的GetDistance返回值如下

std::pair<size_t, bool>

需要注意的是，对于不足k次的，返回的是第一次的访问时间 + false

Task #2 - Buffer Pool Manager

注意点：UnpinPage操作中，不能直接将相应page的dirty位设置成is_dirty,因为is_dirty只代表当前线程是否更改了page。

Task #3 - Read/Write Page Guards

注意移动拷贝和赋值需要把other的指针置为空,同时赋值操作需要调用Drop()释放原有资源。
特别注意：加锁和pin的顺序，需要先pin再加锁，以及先解锁再unpin。（笔者被这个bug困扰了很久）
FetchPageBasic这些函数，为了防止代码冗余需要调用FetchPage，又为了防止死锁，笔者写了一个无锁版的FetchPageWithoutLatch供FetchPage和FetchPageBasic等函数调用。