磁盘哈希结构-Linear Hashing

1. Linear Hashing

最近在思考一个问题，如果一个存储引擎不需要支持范围查询，那么使用hashtable这样的数据结构是否更合适？恰好看到了lotusdb中使用了一个diskhash的库，从源码看是使用了一种Linear Hashing的哈希表数据结构，由于磁盘与内存的特性不同，因此磁盘哈希结构与常见的内存hashtable不太一样，特意研究了下。

2. 数据结构

通过primaryFile文件来存储hash桶，每个桶上有slotsPerBucket个槽，每个槽存储一个KV对，桶的数量为2 ^ Level个。当所有槽都用完时，在overflowFile中创建溢出桶，并通过nextOverflow记录新创建的溢出桶在文件中的offset。

初次创建时，会将Level初始化为0，SplitBucketIndex为0，然后创建出primaryFile并初始出一个桶

3. Put

写入过程如下： * 计算key的hash，然后hash对桶数量取模计算出key所在的桶

bucketIndex := keyHash & ((1 << t.meta.Level) - 1)

• 遍历bucketIndex对应的桶以及该桶所有溢出桶上的所有slot，寻找key对应的槽
  • 如果找到则原地更新
  • 如果没有找到说明这是一个新key，则在第一个空槽上插入
  • 如果是新key且没有空槽，这时就需要创建一个溢出桶出来
• 如果是新增key，需要判断下当前的负载因子是否超过阈值，超过阈值需要进行扩容

3.1 创建溢出桶

一般情况下溢出桶的创建是通过调用File.Truncate()扩容实现的，这里还有个逻辑是在hashtable进行扩容时，有些溢出桶不再使用可以被释放，这些溢出桶会被缓存下来，在创建溢出桶复用这些被释放的溢出桶。

4. 扩容

Linear Hashing的扩容是其核心部分，与内存hashtable常见的扩容策略有所不同，这里重点解释下

4.1 扩容时机

每当新增key之后都会重新计算当前的负载因子，负载因子的计算公式如下

keyRatio := float64(t.NumKeys) / float64(t.NumBuckets*slotsPerBucket) // slotsPerBucket是一个常量

即KV对的数量除以槽的数量。当负载因子超过阈值（默认是0.7）时触发扩容

if keyRatio > t.options.LoadFactor {
	t.split()
}

4.2 扩容过程

Linear Hashing维护一个指针SplitBucketIndex，每次扩容时就拆分这个指针指向的桶。

拆分前会将存储桶的文件扩大一个桶的大小，即增加一个桶。拆分时遍历旧桶所有槽，重新计算槽所在的位置，然后迁移到新桶上。

然后将SplitBucketIndex加1指向下一个桶，加完之后如果溢出了则将SplitBucketIndex归零，这时还要将Level+1，即标识桶数量翻倍。

5. 删除

删除过程比较简单，首先计算key的hash，然后取模计算出所在的桶，遍历桶上所有槽，如果找到槽则将槽置为空，然后写回磁盘