CMU 15-445: project2 - Extendible Hash Index

概述

第二个project是为BusTub实现一个基于磁盘的hash table index。

你需要使用可扩展(磁盘)散列方案实现一个散列表。该索引包含一个目录页，该目录页包含指向桶页的指针。这个table会通过你在project 1中实现的buffer pool来获取数据。

测试方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


zip project2-submission.zip src/include/buffer/lru_replacer.h \
src/buffer/lru_replacer.cpp \
src/include/buffer/buffer_pool_manager_instance.h \
src/buffer/buffer_pool_manager_instance.cpp \
src/include/buffer/parallel_buffer_pool_manager.h \
src/buffer/parallel_buffer_pool_manager.cpp \
src/include/storage/page/hash_table_directory_page.h \
src/storage/page/hash_table_directory_page.cpp \
src/include/storage/page/hash_table_bucket_page.h \
src/storage/page/hash_table_bucket_page.cpp \
src/include/container/hash/extendible_hash_table.h \
src/container/hash/extendible_hash_table.cpp

Task # 1 - PAGE LAYOUTS

需要实现两类Page的布局, 一个是作为目录, 一个则是bucket本身

HASH TABLE DIRECTORY PAGE

这个page包括整个hashtable的元数据, 他被分成以下几个field

Variable Name	Size	Description
`page_id_`	4 bytes	Self Page Id
`lsn_`	4 bytes	Log sequence number (Used in Project 4)
`global_depth_`	4 bytes	Global depth of the directory
`local_depths_`	512 bytes	Array of local depths for each bucket (uint8)
`bucket_page_ids_`	2048 bytes	Array of bucket `page_id_t`

实现这个只能修改 src/include/storage/page/hash_table_directory_page.h 和 src/storage/page/hash_table_directory_page.cpp.

HASH TABLE BUCKET PAGE

occupied_ : 如果occupied_ 的第i位为1代表array_的第i个索引已经被占用
readable_ : readable_的第i位为1代表array_的第i个索引保存了可读的value
array_ : 保存key-value对的数组

单个哈希表实例中key/value的大小将是相同的，但不能假设它们对所有实例相同.

只能修改src/include/storage/page/hash_table_bucket_page.h和src/storage/page/hash_table_bucket_page.cpp文件. 每次尝试读取或写入页面时，您需要首先使用其唯一的page_id从buffer pool中获取页面, 然后强制转换为一个目录或者bucket page.

要实现以下函数

Bucket Page: - Insert - Remove - IsOccupied - IsReadable - KeyAt - ValueAt

Directory Page: - GetGlobalDepth - IncrGlobalDepth - SetLocalDepth - SetBucketPageId - GetBucketPageId

思路

Bucket Page操作的逻辑?

看get函数的参数, 结果是一个 vector; 所以get的实现应该是遍历这个bucket, 然后找到所有匹配的value

这个occupied状态有点让人迷惑. 在测试中, 当insert之后, 该key-value对应的occupied和isReadable都被设置为1, 但是当remove之后, 这个occupied保持原样, 而isReadable为0, 这是为什么. 被占用之后岂不是没办法再使用吗如果不释放的话?

发现了一个新奇的东西: atomic_char. 在实验中, 为了并发安全需要使用他的方法去更新

实现这两个page的时候需要仔细地看单元测试程序, 因为它的occupied和readabled的含义有点混淆, 所以不能直接靠表面意思去猜测. 实际上, 在Insert和GetValue等函数中, 判断一个key是否存在都是使用的IsReadable, 而不是IsOccuped, 而在测试中, 当Remove一个已存在的key-value之后, 它的IsOccupied状态还是true, 而它的IsReadable状态则为false了. 这个IsOccupied状态还是让人困惑.

这个part的主要内容就是实现文档中描述的几个方法, 但实际上在实现part2的时候, 剩下的一些方法也需要去实现. 这里有很多位操作, 例如对判断一个bucket page是否Full的时候, 需要根据它的readable数组, 判断每一位是不是都为1, 例如

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


template <typename KeyType, typename ValueType, typename KeyComparator>
bool HASH_TABLE_BUCKET_TYPE::IsFull() {
  for (int i = 0; i < (int)OCCUPIED_BYTE_SIZE; i++) {
    // 不能写成 *(readable_ + i) != 0xff, 会被直接优化成 return false; 打不了断点
    if (*(readable_ + i) != -1) {
      return false;
    }
  }
  return true;
}

看起来有点麻烦, 因为每次判断一个page是否是full都需要遍历这个数组. 如果能维护一个size变量从而比较快的判断出是否是full就更好了. 但是这个bucket page似乎是要直接从buffer pool上的一个page强制类型转化的, 所以似乎不能随便添加成员变量.

而directory_page那部分就更简单了, 每个方法都只有少数的几行.

TASK #2 - HASH TABLE IMPLEMENTATION

概述

要实现这个project, 需要先了解Extendible Hash这种数据结构. 他是一种dynamic hashtable, 可以动态扩展的. hashtable扩展一直是个问题. 在redis中, 它的hash使用率达到一定阈值的时候, 他就会进行扩展, 方法是开启一个二倍容量的hashtable, 然后一遍接收外部的操作, 一边将原先hashtable的key/value数据增量地转移到新的hashtable, 从而避免一次性扩展时导致的CPU密集问题.

而这个Extendible Hash, 分为两大部分, 一个部分是目录, 一个部分是真正存储key/value数据的page集合.

文档要求

需要同时支持相同和不相同的key, 例如可以存在(key0, value0), (key0, value1), 但不可以存在两个(key0, value0).

KeyType只会是GenericKey类型, ValueType只会是64位的RID; KeyComparator是用来比较两个key的(不可以比较value); 它提示说可以简单地用 == 来比较两个ValueType.

以下是需要实现的功能:

目录索引
分裂buckets

当一个bucket满了无法进行插入的时候, 就需要将他split
当一个bucket是empty的时候, 就需要将其合并

bucket只能和他们的split image合并, 如果这个split image的local depth是和他一样.

并且只有当他们的local depth大于0的时候才可以merge(当local depth为0时, 只有一个bucket page吧, 那也无法merge啊, 这是初始page).

这个split image的概念他说可以看算法和代码的文档, 说明有啥我之前不知道的资料…找找看

然后发现了这个资料, 一个HashTable相关的文档, 不过它讲的太简略了, 需要搜索这个算法的原理: Extendible Hashing.

这里有一篇文章对这个介绍的不错, 15445课中也对这个算法进行了介绍, 当时我当时应该是开小差了, 没啥印象.
DIRECTORY GROWING

目录是可以增长的
Directory shrinking

只有当需要的时候才使用write lock或write latch, 否则可能会出现超时.

测试时发现一个bucket page的最大key-value数量为 496 (在当前key-value size的场景下)

1

2021-11-04 21:54:01 [../src/storage/page/hash_table_bucket_page.cpp:36:Insert] DEBUG - 一个bucket page中的key-value数量, BUCKET_ARRAY_SIZE: 496

实现相关的问题:

如果一个key-value的重复key太多, 例如513个, 超过了一个bucket的容量, 在split的时候应该如何划分? 因为同一个key他们的hash是一样的, split之后还是无法解决问题啊

恐怕需要扩展这个hashtable才能解决这个问题吧.

思路与实现

实现中最复杂的一部分就是SplitInsert和Merge, 因为他们涉及bucket page的分裂和合并, 不仅需要修改bucket page, 还需要修改directory page信息, 而如何找到对应的directory page的信息, 需要比较精细的位操作. 在fix了几个bug之后终于实现了SplitInsert, 并且增加了一个单元测试. 原先的单元测试较为简单, 只有十几个key-value的写入和查找以及remove, 并不会涉及到bucket page的split, 因此我把key-value数扩展到了60000个, 并成功通过了测试.

SplitInsert的思路如下:

首先, 在Insert执行时发现想要进行插入的Bucekt Page是Full的, 那么不能直接插入, 而是调用SplitInsert, 它实现了将这个key/value对应的Bucket page split成两个bucket page, 并重新分配这些key-value的逻辑.

在SplitInsert中, 首先按流程获取dir_page, bucket_page等信息, 然后需要遍历dir_page的所有bucket_index从而找到这个bucket page对应的所有bucket_index, 而这个过程是通过比较复杂的, 因为需要通过local depth 掩码的比较来判断.

例如, 当前的dir_page总共指向4个bucket_page, 在bucket_index中他们的后缀分别为00, 01, 10, 11, global depth mask位11, 每个bucket_page的local depth也为0, mask也为11. 当我们需要对10所对应的bucket_page执行split操作时, 标识这两个page的后缀应该变为010, 110, 那么在操作的时候, 先遍历找到所有后缀为10的索引, 然后再将其中后缀为110的一半的索引对应的bucket_page设置为新分配的索引, 从而实现了一个bucket page的分裂.

在这之后需要将LocalDepth+1, 如果其大小超过了GlobalDepth, 那么需要更新GlobalDepth. 之后, 需要将旧的bucket_page中的所有key-value进行重分配, 可以在遍历的时候进行判断它是否需要更新bucket_page, 如果是则将其插入到新的bucket_page, 并在旧的bucket_page中remove掉, 否则就不需要处理.

实现代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


template <typename KeyType, typename ValueType, typename KeyComparator>
bool HASH_TABLE_TYPE::SplitInsert(Transaction *transaction, const KeyType &key, const ValueType &value) {
  if (nullptr == transaction) {
    // 更新 对应bucket 的 LocalDepth
    HashTableDirectoryPage *dir_page = FetchDirectoryPage();
    // 通过hash函数找到对应的bucket page对应的 pageid
    page_id_t bucket_page_id = KeyToPageId(key, dir_page);
    auto bucket_page = FetchBucketPage(bucket_page_id);
    page_id_t new_bucket_page_id;
    Page *new_bucket_page = buffer_pool_manager_->NewPage(&new_bucket_page_id); // 内存泄漏
    if (nullptr == new_bucket_page) {
      LOG_ERROR("Split时分配新的bucket page失败"); // 泄露
      std::cout << value << std::endl;
      return false;
    }
    uint32_t bucket_index = KeyToDirectoryIndex(key, dir_page);
    uint32_t local_depth = 0;
    uint32_t mask = bucket_index & dir_page->GetLocalDepthMask(bucket_index);
    // 转移, 将 directory page 上的bucket_id进行重分配
    for (uint32_t i = 0; i < DIRECTORY_ARRAY_SIZE; i++) {
      // 找到需要指向新的 bucket_page 的 indexes
      if (mask == (i & dir_page->GetLocalDepthMask(i))) { // ! 这里应该用 LocalDepthMask吧(是的!!!nice!!!)
        if (i & (1 << dir_page->GetLocalDepth(i))) { 
          dir_page->SetBucketPageId(i, new_bucket_page_id);
        }
        dir_page->IncrLocalDepth(i); // local depth + 1
        if (dir_page->GetLocalDepth(i) > local_depth) {
          local_depth = dir_page->GetLocalDepth(i);
        }
      }
    }
    // 更新GlobalDepth, 如果需要的话
    if (local_depth > dir_page->GetGlobalDepth()) {
      dir_page->IncrGlobalDepth();
    }
    // 将旧的key-value全部取出来, 然后重新执行插入
    std::vector<MappingType> all_key_values;
    all_key_values.push_back(std::make_pair(key, value));
    for (int i = 0; i < (int)BUCKET_ARRAY_SIZE; i++) {
      all_key_values.push_back(std::make_pair(bucket_page->KeyAt(i), bucket_page->ValueAt(i)));
      bucket_page->RemoveAt(i); // remove干净
    }
    bool insert_success;
    for (size_t i = 0; i < all_key_values.size(); i++) {
      // ! 靠, 之前这里 key 传递成了上面的key, 导致 hash值一直是一样的我日
      page_id_t page_id = KeyToPageId(all_key_values[i].first, dir_page);
      auto page = FetchBucketPage(page_id);
      insert_success = page->Insert(all_key_values[i].first, all_key_values[i].second, comparator_);
      if (!insert_success) {
        std::cout << "SplitInsert 失败: " << all_key_values[i].second << std::endl;
        page->Insert(all_key_values[i].first, all_key_values[i].second, comparator_);
      }
    }
    return true;
  }
  return false;
}

Merge部分的逻辑相对SplitInsert比较简单, 只需要找到对应key的bucekt index, 然后根据这个bucket index找到对应的split image的索引, 然后将选择这两个中较小的一个作为合并索引(他们共同的前缀). 之后在dir_page上遍历以更新信息, 维护local depth, 最后判断global depth是否也需要更新.

TASK #3 - CONCURRENCY CONTROL

在前面的测试中可以假定hashtable是单线程, 但是从这里开始需要支持多线程并发.

需要为每一个bucket添加一个latch, 以便在一个线程访问某bucket的时候, 其他的线程不能对他进行读写. 但是, 当一个线程在读的时候, 其他线程也可以读. 即需要实现对每一个bucket的读写锁, 支持并发读.

当进行split, merge以及global depth等信息变更的时候, 需要使用latch将整个结构保护起来.

在project中, 可以使用两种锁, 一种是在头文件中定义的table_latch_, 他是一种读写锁(用于全局); 第二种则是在page.h中定义的latch, 用于每一个bucket page, 在使用之前需要用reinterpret_cast进行转化.

其他

又出现了这种情况, 到底是为什么啊… 难搞啊

参考

https://zhuanlan.zhihu.com/p/121118364

这个资料很好: https://blog.csdn.net/qq_37904988/article/details/105102620

18年的实验, 跟21年比较像, 反而是19年和20年跟21年的不太像: https://cakebytheoceanluo.github.io/2020/04/17/CMU-15445-17-18-Project1-1/ , 不过它似乎是内存上的? 不像是使用了buffer pool

Contents

概述