ZhuQiwei's Blog
0%

lab2-extendible hash index

Posted on In

Lab2 的任务是实现一个可扩充（扩缩容）的哈希索引。其作用是对数据库内的数据进行索引从而快速查询，以避免在检索时的逐行扫描。哈希索引分为directory和bucket，它们都存储在Page上，即整个哈希索引只有一个directory结构，存储于一个Page上，而哈希索引有若干bucket，每个bucket存储在一个Page上。哈希索引通过lab1实现的buffer pool实现对Page的载入和写回。

extendible hash index

首先介绍一下extendible hash index算法的原理（详细描述可参考《数据库系统概念》，英文版《Database System Concepts》）。如下图所示为一个extendible hash index。每个虚线框都代表一个Page。左边部分是directory，存储了一个depth，称为global depth，还有一个pageId映射表，存储了每个哈希值对应bucket的pageId。右边是一些bucket，每个bucket都有一个自己的专属depth，称为local depth。

extendible_hash_index

在拿到一个key之后，可扩充索引算法首先求出key的哈希值hash_key，我们假设其有32位，为uint32_t。我们不可能为每个哈希值都建立一个bucket，因为这需要2^32个桶，不现实。可扩充索引的原理是，我们初始的时候全局仅仅建立一个桶，所有key都存放在该桶中，当桶被填满后，我们新建一个桶，把旧桶中一部分元素转移到新桶中(rehash)。那么rehash的原则是什么呢？有一个办法，就是根据hash_key的二进制的尾数，即最后一位为0的key待在原bucket a，最后一位为1的转移到新bucket b。此时，全局就有了两个桶a和b，以后新的待插入key都要根据其hash_key的最后一位是0还是1来决定放入哪个桶。当两个桶中的某个满了(假设为b，它原本接受hash_key位数为1的所有key)，我们就再新建一个桶c，把b的一部分数据转移到新桶c中，转移的原则是什么呢？现在就该根据hash_key的最后2位来决定了。原本hash_key最后1位尾数为1的所有key可以分为两位尾数为01和11，如果其最后2位尾数为01，则待在原桶b，否则若尾数为11，则转移至c桶。然后，当转移完key之后，我们还要考虑后续新来的key如何做插入。我们现在看新的key的hash_key的二进制最后两位，若后两位为00、10，就放在a中（与第一次分裂的规则一致）。若key的后两位为01，则插入桶b，后两位为11，插入桶c。

这就是extendible hash index的原理，可以看出，决定待插入key该放在哪个桶，应该看key的哈希值hash_key的二进制数的最后若干位，这就是global depth的用处。而local depth的作用是决定如何进行桶的分裂。

查询

查询主要依靠global depth。对于某个待查询的key，我们首先用哈希函数h计算其哈希值hash_key（这里的h有若干选择，如CRC32、murmur Hash等）。然后我们根据global depth，获取hash_key的二进制形式的最后global depth位，将其作为索引数字idx，然后找到directory中pageId映射表的第idx个位置，查看其对应的bucket的page_id是多少。然后凭借page_id拿到bucket，在bucket内部顺序检索即可(可以做一些优化，如设置墓碑标记，使得顺序查找可以提前结束)。

插入

简单的插入原则和查询一致。但当插入导致bucket溢出时，我们需要做bucket的分裂。

首先检查溢出bucket的local depth，若local depth小于global depth，我们只用做bucket split；如果local depth等于global depth，则先做directory expandsion，然后再做bucket split。

  • directory expandsion：这是一个将directory double的过程，我们只需要改动directory内的一些数据
    • global depth 加一
    • 将pageId映射表大小变为原来的2倍，并填充新增表项的内容
  • bucket split：我们需要新建一个bucket，然后把溢出的bucket内的一部分key转移到新bucket中，然后在directory中做一些更新
    • 溢出bucket的local depth加一
    • 根据溢出bucket的local depth，决定bucket中的表项是否转移至新bucket，并转移
    • 设置新bucket在directory中的索引
    • 遍历pageId映射表，把原来指向溢出bucket的表项中，一半的表项指向新的bucket
  • directory的性质
    • 如果一个bucket的local_depth小于directory的global_depth，则directory中会有多个idx指向该bucket。具体个数为2global_depth -local_depth
    • global_depth主要用于key到bucket的导航；local depth主要用于split和merge时发现镜像pair。

删除

简单的删除原则和查询一致。但当删除导致bucket为空时，需要做bucket的merge（这里比较严格，实际上可以是bucket的占用率低于某个条件就做merge，可以人为规定merge时机）。

  • 实验中merge必须满足的几个条件
    • 当前bucket为空时，才对它进行merge
    • 当前bucket的local_depth必须和其image_bucket的local_depth相等
    • 当前bucket的local_depth必须大于0
  • merge过程
    • 将当前bucket的page删除
    • 把原本指向当前bucket的所有pageId映射表表项，修改为指向image_bucket；
    • 检查所有local depth，如果所有的local depth都小于global depth，则可以将global depth减一

CONCURRENCY CONTROL

我们需要对哈希索引做并发控制，使得其支持多线程访问。我们使用两类锁配合实现并发控制：table_lock 和 bucket_lock。table_lock只有一个，用于保护directory，可以以读模式和写模式获取。bucket_lock每个bucket有一个，用于保护单个bucket的读写。

具体的实现逻辑如下

insert & split

插入操作需要全程在directory读锁的保护下进行，以确保插入过程中diectory不会变动。此外我们还需要对应bucket的写锁。

我们首先在directory读锁和bucket写锁的保护下检测bucket是否是满的，如果不满则直接插入并返回。

如果bucket是满的，则需要做split。我们先释放之前获取的锁，然后请求directory的写锁。然后做split_and_insert。因为释放之前的锁和请求directory的写锁之间不是原子的，会有时间间隙，在这段时间内bucket可能又是不满的了，因此我们在split_and_insert内再次先判断一下bucket是否满，如果满了，再做split，否则直接insert。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool insert(...){
  table_lock.read_lock();
  bucket_lock.write_lock();
  //try to insert
  bool succeed;
  if(bucket is not full){
    succeed = bucket_insert(...);
    bucket_lock.write_unlock();
    table_lock.read_unlock();
    return succeed;
  }else{
    bucket_lock.write_unlock();
    table_lock.read_unlock();
    //use table write lock to split and insert
    table_lock.write_lock();
    succeed = split_and_insert(...);
    table_lock.write_unlock();
    return succeed;
  }
}

bool split_and_insert(){
  while(bucket is full){
    //do split
  }
  return bucket_insert(...);
}

delete & merge

和上面的同理。我们在directory的读锁和bucket的写锁保护下，先删除元素，然后顺便探测一下是否需要merge。如果需要，则释放directory的读锁和bucket的写锁，重新申请directory的写锁，然后做merge。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool delete(...){
   table_lock.read_lock();
   bucket_lock.write_lock();
   bool succeed = bucket_delete(...);	
   if(we need merge){
     bucket_lock.write_unlock();
     table_lock.read_unlock();
     
     table_lock.write_lock();
     merge();
     table_lock.write_unlock();
   }else{
     bucket_lock.write_unlock();
     table_lock.read_unlock();
   }
   return succeed;
}

void merge(){
  //recheck if we need merge
  if(we need merge){
    	//do merge
  }
  return;
}

实验结果

一些注意事项

  • split要实现成循环的。因为一次split后，bucket可能还是满的
  • 我们new一个page、fetch一个page后默认已经pin了，因此我们只需要注意unpin时机，以及dirty的设置
  • bucket lock是在page上存储的，为防止还没释放锁，page就被换出了，必须先解锁再unpin bucket page；table_lock则无所谓
  • gdb 调试作用不大。一般错误主要出在split和merge上，善用PrintDirectory和PrintBucket就行
  • 实验代码提供了检验directory完整性的函数VerifyIntegrity（依据directory的性质实现），可以在每次split或merge后调用一下，帮你发现一些问题

附上实验结果

lab2_result