CMU 15445 2023fall #Project0 实现一个简单的k-v存储引擎

Andromeda

发布于 2024-01-20 09:43:09

7580

发布于 2024-01-20 09:43:09

文章被收录于专栏：Andromeda的专栏

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()) {
    const bustub::TrieNodeWithValue<T> *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 (size_t i = 0; i < key.length(); i++) {
    auto it = cur->children_.find(key[i]);
    // 没找到
    if (it == cur->children_.end()) {
      return nullptr;
    }
    // 找到了
    cur = it->second;
  }
  if (cur->is_value_node_) {
    const bustub::TrieNodeWithValue<T> *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 put(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();
        // 递归写入
        put<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>();
      // 递归
      put<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>> newRoot = nullptr;

    // 如果根节点无子节点
    if (root_->children_.empty()) {
      // 直接修改根节点
      newRoot = std::make_unique<TrieNodeWithValue<T>>(std::move(val_p));
    } else {
      // 如果有，构造一个新节点，children指向root_的children
      newRoot = std::make_unique<TrieNodeWithValue<T>>(root_->children_, std::move(val_p));
    }
    // 返回新的Trie
    return Trie(std::move(newRoot));
  }

  // ! 拷贝根节点，如果为空，则新建一个空的TrieNode
  std::shared_ptr<bustub::TrieNode> newRoot = nullptr;
  if (this->root_ == nullptr) {
    newRoot = std::make_unique<TrieNode>();
  } else {
    newRoot = root_->Clone();
  }

  // ! 递归插入
  put<T>(newRoot, key, std::move(value));

  // ! 返回新的Trie
  return Trie(std::move(newRoot));

  // 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
 *******************************************************/
bool remove(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 = remove(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 Trie();
      } else {
        // 根节点有子节点，转为tirenode
        std::shared_ptr<bustub::TrieNode> newRoot = std::make_shared<TrieNode>(root_->children_);
        return Trie(newRoot);
      }
    }
    // 根节点无value，直接返回
    return *this;
  }

  // 创建一个当前根节点的副本作为新的根节点
  std::shared_ptr<bustub::TrieNode> newRoot = root_->Clone();

  // 删除
  bool flag = remove(newRoot, key);
  if (!flag) {
    return *this;
  }

  if (newRoot->children_.empty() && !newRoot->is_value_node_) {
    newRoot = nullptr;
  }

  return Trie(std::move(newRoot));

  // 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();
}

------本页内容已结束，喜欢请分享------

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

std