CMU 15-445/645 (fall 2023) Project 2 Extendible Hash Index

本篇为15-445 project 2 extendible hash index的总结。

什么是Hash Index？

索引就是帮助存储引擎快速获取数据的一种数据结构，形象的说就是索引是数据的目录。23 Fall前都是B+ tree索引，这是BusTub第一次引入hash索引。hash索引相较于B+ tree索引，只适合于等值查询，查找时间复杂度为O(1)，B+ tree索引叶节点是相互连接的，十分适用于范围查询和顺序访问，查找效率通常是O(log n)。

Page Guard

在写page guard之前应该先了解C++中RAII的概念，有了RAII我们可以少很多管理资源获取与释放的心智负担。实验室师兄在面阿里云时面试官说现代C++就尽量不要用裸指针和锁了，尽量采用智能指针和lock_guard等，所以这里RAII的概念还是挺重要的。

Page guard需要注意的点不多，page guard创建时不需要获取latch，而应该由BufferPoolManager在FetchPageRead和FetchPageWrite时先获取对应的latch再创建ReadPageGuard或者WritePageGuard，在析构或者Drop时对latch进行相应的释放。在对BasicPage进行upgrade时drop之前，先将Page对象指针置空，这样就会告诉Drop时不要调用Unpin，Page也就不会被设为evictable。

Extendible Hash Table Pages

索引是需要持久化到磁盘中的，这一部分实现的三个Page就是未来我们存储索引的地方。BusTub中page为固定的4096 Bytes，Header中存的是每个directory的page_id，最大可以存512个page_id，占2048 Bytes，MaxDepth占4 Bytes，空余2044 Bytes；directory中存的是每个bucket的page_id，至多可存512个page_id，占2048 Bytes，其余的占空间大小看每个头文件开头和实验手册的注释即可；Bucket才是真正存数据对应索引的地方，key是索引的值，value则是该元组的RID（即page_id + slot_num）。这些标明的量都是需要持久化到磁盘中的：

* 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)
*  --------------------------------

完成这个task的时候可以不求甚解，面向测试用例编程，到task3写的不对的再改就好，但是心里要清楚每个page各自起到什么作用。写的时候不清楚local_depth和global_depth究竟怎么一回事可以去看看VerifyIntegrity()这个方法究竟是怎么判定的。

小tips:

在计算HashToBucketIndex()时直接return hash & ((1 << global_depth_) - 1); 不要写复杂了hh

Extendible Hashing Implementation

Task 3是project 2里最复杂的一部分，开始之前一定要弄明白实验手册里给的hint，不清楚一定要自己动手画画图，多打印日志，不要偷懒。可以参考这篇博文过程写的很详细，这一篇流程图画的比较清晰。

Concurrency Control

只要保证task 3在管理读写锁时遵守课上讲的crabbing法则应该不会有什么问题。只有一个测试用例会卡锁住的page数量，记得拿到directory page后drop header page就ok了。

总结

Project 2对比1来说要复杂不少，尤其是task 3 remove方法bucket merging和directory shrinking细节比较多，调试会花费大量的时间。但是就面试而言还是B+ tree索引问的多一些，有空的话我也会回头看看同学写的23 spring 的代码学习一下。

一些牢骚

去年的时候找到一个数据库相关和企业合作的毕设还挺开心的，结果这一个月都是在分析trace做些表面功夫，一行系统的代码都没写过很是心累，而这样一个大企业的核心业务架构也十分的丑陋，虽然我知道这肯定是多方妥协的结果，但还是挺可笑的。最近刷知乎看到不少劝退数据库岗位的文章，主要的论调是虽然写system的代码很爽，但是业界根本没有那么多需求，数据库公司挣不到钱。

牢骚归牢骚，希望自己能赶快把手头的毕设搞完，在读研前找到个有意思的实习。😇