CMU15445(2023fall) Project #2 - Extendible Hash Index 匠心分析

胡未灭，鬓已秋，泪空流

此生谁料

心在天山

身老沧州

——诉衷情

完整代码见：

SnowLegend-star/CMU15445-2023fall: Having Conquered the Loftiest Peak, We Stand But a Step Away from Victory in This Stage. With unwavering determination, we press onward, for destiny favors those brave enough to forge ahead, cutting through the thorns and overcoming every obstacle that dares to stand in their way.

Task #1 - Read/Write Page Guards

实验说明分析：

        在缓冲池管理器中，FetchPage 和 NewPage 函数返回已经锁定的页面指针。这个锁定机制确保页面在没有任何读取和写入时不会被驱逐。为了表示页面在内存中不再需要，程序员必须手动调用 UnpinPage。

        然而，如果程序员忘记调用 UnpinPage，页面将永远不会被驱逐出缓冲池。由于缓冲池实际上只有较少的帧，这将导致更多的页面在磁盘和内存之间交换。这样不仅会影响性能，而且这个 bug 很难被发现。

        您将实现 BasicPageGuard 类，它存储指向 BufferPoolManager 和 Page 对象的指针。一个页面保护器确保一旦超出作用域，就会调用 UnpinPage 来解除锁定页面。请注意，它仍然应该提供一个供程序员手动解除锁定页面的方法。

        由于 BasicPageGuard 隐藏了底层的页面指针，它还可以提供只读/写数据的 API，这些 API 在编译时进行检查，确保正确设置 is_dirty 标志。

        在这个和后续项目中，多个线程将会读取和写入相同的页面，因此需要使用读写锁来确保数据的正确性。请注意，在 Page 类中，已经为此目的提供了相关的锁方法。类似于解除锁定页面，程序员可能会忘记在使用后解除锁定。为了解决这个问题，您将实现 ReadPageGuard 和 WritePageGuard，它们会在作用域结束时自动解除页面的锁定。

        由于在2024-fall的project1分析过了类似的，故实现这块不在赘述。说实话我个人还是更喜欢2023f版的，这个版本的对PageGuard进行拆分得恰到好处。先是给出BasicPageGuard让我们对PageGuard的作用有个具体的理解，再Basic的基础上可以进一步升级为ReadPageGuard(下面简写为RPG)和WritePageGuard(简写为WPG)。这一套流程看下来2024f版对PageGuard的拆分程度太高了，上来就要求实现RPG和WPG，理解起来的难度要大不少。

        接下来具体分析关于如何使用PageGuard。我相信很多人可能会对As和AsMut的用法有所疑惑。但无论是RPG还是WPG，其As与AsMut都是调用BasicPG的函数。我们只要理解透彻下面四个函数那对于PageGuard的使用也就是手到擒来了。

        可以发现，GetData()与As()是配套的，而GetDataMut()和AsMut()也是配套的。而且GetDataMut这个函数中，修改了is_dirty_位，这说明一旦我们选择调用AsMut，那最好是真的对page的内容进行了修改，自然也只有WPG才能调用AsMut的。

        那什么时候调用RPG与WPG的情况也就呼之欲出了。只要需要修改page时，才需要调用WPG。如果只是读取page，那调用RPG就可以了。但是！如果你懒得思考要不要修改page那直接调用WPG也不是不行，就是会多造成disk IO降低吞吐率。如果不清楚是否需要修改page，保险起见可以直接调用WPG。

 1.   auto GetData() -> const char * { return page_->GetData(); }2.  3.   template <class T>4.   auto As() -> const T * {5.     return reinterpret_cast<const T *>(GetData());6.   }7.  8.   auto GetDataMut() -> char * {9.     is_dirty_ = true;
10.     return page_->GetData();
11.   }
12.  
13.   template <class T>
14.   auto AsMut() -> T * {
15.     return reinterpret_cast<T *>(GetDataMut());
16.   }
17.  

Task #2 - Extendible Hash Table Pages

实验说明分析

哈希表头页面（Hash Table Header Page）

头页面位于基于磁盘的可扩展哈希表的第一层，并且每个哈希表只有一个头页面。它存储指向目录页面的逻辑子指针（作为页面ID）。可以将其视为一个静态的第一层目录页面。头页面具有以下字段：

变量名	大小	描述
directory_page_ids_	2048	一个目录页面ID的数组
max_depth_	4	头页面可以处理的最大深度

请注意，尽管页面的大小是物理限制，您应该使用 max_depth_ 来确定 directory_page_ids_ 数组的上限大小。

您必须通过仅修改其头文件（src/include/storage/page/extendible_htable_header_page.h）和相应的源文件（src/storage/page/extendible_htable_header_page.cpp）来实现可扩展哈希表的头页面。

哈希表目录页面（Hash Table Directory Page）

目录页面位于基于磁盘的可扩展哈希表的第二层。每个目录页面存储指向桶页面的逻辑子指针（作为页面ID），并包含用于处理桶映射以及动态扩展和收缩目录的元数据。目录页面具有以下字段：

变量名	大小	描述
max_depth_	4	头页面可以处理的最大深度
global_depth_	4	当前目录的全局深度
local_depths_	512	一个桶页面本地深度的数组
bucket_page_ids_	2048	一个桶页面ID的数组

请注意，尽管页面的大小是物理限制，您应该使用 max_depth_ 来确定 bucket_page_ids_ 数组的上限大小。

您必须通过仅修改其头文件（src/include/storage/page/extendible_htable_directory_page.h）和相应的源文件（src/storage/page/extendible_htable_directory_page.cpp）来实现可扩展哈希表的目

录页面。

哈希表桶页面（Hash Table Bucket Page）

桶页面位于基于磁盘的可扩展哈希表的第三层。它们实际上存储键值对。桶页面具有以下字段：

变量名	大小	描述
size_	4	桶中当前存储的键值对的数量
max_size_	4	桶可以存储的最大键值对数量
array_	小于或等于4088	存储键值对的数组

请注意，尽管页面的大小是物理限制，您应该使用 max_size_ 来确定 array_ 数组的键值对的上限大小。

您必须通过仅修改其头文件（src/include/storage/page/extendible_htable_bucket_page.h）和相应的源文件（src/storage/page/extendible_htable_bucket_page.cpp）来实现可扩展哈希表的桶页面。

重要说明：

每个可扩展哈希表的头/目录/桶页面对应于通过缓冲池获取的内存页面的内容（即 data_ 部分）。每当您读取或写入页面时，必须先从缓冲池中获取页面（使用其唯一的 page_id），然后将其重新解释为相应的类型，在读取或写入后解锁该页面。我们强烈建议您利用在任务1中实现的 PageGuard API 来实现这一目标。

举例说明可扩展哈希的插入流程

接下来直接举个例子来解释可扩展哈希表的具体实现过程：

初始Global_Depth=0，每个Bucket的Local_Depth=0，Bucket的max_size_=2。假设我们需要插入0 1 2 3 4 5 6 7 8 。

咳咳，又到了展示我精湛画图功力的时候了。Show time！

①插入0，1。由于初始的Bucket空间大小足够，可以直接插入到Bucket0中。紫色笔记表示depth，左侧表示Directory，右侧表示Buckets。

③接下来插入2，发现B0已经满了，无法直接插入。

1. 所以B0先尝试local_depth++来进行桶分裂，但是由于此时local_depth已经等于global_detph了，所以loc_d自增失败，需要glo_d先自增。此时glo_d=1
2. Loc_d++，即loc_d=1，自增成功可以进行桶分裂。原桶与新桶(brother)的loc_d都是1
3. 将原Bucket的元素进行重映射，即遍历B0的所有元素，进行key&loc_depth_mask将元素分配到原桶和新桶中。

如下图。0&1=0，1&1=1。所以0依然放在原桶中，1重新放在下标为1的新桶中。

• 重新尝试插入2。通过2&global_depth_mask即10&1=0来把2放入B0中。

③插入3。通过3&global_depth_mask即11&1=1来把3放入B1中。

④插入4。4&global_depth_mask即100&1=0，发现B0已经满了，故准备进行桶分裂。

1. 所以B0先尝试local_depth++来进行桶分裂，但是由于此时local_depth已经等于global_detph了，所以loc_d自增失败，需要glo_d先自增。此时glo_d=2
2. Loc_d++，即loc_d=2，自增成功可以进行桶分裂。原桶与新桶(brother)的loc_d都是2
3. 将原Bucket的元素进行重映射，即遍历B0的所有元素，进行key&loc_depth_mask将元素分配到原桶和新桶中。

如下图。0&11=00，10&11=10。所以0依然放在原桶B0中，2重新放在下标为2的新桶B10中。

• 重新插入4。4&global_depth_mask即100&11=00，所以把4插入到B0中

⑤插入5，5& global_depth_mask即101&11=01，发现B1这个桶已经满了，准备桶分裂

1. Glo_d > loc_d，loc_d++成功，故桶B1可以直接分裂，得到新桶B11
2. 将原桶B1的元素进行重映射(key&local_depth_mask)分配到B01和B11中
3. 重新尝试插入5，5& global_depth_mask即101&11=01，插入B01成功。如果插入失败继续尝试桶分裂。

⑥插入6，6& global_depth_mask即110&11=10，成功插入到B10中

⑦插入7，7& global_depth_mask即111&11=11，成功插入到B11中

⑧插入8,8& global_depth_mask即1000&11=00，发现桶B00已经满了，尝试进行桶分裂

1. 所以B00先尝试local_depth++来进行桶分裂，但是由于此时local_depth已经等于global_detph了，所以loc_d自增失败，需要glo_d先自增。此时glo_d=3
2. Loc_d++，即loc_d=2，自增成功可以进行桶分裂。原桶与新桶(brother)的loc_d都是3
3. 将原Bucket的元素进行重映射，即遍历B0的所有元素，进行key&loc_depth_mask将元素分配到原桶和新桶中。
4. 重新尝试插入8，8& global_depth_mask即1000&111=000插入成功。如果插入失败继续尝试桶分裂。

最后可扩展哈希表如下:

其实这个例子中，应该用page_id来标记唯一的桶，为了方便理解我就直接用下标来标识每个Bucket。

通过上述例子，我们可以总结可扩展哈希表的插入流程

1. 尝试插入key。进行key&global_depth_mask从而找到对应的Bucket下标。当前Bucket不满，直接插入成功，return。如果失败进行步骤2
2. Bucket满了。
   1. 当前global_depth > local_depth，此Bucket进行local_depth++成功，可以直接进行桶分裂。进行步骤3
   2. 当前global_depth =local_depth，此Bucket进行local_depth++失败，不可以可以直接进行桶分裂。进行Global_depth++，所以此Bucket可以进行local_depth++，桶分裂成功。进行步骤3
3. 重映射。桶分裂成功后，遍历原Bucket，对其中的每个元素elem进行elem&local_depth_mask，从而将原Bucket的元素分配到原桶和新桶中。重新进行步骤1

实现过程分析

我最近发现了个方法论，把实验需求看了几遍之后，把lab涉及到的头文件，在这里是header_page.h、directory_page.h和bucket_page.h重新归纳一遍。只是硬看的话在实现函数的过程中很容易前面忘了，后面忘了，全忘了~简称忘3

一言蔽之，这个过程就是将插入的key进行各种转换，最终找到相应bucket。我直接将lab给出的图例进行了一番改造，下图就是一个key进行映射的过程。

为了更好地理解lab要求，在粗略浏览一番代码后，我们应该弄清楚以下几个问题：

Q：在Header部分，核心函数HashToDirectoryIndex的目的是什么呢？

A：提取key的最高几位，从而尝试进入对应的Directory。

Q：在Directory部分，如何获得Global_Depth？

A：作为task2的核心部分，大部分功能都是在directory_page.cpp进行实现的。在init()直接将Global_Depth和每个Bucket的Local_Depth都初始化为0就行。

Q：在Directory部分，HashToBucketIndex的目的是什么呢？

A：提取key的最低几位，从而尝试进入对应的bucket。这里用page其实更合适，因为每个bucket本质都是一张page。

Q：搞清楚bucket_index和page_id的区别？

A：bucket_index并不是我以为的、、这种，而仅仅是指directory中的数组下标。而page_id才是真正的bucket序列号，用来区分唯一的bucket。

Q：GetSplitImageIndex()这个函数的作用是什么？

A：这个函数感觉没描述清楚，通俗来说就是获得当前bucekt的兄弟bucket。将当前bucket在Directory的下标最高有效位取反，就可以得到bro。例如，B0的兄弟是B1，B101的兄弟是B001。因为B101和B001都是从B01分裂而来的，所以他俩互为bro。

值得一提的是，task2并不需要实现这个函数。这个函数在task3才需要用到。

理解上述几个问题后，可以先尝试粗糙地将函数功能实现，然后对着测试样例一步步改进细化。

 

 Task #3 - Extendible Hashing Implementation

实现了task2后，对可扩展哈希表的工作流程就已经大体了解得差不多了，现在就是具体实施对(key, value)的处理流程。为了找好着手点，我们可以自行模拟插入三个元素时，hash_table的工作流程。

就GetValue()、Insert()和Remove()三个核心操作而言，有一套共同的前期流程：

1、先从bufferpool中获得Header Page。至于是以ReadGuadPage还是以WriteGuadPage获得就取决于这次操作是否会修改Header Page了。得到key的最高几位后，在Header Page中找到这个key对应的Directory 页表项。如果存在，进入步骤2。

        如果没找到对应的Directory，return false或者从bufferpool中申请一个新的page来存放新的Directory Page，即调用InsertToNewDirectory。

2、找到对应Directory的页表项后，以Page Guad的方式从bufferpool中获取这个Directory Page。然后得到key的最低几位后，在Directory Page中找到这个key对应的bucket页表项。如果存在，进入步骤3。

3、同样是以Page Guad的方式从bufferpool中获取这个Bucket Page，然后就可以进行具体的操作了。

4、至于桶分裂、桶合并等操作就需要自己具体实现了。

对于桶合并的问题，分为三种情况：

1. 当前bucket并没有bro，即它的local_depth=0
2. 当前bucket有bro，但是bro和它指向同一个bucket page，这种连体婴就不需要继续合并了
3. 当前bucket有bro，且bro和它指向不同的bucket page，这种情况才可以正常合并

Q：什么时候需要合并呢？

A：当前bucket和bro有一方为空的时候进行合并。

OK，然后就是对着测试样例一步步修正自己的代码了。在提交到gradescope时，果不其然我遇到了两个bug。

遇到的bug

1、合并时机没领悟通透，像下面这种情况是需要继续合并的

2、没有及时释放页面的锁

        说实话这个问题过于隐晦了。测试样例将bufferpool_size设置为3。而访问Header Page需要占据一个frame，访问对应的Directory Page需要占据第二个frame，访问对应的Bucket Page需要占据第三个frame。

        这个时候，如果需要访问当前bucket的bro，就需要从当前bufferpool中逐出一个page。但是由于我没有及时释放Header Page，就导致前面三个page赖在bufferpool不走了，也就无法访问新的page，造成访问地址错误。

        其实我感觉设置bufferpool_size=3是真的过于刻意了，就是盯着只有Header Page只有1个才想出来的馊主意。如果最高级的是root page，而且Header Page不止1个呢，那估计就会设置个bufferpool_size=4来卡一手人了。

        总而言之，个人感觉Extendible Hash Index思维难度并不高，代码量也适中。给我的感觉是构建一个b+树demo工作量就能与之一战了。

最后放一张通过的图