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

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

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

前言

实验要求网站

太吓人了,这甚至只是个课程入门实验,但是前两部分主要的内容差不多花了我一整天🥲🥲🥲(可能是我的C++基础太差了😥😥😥。

image-20240119165532331

主要是考察一下对C++的熟练程度,比如智能指针、移动语义、并发控制,还有数据结构的基础。

19d7df643904

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的子节点即可。

image-20240119171838741

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

image-20240119171827283

如果要在其中插入一个(bc, 3),首先拷贝root到newRoot

image-20240119172024363

在newRoot中发现没有b这条路径,那么直接创建一个新节点即可,对新建的b节点进行递归操作

image-20240119172230480

发现没有c路径,同样创建一个新节点,这是key的末尾,因此直接设置value为3,结束递归

image-20240119172414136

然后在退出调用栈的过程中建立新的指向关系,这样就完成了插入的过程。

image-20240119172521865

如果键的前面一部分在trie中已经存在了,步骤还是类似的,只不过不是新建节点而是拷贝那个节点,然后再拷贝到新节点上进行递归。比如要在其中插入一个(ad, 3)。拷贝根节点后拷贝a,递归处理a。

image-20240119172901891

然后发现a的子节点无d这条路径。那么新建一个节点,然后恢复调用栈的过程中建立新的指向关系。

image-20240119173058846

这里要注意智能指针和移动语义的运用。

/*******************************************************
 * @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也很简单,找到在哪里改就行了。

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

文章作者
能不能吃完饭再说
隐私政策
PrivacyPolicy
用户协议
UseGenerator
许可协议
NC-SA 4.0


© 版权声明
THE END
喜欢就支持一下吧
点赞20赞赏 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片