CMU 15-445 Project 0 (2023 Fall)

实验主页:https://15445.courses.cs.cmu.edu/fall2023/project0/

project 0 的主要目的是测试大家的 C++ 基础。需要完成该 project 才能开始后续 project 的编写。如果你感觉在完成该 project 的时候比较吃力,那么说明你的 C++ 基础不足以学习该课程,需要先学习 C++。

我是用的是 vscode 来完成实验。按照实验的要求,需要安装 CMake Tools、C/C++ Extension Pack 和 clangd,然后参考 Debug a C++ project in VS Code 来使用 vscode 的 debug 功能。

我使用的实验环境是 macOS 和 Windows + WSL2 (Ubuntu 22.04),C++ 编译器采用的是 clang14。

该 project 的内容是实现一个可以存储 KV 对的可持久化 trie 树。

关于 clang 的版本

请尽量使用 llvm 的 clang14 作为编译器。如果使用其他的版本可能会导致使用 clang-tidy 指令进行代码规范检查的时候出现题目代码被检查出错误的情况。

如果你使用的是 macOS 并且安装了 Homebrew 包管理器,可以使用下面的指令来安装 llvm clang 14:

1
brew install llvm@14

安装完成之后还需要按照 brew 给出的提示添加 PATH。

该任务内容是修改 trie.h 和 trie.cpp 实现可持久化 trie 树。

在可持久化 trie 中,操作不会直接修改原始节点,而是新建节点存放修改的数据,然后把新建的节点连向旧的节点来实现对未被修改的数据的访问。显然,每次操作结束的时候,都会生成一个新的根。通过访问不同的根,就可以访问各个历史版本。

该任务全部使用 C++11 的智能指针来进行内存管理,因此禁止使用 new 和 delete 来管理内存。

测试指令:

1
2
3
cd build
make trie_test trie_noncopy_test -j$(nproc)
./test/trie_test && ./test/trie_noncopy_test

get 操作就是从 trie 中获取 key 对应的值。

首先需要一个指针 now 表示当前所在的节点。然后从左到右遍历 key 的每一个字符,每次寻找当前 now 的节点是否有这个字符对应的 children_,如果有就往下跳,然后继续遍历下一个字符,如果没有就表示该 key 不存在,返回 nullptr。

当遍历完 key 的每一个字符之后,说明我们到达了该 key 的 terminal 节点。使用 dynamic_cast 将指针转换为 TrieNodeWithValue 类型。如果转换完得到了 nullptr,说明当前节点不是一个 terminal 节点,也就代表 key 不存在,返回 nullptr。否则调用对应的方法获取该节点的值并返回。

std::string_view

在 trie 类型的参数里有一个很新的类型:std::string_view。

std::string_view 是 C++ 17 新引入的一个字符串类型,其功能是创建一个对已存在的字符串的查看。

string_view 和 string 的区别是,string_view 并不是真正地创建了一个字符串,而只是创建了一个“视图”,类似数据库中的视图。因此 string_view 必须要基于一个已经存在的字符串而创建。而且其对原始字符串是只读的,也就是说 string_view 只能读取原始字符串的内容,而不能修改。

当只需要访问一个字符串的时候,使用 string_view 来传递参数比使用 string 效率要高得多,因为 string_view 只记录了自己对应字符串的地址和偏移位置,而 string 会复制一次字符串。

string_view 和 const char * 或 const string& 的区别是,string_view 可以基于原始字符串的其中一部分来创建,而不只是完整的原始字符串。该语法是 std::string_view stringView(cstr, 4),其中 cstr 是一个字符指针,表示字符串的起始位置,4 表示长度。

当 string_view 对应的原始字符串被销毁(内存释放)后,string_view 返回的值就是未定义内容,也就是会访问到非法内存。

put 操作是将一个 kv 对放入 trie 中。

由于我们实现的是可持久化 trie,因此 put 操作并不是单纯地遍历节点,而是应该将我们遍历的所有节点都新建,无论是否有修改。

当想要访问一个存在的节点的时候,需要新建一个该节点的拷贝,然后访问这个拷贝,并且将我们前往这个点对应的指针替换成指向这个拷贝。

当想要访问一个不存在的点的时候,就直接新建一个节点访问。

显然,每次 put 操作都会生成一条 key 路径的链,且必定会生成一个新的根节点。通过访问不同的根节点,就可以进入不同的历史版本。

空的 key
在测试集里面会出现 key 为空的情况,尽管题目没有说明。根据测试的内容,key 为空也算是一种合法的插入。

remove 操作是将一个 key 从 trie 中删除。删除的过程中如果一个节点没有孩子了,那么需要删除这个节点。

和 put 操作一样,还是需要将我们遍历过的点都新建一遍。当删除完之后,我们还需要把删除的 TrieNodeWithValue 节点重新转换为普通的 TrieNode 节点。

由于本任务提示不需要新建函数,因此可以使用一个栈来维护我们访问过的点,当遍历完 key 之后,依次退栈,判断当前点的孩子数量并决定是否删除。

若要删除一个点的某个孩子,需要使用 .erase() 方法来删除,而不能只是将其置为 nullptr。

该任务的内容是修改 trie_store.h 和 trie_store.cpp ,在我们实现的可持久化 trie 上继续实现多线程 trie。和普通的多线程 trie 不一样的是,由于我们实现了可持久化 trie 作为基础,因此不仅需要实现读写锁,还需要实现读和写同时进行。

具体来说,当有多个读线程访问 trie 的时候,是在同一个 trie 的对象上进行读取操作;此时若有一个写线程进来,按照可持久化 trie 的方式,原本的读线程所读取的内容并不会被写线程所影响,因此可以实现多个写线程和一个读线程同时进行。

对于具体代码的实现,我们只需要按照合理的顺序获取锁和调用在 task 1 实现的函数就可以了。由于该任务是基于 task 1 的,因此需要保证 task 1 的测试完全通过后才能进行本任务。

测试指令:

1
2
3
cd build
make trie_store_test trie_store_noncopy_test -j$(nproc)
./test/trie_store_test && ./test/trie_store_noncopy_test
write_latch 和 root_latch 的顺序
对于 Get 操作,只需要获取 root_latch 就可以了。而对于 Put 和 Remove 操作,还需要获取 write_latch。请仔细考虑这两个锁的获取顺序是什么。错误的获取顺序会导致死锁的发生。
mutex.lock() vs mutex.try_lock()

lock() 会在等待锁的时候被一直阻塞,直到获取锁后才返回。

try_lock() 会在尝试获取锁后,无论是否成功都立刻返回。如果成功返回 true,失败则返回 false。

c++ optinal<T>

optinal 是 C++17 引入的一个类型,其跟 rust 和 swift 里的 optinal 作用一样,都是用来表示可以为“空”的数据类型。

如果想要表示空,使用 std::nullopt。可以看出,optional 的作用就相当于是支持“NULL”的变量。只能说,为了让大家尽量少使用指针,C++ 真是想破了头。

这个任务没什么好说的,就是强制你使用 gdb/lldb 进行调试。当然你可以使用 printf() 来调试,但学习一下 gdb/lldb 的使用总归是好的。

如果你配置了 vscode 来进行调试,那么本任务就更加简单了。

这个任务是要求实现两个 SQL 中的函数 upper() 和 lower():

  • upper():接受一个字符串作为参数,将所有的字母大写并返回;
  • lower():接受一个字符串作为参数,将所有的字母小写并返回。

也很简单,直接遍历字符串并修改就好了。

稍微麻烦一点的是注册指令,其实就是用 if 判断指令是不是 upper 和 lower,还需要判断一下参数是否符合要求,不符合的话需要抛出异常。具体如何实现阅读一下源代码就可以知道了。

make submit-p0

在 2024/01/17 使用最新的代码进行打包,会出现代码打包不完整的问题:

./pics/2024-01-18-18-44-04.png

在 discord 上询问后,迟宝(bustub 的维护者)回复了我 🤩!!

./pics/2024-01-18-18-46-45.png

最后我是用 git rebase -i 将代码回退到了最新的 release 版本(commit id:fc57dab),再运行 make submit-p0 就正常打包了。

./pics/2024-01-18-18-29-56.png

🥳