CS15445-lab2

实验2-EXTENDIBLE HASH INDEX

实验要求

需要我们在实验一的基础上建立一个哈希索引。

任务一：页面布局设计

• 任务简介

如果创建了一个哈希索引，需要把数据写入到磁盘中，这样才能保证在重启DBMS的时候能够加载哈希索引。为了能够完成哈希索引的建立，需要我们完成两个类，一个是Hash Table Directory Page，另一个是Hash Table Bucket Page。

• Hash Table Directory Page：这个类保存了哈希table的元数据信息，分为了以下几个变量：

变量名	大小	描述
page_id_	4字节	自己的页编号
lsn	4字节	日志顺序编号
global_depth_	4字节	目录的全局深度
local_depths_	512字节	本地的深度
bucket_page_ids_	2048字节	保存page_id的数组

bucket_page_ids_数组变量保存了bucket和页编号的映射关系，第i个元素代表了编号为i的bucket对应的页面的编号。

• HASH TABLE BUCKET PAGE：这个类维护了三个数组：
  1. occupied数组：第i个元素如果为1，代表了array_数组的第i个元素从来没有被占用。
  2. readable数组：第i个元素如果为1，代表了array_数组的第i个元素是可读的。
  3. array数组：保存了kv键值对。
     哈希table中的空余插槽的个数受到键值对的类型以及长度影响，我们这里只需要支持变长的键值对即可，在每个哈希table实例中的键值对大小是相同的，但是你不能够假设对于所有的哈希table，键值对大小都是相同的。

每一个哈希table都会在缓存池中有页面与之对应，每次需要对一个页面进行读写操作，首先需要通过页面编号在缓存池中获取对应的页面，然后强制转换成一个目录页或者是bucket页，最后在读写操作操作完成后unpin对应的页面。

• 原理学习

首先需要学习什么是extendible hashing。extendible hashing分为两个组成部分，一个是保存元数据的directories页面，另外一个是保存数据的bucket页面。

1. directories：保存了指向buckets的指针。每一个directories都有一个唯一的编号，每次在哈希表动态调整后哈希函数会返回一个directories编号，directories的数量是2^global_depth。
2. buckets：保存了键值对，如果一个buckets的local_depth小于global_depth，代表一个buckets包含多个键值对。
3. global_depth:它与目录相关联。它们表示散列函数用于对密钥进行分类的位数。全局深度 = 目录ID中的位数。
4. local_depth:它与global_depth相同，只是local_depth与存储桶相关联，而不是与目录相关联。局部深度根据全局深度来决定发生溢出时要执行的动作。局部深度总是小于或等于全局深度。
5. buckets splitting:当一个bucket的元素个数大于一个值后，会分裂成两个buckets。
6. directories expansion:当local_depth和global_depth大小相等时会发生。

• 接下来通过一个例子来解释其工作原理：

  1. 插入6，15，34，18，每个bucket最多容纳2个条目
  2. 把数字转换成二进制形式，110，1111，100010，10010
  3. 首先global和local的深度初始化为1
     • dir0（1）：110，100010，10010
     • dir1（1）：1111
  4. 插入18后触发了overflow，dir0对应的bucket超出了容量上限，并且此时的local和global深度相同，该buckets会发生分裂，分裂出来的新的bucket的local深度为1。global深度增加1，local深度增加1，重新进行哈希：
     • dir00（1）：
     • dir01（1）：
     • dir10（2）：110，100010，10010
     • dir11（2）：1111
  5. 发现dir10仍旧是超出了最大值，并且此时的local深度和global深度相同，需要分裂dir10对应的bucket并扩容dir：
     • dir000（1）：
     • dir001（1）：
     • dir010（3）：100010，10010
     • dir011（1）：
     • dir100（1）：
     • dir101（1）：
     • dir110（3）：110
     • dir111（2）：1111
  6. 以上就是完整的extendible hash的原理

• 实现思路

  • directory_page的实现：理解了extendible hash的思路，首先完成directory_page的编写，稍微有一点难度的是掩码的获取：

    auto HashTableDirectoryPage::GetGlobalDepthMask() -> uint32_t {
        return (1 << global_depth_) - 1; 
    }

    其余的函数基本上根据注释都能够编写出来。
  • bucket_page的实现：比较难的在于bucket_page的设计思路：occupied和readable数组用来标记bucket中的slots。这里看到一个比较有趣的声明：

    MappingType array_[1];

    array数组明明应该是保存了bucket中的所有键值对信息，为什么这里只是声明了数组长度为1的slot数组？查阅了相关的文档后发现一个HashTableBucketPage类占用一个整页，这个页的开头是两个bitmap数组，存储每个键值的位信息，之后的就全都归键值了。访问第i个键值的时候，可以直接用array_[i]的形式，因为array_[i]完全等价于*(array_ + i)。

  最后需要我们实现的是增删查几个函数，需要注意的一点是，这里的hashmap支持key对应多个value的情况，因此在插入的时候需要注意要先比较key值，再比较value值才能够确定是否需要插入。针对occupied数组，只有在第一次在一个slot中插入数据的时候才需要置为1，readable数组在写入数据后需要置为1，擦除数据只需要把readable数组对应的比特位置为0即可。最后编译hash_table_page_test，运行测试，成功通过。

任务二：hash table的实现

• 任务简介

  这个任务主要是实现extendible hash算法，之前在任务一中介绍了相关的原理。这里给的任务书中把工作分成了几个模块：

  1. directory indexing：当我们在索引中插入一个键值对的时候，我们会想用最低有效位来保证操作更加简洁。
  2. splitting buckets：当一个bucket满了的时候，我们会考虑对bucket进行分割操作 ，你可以选择当bucket满了的时候立刻进行分割。但是，给出的参考解决方案希望当整个页面溢出的时候再进行分割操作，提供给你的api可能会更适合这种方案。
  3. merging buckets：当一个bucket变成空的时候需要进行合并操作。有一种比较激进的方式，通过检查bucket的占用情况以及镜像buckets来确定是否为空，但是时间开销太大，这里不是很推荐。这里给出了更加简洁高效的解决方案：
     1. 只有全空的buckets才能够被合并
     2. 镜像buckets和原buckets只能local depth相同的时候才能进行合并
     3. buckets只能够再local depth大于0的时候才能进行合并
  4. directory shrinking：只有当每一个buckets的local depth都严格小于global depth才能够对directory进行缩小。您可能会看到其他用于缩小目录的测试，但这个测试很简单，因为我们将本地深度保留在目录页面中。

• 实现思路

  需要我们修改src/container/extendible_hash_table_index.cpp和src/include/container/extendible_hash_table_index.h两个文件,建议是先实现简单的insert，remove功能后再去实现split和merge等方法，具体的实现原理参照上面给出的extendible hash原理进行。

任务三：并发要求

• 任务简介

  需要我们完成并发功能

• 实现思路

  首先看到任务中给出的提示：需要我们在每个bucket添加一个锁，保证在写入一个bucket的时候index不被读或者写。还需要我们保证多个读者同时读取同一个bucket。

  • 上锁策略

    1. getvalue需要对索引和对应的bucket上读锁
    2. insert函数需要对索引上读锁，对bucket上写锁
    3. remove函数需要对索引上读锁，对bucket上写锁
    4. merge函数需要对索引上写锁，对bucket上读锁
    5. insertsplit函数需要对索引和bucket上写锁

  • 提供的提示

    在extendible_hash_table.h中提供了table_latch_读写锁用来给索引上锁。在src/include/storage/page.h中提供了了一个rwlatch_读写锁来对bucket进行上锁。

  最后成功通过测试。

• 参考

  • extendible hash