CMU15-445 PROJECT1 BUFFER POOL MANAGER 项目记录

任务1：可扩展哈希表
TASK#1: EXTENDIBLE HASH TABLE

个人认为通过网上的资料比听网课效率更高，所以本人通过参考各种网站以及博客来学习可扩展哈希表算法。 再加之项目注释写得也比较清楚了，按照注释以及项目主页的提示按部就班地进行编码，还是比较容易完成的。

可扩展哈希 是一种动态散列方法，其中目录（directory）和桶（bucket）用于散列数据。

主要特点及相关术语

目录：目录存储指向桶地址的指针。每个目录都有一个唯一的 id，每次扩展时该 id 可能会发生变化。哈希函数返回此目录 id，用于导航到适当的存储桶。

\(目录数 = 2^{Global Depth}\)。

桶：桶用于散列实际数据。如果桶的局部深度小于全局深度，则桶可能包含多个指向它的指针。

全局深度：与目录相关，表示哈希函数用于对密钥进行分类的位数。全局深度 = 目录 id 中的位数。

局部深度：与 全局深度 类似，只是 局部深度 关联的是桶而不是目录。根据全局深度的局部深度用于决定在发生溢出时要执行的操作。局部深度≤全局深度。

桶分裂（split）：当桶中的元素数量超过特定大小时，桶被分成两部分。

目录扩展（expand）：目录扩展发生在桶溢出时。当 溢出桶的 局部深度 等于 全局深度 时，执行目录扩展。

实现过程

Bucket类的实现

课程主页建议我们先完成 Bucket 类的编写，其中包括 Find(), Remove(), Insert()三个方法的实现。 Bucket类内置list结构，存储键值对。三个函数的实现方式都是遍历该list。

Find() 在找到对应元素时返回 true，否则返回 false；Remove()在找到对应元素时使用list.erase() 删除该元素并返回 true，若没有找到对应元素返回 false； Insert()在遍历过程中如果发现同样的键值则返回 false，否则使用 list.emplace_back() 插入键值对。

Insert()方法实现

首先理解一下项目给出的 IndexOf() 方法，因为 Insert() 方法的实现需要借鉴类似的思想。

1
2
3
4
5
template <typename K, typename V>
auto ExtendibleHashTable<K, V>::IndexOf(const K &key) -> size_t {
  int mask = (1 << global_depth_) - 1;
  return std::hash<K>()(key) & mask;
}

对于给定的键值，首先根据全局深度计算mask，比如如果全局深度是5，则(1 << global_depth_)为100000，mask则为11111，与mask按位与即保留原key哈希值的后5位，即得到对应目录的位置。

理解这个原理后先放一边，先讨论以下最简单的情况，也就是 桶无须分裂 的时候：

此时调用IndexOf()找到的index对应的就是需要进行插入操作的桶。此时有两种情况： * 如果键值已经存在，则修改key对应的value为新的值，并直接return即可； * 否则 直接调用 Bucket-> Insert() 在这个桶中插入键值对即可。

接着就是最复杂的部分，就是 需要目录扩展和桶分裂 的情况：

首先要知道，桶在一次插入的过程中可能需要进行多次分裂，所以我们需要进入while (dir_[IndexOf(key)]->IsFull())循环。

多次分裂是什么情况呢？

一个桶装满的时候，桶中的key对应的hash后若干位（取决于局部深度）一定是一样的，但我们无法保证前面的几位是否就不一样，如果运气不好，在局部深度前的几位都是相同的话，则可能需要分裂出更多的桶来装，否则根本就装不进去。

如果全局深度等于局部深度，则目录需要扩展。

如何进行目录扩展？LRU-K中的k，其实是指最近访问页面的次数，所以我们不难理解，上文所介绍的LRU算法其实就是LRU-1，但是因为仅访问1次就能替代别人，可能会造成“缓存污染”的问题，因此提出了LRU-K的概念。

其核心思想就是将访问一次就能替代的“1”提升为"K"。

将目录的size扩展为原来的两倍，上面的一半最高位是0，下面的一半最高位是1.

下面的一半直接拷贝上面的一半，因为 要指向除最高位以外所有低位相同对应的桶。 杨是要进行分裂的。

如何将桶进行分裂？

首先弄出两个桶，再将原桶中的元素一个个装进去。这里分桶装也是根据key的hash和mask的按位与，只不过这里 

1
int mask = 1 << target_bucket->GetDepth();
这是因为我们需要看他的高位而不是低几位。

分完桶中的键值对之后，再将dir中的原先指向target_bucket的指针重新分配一遍。

注意这里我们的bucket都用shared_ptr，所以不用担心原来的bucket会怎么样。

遇到问题及解决方案

在本地测试的时候，进程停滞了，调试提示 

1
auto bucket_0 = std::make_shared<Bucket>(bucket_size_, target_bucket->GetDepth() + 1);
这行代码有问题。

原因是我的逻辑本身没有完善就拿去跑测试了。那为什么会停滞呢？那是因为在进行扩展时，需要将原有的桶分裂成两个新的桶，同时将哈希表中的指针进行重新分配。我的代码中实现了这个分裂过程，但是没有将新的桶的指针更新到哈希表中。这会导致新的键值对无法正确插入，最终导致进程停滞。

任务2：LRU-k页面置换算法
TASK#2: LRU-K Replacement Policy

算法本身比较复杂，本人是先从leetcode的medium题lru入门，lru-k是在此基础上优化的一种算法。

先说什么是LRU，LRU是Least Recently Used的缩写，即最近最少使用算法。leetcode上是通过一个双向队列和一个哈希表实现的。具体来说：

维护一个队列，最近访问的在最底层，最近最少访问的在最上层。

当队列满了，有新的元素进队时，将最上层的元素出队列，将新元素放到队尾。

当访问已经存在于队列的中的老元素，将老元素放到队列的最后一位，其他元素往前补位。

而LRU-K中的k，其实是指最近访问页面的次数，所以LRU算法其实就是LRU-1，但是因为仅访问1次就能替代别人，可能会造成“缓存污染”的问题，因此提出了LRU-K的概念。

算法原理

与LRU算法不同，LRU-K算法需要维护两个队列：历史队列 和 缓存队列。

历史队列保存着每次访问的页面，而缓存队列则是保存已经访问k次的页面。

对于一个访问页面，有以下三种情况：

  1. 当页面访问次数达到了k次，就将其从历史队列中移除，并将其加入缓冲队列。

  2. 若页面访问次数尚未达到k次，则将其移到历史队列队首。

  3. 若页面访问次数大于k_次，将其移到缓冲队列队首。

当我们需要淘汰一个页面时，则先从历史队列淘汰，再从缓冲队列淘汰。这里LRU-k算法可能会有不同的说法，比如理解是 第k次访问距离现在最久 的那个页面。但在本项目中，根据项目注释，

驱逐操作中，找到具有最大后向 k 距离的帧并驱逐该帧。只有标记为“可驱逐”的帧才是驱逐的候选者。 具有少于 k 个历史值的帧的向后 k 距离将被认为是 +inf。 如果多个帧具有 inf 后向 k 距离，则驱逐具有最早时间戳的帧。 框架的成功驱逐应该减少替换器的大小并删除框架的访问历史记录。

这正好与先淘汰历史队列再淘汰缓存队列的操作吻合。

另外，我的实现类中有以下私有成员： 

1
2
3
4
5
6
7
8
size_t curr_size_{0};
size_t replacer_size_;
size_t k_;
std::mutex latch_;
std::unordered_map<frame_id_t, size_t> use_count_;
std::list<frame_id_t> his_list_, cache_list_;
std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> his_map_, cache_map_;
std::unordered_map<frame_id_t, bool> is_evictable_;
curr_size_ 记录当前可驱逐的页面数量； use_count_记录页面的使用次数；his_list_, cache_list_ 分别是 历史队列 和 缓冲队列；his_map, cache_map_分别记录页面在历史队列或者缓冲队列中的位置；is_evictable_用于记录页面是否可以被驱逐。

遇到问题及解决方案

其实在做project1的时候，遇到的问题有很多，但是都没有及时记录，现在通过在gradescope的提交记录回忆一下。

最严重的问题其实是忘记加锁了，在万分仔细地检查逻辑之后发现没有加锁，导致了本地测试能过，而线上测试不能过。

另外，由于本地测试对于Remove()方法的测试太弱了，导致线上Remove()引发的问题很多，于是在修改这个方法上花了比较多的时间。对于这个方法，在按要求判断是否需要抛出异常时，需要判断!is_evictable_[frame_id]而frame_id不一定存在在表中，所以要修改异常部分代码： 

1
2
3
if (is_evictable_.find(frame_id) != is_evictable_.end() && !is_evictable_[frame_id]) {
    throw std::exception();
  }

在Evict()以及Remove()方法中，需要驱逐或者删除页面的时候，要注意各个成员的erase()顺序，否则会出现heap-use-aftrer-free的错误。

任务3：缓冲池管理器实例
Task #3 - Buffer Pool Manager Instance

这部分没有太难的数据结构与算法上的实现。让人眼花缭乱的是根据注释编写代码。

部分功能实现

比较复杂的是NewPgImp()：

  1. 首先检查缓冲池中是否有可用的空闲页面。如果有，从空闲页面中选择一个页面。否则，从替换器中选择一个可替换的页面。

  2. 分配新的页面 ID。如果分配失败，则返回 nullptr。

  3. 更新元数据并pin页面。这里更新两个地方的元数据：

    缓冲池中的 page_table_：从原有页面 ID 的映射中删除该页面，插入新的页面 ID 和缓冲池中选择的帧 ID 的映射。

    帧表 frame_table_：重置帧的元数据和数据。更新页面 ID 和 pin 计数，并将 is_dirty_ 设置为 false。 将新页面插入缓冲池，并且返回该页面的指针。返回前要确保该帧被固定（Pinned），并且更新 replacer 访问历史。

以及 FetchPgImp()：

  1. 在缓冲池中查找目标页面，如果找到则直接返回对应的 Page 对象，并将该帧设置为不可淘汰（即被固定）。

  2. 如果目标页面不在缓冲池中，则需要从磁盘中读取该页面并将其载入到缓冲池中。首先需要选择一个可用的帧（令其id为frame_id）来存放该页面，此过程与NewPgImp()中的过程类似。

  3. 如果找到了可用的帧，则需要将旧页面从该帧中移除，然后读取目标页面的数据并将其存入该帧中。如果该帧原来的页面是脏页面，则需要将其写回磁盘。

  4. 接着调用disk_manager_->ReadPage()从磁盘读取数据存到frame_id处。

  5. 最后需要将该帧设置为不可淘汰（即被固定），并将其访问历史记录到replacer中，以便在进行淘汰时能够选择最近最少访问的帧。然后返回pages_[frame_id]。

    需要注意的是，如果在创建新页面时发现内存不足，则会返回 nullptr。

过多的此处就不赘述了，task3就是按规矩办事，别多办别漏办别办错就行。

遇到问题及解决方案

出现LeakSanitizer: detected memory leaks问题，并且在gradescope测试中的HardTest总是过不了，最后发现是在一个free_list_的取帧操作中忘记pop了。

内存泄漏可能是程序的一个严重问题，可以导致程序崩溃、性能下降等问题，因此在开发过程中应该注意内存管理，避免出现内存泄漏问题。

最后附上通关图！！！

满分通关！！！
通关！！！
开发
#C++ #CMU15-445 #数据库
CMU15-445 PROJECT1 BUFFER POOL MANAGER 项目记录
http://example.com/2023/03/06/CMU15445-PROJ1/
作者
Melrose Wei
发布于
2023年3月6日
许可协议