撰写本文的目的：记录本人在不参考其他任何形式的解决方法（思路/源码）、仅靠课程提供的资源（课本/参考资料）和Discord中high level的讨论的情况下，独立完成该课程的过程。

欢迎大家和我讨论学习中所遇到的问题。

ZiHao's Blog

由于gradescope中对non-cmu students还未开放Project#2，本文方法仅通过了本地测试，极有可能有错误（并发访问）

Project #2: Extendible Hash Index

先记录完成的过程，然后再总结和思考

准备

Due：四个星期左右（通过本地测试-4天左右+通过线上测试-待定）

在开始完成该项目之前，首先确保两件事

1. 确保Project#1的代码实现是正确的，最好多提交几次，因为测试用例可能会有不同
2. 一定要先从原bustub仓库pull最新的代码，不然可能会缺少一些给定的实现

实验环境：

• MacOS
• CLion/VSCode

Task #1-Read/Write Page Guards

• 数据成员：存储指针

  • 指向BPM
  • 指向Page对象

• 析构函数：确保当BasicPageGuard对象离开作用域的时候：自动调用UnpinPage

• 方法成员：除此之外，需要提供方法使得能够手动unpin

• 数据成员：writer-reader latch

  • 可以尝试调用Page中的相关方法

• 方法成员：能够在对象离开作用域时，自动释放latch

BasicPageGuard/ReadPageGuard/WritePageGuard

对于BasicPageGuard

• PageGuard(PageGuard &&that): Move constructor.

  • 参考C++Primer

    • 移动构造的时候从给定对象中窃取资源而非拷贝资源，即移动构造函数不分配任何新内存
    • 需要确保移后源对象销毁是安全的

• operator=(PageGuard &&that): Move assignment operator.

• 需要处理移动赋值对象是自身的情况

  • 直接返回*this

• 否则，需要处理原page

  • 按需调用Drop
    • 类似于移动构造

• Drop(): Unpin

  • 先clear
  • 再调用UnpinPage

• ~PageGuard(): Destructor.

  • 需要先判断是否已经手动Drop

    • 若否则直接调用Drop

• read-only和write dataAPIs

  • 分别为As和AsMut
    • As以const修饰符返回Page内部的data
    • AsMut则不然，并且注意AsMut会将PageGuard的成员变量is_dirty置为true
  • 可以在编译时期检查data用法是否正确：
    • 例如，在实现Task3或Task4的Insert时，你可能认为某个部分仅仅是查阅了HeaderPage，因此以As返回，却没想到其实有可能在HeaderPage中无相应DirectoryPage后，会修改HeaderPage。例子可能不大恰当

对于ReadPageGuard

• 移动构造和移动赋值都可以使用std::move完成

  • std::move()移动赋值时，会对赋值guard调用析构函数并调用Drop，因此不必担心赋值后移后源对象会对page造成影响

• 需要注意Drop中资源的释放顺序，需要在Drop BasiPage之前释放RLatch，

  • 可能会因为Unpin调用了RLatch而死锁

  • 更重要的原因：先UnpinPage的话，可能会被replacer evit

• 需要在析构函数中判断是否已经手动drop/移动赋值/移动构造过，避免重复Drop导致重复释放Latch

对于WritePageGuard：同上

Upgrade

guarantee that the protected page is not evicted from the buffer pool during the upgrade

• UpgradeRead(): Upgrade to a ReadPageGuard

• UpgradeWrite(): Upgrade to a WritePageGuard

目前这两个函数我都没有使用到，或者说是不知道该如何实现以及使用：

• 如何实现？我本以为防止evict只需要将page的pin_count_++，但是并PageGuard不是Page的friend class，无法直接访问Page的私有成员
• 如何使用？我能想到该函数存在的原因，是新建一个需要修改的DirectoryPage或者BucketPage，但是没有NewWritePageGuard和NewReadPageGuard函数的实现，只能 NewPageGuard之后立刻Upgrade。
  • 我认为：实际上该线程新建的Page目前只能该线程自己访问，并不需要使用Guard来保护啊
  • 因此我在InsertToNewDirectory和InsertToNewBucket中都只是用了BasicPageGuard并且调用了AsMut，而未使用WritePageGuard。并且这是能够通过本地测试的

Wrappers

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

注释中说明得足够清晰，不再赘述

Tests

Task #2-Extendible Hash Table Pages

这里主要实现三层可扩展哈希表的三个部分，如上图所示：

1. Header Page：
   1. 课本中的2-Level并没有该部分，该部分的max depth/prefix（例如上图中的2）是固定的
   2. 主要是用来索引能够索引到存储key的BucketPage位置的Directory Page在Header Page中的位置（比较拗口）
      1. 通过HashToDirecotryIndex实现
   3. HeaderPage的优点（文档中提到）：
      1. More Direcotry Pages -> More Bucket Pages -> More Keys
      2. 并且由于Latch Crabbing的并发策略，使得Header Page的Latch很快的被释放
2. Directory Page
   1. 与课本中一致
      1. global depth = hash prefix：三个作用
         1. 用来限制某个时刻可以使用的Directory条目数量 $2^{global depth}$ 个
         2. 用来获得哈希值从LSB开始的global_depth个位，作为在dierctory中的索引，找到key所在的bucket
            1. HashToBucketIndex实现
         3. 并且在某个bucket满时，通过比较global depth和local depth来决定如何处理split
      2. local depth = bucket hash prefix
         1. 通过比较和global_depth的关系，判断指向当前bucket的指针数量，分裂时如何处理
3. Bucket Page
   1. 以数组的形式存储<key, value
   2. 注意本项目并不会处理non-unque key，因此对于插入相同的key直接返回false（Insert函数）

Task2中相关源码的注释并没有很详细，需要自己根据本地测试来判断该函数具体完成了什么工作

• 可以在实现Header Pages和Directory Pages的时候，通过HeaderDirectoryPageSampleTest来测试或者Debug
• 实现Bucket Pages的时候，通过BucketPageSampleTest测试
• 例如：HashToDirectoryIndex是通过hash value的max_depth个MSB求得的

Hash Table Header Pages

成员变量：

directory_page_ids：page_id（4B）的数组

• 元素个数：1<<9

  • 即512个

• 占用内存：512*4 = 2048

max_depth_: 通过page_id(32位)哈希值的高max_depth_位，来判断page_id在directory_page_ids_中的位置

• 占用内存：4B

方法实现：

- [✅] HashToDirectoryIndex(uint32_t hash)

• 通过测试可以看到，实际上该函数是将hash的高max_depth_位，作为directory page id在数组directory_page_ids_的索引
• 将hash向右移动32-max_depth_位，可以获得高max_depth_位对应的uint32_t表示
• Hint: 考虑max_depth_为0的情况，实际上对于4B的整型右移32位是undefined？

- [✅] MaxSize()：Get the maximum number of directory page ids the header page could handle

• 由于directory_page_ids中每个条目只能存放一个page id元素，因此directory_page_ids_最大能存入HTABLE_HEADER_ARRAY_SIZEdirectory page id

• 而max_depth_

  • 对于线性探测解决冲突的哈希表：会决定directory_page_ids的大小
  • 不使用线性探测解决冲突：似乎并不会影响directory_page_ids_的大小，

• 根据题目要求，Header Pages并没有使用线性探测，因此需要返回max_depth_能表示数的数量和HTABLE_HEADER_ARRAY_SIZE之中的较小值

Hash Table Directory Pages

成员变量：

max_depth_：

• 4B
• Header Page的directory page id数组中，所有的directory page拥有相同的max_depth值，代表一个directory能够用的掩码的最大位数

global_depth_：

• 4B

• 类似于: 课本中的bucket address table的global prefix，用来控制当前table使用条目的数量，上限是2^max_depth

• 简而言之：global_depth用来掩码hash value，以获得存储key的bucket在directory 中的索引

• global_depth<=max_depth_

local_depth_s：数组

• 1B * (Size of array of Bucket page id )
• 类似于：课本中每个bucket持有的local prefix，用来按需生成bucket，进行local prefix后拥有相同值的entry指向同一个bucket
• 简而言之：local_depth用来掩码，使得确定其在哪个bucket page中

bucket_page_ids_

• 存储bucket page id的数组

方法实现：

- [✅] Init:

• 将global depth和local depth初始化0
• bucket page id初始化为-1或者其他特殊标记

- [✅] HashToBucketIndex:

• 类似于Header Page中的HashToDirectoryIndex，只不过掩码长度为global_depth_，并且是将Hash值的低global_depth_位(从LSB开始)处理作为bucket在directory中的索引
• 像测试中直接%Size()是极好的，但是我一开始脑子没转过来，
  • 一直想用位操作。。。
    标签：Index,global,bucket,Page,Project,depth,id,Extendible,page
    From： https://www.cnblogs.com/zihao626/p/17802365.html