【手写数据库内核组件】0202分段哈希表Partial Hash Table，大并发场景下提 ...

0202 分段hash表

   ​专栏内容：
  

• postgresql利用入门基础
  
• 手写数据库toadb
  
• 并发编程
  

    个人主页：我的主页
管理社区：开源数据库
座右铭：天行健，君子以自强不息；阵势坤，君子以厚德载物.
  
  
一、概述

---

上节介绍了hashTable的原理与实现，在数据库中，往往是高并发，高性能的要求，对于hashTable的操作，必须加读写锁来掩护同等性。
当一个使命要插入一条key-value数据时，其它并发都需要等候，吞吐量明显不足。
本节就来分享一种分段式的hashTable，当hashKey 在不同分段时，可以进行并发的插入和删除操作，这对于高并发来讲，性能就会成倍的提升。
二、分段hash并发操作原理

---

在并发操作中，会对共享数据加锁掩护，了为提升读取数据的并发性能，一样平常会在读操作时加读锁，写操作时加写锁。
其中:

• 读读不冲突，可以同时多个使命进行读操作；
  
• 读写冲突，读时写的使命在等候，写时读的使命会等候；
  
• 写写冲突，同一把锁上，只能有一个写的使命运行，其它都会等候；
  

上面锁的冲突规则是对于一把锁来讲，当有多把锁时，各锁之间是相互不干涉的，也就是有几把锁，就可以同时运行几个写使命。
这就是分段hash的理论基础，每个分段会对应的独立的一把段级别的锁，只负责掩护此分段的hashtable操作，如许几个分段就可以同进行分段操作了。

• 分段的hashtable中有多个segment；
  
• 每个segment相当于一个独立的hashtable；
  
• 每个segment中有一把并发控制的锁segmentLock；
  
• 在segment内部用锁进行同步处理。
  

三、分段算法原理

---

对于分段的hashtable来讲，分段就非常关键，既要简朴高效，又需要算法稳定，同时还要尽可能的分散，看起来要求挺高的，下面我们来看怎样筹划分段算法。
在hashTable中，散列的主要依据是hashKey，是否继承在hashKey上做文章呢？
答案是肯定的，将hashKey的高bit位定义位segment的序号，低bit位定义位段内的bucket序号；

如图所示，对于64bits的hashKey, 可以将高字节定义位segment 序号，低7字节定义为bucket序号；
这里的划分算法可以是固定位的，也可以是不固定位的。
3.1 固定位的分段算法

固定划分，也就是segment序号对应的bit数目是固定的，比如一个字节，8bits。

• 此时最大可以表现256个segment，也就是不能凌驾最大值。
  
• 当配置的segment小于256时，可以采用 取余的算法，将一个节字的数字散列到此区间内；
  

固定划分，算法相对简朴，当划分的segment不能逐一对应时，需要一次映射盘算。
3.1 不固定位的分段算法

当segment数目，可以更新数据量进行优化配置时，比如数据量为2GB时，配置16个segment，而数据量为2TB时，有更多的数据会产生冲突，进一步通过增长segment进行分散，可以配置segment为256。
同时又期望划分后的bits可以直接是segment的下标，那么就要盘算不同划分下，需要占用多个少bit。
算法形貌如下：

• segment数目必须是2的幂次，如果配置的不是2的幂次时，取大于此值的2的幂次数；如许包管与bit数目逐一对应。
  
• 盘算2的幂次数，也就是 2n ,n的具体值；比如配置为1024个segment，那么它就是210；
  
• 幂次数n就是segment序号的bit数目，从最高到低位取；
  

下面来看代码的具体实现。
向上取2的幂次数
对于32位HashKey的算法如下：

1. HASHKEY getAlignNum(unsigned int num)
2. {
3.     HASHKEY mask = num - 1;
5.     mask |= mask >> 1;
6.     mask |= mask >> 2;
7.     mask |= mask >> 4;
8.     mask |= mask >> 8;
9.     mask |= mask >> 16;
11.     return mask+1;
12. }

复制代码

这是一个很奇妙的算法，通过将该数字二进制中的最高位的1，添补到全部低位的，再加1就酿成了最大的2的幂次数。
比如输入时9 对应的二进制是 1001,那么盘算步骤为：

• 减1； -> 1000
  
• mask |= mask >> 1; -> 1100
  
• mask |= mask >> 2; -> 1111
  
• 背面步骤没有变化；
  
• mask + 1 -> 10000
  

最后得到的是16；
整个操作的位置是hashKey的一半，比如hashKey是32位时，只需要16位的移动，如果hashKey为64bits时，需要最高32位的移动；
盘算bit位数
统计key中的最高位1的位置序号。

1. int getShiftNum(HASHKEY key)
2. {
3.     int shift = 0;
4.     while(key = key >> 1)
5.     {
6.         shift ++;
7.     }
8.     return shift;
9. }

复制代码

获取segment序号
先要盘算segment序号对应的掩码。

1. #define HASH_BITS       (sizeof(HASHKEY)*8)
2. HASHKEY partitionMask = getAlignNum(partNum);
3. HASHKEY partitionShift = HASH_BITS - getShiftNum(partitionMask)
5. partitionMask = ~(((HASHKEY)1 << partitionShift) - 1);

复制代码

• 先对输入的partNum向上取2的幂次数；
  
• 然后盘算对应的二进制位数 partitionShift ；
  
• 盘算segment对应bit为1的掩码，比如当segment占8bits时，掩码的十六进制为 0xF000000000000000
  

根据掩码可以从HashKey中获取到segment序号。

1. int GetPartitionIndex(HASHKEY key)
2. {
3.     int partition = key & partitionMask >> partitionShift;
5.     return partition;
6. }

复制代码

通过掩码与之后，得到高位为有效数字，低位为0的值，再向右移位得到正常值。
四、hash表操作

---

分段hash表的操作，与普通hash表操作会多出来获取segment序号，以及对segment加锁的步骤，具体对hash buckets的操作是一样的。
hash bucket序号获取

与segment序号获取一样，先通过掩码与，再根据bucket数目进行散列。

1. int GetBucketIndex(HASHKEY key, PHashTableInfo hashTableInfo)
2. {
3.     int bucket = key & (~partitionMask) % hashBucketSize;
5.     return bucket;
6. }

复制代码

• 没有单独记录bucket的掩码，将segment的掩码取反就可以得到；
  
• hashBucketSize是每个segment中buckets数组的巨细，取余后得到bucket的序号；
  

分段hash的定义

每个segment可以定义位一个结构体，固定命量时，可以直接定义为静态数组；如果数目可变，可以动态申请空间。
hash段数据结构定义

1. #define HASH_SEGMENT_SIZE (32)
2. typedef struct HashSegment
3. {
4.     // SPINLOCK        segLock;   
5.     HashElement    segBuckets[HASH_SEGMENT_SIZE];
6. }HashSegment;

复制代码

这里的锁可以根据本身需要的类型进行定义，这里暂时注释代替，背面并发分享时再分析。
分段hash表定义
将上面的分散的参数，都可以加到hashTableInfo的数据结构中来。

1. #define HASH_SEGMENT_NUM (32)
2. typedef struct HashTableInfo
3. {
4.     int partitionNum;
5.     HASHKEY partitionMask;
6.     int partitionShift;
8.     int bucketShift;
9.     int hashSegmentSize;
11.     HashSegment        segmentArray[HASH_SEGMENT_NUM];
12. }HashTableInfo;

复制代码

这里段的数目采用HASH_SEGMENT_NUM来定义，固定巨细，每次修改需要重新编译。
hash 查找

相比简朴hash表，分段hash表增长了分段的查找与加锁步骤，hash查找的步骤如下：

• 调用hash盘算函数，盘算hashKey；
  
• 获取分段序号；
  
• 加锁对应的分段；
  
• 获取bucket序号；
  
• 从对应的bucket链中查找；
  
• 如果找到返回；否则返回NULL；
  

其它插入和删除操作，也是多了2，3步骤，别的雷同。
五、总结

---

本文分享了分段hash表的实现与原理，在高并发场景下，为了hash操作的同等性，又同时提升hash表的吞吐量，采用分段hash，在没有hash段冲突时，可以同时进行N个并发操作，N即为段的数目。
对于分段的原量，分享了段数目可变的分段方法，通过盘算段数目的2的幂，来动态确定占用的二进制位的数目，天生对应的段掩码。
结尾

---

   非常感谢各人的支持，在欣赏的同时别忘了留下您宝贵的品评，如果觉得值得鼓励，请点赞，收藏，我会更加努力！
  作者邮箱：study@senllang.onaliyun.com
如有错误大概疏漏接待指出，互相学习。
注：未经同意，不得转载！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。