【CMU15-445 Fall2023】Project2 Extendible Hash Index 小结

发表于 分类于 标签 , Disqus： 本文字数： 3.5k 阅读时长 ≈ 13 分钟

该系列博客只是为了记录自己在写Lab时的思路，按照课程要求不会在Github和博客中公开源代码。欢迎与我一起讨论交流！

太菜了，从没打过这么艰难的仗QAQ。由于课程的要求不能公开源代码，所以网上的资源会少很多，平台上的测试案例比较全面，有的还比较刁钻，需要考虑到可拓展哈希的实现细节。在自认为写完了后，提交了近40来次总有几个测试集过不了，还好没有崩溃，在看了几篇博客的方法后，加上自己画图理解，最后终于过了😭。不过回头写博客的时候再去看代码，也没有特别的复杂，还是得明白其中的算法逻辑是如何实现的。

Task1 - Read/Write Page Guards

简单来说，就是为Page实现一个RAII来自动管理资源。因为在BufferPoolManager::Unpin中，每次调用这个函数，都会让对应的page的pin_count_ - 1，当这个值为0时，这个page就可以被回收，或者说被替换了。但如果我们忘记去手动调用，该页面将永远不会被逐出缓冲池。由于缓冲池以更少的帧数运行，磁盘内外的页面交换将更多。不仅性能受到影响，而且很难检测到错误。

主要需要考虑如何编写移动构造、移动赋值的逻辑。移动了一个对象后，原来的对象的资源应该转移到了新对象上，那么原来的对象无法再访问资源（将原来对象的资源重置nullptr或清空）。

还有一个Drop()的接口，这是提供给使用者的释放资源的api，在实现虚构函数时可以直接调用它。Drop的实现就是调用Unpin，然后置空资源。需要注意的是，在进行移动赋值时，一开始也要Drop一下，考虑这样一种情况：

1
2
auto p = std::move(basic_page_guard);
p = std::move(basic_page_guard2);

这个时候同一个变量p接管了两个page，那么应该在第二个移动赋值时先drop掉第一个，因为第一个page不再使用了，自然要Unpin。

还有就是在三个page guard类重载移动赋值时，如果需要移动的对象和自身是同一个，那么直接返回自己就好：

1
2
3
4
5
6
auto BasicPageGuard::operator=(BasicPageGuard &&that) noexcept -> BasicPageGuard & {
  if (&that == this) {
    return *this;
  }
  // ... 其他操作
}

在ReadPageGuard和WritePageGuard的Drop()中，还需要考虑释放管理的page的锁。对应的，锁的获取发生在FetchPageWrite()和FetchPageWrite()中。

Task2 - Extendible Hash Table Pages

为什么我们需要可扩展哈希？

下图来源：https://www.bilibili.com/video/BV1Qt421w7JT

在bustub的设计中，Header Page，Directory Page和Bucket Page都是无法直接构造出来的，即不能通过构造函数创建，只能通过各自的PageGuard中的As()或者AsMut()函数来转换。

header page中有一个max_depth_的成员变量，1 << max_depth_即为header page中能存放的目录的索引的数量。当我们有值需要放入哈希表时，获取hash(key)的二进制最高max_depth_位作为索引，再从header中对应位置去找到directory。对应的ExtendibleHTableHeaderPage中的功能实现并不难。

Directory

directory中有两个depth：

  • Global Depth：若global depth为n，那么这个Directory就有2^n个entry（相当于指向2^n个bucket）
  • Local Depth：若local depth为n，则在这个对应的bucket下，每个元素的key的最后n位都相同

类似header中获取下一级页的索引，directory获取hash(key)的二进制最低global_depth_位作为索引。那local depth的作用是什么呢？

这就要说到可拓展哈希中的插入和删除操作了。简单来说，在可拓展哈希表中，目录directory的大小是可以变化的（只要不超过最大容量限制）。目录中可能有多个entry映射到同一个bucket。当需要插入时，如果这个bucket还没有满时，可以直接插入；否则，需要将这个bucket分裂成两个bucket（或者说，将这个bucket中的一部分移动到另一个bucket中），并且这个bucket对应的local depth + 1，这样相比之前就多了一位二进制位去识别bucket。具体的用法可以看后面的Task3部分的笔记。

下面讲几个稍微难懂的函数：

GetGlobalDepthMask

这个函数的作用是获取global_depth_个二进制1，举个例子，如果global depth是2，那么说明这个目录当前的容量为2^2=4，索引为0~3，用两位二进制就能表示。

主要用于和hash(key)进行&操作，获取在directory中对应的索引位置。例如，假设key=3，hash(key)=101（二进制），global depth还是2，那么检查hash(key)的最低两位即为01，那么在directory就是第1个entry。

CanShrink

CanShrink() 的核心功能是检测是否可以减少全局深度（global depth），从而缩小哈希表的大小。它基于以下原则：

在可扩展哈希表中，每个桶（bucket）都有自己的局部深度（local depth），而整个哈希表有一个全局深度（global depth）。如果所有桶的局部深度都小于当前的全局深度，说明哈希表的某些位（超过局部深度的那些位）并没有被实际使用，因而可以安全地减少全局深度。

GetSplitImageIndex

GetSplitImageIndex() 是在可扩展哈希表中用于桶（bucket）拆分时确定拆分后的另一个桶的索引。

在可扩展哈希表中，当一个桶装满时，目录容量会翻倍，这个桶会拆分成两个桶（但是除了需要拆分的桶，其他目录还是指向原来的桶）。

  • 每个桶都有一个局部深度（local depth），表示这个桶在哈希表中使用了多少位哈希值来定位数据。桶拆分时，局部深度会增加。
  • 拆分后的桶与当前桶具有相同的局部深度值，只是在第一位上有所不同。例如，如果当前桶的局部深度为 2，那么拆分后的桶与其前后 2 位相同，只有第 1 位不同。

例如，当前桶的索引为 01，局部深度为 3。

  1. 计算翻转位的值：1 << (local_depth - 1) = 1 << (3 - 1) = 1 << 2 = 100 （即二进制的 0100）。
  2. 按位异或：bucket_index ⊕ 100 = 001 ⊕ 100 = 101（即二进制的 101，也就是十进制的 5）。

因此，拆分后的桶的索引是 101（5 in decimal）。

GetLocalDepthMask

这个函数主要是用在bucket的分裂和合并中，用于判断需要操作的bucket中的项在更新后应该属于directory下哪个entry对应的bucket（有点绕）。

和GetGlobalDepthMask一样，当前directory的entry映射的bucket的local_depth_是多少，其mask的二进制就是多少个1。

Bucket

Bucket存储着多个键值对，没有使用标准库的map，而是使用std::pair数组（如果都用标准库了要你实现啥哈希表hh）。

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MappingType std::pair<KeyType, ValueType>
static constexpr uint64_t HTABLE_BUCKET_PAGE_METADATA_SIZE = sizeof(uint32_t) * 2;
constexpr auto HTableBucketArraySize(uint64_t mapping_type_size) -> uint64_t {
  return (BUSTUB_PAGE_SIZE - HTABLE_BUCKET_PAGE_METADATA_SIZE) / mapping_type_size;
};

class ExtendibleHTableBucketPage {
  ...
 private:
  uint32_t size_;
  uint32_t max_size_;
  MappingType array_[HTableBucketArraySize(sizeof(MappingType))];
};

任务就是在这个bucket中增删查对应的key and value，由于内部使用的是定长数组，所以最简单的方法就是顺序操作。

但是需要注意的是，在bucket page的Insert操作中，注释上给的提示是：“当插入成功时返回true，插入失败或者键已经存在时返回false”。但是如果你按着“先判断bucket是否满了，再遍历bucket中的键值对数组，查找有没有key相同的，最后再插入”这样的逻辑去写，那当你提交时怎么测试都有几个测试集过不了，当时我想得脑子都要炸了也想不清怎么回事。

在看了一篇博客后，我按照他的逻辑~~“先遍历数组，如果有键值相同的，更新它而不是返回false，然后再判断是否已经满了，没满就再插入”~~去写，最后对了。（这里为啥用了删除线，是因为我的代码是按照这个逻辑来写的，但是在我写这篇博客时感觉不对劲，假如这个键已经存在，且此时bucket没有满，那更新之后又插入了一次，数据有重复）

Task3 - Extendible Hashing Implementation

细节！细节！还是TMD细节！

前两个task比较容易写，这个task其实本质上还是一个数据结构的设计实现问题，也就是哈希表如何插入数据和删除数据，但是细节需要注意太多了！如何考虑插入后的分裂，还有删除时的合并。从第一次提交到全部通过一共用了7天（哭）。

Insert

Insert操作需要注意的就是插入失败后的分裂问题，小细节在于下面逻辑步骤中的3，8.5和9（加粗表示）:

  1. 检查需要插入的键是否已经存在，如果存在就返回false，否则继续第二步
  2. 对key使用hash算法
  3. 从header通过hash(key)找到对应的directory page，如果directory不存在，那么创建新的directory page，再创建新的bucket page后执行插入；否则继续第四步。需要注意，如果判断了directory存在后，需要对header page guard进行Drop()操作，因为平台的测试集中有比较刁钻的情况，其buffer manager pool的大小只有3，如果不把header page释放，那么到时候需要进行分裂时无法再获取一个新的page！
  4. 从directory通过hash(key)找到对应的bucket page，如果page不存在，那么创建新的bucket page再插入；否则继续第五步
  5. 向bucket page中插入键值对，如果插入成功，返回true；否则继续第六步
  6. （循环开始）
  7. 检查当前directory是否已经满了，比如说directory的max_depth_是2，那么说明最多只能有四个bucket page，若此时已经有四个bucket了，那么已经满了，无法继续分裂桶；没满继续第八步
  8. 分裂桶
    1. 先创建新的bucket page作为当前bucket的镜像桶
    2. 如果global depth等于当前bucket的local depth，说明需要扩充directory的大小，同时调整扩充后的directory中的entry与bucket的映射
    3. 在directory中设置镜像桶，增加原桶和镜像桶的local depth，此时获取原桶的local depth对应的mask
    4. 通过mask将原桶拆成两个桶，比如原桶的local depth为2，对应的mask的二进制为$(11)_2$，通过&操作获取桶中每个键值对的hash(key)的最低两位，如果与bucket_index & mask相同，那么就说明这个键值对应该留在原桶，反之应该移至镜像桶
    5. 分裂成两个桶后，在使用mask判断需要插入的键值对应该插入那个桶，记录插入是否成功
  9. 考虑这样一种情况，需要插入的bucket满了后要进行分裂，但是有可能分裂后原来的键值对还是在一个bucket中，那这个时候插入就失败了，所以需要继续从第七步执行，直到directory满了或者插入成功
  10. （循环结束）
  11. return true

Remove

由于课程要求不能公开代码，加上网上关于可拓展哈希的操作多只有Insert，而Remove很少有介绍说明的，所以不得不去思考很多情况，加上自己画图去理解，当然还是去看了几篇大佬的博客我才慢慢写出了解决方案。

实验指导中说了对于Remove的合并需要进行递归的处理，但其实我们用循环去处理就行，至于为什么要递归去处理，下面的步骤9和步骤13中有加粗解释：

  1. 对key使用hash算法
  2. 从header通过hash(key)找到对应的directory page，如果directory不存在，return false；否则继续第3步。类似Insert，这里也需要Drop header page
  3. 从directory通过hash(key)找到对应的bucket page，如果page不存在，那return false；否则继续第4步
  4. 删除bucket中的key对应的键值对，如果删除失败，返回false；否则继续第5步
  5. 如果删除成功后bucket不为空，说明不需要合并，返回true；否则继续第6步
  6. （循环开始）
  7. 获取当前bucket的镜像bucket，如果二者的local depth不相同，那么结束循环；否则继续第8步
  8. 当前桶和镜像桶可以合并，将当前桶的映射更新到镜像桶，并且local depth都 -1，删除当前桶的bucket page
  9. 删除了bucket_index对应的page后，虽然调整了其对应的local depth和page id，但是还应该遍历所有的可成为镜像桶的index，如果它们的local depth相同，也应该合并，记录需要合并的的bucket的page id
    1. 在遍历时不需要一个一个去遍历directory的entry，而是可以跳着遍历：只有index的后local_depth - 1位相同的才可能需要合并
  10. 如果需要合并的的bucket的page id数量为0，说明已经没有可以合并的bucket了，不应该继续合并，可以结束循环了；否则继续第11步
  11. 因为又合并了，所以原桶和其镜像桶对应的 local depth 又要 -1
  12. 删除需要合并的的bucket的page
  13. 从第7步继续，因为合并后的bucket在其local depth - 1后可能会碰到和其local depth相同的bucket，且其中还有空的bucket，这就需要不断去合并（这就是实验中说的递归合并）
  14. （循环结束）
  15. 缩减目录大小，直到无法缩小
  16. return true

Reference

  • https://www.cnblogs.com/wevolf/p/18302985
  • https://zhuanlan.zhihu.com/p/622221722
  • https://zhuanlan.zhihu.com/p/701875021