CMU 15445 2023fall #Project0 实现一个简单的k-v存储引擎
前言
太吓人了，这甚至只是个课程入门实验，但是前两部分主要的内容差不多花了我一整天🥲🥲🥲（可能是我的C++基础太差了😥😥😥。
主要是考察一下对C++的熟练程度，比如智能指针、移动语义、并发控制，还有数据结构的基础。
Task #1 - Copy-On-Write Trie
要求实现一个写时拷贝的前缀树，对前缀树不熟悉的可以做做leetcode的这题，能快速理解到前缀树是什么。
关于写时拷贝（Copy-On-Write，COW）
在使用写时拷贝的情况下，当多个进程或线程共享同一份内存数据时，它们实际上共享同一个物理内存页。这意味着在一开始，这些进程或线程都指向相同的内存页。当其中一个进程或线程尝试修改这个共享的内存页时，才会进行实际的拷贝操作。这个操作会将要修改的内存页复制一份，使得修改操作只影响到修改操作的那个进程或线程，而不会影响其他共享该内存页的进程或线程。
写时拷贝的优点是在数据没有发生写操作之前，多个进程或线程可以共享同一份内存数据，避免了不必要的内存复制。这对于需要共享大量数据或频繁进行复制操作的情况下，可以提高性能和节省内存空间。
在写时复制trie中，操作不直接修改原始trie的节点。而是为修改后的数据创建新的节点，并为新修改的trie返回新的根。在root中插入 ("ad", 2) 。首先复制一个newroot节点，然后遍历key发现需要修改的路径有a，所以拷贝一份Node1到Node2，并将其作为newroot节点的子节点。之后继续在Node2，发现存在d路径，于是拷贝原来的value为1的节点，并修改value为2，最后更新Node2的子节点即可。
Get
get的实现其实很简单，做到leetcode上的那题就能写出来了。
如果trie为空，则直接返回nullptr。
如果key为空，先找根节点，如果根节点是一个存储value的节点，则返回value。
如果key不为空，让cur指向根节点。遍历key的字符，如果当前字符在cur的子节点map中，则让cur等于当前字符在cur的子节点中的映射节点继续遍历；否则不存在该key，直接返回nullptr即可。
最后把找到的value指针返回。
/*******************************************************
* @brief 获取键值
*
* @tparam T
* @param key
* @return const T*
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-19
*******************************************************/
template <class T>
auto Trie::Get(std::string_view key) const -> const T * {
// throw NotImplementedException("Trie::Get is not implemented.");
// 如果key为空，则查找根节点
if (key.empty()) {
auto tnwv = dynamic_cast<const bustub::TrieNodeWithValue<T> *>(root_.get());
return tnwv == nullptr ? nullptr : tnwv->value_.get();
}
// 检查根节点是否为空，则返回当前的 Trie
if (this->root_ == nullptr) {
return nullptr;
}
std::shared_ptr<const bustub::TrieNode> cur = this->root_;
for (char ch : key) {
auto it = cur->children_.find(ch);
// 没找到
if (it == cur->children_.end()) {
return nullptr;
}
// 找到了
cur = it->second;
}
if (cur->is_value_node_) {
auto tnwv = dynamic_cast<const bustub::TrieNodeWithValue<T> *>(cur.get());
return tnwv == nullptr ? nullptr : tnwv->value_.get();
}
return nullptr;
// You should walk through the trie to find the node corresponding to the key. If the node doesn't exist, return
// nullptr. After you find the node, you should use `dynamic_cast` to cast it to `const TrieNodeWithValue<T> *`. If
// dynamic_cast returns `nullptr`, it means the type of the value is mismatched, and you should return nullptr.
// Otherwise, return the value.
}Put
设置键对应的值。如果键已经存在，则覆盖现有值。注意，值的类型可能是不可复制的（即， std::unique_ptr<int> 因此需要使用移动语义）。这个方法返回一个新的trie，也就是说，实现写时拷贝。
假设有这样一个trie
如果要在其中插入一个(bc, 3)，首先拷贝root到newRoot
在newRoot中发现没有b这条路径，那么直接创建一个新节点即可，对新建的b节点进行递归操作
发现没有c路径，同样创建一个新节点，这是key的末尾，因此直接设置value为3，结束递归
然后在退出调用栈的过程中建立新的指向关系，这样就完成了插入的过程。
如果键的前面一部分在trie中已经存在了，步骤还是类似的，只不过不是新建节点而是拷贝那个节点，然后再拷贝到新节点上进行递归。比如要在其中插入一个(ad, 3)。拷贝根节点后拷贝a，递归处理a。
然后发现a的子节点无d这条路径。那么新建一个节点，然后恢复调用栈的过程中建立新的指向关系。
这里要注意智能指针和移动语义的运用。
/*******************************************************
* @brief 递归插入子树
*
* @tparam T
* @param new_root
* @param key
* @param val
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-19
*******************************************************/
template <class T>
void PutNode(const std::shared_ptr<bustub::TrieNode> &new_root, std::string_view key, T val) {
bool find = false;
// 在new_root的children找key的第一个元素
for (auto &pair : new_root->children_) {
// 如果找到了
if (key.at(0) == pair.first) {
find = true;
// 剩余键长度大于1
if (key.size() > 1) {
// 复制一份找到的子节点，然后递归对其写入
std::shared_ptr<bustub::TrieNode> ptr = pair.second->Clone();
// 递归写入
PutNode<T>(ptr, key.substr(1, key.size() - 1), std::move(val));
// 覆盖原本的子节点
pair.second = std::shared_ptr<const TrieNode>(ptr);
} else {
// 剩余键长度小于等于1，则直接插入
// 创建新的带value的子节点
std::shared_ptr<T> val_p = std::make_shared<T>(std::move(val));
TrieNodeWithValue node_with_val(pair.second->children_, val_p);
// 覆盖原本的子节点
pair.second = std::make_shared<const TrieNodeWithValue<T>>(node_with_val);
}
return;
}
}
if (!find) {
// 没找到，则新建一个子节点
char c = key.at(0);
// 如果为键的最后一个元素
if (key.size() == 1) {
// 直接插入children
std::shared_ptr<T> val_p = std::make_shared<T>(std::move(val));
new_root->children_.insert({c, std::make_shared<const TrieNodeWithValue<T>>(val_p)});
} else {
// 创建一个空的children节点
auto ptr = std::make_shared<TrieNode>();
// 递归
PutNode<T>(ptr, key.substr(1, key.size() - 1), std::move(val));
// 插入
new_root->children_.insert({c, std::move(ptr)});
}
}
}
/*******************************************************
* @brief 写时拷贝
*
* @tparam T
* @param key
* @param value
* @return Trie
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-19
*******************************************************/
template <class T>
auto Trie::Put(std::string_view key, T value) const -> Trie {
// Note that `T` might be a non-copyable type. Always use `std::move` when creating `shared_ptr` on that value.
// throw NotImplementedException("Trie::Put is not implemented.");
// ! 在根节点插入
if (key.empty()) {
std::shared_ptr<T> val_p = std::make_shared<T>(std::move(value));
std::shared_ptr<bustub::TrieNodeWithValue<T>> new_root = nullptr;
// 如果根节点无子节点
if (root_->children_.empty()) {
// 直接修改根节点
new_root = std::make_unique<TrieNodeWithValue<T>>(std::move(val_p));
} else {
// 如果有，构造一个新节点，children指向root_的children
new_root = std::make_unique<TrieNodeWithValue<T>>(root_->children_, std::move(val_p));
}
// 返回新的Trie
return Trie(std::move(new_root));
}
// ! 拷贝根节点，如果为空，则新建一个空的TrieNode
std::shared_ptr<bustub::TrieNode> new_root = nullptr;
if (this->root_ == nullptr) {
new_root = std::make_unique<TrieNode>();
} else {
new_root = root_->Clone();
}
// ! 递归插入
PutNode<T>(new_root, key, std::move(value));
// ! 返回新的Trie
return Trie(std::move(new_root));
// You should walk through the trie and create new nodes if necessary. If the node corresponding to the key already
// exists, you should create a new `TrieNodeWithValue`.
}Remove
不仅要删除键值，还需要在删除后清除所有不必要的节点。如果能理解Put的逻辑，那么Remove就很简单了。
递归遍历key，如果发现当前的key的元素不在当前递归的trie节点的子节点映射中，则说明trie没有这个键，直接返回false表示没有移除任何键值。
如果当前的key的元素在当前递归的trie节点的子节点映射中，继续判断这是不是key的最后一个元素（遍历到终点），如果遍历到终点，则判断key节点是否有子节点，如果没有子节点则说明可以直接删除key节点，如果有子节点则不能删除，只能将key节点转为无value的普通节点，然后返回true表示删除了一个键值。
如果没有遍历到终点，和Put逻辑一样，拷贝当前的key[i]在当前递归的trie节点的子节点映射的节点，然后以拷贝得到的节点继续递归。获取递归的结果，如果为false，则说明没有删除任何节点，直接返回false，否则判断当前节点是否可删除（是否为value节点 or 是否有子节点），如果可删除则删除当前节点并返回true。
/*******************************************************
* @brief 递归remove操作
*
* @param new_root
* @param key
* @author Andromeda (ech0uname@qq.com)
* @date 2024-01-19
*******************************************************/
auto RemoveNode(const std::shared_ptr<bustub::TrieNode> &new_root, std::string_view key) {
// 在new_root的children找key的第一个元素
for (auto &pair : new_root->children_) {
// 继续找
if (key.at(0) != pair.first) {
continue;
}
if (key.size() == 1) {
// 是键结尾
if (!pair.second->is_value_node_) {
return false;
}
// 如果子节点为空，直接删除
if (pair.second->children_.empty()) {
new_root->children_.erase(pair.first);
} else {
// 否则转为tirenode
pair.second = std::make_shared<const TrieNode>(pair.second->children_);
}
return true;
}
// 拷贝一份当前节点
std::shared_ptr<bustub::TrieNode> ptr = pair.second->Clone();
// 递归删除
bool flag = RemoveNode(ptr, key.substr(1, key.size() - 1));
// 如果没有可删除的键
if (!flag) {
return false;
}
// 如果删除后当前节点无value且子节点为空，则删除
if (ptr->children_.empty() && !ptr->is_value_node_) {
new_root->children_.erase(pair.first);
} else {
// 否则将删除的子树覆盖原来的子树
pair.second = std::shared_ptr<const TrieNode>(ptr);
}
return true;
}
return false;
}
auto Trie::Remove(std::string_view key) const -> Trie {
// throw NotImplementedException("Trie::Remove is not implemented.");
if (this->root_ == nullptr) {
return *this;
}
// 键为空
if (key.empty()) {
// 根节点有value
if (root_->is_value_node_) {
// 根节点无子节点
if (root_->children_.empty()) {
// 直接返回一个空的trie
return {};
}
// 根节点有子节点，转为tirenode
std::shared_ptr<bustub::TrieNode> new_root = std::make_shared<TrieNode>(root_->children_);
return Trie(new_root);
}
// 根节点无value，直接返回
return *this;
}
// 创建一个当前根节点的副本作为新的根节点
std::shared_ptr<bustub::TrieNode> new_root = root_->Clone();
// 删除
bool flag = RemoveNode(new_root, key);
if (!flag) {
return *this;
}
if (new_root->children_.empty() && !new_root->is_value_node_) {
new_root = nullptr;
}
return Trie(std::move(new_root));
// You should walk through the trie and remove nodes if necessary. If the node doesn't contain a value any more,
// you should convert it to `TrieNode`. If a node doesn't have children any more, you should remove it.
}
Task #2 - Concurrent Key-Value Store
写时拷贝允许多个线程或进程同时读取共享数据，而不需要加锁，因为写进程并不修改原始的内存，而是在写入时拷贝一份原始的内存。所以，只有在有写操作需要修改共享数据时，才会进行加锁操作。这样可以减少锁的竞争，提高并发性能。
刚刚实现了单线程环境中使用的写时复制trie，接下来多线程环境实现一个并发控制的键值存储。
对于Get操作，先获取访问控制锁，防止此时其他写进程修改trie。得到当前时间节点的trie并释放访问控制锁。
由于实现了写时拷贝，因此只需要加锁得到了当前时刻的trie，之后就不需要管写进程了。
template <class T>
auto TrieStore::Get(std::string_view key) -> std::optional<ValueGuard<T>> {
// Pseudo-code:
// (1) Take the root lock, get the root, and release the root lock. Don't lookup the value in the
// trie while holding the root lock.
// (2) Lookup the value in the trie.
// (3) If the value is found, return a ValueGuard object that holds a reference to the value and the
// root. Otherwise, return std::nullopt.
// throw NotImplementedException("TrieStore::Get is not implemented.");
// access lock
std::unique_lock<std::mutex> lock(this->root_lock_);
Trie root = this->root_;
lock.unlock();
// 获取键值
const T *val = root.Get<T>(key);
// 封装
if (val != nullptr) {
return ValueGuard<T>(root, *val);
}
return std::nullopt;
}先获取读写锁，防止其他写进程写入trie，然后向root中放入key-value（此时不需要获取访问锁，因为是写时拷贝，所以不会影响原始的trie）。
之后获取访问锁，此时需要更新trie，所以需要避免其他进程读。更新原始trie后释放锁。
template <class T>
void TrieStore::Put(std::string_view key, T value) {
// You will need to ensure there is only one writer at a time. Think of how you can achieve this.
// The logic should be somehow similar to `TrieStore::Get`.
// throw NotImplementedException("TrieStore::Put is not implemented.");
// 先获取写锁
std::unique_lock<std::mutex> wlock(this->write_lock_);
// 向root中插入kv，并得到新的trie
const Trie trie = this->root_.Put<T>(key, std::move(value));
// 再获取访问锁
std::unique_lock<std::mutex> alock(this->root_lock_);
// 更新root
this->root_ = trie;
// 释放锁
alock.unlock();
wlock.unlock();
}Remove和Put是一样的，不再赘述了。
void TrieStore::Remove(std::string_view key) {
// You will need to ensure there is only one writer at a time. Think of how you can achieve this.
// The logic should be somehow similar to `TrieStore::Get`.
// throw NotImplementedException("TrieStore::Remove is not implemented.");
// 先获取写锁
std::unique_lock<std::mutex> wlock(this->write_lock_);
// 删除key，并得到新的trie
const Trie trie = this->root_.Remove(key);
// 再获取访问锁
std::unique_lock<std::mutex> alock(this->root_lock_);
// 更新root
this->root_ = trie;
// 释放锁
alock.unlock();
wlock.unlock();
}最后两个，一个调试任务（推荐vscode或者Clion或者GDB，不推荐瞪眼法或者cout法，相信我，这样调试会怀疑人生的）没啥说的。一个实现upper和lower也很简单，找到在哪里改就行了。
