Extendible Hash Table 算法实现

Smith • 2021年11月4日下午1:59 • Database • 阅读 7162

这篇文章围绕 Extendible Hash Table 的工程实现展开，重点补足很多资料只讲扩容不讲收缩、只讲概念不讲代码的空白。正文先约定 directory、bucket、page、global depth、local depth 和 split image bucket 等术语与规则，再分别说明如何根据深度生成 mask、如何计算兄弟 bucket、以及 directory 的 grow 和 shrink 逻辑。后半部分详细拆解插入、删除和收缩流程，解释桶分裂时 page 的重新分配、directory 指针和 local depth 的更新方式，以及在 bucket 为空时如何与 split image bucket 合并并尝试压缩 directory。

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$ 。

进行分流的操作统一从低位开始，比如 $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。

辅助类算法

根据 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）

计算插入数据 A Key 的 Hash 值。
与 global depth 进行 & 运算，得到其 bucket index。
如果 bucket index 没满，直接插入即可，返回成功，否则进行步骤 4。
增加对应 bucket index 的 local depth，然后根据新的 local depth 计算得到它的 image split bucket index。
如果新的 local depth 大于 global depth，对 directory 进行扩容。
给 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）。至此，原数据的迁移完成。
将所有同一级的 bucket 设置为相同的 local depth 和 page，这样说不清，直接看代码吧。
重新尝试插入 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 删除

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

Shrink 收缩

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

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

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

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

总结

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

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

Dynamic Hash Hash Table

打赏

微信扫一扫

Smith

StarRocks 全新云厂商鉴权系统食用指南

上一篇 2023年4月9日上午10:45

数据库查询实现原理

下一篇 2022年1月20日下午2:12

Database

Bitmap Indexing（位图索引）

这篇文章用一个包含 `Job` 和 `Sex` 字段的简单员工表示例，介绍了 Bitmap Indexing 的基本存储方式和查询优势。正文先说明 bitmap 索引会为每种取值维护一段位图，并展示如何通过按位与运算快速筛选同时满足多个条件的记录，随后将这种做法与传统 B+ 树在多条件分析场景下的开销进行对比，最后总结了 bitmap 索引适合低基数字段、OLAP 多维分析和逻辑运算场景，以及在高基数字段和频繁更新场景下的局限。

2022年6月22日
4.3K2
StarRocks

StarRocks 中关于 Hadoop Hedged Read 性能测试

这篇文章围绕 StarRocks 接入 HDFS 后启用 Hadoop Hedged Read 的效果做了一轮系统性能测试，重点观察不同线程池大小和超时阈值对查询耗时的影响。正文先介绍 Hedged Read 的工作机制和实验环境，再分别在单线程、慢节点和高并发 CPU 打满等场景下比较多组配置结果，最后结合 DFSClient 的线程池实现分析其共享方式和扩缩容行为，并给出较大的超时阈值配合较宽线程池的推荐配置。

2023年7月6日
1.6K2
StarRocks

How to deploy StarRocks with IAM enabled in AWS EKS?

This article records a practical walkthrough for deploying StarRocks on AWS EKS with IAM enabled, using CloudShell, eksctl, Helm, and IAM service accounts. It starts from creating an EKS cluster and fixing pod scheduling issues by reducing FE and BE resource requests, then shows how to bind IAM roles to StarRocks pods so they can access services such as S3 and Glue, and finally covers applying the updated Helm values, connecting to the cluster, and cleaning up both the IAM service account and the EKS cluster after the test.

2024年9月9日
1.2K0

发表回复

评论列表（42条）

2021 CMU 15-445 实验笔记 | 沧海月明 2026年3月29日下午3:32

[…] Extendible Hash Table 的算法实现，可以看我的另一篇文章：https://www.inlighting.org/archives/extendible-hash-table-algorithm […]

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

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

回复
- Smith 2024年4月25日上午11:19
  
  @小学：以下楼层均已发
  
  回复
依然 2023年3月30日下午8:40

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

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

求个源码

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

楼主你好，可以求一份代码吗？

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

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

回复
- Smith 2023年1月14日上午12:55
  
  @whznpu_ruc：一样的
  
  回复
疯狂的麦克斯 2022年12月29日上午2:28

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

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

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

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

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

回复
- Kenerl 2022年10月1日下午4:45
  
  @Kenerl：不用了佬，我 debug 出来了，脑子一抽觉得插入失败要么是重复要么是满了，没有考虑满了也会重复的情况。
  
  回复
- Smith 2022年10月1日下午10:23
  
  @Kenerl：我发你了呀，难道你邮箱没收到？
  
  回复
- Kenerl 2022年10月3日下午9:39
  
  @Smith：谢谢，邮箱没有开消息提醒，然后觉得应该没有这么快发过来，在回复之前就没有看邮箱了🙌
  
  回复
FORWARD 2022年9月7日上午11:28

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

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

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

回复
- xin 2022年9月5日下午9:03
  
  @xin：同学，我找到原因了。
  
  回复
- Smith 2022年9月6日上午10:58
  
  @xin：ook
  
  回复
GeekWu 2022年8月26日下午4:40

能否法一下代码

回复
- Smith 2022年8月26日下午5:19
  
  @GeekWu：此楼之前均已发。
  
  回复
logicix 2022年8月24日下午9:00

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

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

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

回复
- Smith 2022年8月14日上午12:29
  
  @daiym：发你代码了，你看看吧。按道理 test_memory_safety 不会 timeout 的。
  
  回复
- daiym 2022年8月14日上午12:40
  
  @Smith：其实有可能的，在 test_memory_safety 里用时会翻20多倍。
  
  回复
- Smith 2022年8月14日下午2:26
  
  @daiym：好吧，时间太久了，都忘了。
  
  回复
Kaip 2022年8月7日下午2:40

求份代码找bug

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

求份代码找bug

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

大哥可以分享一份源码嘛

回复
jared 2022年6月28日下午6:56

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

回复
- Smith 2022年6月28日下午10:33
  
  @jared：发了
  
  回复
- jared 2022年6月29日下午10:11
  
  @Smith：太感谢了，原来是bucket page insert的时候要利用之前被删除的slot, 现在改完了之后总算满分过了！！
  
  回复
Ricardo 2022年6月24日下午10:10

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

回复
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的结果）

回复
- Smith 2022年5月30日上午9:24
  
  @Jojo：额，感觉你还没有把逻辑搞清楚，你可以看看 https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/，源码我也私发你邮箱了。
  说实话有些细节我自己都忘了，最近比较忙，没有时间回味。
  
  回复
- 小猪配迪 2022年6月13日下午3:30
  
  @Jojo：那四个for循环的作用应该是在目录扩容后，将扩容的同级bucket的depth和page_id进行复制吧。
  
  回复
- soar 2022年8月1日下午11:43
  
  @Jojo：hxd,不知道你理解了吗，我遇到和你一样的问题了
  
  回复
Tusen 2022年5月25日下午10:06

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

回复
- Smith 2022年5月26日下午1:53
  
  @Tusen：我私发你代码了，要不自己看看源码，最近有点忙。
  
  回复
- Tusen 2022年5月26日下午2:00
  
  @Smith：好的。我改完了。最后发现，如果桶为空，但是remove失败，也要尝试删除空桶。
  
  回复
Tusen 2022年5月16日下午7:00

。

回复
- Smith 2022年5月16日下午7:17
  
  @Tusen：只有当 Bucket 满了，该 Bucket 才会分裂成两个 Page。不然当分裂操作发生时，一些 Bucket 明明没有满的 page，也分裂成两个 page，会产生不必要的数据移动和空间的浪费。
  建议你看看：https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/，先把流程搞清楚哈。
  
  回复
- Tusen 2022年5月16日下午9:12
  
  @Smith：OK,我先看看。lecture给的资料太少了T-T
  
  回复