CMU 15-445 Project 0 (2023 Fall)

Nelson Boss included in category study

2024-01-14 2024-05-15 2703 words 6 minutes

Contents

实验主页：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。

Task #1 - Copy-On-Write Trie

该任务内容是修改 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(key)

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(key, value)

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

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

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

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

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

空的 key

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

Remove(key)

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

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

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

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

Task #2 - Concurrent Key-Value Store

该任务的内容是修改 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++ 真是想破了头。

Task #3 - Debugging

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

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

Task #4 - SQL String Functions

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

upper()：接受一个字符串作为参数，将所有的字母大写并返回；
lower()：接受一个字符串作为参数，将所有的字母小写并返回。

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

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

make submit-p0

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

在 discord 上询问后，迟宝（bustub 的维护者）回复了我 🤩！！

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

结果

🥳