Task #1 - Read/Write Page Guards踩坑
BasicPageGuard的移动构造函数:
- 两个PageGuard有可能指向同一个页面，要先判断是否指向同一个页面，如果指向同一个页面直接返回。
- 由于需要将
page_属性指向另一个页面，因此要先调用Drop方法放弃对当前指向页面的使用。
BasicPageGuard的Drop方法:
- 对于同一个PageGuard，Drop方法应该只生效一次，即Drop方法只在第一次调用时生效，通过设置一个标志位即可。
- 调用
UnpinPage方法时，传入的应该是PageGuard的is_dirty_属性，而不是其指向的page的is_dirty_属性。
ReadPageGuard的Drop方法:
- 要先释放锁，再调用
BasicPageGuard的Drop方法。 如果先调用BasicPageGuard的Drop方法，那么页面可能就会被缓冲管理器淘汰掉，替换为一个新的页面，此时再释放锁会导致新加载进来的页面的锁被释放。
Task #2 - Extendible Hash Table Pages踩坑
ExtendibleHTableHeaderPage
Init方法一定要初始化directory_page_ids_，因为directory是否存在的判断条件是:
header_page->GetDirectoryPageId(dir_index) == static_cast<uint32_t>(INVALID_PAGE_ID)
同时测试函数会调用VerifyIntegrity方法，如果未初始化directory_page_ids_，那么会导致出错。
Init方法实现参考:
void ExtendibleHTableHeaderPage::Init(uint32_t max_depth) {
max_depth_ = max_depth;
auto size = MaxSize();
for (uint32_t i = 0; i < size; i++) {
directory_page_ids_[i] = INVALID_PAGE_ID;
}
}
ExtendibleHTableDirectoryPage
同样的，Init方法要初始化bucket_page_ids_属性。
Task #3 - Extendible Hashing Implementation踩坑
算法的实现可以参考下面的文章和视频。
Extendible Hash Table 算法实现
Extendible Hashing (Dynamic approach to DBMS)
Extendible Hash Table讲解视频
Insert算法流程
- 加载header
- 根据哈希值计算
directory_index，然后根据directory_index获取directory_page_id - 如果
directory_page_id无效，则需要新建一个directory，并且将键值插入到新创建的directory中。 如果directory_page_id有效，则加载对应的directory，并且加键值插入到对应的directory中
插入到新创建的directory:
- 利用
bpm_->NewPageGuarded方法创建一个新的directory和bucket - 初始化
directory和bucket - 将
bucket_page_id插入directory的下标0中，设置下标0的局部深度为0 - 将键值对插入到
bucket中 - 将
directory保存到header中
插入到已有的directory:
- 根据哈希值计算
bucket_idx，并且加载bucket - 判断
bucket是否已满，若未满，则执行步骤8；若已满，则接着执行步骤3 - 判断
bucket_idx对应的局部深度是否等于全局深度，如果等于全局深度，接着执行步骤4，否则执行步骤6 - 判断
directory是否已满，即Size()>=MaxSize()，若是directory已满，则直接返回false，directory未满，接着执行步骤5。 - 增加全局深度
- 分裂bucket，具体分裂流程参照后面详细步骤
- 回到步骤1重新尝试插入
- 调用
bucket的Insert方法将键值插入即可
分裂bucket流程
- 将
bucket_idx对应的局部深度加一 - 创建一个新的
bucket，并且初始化 - 将旧的bucket中的数据重新分配到两个bucket中，遍历旧的bucket中的所有元素，利用新的局部深度计算
new_bucket_idx，如果new_bucket_idx等于bucket_idx，那么数据仍然插入到旧的bucket中，否则插入到新的bucket中 - 重新分配
directory指向的bucket，具体算法如下:
// 参考文章: https://www.inlighting.org/archives/extendible-hash-table-algorithm
// 辅助函数
auto ExtendibleHTableDirectoryPage::GetImageBucketIndex(uint32_t bucket_idx) const -> uint32_t {
uint32_t local_depth = local_depths_[bucket_idx];
return bucket_idx ^ (1 << (local_depth - 1));
}
// 分配算法
auto image_bucket_idx = directory_page->GetImageBucketIndex(bucket_idx);
uint32_t diff = 1 << directory_page->GetLocalDepth(bucket_idx);
for (uint32_t i = bucket_idx; i >= 0; i -= diff) {
directory_page->SetBucketPageId(i, directory_page->GetBucketPageId(bucket_idx));
directory_page->SetLocalDepth(i, directory_page->GetLocalDepth(bucket_idx));
if (i < diff) {
break;
}
}
for (uint32_t i = bucket_idx+diff; i < directory_page->Size(); i += diff) {
directory_page->SetBucketPageId(i, directory_page->GetBucketPageId(bucket_idx));
directory_page->SetLocalDepth(i, directory_page->GetLocalDepth(bucket_idx));
}
for (uint32_t i = image_bucket_idx; i >= 0; i -= diff) {
directory_page->SetBucketPageId(i, new_bucket_page_id);
directory_page->SetLocalDepth(i, directory_page->GetLocalDepth(bucket_idx));
if (i < diff) {
break;
}
}
for (uint32_t i = image_bucket_idx+diff; i < directory_page->Size(); i += diff) {
directory_page->SetBucketPageId(i, new_bucket_page_id);
directory_page->SetLocalDepth(i, directory_page->GetLocalDepth(bucket_idx));
}
Task #4 - Concurrency Control踩坑
在Task #1中，实现了FetchPageWrite 和 FetchPageRead，这两个方法都会加锁，因此不需要额外的锁，在Insert和Remove方法中，通过FetchPageWrite来获取页面，在GetValue方法中，通过FetchPageRead方法获取页面即可实现并发安全。页面使用完以后，在适当的时候就可以调用Drop方法。
例如Insert方法:
template <typename K, typename V, typename KC>
auto DiskExtendibleHashTable<K, V, KC>::Insert(const K &key, const V &value, Transaction *transaction) -> bool {
// ...
auto header_guard = bpm_->FetchPageWrite(header_page_id_);
auto header_page = header_guard.template AsMut<ExtendibleHTableHeaderPage>();
//...
auto directory_guard = bpm_->FetchPageWrite(directory_page_id);
auto directory_page = directory_guard.template AsMut<ExtendibleHTableDirectoryPage>();
// ...
auto bucket_guard = bpm_->FetchPageWrite(directory_page->GetBucketPageId(bucket_idx));
auto bucket_page = bucket_guard.template AsMut<ExtendibleHTableBucketPage<K, V, KC>>();
}
通过截图
