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等函数调用。
测评
到提交为止(2023-05-10),gradescope大概有100人完成了project1。笔者对于并发的处理都是加锁,并没有优化。