CMU15-445 Fa23: PROJECT2 - EXTENDIBLE HASH INDEX

1. 理解 Extendible Hash

后续有空整理一下贴上自己写的测例，有需要可留言给个邮箱。

2. task#1 - Read/Write Page Guards

Page Guard 的作用是实现一个基于 C++ 的 RAII(Resource Acquisition Is Initialization) 机制的 Page 管理类，这个类能够通过析构或手动 Drop UnpinPage 并释放相应的 RLock 或者 WLock，能够避免后续 Extendible Hash Index 实现时由于人为对读写锁的使用失误以及忘记 UnpinPage 导致 BufferPoolManager 的页管理出错。

2.1 task#1 实现细节提示

Project Specification 特地将这几个函数的实现放在一起是有其道理的， BasicPageGuard 删除了拷贝构造和拷贝赋值，需要实现移动构造和移动赋值以及其析构函数。这里会需要较多的代码的复用，尤其是 Drop 函数。

PageGuard(PageGuard &&that): Move constructor.

对于 Basic 版本直接对 page_， bpm_， is_dirty 进行赋值，出于习惯将右值 that 中的指针都置为 nullptr。而 Upgrade 版本则可方便地通过 std::move 赋值 guard_。
operator=(PageGuard &&that): Move operator.

这里需要注意两点： 1. that 是否为自身； 2. 如果当前的 guard_.page_ 或 page_ 非 nullptr，需要先 Drop 已存储在当前 PageGuard 中的 Page。
Drop(): Unpin and/or unlatch.

对 Basic 版本，在 Page 有值的情况下需要调用 UnpinPage 进行资源释放。而对于 Upgrade 版本则需要释放相应的读写锁并调用 Basic 的 Drop。之前擅作主张添加了一个标志位表示是否已经调用过 Drop，想要以此避免后续手动调用 Drop 函数可能出现的重复调用，但实际上原有的对 page 指针的判断已经足够。添加这个标志位反而引起 P3 的 shell 报错 deadlock。
~PageGuard(): Destructor.

直接调用 Drop 就行啦！

至于下面这两个函数则让我面目狰狞，给的注释说的非常隐晦，要保证在 Upgrade 的过程中 Page 不被 Evict，又说 BasicPageGuard 在调用这个函数后会 invalid。具体细节参考下一小节的 PageGuardTest.BPMTest 调试。

UpgradeRead(): Upgrade to a ReadPageGuard
UpgradeWrite(): Upgrade to a WritePageGuard

而下面这四个函数也是清晰的，对有 Read 和 Write 需求的就相应的给上读/写锁，但这里考虑到 WritePageGuard 可能会被更改，我个人认为需要在 Fetch 的同时将相应的 Page 设置为 dirty。

FetchPageBasic(page_id_t page_id)
FetchPageRead(page_id_t page_id)
FetchPageWrite(page_id_t page_id)
NewPageGuarded(page_id_t *page_id)

2.2 task#1 的调试与解析

PageGuardTest.BPMTest

Gradescope 中的 PageGuardTest.BPMTest 报错如下:

/autograder/source/bustub/test/storage/grading_page_guard_test.cpp:222: Failure
Expected equality of these values:
  2
  page1copy->GetPinCount()
    Which is: 3

我自己模仿所给范例写了一些本地的测试都是通过的，唯一感觉有些不确定的是 BasicPageGuard::UpgradeRead() 和 BasicPageGuard::UpgradeWrite() 这两个函数，对于他们的实现细节我不是很清楚。为了确定 Bug，我用了 LOG_DEBUG(...) 打印所有与 pinCount 变更相关的信息，再次提交 Gradescope 后得到了这样的输出：

2023-11-27 08:49:55 [buffer_pool_manager.cpp:210:NewPageGuarded] DEBUG - new basic page guard
2023-11-27 08:49:55 [buffer_pool_manager.cpp:61:NewPage] DEBUG - Create new page, page_id 0, pinCount [1]
2023-11-27 08:49:55 [buffer_pool_manager.cpp:79:FetchPage] DEBUG - fetch page_id 0 from buffer, pinCount from [1] to [2]
2023-11-27 08:49:55 [page_guard.cpp:23:Drop] DEBUG - page_id 0, pinCount from [2] to [1]
2023-11-27 08:49:55 [buffer_pool_manager.cpp:186:FetchPageBasic] DEBUG - fetch basic page
2023-11-27 08:49:55 [buffer_pool_manager.cpp:79:FetchPage] DEBUG - fetch page_id 0 from buffer, pinCount from [1] to [2]
2023-11-27 08:49:55 [page_guard.cpp:23:Drop] DEBUG - page_id 0, pinCount from [2] to [1]
2023-11-27 08:49:55 [buffer_pool_manager.cpp:210:NewPageGuarded] DEBUG - new basic page guard
2023-11-27 08:49:55 [buffer_pool_manager.cpp:61:NewPage] DEBUG - Create new page, page_id 1, pinCount [1]
2023-11-27 08:49:55 [buffer_pool_manager.cpp:79:FetchPage] DEBUG - fetch page_id 1 from buffer, pinCount from [1] to [2]
2023-11-27 08:49:55 [buffer_pool_manager.cpp:192:FetchPageRead] DEBUG - fetch read page
2023-11-27 08:49:55 [buffer_pool_manager.cpp:79:FetchPage] DEBUG - fetch page_id 1 from buffer, pinCount from [2] to [3]
2023-11-27 08:49:55 [page_guard.cpp:58:UpgradeRead] DEBUG - Upgrade BasicPageGuard to ReadPageGuard, page_id 1, pinCount from [2] to [3]
/autograder/source/bustub/test/storage/grading_page_guard_test.cpp:222: Failure
Expected equality of these values:
  2
  page1copy->GetPinCount()
    Which is: 3

2023-11-27 08:49:55 [page_guard.cpp:99:~ReadPageGuard] DEBUG - ReadPageGuard deconstructor Drop
2023-11-27 08:49:55 [page_guard.cpp:86:Drop] DEBUG - read page guard is dropped.
2023-11-27 08:49:55 [page_guard.cpp:23:Drop] DEBUG - page_id 1, pinCount from [3] to [2]
2023-11-27 08:49:55 [page_guard.cpp:50:~BasicPageGuard] DEBUG - BasicPageGuard deconstructor Drop
2023-11-27 08:49:55 [page_guard.cpp:23:Drop] DEBUG - page_id 1, pinCount from [2] to [1]

可以看到错误就发生在 BasicPageGuard 转为 ReadPageGuard 的过程中，按照我之前的理解，理应 Upgrade 应当增加一次对相应的 Page 的访问，所以最开始的代码如下：

auto BasicPageGuard::UpgradeRead() -> ReadPageGuard {
  return bpm_->FetchPageRead(page_->GetPageId());
}

但按照所给测例的输出， BasicPageGuard 应当在 Upgrade 之后释放原有的资源，这意味着 BasicPageGuard 在 Upgrade 之后无法再通过 Upgrade 返回一个 Read/WritePageGuard，在 Upgrade 完成后需要手动调用 BasicPageGuard::Drop() 释放原有的资源，当然这个猜想在所给代码注释中得到了印证：

/**
  * The protected page is not evicted from the buffer pool during the upgrade,
  * and the basic page guard should be made invalid after calling this function.
  */

至于为什么用 FetchPageRead 而不是直接返回一个全新的 ReadPageGuard，主要是考虑到在 Upgrade 过程中会 Drop 原有的 Basic Guard，而 Upgrade 需要保证这个 Page 不会被缓存池的 LRU-K 算法 Evict，那需要保证这个 Page 处于一个 Pin 的状态。 Fetch 可以增加一次 pinCount, 可以与 Drop 中调用的 UnpinPage 导致 pinCount 的一次减少抵消。

后续提交通过了 BMPTest 证明了我的猜想。

// reference code
auto BasicPageGuard::UpgradeRead() -> ReadPageGuard {
  ReadPageGuard read_guard = bpm_->FetchPageRead(page_->GetPageId());
  Drop();
  return read_guard;
}

auto BasicPageGuard::UpgradeWrite() -> WritePageGuard {
  WritePageGuard write_guard = bpm_->FetchPageWrite(page_->GetPageId());
  Drop();
  return write_guard;
}

3. task#2 - Extendible Hash Table Pages

相较往年 23Fall 版本增加了 Header Page，但整体思路应当是一致的，需要注意的是我们不能更改任何 private 和 public 域中的函数和变量，在每个头文件的顶部说明规定了这些 Page 的结构和大小。

 Header page format:
  ---------------------------------------------------
 | DirectoryPageIds(2048) | MaxDepth (4) | Free(2044)
  ---------------------------------------------------

 Directory page format:
  --------------------------------------------------------------------------------------
 | MaxDepth (4) | GlobalDepth (4) | LocalDepths (512) | BucketPageIds(2048) | Free(1528)
  --------------------------------------------------------------------------------------

 Bucket page format:
  ----------------------------------------------------------------------------
 | METADATA | KEY(1) + VALUE(1) | KEY(2) + VALUE(2) | ... | KEY(n) + VALUE(n)
  ----------------------------------------------------------------------------

 Metadata format (size in byte, 8 bytes in total):
  --------------------------------
 | CurrentSize (4) | MaxSize (4)
  --------------------------------

这里我偷偷改了 GetDirectoryPageId 的返回类型，不然和 directory_page_ids_ 数组的类型不统一。

auto ExtendibleHTableHeaderPage::GetDirectoryPageId(uint32_t directory_idx) const -> page_id_t;

3.1 task#2 实现细节提示

Init：需要将 directory_page_ids_ 数组中的 page_id 都初始化为 INVALID_PAGE_ID， max_depth 是有它的上限的。
HashToDirectoryIndex：就比较阴险了，对于 header 而言，要获取 directory 的索引值，是通过 32 位 Hash 的 MSB 实现的。设想 max_depth 为零， 32 位 Hash 右移 32 位仍是其本身。因而需要特殊处理 max_depth 为零的情况，应返回一个 0 值。

Hash Table Directory Page

Init：同样需要初始化 local_depth_ 以及 bucket_page_id_ 这两个数组。 local_depth_ 以及 global_depth_ 需要初始化为 0。
HashToBucketIndex：有个比较巧妙的办法就是直接用 hash 值对 Size() 取模，这和使用 GetGlobalDepthMask 是一样的。
GetSplitImageIndex：主要得理解 Extendible Hash Index 的 Split 的思路， directory 部分扩大事实上就是左移了一个 global depth，这导致 directory 数量变为原来的两倍。例如 00 会分裂为 000 和 100 但二者都指向同一个 bucket。所以我们只需要得到当前 bucket 并对其 global_depth 位取反，就能得到镜像的 bucket 的索引值。
```
auto ExtendibleHTableDirectoryPage::GetSplitImageIndex(uint32_t bucket_idx) const -> uint32_t {
  // Ensure the bucket local depth has increased!
  assert(local_depths_[bucket_idx] > 0);
  return bucket_idx ^ (1 << (local_depths_[bucket_idx] - 1));
}
```

IncrGlobalDepth：结合上个函数的解析，如果理解了 Extendible Hash Index 的实现思路，增加 global_depth 要做的就是拷贝一份原有的 buckets，如 bucket_idx 00 分裂为 000 和 100，把 00 的内容拷贝一份到 100 中即可。

void ExtendibleHTableDirectoryPage::IncrGlobalDepth() {
  assert(global_depth_ < HTABLE_DIRECTORY_MAX_DEPTH);
  uint32_t prev_expansion_num = Size();
  for (uint32_t prev_idx = 0, curr_idx = prev_expansion_num; prev_idx < prev_expansion_num;
      prev_idx += 1, curr_idx += 1) {
    local_depths_[curr_idx] = local_depths_[prev_idx];
    bucket_page_ids_[curr_idx] = bucket_page_ids_[prev_idx];
  }
  global_depth_ += 1;
}

CanShrink：检查所有的 bucket 的 local_depth，如果都比 global depth 要小，就可以缩小 global_depth。这个函数在后续 Merge 的时候需要用到。

其他的该加加该减减就行，不用想太多，就是纯粹的增减！

Hash Table Bucket Page

讲道理开始一点思路没有，我看到有人在知乎 - zihao 彼方 CMU15-445(2023FALL)-Project#2: Extendible Hash Index 发了篇文章，里面提到需要对 bucket 中的 array_ 数组全部初始化为一个特殊值， 坑爹啊！！！ 这导致我后续花了将近 6 个小时找 GrowShrinkTest 的错误。

实际上 bucket 的实现非常简洁，我后来在看 PrintBucket 的实现的时候得到了启发， BUSTUB 直接访问的前 size_ 个元素。说明每次 Insert 的时候利用 size_ 可以对数组进行尾部插入，这是因为 size_ 始终指向下一个插入的位置。而每次 Remove 的时候只用 size_ 指向当前数组的尾部数据 (人话就是 size_ -= 1)，让这个尾部数据填充到 RemoveAt 的那个 bucket_idx 位置即可。

我们无需对数组进行初始化等操作， size_ 表示当前的数据大小可以很好的控制访问权限。

3.2 task#2 的调试与解析

GrowShrinkTest

对 Bucket Page 理解不到位，重构后能够通过该测例。

4. task#3 - Extendible Hashing Implementation

感觉没必要细说，但需要写一下踩过的坑以及记录一些实现相关的细节。

大家真没辙了参考这位大佬 21 年实现的版本， cmu15-445/2021，核心与框架都是一致的。

4.1 task#3 实现细节提示

这里实现的时候需要考虑 BasicPageGuard， ReadPageGuard， WritePageGuard 的使用场景。一般来说，只有需要通过 NewPageGuarded 获取新 Page 才会用到 BasicPageGuard，之后都会通过 Upgrade 函数将这个获取到的 Page 加上读写锁。使用 PageGuard 原则就是看是否后续操作会产生对数据的更改，如果不会更改就尽量使用 Read，并在适当的时候通过 Drop 函数提前释放相关的读写锁，以提高并行效率。

MigrateEntries

我相信很多人看到这个函数是懵的，这个函数究竟什么作用根本没有提示。这个函数和 UpdateDirectoryMapping 函数都是用在 Split Bucket 中的。试想有一个 bucket_idx 为 00 的 bucket 存储了两个 KV 数据，在我们增加 global_depth 和 local_depth 之后，我们需要将 bucket_idx 00 中的数据填充到新的 000(原 00) 和 100 这两个 bucket，此时就要用到 MigrateEntries 函数。

首先将原有数据拷贝出来，这里需要注意的是，如果使用 ExtendibleHTableBucketPage<K, V, KC>::EntryAt 函数会有问题，我们无法对一个 const 引用进行拷贝构造。解决办法就是单独用 KeyAt 和 ValueAt配合 std::make_pair 构造一个新的 KV。

可以自己尝试用 LOG_DEBUG 看看结果，不出意外的话 copied 的 KV 应都是 0 值。

之后根据新的 local_depth 将拷贝的数据按照新的 bucket_idx 插入 old_bucket 或 new_bucket。

template <typename K, typename V, typename KC>
void DiskExtendibleHashTable<K, V, KC>::MigrateEntries(ExtendibleHTableBucketPage<K, V, KC> *old_bucket,
                                                       ExtendibleHTableBucketPage<K, V, KC> *new_bucket,
                                                       uint32_t new_bucket_idx, uint32_t local_depth_mask) {
  /* Get valid items in old bucket */
  uint32_t old_bucket_size = old_bucket->Size();
  auto copied = std::vector<std::pair<K, V>>(old_bucket_size);
  for (uint32_t idx = 0; idx < old_bucket_size; idx += 1) {
    copied[idx] = std::make_pair(old_bucket->KeyAt(idx), old_bucket->ValueAt(idx));
  }
  /* reset old bucket */
  old_bucket->Init(bucket_max_size_);
  BUSTUB_ASSERT(old_bucket->Size() == 0, "old bucket should be reset");

  /* Do rehashing */
  for (uint32_t idx = 0; idx < old_bucket_size; idx += 1) {
    const auto &[key, value] = copied[idx];
    uint32_t target_bucket_idx = Hash(key) & local_depth_mask;
    if (target_bucket_idx == new_bucket_idx) {
      new_bucket->Insert(key, value, cmp_);
    } else {
      old_bucket->Insert(key, value, cmp_);
    }
  }
}

UpdateDirectoryMapping

这又是做什么？可以想象的是，有时候我们有很多 bucket_idx 指向的是同一个 page_id，如果不清楚请参考理解-extendible-hash 我们在 Split Bucket 完成后，需要让原来指向 split_bucket_idx 的那些 buckets 重新分配指向，要么是 split_bucket_idx，要么是 image_bucket_idx，并且都需要设定新的 local_depth。

template <typename K, typename V, typename KC>
void DiskExtendibleHashTable<K, V, KC>::UpdateDirectoryMapping(ExtendibleHTableDirectoryPage *directory,
                                                               uint32_t new_bucket_idx, page_id_t new_bucket_page_id,
                                                               uint32_t new_local_depth, uint32_t local_depth_mask) {
  uint32_t msb_diff = 1 << new_local_depth;
  for (uint32_t i = new_bucket_idx; i >= msb_diff; i -= msb_diff) {
    directory->SetBucketPageId(i, new_bucket_page_id);
    directory->SetLocalDepth(i, new_local_depth);
  }
  for (uint32_t i = new_bucket_idx; i < directory->Size(); i += msb_diff) {
    directory->SetBucketPageId(i, new_bucket_page_id);
    directory->SetLocalDepth(i, new_local_depth);
  }
}

4.2 task#2 的调试与解析

GetValue 和 Remove

这两个函数的接口都是 key，说明有时候可能这个 key 是不存在于 BufferPool 的，我们需要在获取 directory index 的时候就可以判断，如果 directory_idx 为 INVALID_PAGE_ID 可以提早返回结果，因为这个 key 并不存在。

另外注意 Fall 2023 版本是 unique-key，不存在一个 key 对应多个值的情况。

auto GetValue(const K &key, std::vector<V> *result, Transaction *transaction = nullptr) const -> bool;
auto Remove(const K &key, Transaction *transaction = nullptr) -> bool;

Insert

Insert 中在 directory 的 page_id 为 INVALID_PAGE_ID 时调用 InsertToNewDirectory，在 InsertToNewDirectory 中调用 InsertToNewBucket，这是这两个函数的使用方式。

如果发现 directory 索引超过了 header 的最大限制，需要直接返回 false。
判断当前需要插入的 bucket 的情况，如果没有满则可以直接调用 bucket 的 Insert 函数，如果满了则调用 SplitInsert 函数。

SplitInsert

这个函数不进行任何插入操作，插入操作仅在 Insert 中进行，因而在该函数完成对 global_depth 和 local_depth 的扩容后，需要再次调用 Insert 完成数据插入。

需要注意以下几点：

当前的 bucket_idx 获取的 local_depth 已经与传入的 directory_max_depth_ 相等了，说明 directory 已经扩容到最大， bucket 也扩容到最多，无法继续扩容，直接返回 false。
如果上述条件不满足，说明还可以继续扩容，如果 local_depth 已经和 global_depth 相等了，先增加 global_depth。
增加 local_depth。
调用 MigrateEntries 以及 UpdateDirectoryMapping（有两次）完成扩容。
重新尝试 Insert。

Merge

需要注意的是 Recursive Merge，因为很可能一次 Merge 后还能够接着下一次 Merge 直到最小单位。由于 Merge 的时候会将当前的 bucket 指向 image bucket 以达到 Merge 的目的，所以如果要递归进行 Merge，就要以 image_bucket_idx 和 new_local_depth 生成新的 bucket_idx 进行下次 Merge 的调用。

另外注意 Merge 的几个先后条件：

local_depth 为 0，说明已经到达 Merge 的极限了，直接返回。
当前的 bucket_idx 得到的 local_depth 和镜像的 image_bucket_idx 得到的 image_local_depth 不一致，深度不一致则不能 Merge，也需要直接返回。
我们需要在 Merge 的过程中对 bucket_idx 再进行一次 IsEmpty 的判断，如果非空直接返回。这是因为在 Remove 函数中我们判断 bucket 为空后，释放 latch 的瞬间这个 latch 被 Insert 拿走了，这个 bucket 可能又被塞入了新的值，后续 Merge 函数获取到锁的时候就可能看到的是这个新值了。
删除 bucket_idx 对应的 Page 后要将之前所有指向这个 bucket_idx 存储的 Page 的那些 buckets 重新直线新的 image_bucket 对应的 Page 以及设置新的 local_depth。
需要循环调用 CanShrink 缩小 global_depth。

  ...
  /* recursive merge */
  if (directory_write_page->GetGlobalDepth() > 0) {
    uint32_t next_bucket_idx = image_bucket_idx & new_local_depth;
    uint32_t next_image_bucket_idx = directory_write_page->GetSplitImageIndex(next_bucket_idx);


    Merge(directory_idx, next_bucket_idx, transaction);
    Merge(directory_idx, next_image_bucket_idx, transaction);
  }

5. task#4 Concurrency Control

实现的时候给 Insert， Remove 以及自定义的一些会更改 directory 或 bucket 的函数都加上了一把 latch，在 return 或进入另一个函数前释放 latch，能完美通过测试。

6. 写在最后

不枉这一个星期的努力， P2 顺利收官了！

虽然最后成功通过了 P2 的所有测试，但整个 Project 并没有完全独立完成，设计上也有参考前述的 2021 年的 Extendible Hash Index 的实现。除了所给函数没注释导致对其功能的理解上的缺失，还有阅读 Specification 和代码注释不仔细，对 Extendible Hash Index 的原理以及概念不熟悉不透彻。对于 Debug 目前能用的就是 LOG_DEBUG 以及配置 VSCode 的 CodeLLDB 实现图形化调试，一旦遇到多线程的情况，大多只能依赖 LOG_DEBUG，可想而知 P4 将是个令人望而生畏的任务。

Project2 LeaderBoard Rank, HangX-Ma

PREVIOUSCpp-Quiz

NEXTVim Plugin: YouCompleteMe 旧版本装配