Benson's blog

最好的安排

0%

CMU15445 Project

发表于 更新于 分类于

本文章记录CMU15445 2023fall课程的实验内容，实验初始源代码链接，注意不要在github中下载最新的bustub源代码，并采用官方提供的Autograde平台进行评测，邀请码KK5DVJ

Project0 C++ Primer

2024-09-10-11-23-39.png

本实验要求为前缀树数据结构完善Get\Put\Remove三种方法，需要注意的是，为了提高前缀树的并发可访问性，我们需要用新的map构建新的节点，以返回新的前缀树Trie

Task1 写时复制前缀树

Get

实现Get读取方法需要考虑以下几点

  • 存在以下两种边缘情况

    • Trie为空(root_=nullptr)，default()构造或Remove删除尽有效值节点

    • key字符串为空，直接查找根节点中的值

  • 遍历节点时，以下两种情况直接返回

    • 目标key不存在，直接返回nullptr
    • 查找到目标节点，并使用std::dynamic_pointer_cast方法成功转化为TrieNodeWithValue进行值读取，需要注意的是std::dynamic_pointer_cast方法在运行时检查类型转换

Put

关于Put和Remove两种写方法，可以采用递归实现，每一层递归用于向子节点插入key字符串的去头子串，关于该递归方法需要考虑以下几点

1
2
3
4
// 函数签名
template <class T>
static auto RecursivePut(const std::shared_ptr<const TrieNode> &node, std::string_view key, T value)
    -> std::shared_ptr<const TrieNode> {

  • 两种边缘情况

    • key字符串为空，直接将值插入当前节点，但需要注意继承原先节点的children_子节点映射
    • key字符串长度为1，考虑两种情况
      • 该字符已存在对应子节点，需要继承原节点的children_映射并更新value_
      • 该字符不存在对应子节点，则用value_构造新的子节点，并与父节点连接

  • 递归插入，同样考虑两种情况

    • 当前字符串key的首字符已存在子节点，则需要向递归函数中传入已存在的子节点指针

    • 当前字符串首字符不存在子节点，则传入新构造的空子节点指针

      此处存在缺陷是，函数传入的空子节点，进入函数体内部后又会被重新Clone()一次，舍弃原先的空节点，造成无用的重复构造

Remove

1
2
3
// 函数签名
static auto RecursiveRemove(std::shared_ptr<const TrieNode> node, std::string_view key)
    -> std::shared_ptr<const TrieNode>
  • 三种边缘情况
    • key字符串为空，需要删除根节点中的值
    • key字符串的首字符不存在，说明待删除的键不存在，直接返回原节点
    • key字符串长度为1
      • 该字符对应的节点不存在值，说明该键值对不存在，直接返回原节点
      • 键值对存在，但是值节点不是叶子节点，需要将值节点降级为内部节点
      • 键值对存在，且值节点是叶子节点，则需要children_.erase()删除节点
  • 递归删除，考虑两种情况
    • 返回的子节点既不是值节点，children_也为空，则需要摒弃该子节点
    • 否则，将新的子节点连接到当前节点

Task2 并发键值存储

在前缀树的并发访问中，题目要求读之间兼容、写操作互斥、写操作进行时，读操作能够从旧根中开始。该并发设计最难在于最后一点，但是Task1的正确实现能够满足这一点

如上图所示，当读写操作并行时，只要读操作能够获取原先的旧根指针，就能在Get方法的逻辑中正确读下去，原先逻辑删除的节点仍然物理存在

Project1 Buffer Pool

Task1 LRUKReplacer

​ 在测试LRUKReplacer类型中LRU-K算法时，重点在于Evict()驱逐方法的实现。

​ 关于LRU算法，我们只关注缓冲池中每一个页帧最近一次访问的时间，所谓least recently used算法，即LRU-1算法，最近一次使用距离现在最远的页帧是我们需要淘汰的对象，但LRU-1不能体现LRU算法最近最少使用的思想，因为页帧的淘汰都仅考虑最近一次的访问时间戳（而不是最近多次），其存在弊端就是未能考虑到页帧访问的频率：假设页帧2的访问频率远低于页帧1，而页帧2和页帧1同时存在于缓冲池中，但是页帧2最近一次访问时间近于页帧1，那么在驱逐时可能会将访问频率高得多的页帧1驱逐出去。

​ 因此，在LRU-K算法中，我们跟踪了缓冲池中每一个页帧最近K次访问的时间戳，每当要进行淘汰时，我们驱逐倒数第K次访问距离现在最远的页帧，在这样巧妙的比较下，该算法隐式地将页帧访问频率考虑了进去。

​ 参考以下图片，可以看到容量为2的缓冲池中缓存了A，B的访问频率远小于A，但是B最近的访问近于A，在LRU算法中，此时我们淘汰A；但是在LRU-5算法中，我们将当前时间戳和页帧倒数第5次访问的时间戳做差，发现B的差值更大，说明B的访问频率低于A，淘汰对象为B

2341726911523-pic.jpg