Extendible Hash Table 算法实现

Extendible Hash Table 属于动态哈希的一种,网上有很多关于它的介绍,但是真的在实现它的时候,或多或少有着很多问题。网上很多教程光讲怎么扩容,不讲收缩,而且网上很多都是概念性的东西,不讲代码实操。因 CMU 15-445 的课程需要,自己捣鼓了一下算法流程,这里分享一下。

在看之前请自行了解 Extendible Hash Table 的概念:

https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/

http://www.mathcs.emory.edu/~cheung/Courses/554/Syllabus/3-index/extensible-hashing.html

约定

在开始讲解算法前,我们先进行一些规则的约定。

  • 目录叫 Directory, 桶叫 bucket,bucket 在 directory 的序号叫 index。
  • 每一个 bucket 的空间指向一个 page,存在多个 bucket 公用同一个 page 的情况
  • 扩容叫 grow,收缩叫 shrink。
  • 初始的 $GlobalDepth=0$,且只有一个 Bucket,该 bucket 的 $LocalDepth=0,Index=0$。
image-20211105143555494
  • 进行分流的操作统一从低位开始,比如 $GlobalDepth=2, HASH(A)=1110$,因为我们从低位开始,所以 $MASK=11$,那么我们进行 HASH(A) & Mask = 10,也就是序号为 2 的bucket。
  • 我们定义 split image bucket 就是该 bucket 在分裂时候产生的兄弟,比如 10 的兄弟是 00。也就是 bucket 序号为 0,2 的两个桶。如下图,0 bucket 分裂后生成 00 和 10 两个 bucket,它们两个 bucket 互为 split image bucket。但是它们仍然公用一个 page 0。 image-20211105145235687

辅助类算法

根据 bucket 的 local depth 生成其对应的 mask

mask 的作用就是通过和 HASH 值 & 运算得到 bucket index。

uint32_t HashTableDirectoryPage::GetLocalDepthMask(uint32_t bucket_idx) {
  uint8_t depth = local_depths_[bucket_idx];
  return (1 << depth) - 1;
}

找到一个 bucket 的 split image bucket index

uint32_t HashTableDirectoryPage::GetSplitImageIndex(uint32_t bucket_idx) {
  uint32_t local_depth = local_depths_[bucket_idx];
  return bucket_idx ^ (1 << (local_depth - 1));
}

Directory Grow

根据规则,当某一个 local depth 大于 global depth 时,则需要对 directory 进行 grow。Grow 时,将原有的 bucket 复制一遍,然后追加到末尾上去即可。

void HashTableDirectoryPage::IncrGlobalDepth() {
  int origin_num = 1 << global_depth_;
  int new_index = origin_num;
  int origin_index = 0;
  for (; origin_index < origin_num; new_index++, origin_index++) {
    bucket_page_ids_[new_index] = bucket_page_ids_[origin_index];
    local_depths_[new_index] = local_depths_[origin_index];
  }
  global_depth_++;
}

注意:这里并没有包含数据的迁移,扩容后,每一对 bucket 都还是使用着同一块 page 空间。

Directory Shrink

当所有 bucket 的 local depth 均小于 global depth 的时候,就可以对 directory 进行一次收缩。收缩直接 global_depth – 1即可。

Insert 插入(含 Grow)

  1. 计算插入数据 A Key 的 Hash 值。
  2. 与 global depth 进行 & 运算,得到其 bucket index。
  3. 如果 bucket index 没满,直接插入即可,返回成功,否则进行步骤 4。
  4. 增加对应 bucket index 的 local depth,然后根据新的 local depth 计算得到它的 image split bucket index。
  5. 如果新的 local depth 大于 global depth,对 directory 进行扩容。
  6. 给 image split bucket index 申请一个新的 page 空间,从 bucket index 的 bucket page 中拷贝数据 data,然后清空 bucket index 中的内容。根据当前 local depth 产生的 mask 对 data 重新分配。注意,data 中的数据只会落入当前 bucket page 和 image split bucket page 两个 page 中(注意我这里说的是 page 而不是 bucket)。至此,原数据的迁移完成。
  7. 将所有同一级的 bucket 设置为相同的 local depth 和 page,这样说不清,直接看代码吧。
  8. 重新尝试插入 A,回到步骤 1。

第 7 步代码:

//-------------
uint32_t diff = 1 << dir_page->GetLocalDepth(split_bucket_index);
for (uint32_t i = split_bucket_index; i >= 0; i -= diff) {
  dir_page->SetBucketPageId(i, split_bucket_page_id);
  dir_page->SetLocalDepth(i, dir_page->GetLocalDepth(split_bucket_index));
  if (i < diff) {
    // avoid negative because we are using unsigned int32 i
    break;
  }
}
for (uint32_t i = split_bucket_index; i < dir_page->Size(); i += diff) {
  dir_page->SetBucketPageId(i, split_bucket_page_id);
  dir_page->SetLocalDepth(i, dir_page->GetLocalDepth(split_bucket_index));
}
for (uint32_t i = split_image_bucket_index; i >= 0; i -= diff) {
  dir_page->SetBucketPageId(i, image_bucket_page);
  dir_page->SetLocalDepth(i, dir_page->GetLocalDepth(split_bucket_index));
  if (i < diff) {
    // avoid negative
    break;
  }
}
for (uint32_t i = split_image_bucket_index; i < dir_page->Size(); i += diff) {
  dir_page->SetBucketPageId(i, image_bucket_page);
  dir_page->SetLocalDepth(i, dir_page->GetLocalDepth(split_bucket_index));
}

Remove 删除

  1. 计算删除数据 A Key 的 Hash 值。
  2. 与 global depth 进行 & 运算,得到其 bucket index。
  3. 从 bucket index 对应的 page 中进行查找,找到了就直接删除,找不到就返回不存在。
  4. 判断删除后的 bucket 是否为空,如果为空,对该 bucket 进行 Shrink 操作。

Shrink 收缩

Shrink 这块比较复杂, 我的实现比较简单,就是只有当 remove 后 bucket 为空时才进行 Shrink,并不会自动扫描当前有哪些 bucket 为空,然后进行 Shrink。这样做其实没必要,毕竟频繁的扩容收缩会带来性能上的损耗。这也是为什么很多文章根本不讲 Shrink 的原因。

注意,bucket 的 local depth 为 0 时,是不进行 Shrink 的。

只有当 bucket 和其 split image bucket 的 local depth 相同时,才会进行 Shrink。

  1. 检查 target bucket 是否为空,不为空直接返回。
  2. 检查 target bucket 的 local depth 是否大于 0,且和其 split image bucket 的 local depth 相同,不符合要求直接返回。
  3. 遍历整个 directory ,将所有指向 target bucket page 的 bucket 全部重新指向 split image bucket 的 page。
  4. 将重新指向过的 bucket 的 local depth 均 -1。
  5. 尝试进行 directory 的 shrink。

总结

写的比较简单,适合有基础的人看,毕竟也没有那么多时间做一个详尽的图文教程了。希望大家在 CMU 15-445 的海洋里面快乐的遨游。

原创文章,作者:Smith,如若转载,请注明出处:https://www.inlighting.org/archives/extendible-hash-table-algorithm

打赏 微信扫一扫 微信扫一扫
SmithSmith
上一篇 2022年2月2日
下一篇 2022年1月20日

相关推荐

  • 2023年10月1日数据湖测试

    OLAP 有 ClickBench,向量化有 VectorDBBench,那么数据湖就不能有一个 DataLakeBench?正可谓知己知彼,方能百战不殆。国庆自己整了一个 TPC…

    2023年10月1日
    1.1K0
  • 数据库并发控制原理

    数据库的事务 transaction (txn)很有搞头,特此特别记下这篇笔记,方便自己的回顾,如有错误,请指正。 Transaction 数据库事务以 Begin() 开始,以 …

    2022年1月26日
    4.4K5
  • 2021 CMU 15-445 实验笔记

    陆陆续续终于把 CMU 15-445 刷完了(中间插了个 TinyKV),这也算是自己数据库的启蒙之课。编码耗时共计 98 小时 43 分钟。 我个人给整个项目难度评级:Proje…

    2022年2月2日
    11.2K198

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

评论列表(41条)

  • 小学
    小学 2024年4月25日 上午5:42

    大佬能求一份源码吗,项目里有关并发执行的一些细节自己不知道如何实现。

  • 依然
    依然 2023年3月30日 下午8:40

    大佬能求一份源码吗,项目里有关并发执行的一些细节自己不知道如何实现。

  • lucy
    lucy 2023年3月14日 下午11:06

    求个源码

  • GuoGuo
    GuoGuo 2023年1月19日 上午12:30

    楼主你好,可以求一份代码吗?

  • whznpu_ruc
    whznpu_ruc 2023年1月12日 下午4:41

    博主问一下,你的shrink方法和homework这个一样吗?
    https://15445.courses.cs.cmu.edu/fall2022/files/hw2-sols.pdf
    这里似乎提出了一种方法

  • 疯狂的麦克斯
    疯狂的麦克斯 2022年12月29日 上午2:28

    楼主,能求份源码吗,debug好久没找到问题,万分感谢

  • db
    db 2022年10月5日 下午3:04

    同学您好,可否发一份代码

  • Kenerl
    Kenerl 2022年9月30日 上午10:58

    佬,请问有没有自己写测试用例来测试,我写了一个大批量的插入删除来测试 split 和 merge,本地是能成功的 split 和 merge,但是在线测试 SplitGrowTest 过不了,如果有写的话可以发一下测试吗?

    • Kenerl
      Kenerl 2022年10月1日 下午4:45

      @Kenerl不用了佬,我 debug 出来了,脑子一抽觉得插入失败要么是重复要么是满了,没有考虑满了也会重复的情况。

    • Smith
      Smith 2022年10月1日 下午10:23

      @Kenerl我发你了呀,难道你邮箱没收到?

    • Kenerl
      Kenerl 2022年10月3日 下午9:39

      @Smith谢谢,邮箱没有开消息提醒,然后觉得应该没有这么快发过来,在回复之前就没有看邮箱了🙌

  • FORWARD
    FORWARD 2022年9月7日 上午11:28

    楼主能发一份源码吗,DEBUG心态小崩,非常感谢

  • xin
    xin 2022年9月5日 下午8:47

    同学,想请问一下cmu的那个测评网站project2有超时提示吗?我提交过后一直显示hasn’t finished running yet.

    • xin
      xin 2022年9月5日 下午9:03

      @xin同学,我找到原因了。

    • Smith
      Smith 2022年9月6日 上午10:58

      @xinook

  • GeekWu
    GeekWu 2022年8月26日 下午4:40

    能否法一下代码

  • logicix
    logicix 2022年8月24日 下午9:00

    老哥,带一份源码参考下,谢谢

  • daiym
    daiym 2022年8月13日 下午6:51

    您好,我使用的方法和你差不多,但在执行test_memory_safety时会timeout,前面的都能正确通过。请问有什么优化性能的建议呢。

    • Smith
      Smith 2022年8月14日 上午12:29

      @daiym发你代码了,你看看吧。按道理 test_memory_safety 不会 timeout 的。

    • daiym
      daiym 2022年8月14日 上午12:40

      @Smith其实有可能的,在 test_memory_safety 里用时会翻20多倍。

    • Smith
      Smith 2022年8月14日 下午2:26

      @daiym好吧,时间太久了,都忘了。

  • Kaip
    Kaip 2022年8月7日 下午2:40

    求份代码找bug

  • zaynt
    zaynt 2022年8月3日 下午4:40

    求份代码找bug

  • 风山斩
    风山斩 2022年7月1日 上午11:30

    大哥可以分享一份源码嘛

  • jared
    jared 2022年6月28日 下午6:56

    RemoveTest 总是执行不完,没有Ok,也没有Fail,本地无法复现,可以也发份代码吗

    • Smith
      Smith 2022年6月28日 下午10:33

      @jared发了

    • jared
      jared 2022年6月29日 下午10:11

      @Smith太感谢了,原来是bucket page insert的时候要利用之前被删除的slot, 现在改完了之后总算满分过了!!

  • Ricardo
    Ricardo 2022年6月24日 下午10:10

    老哥,能求份源码吗,万分感谢

  • Jojo
    Jojo 2022年5月29日 下午10:59

    想问 smith哥,我理解的 SplitInsert 最后需要 把当前SplitInsert的两个bucket 重新映射page,以及设置local depth
    那这个把所有同一级的 bucket 设置为相同的 local depth 和 page 具体是指什么呢 ,不理解第七步 四个for函数的作用是什么,而且此时diff 的值不会是比 split_image_bucket_index 和 split_bucket_index 还要大吗 (然后此时也能达到重新映射和设置local depth的结果 )

  • Tusen
    Tusen 2022年5月25日 下午10:06

    佬,能请教一下你的插入和删除寻找兄弟节点的算法是同一个吗。

    • Smith
      Smith 2022年5月26日 下午1:53

      @Tusen我私发你代码了,要不自己看看源码,最近有点忙。

    • Tusen
      Tusen 2022年5月26日 下午2:00

      @Smith好的。我改完了。最后发现,如果桶为空,但是remove失败,也要尝试删除空桶。

  • Tusen
    Tusen 2022年5月16日 下午7:00