【手写数据库内核组件】0202分段哈希表Partial Hash Table，大并发场景下提
0202 分段hash表专栏内容：
[*]postgresql利用入门基础
[*]手写数据库toadb
[*]并发编程
个人主页：我的主页
管理社区：开源数据库
座右铭：天行健，君子以自强不息；阵势坤，君子以厚德载物.
一、概述
上节介绍了hashTable的原理与实现，在数据库中，往往是高并发，高性能的要求，对于hashTable的操作，必须加读写锁来掩护同等性。
当一个使命要插入一条key-value数据时，其它并发都需要等候，吞吐量明显不足。
本节就来分享一种分段式的hashTable，当hashKey 在不同分段时，可以进行并发的插入和删除操作，这对于高并发来讲，性能就会成倍的提升。
二、分段hash并发操作原理
在并发操作中，会对共享数据加锁掩护，了为提升读取数据的并发性能，一样平常会在读操作时加读锁，写操作时加写锁。
其中:
[*]读读不冲突，可以同时多个使命进行读操作；
[*]读写冲突，读时写的使命在等候，写时读的使命会等候；
[*]写写冲突，同一把锁上，只能有一个写的使命运行，其它都会等候；
上面锁的冲突规则是对于一把锁来讲，当有多把锁时，各锁之间是相互不干涉的，也就是有几把锁，就可以同时运行几个写使命。
这就是分段hash的理论基础，每个分段会对应的独立的一把段级别的锁，只负责掩护此分段的hashtable操作，如许几个分段就可以同进行分段操作了。
https://i-blog.csdnimg.cn/direct/b1beed4ccfa441d1b93eaa6b99c60a42.png#pic_center
[*]分段的hashtable中有多个segment；
[*]每个segment相当于一个独立的hashtable；
[*]每个segment中有一把并发控制的锁segmentLock；
[*]在segment内部用锁进行同步处理。
三、分段算法原理
对于分段的hashtable来讲，分段就非常关键，既要简朴高效，又需要算法稳定，同时还要尽可能的分散，看起来要求挺高的，下面我们来看怎样筹划分段算法。
在hashTable中，散列的主要依据是hashKey，是否继承在hashKey上做文章呢？
答案是肯定的，将hashKey的高bit位定义位segment的序号，低bit位定义位段内的bucket序号；
https://i-blog.csdnimg.cn/direct/6d0bf1c8659c4032a8fda03711201288.png#pic_center
如图所示，对于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的算法如下：
HASHKEY getAlignNum(unsigned int num)
{
HASHKEY mask = num - 1;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;
return mask+1;
}
这是一个很奇妙的算法，通过将该数字二进制中的最高位的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的位置序号。
int getShiftNum(HASHKEY key)
{
int shift = 0;
while(key = key >> 1)
{
shift ++;
}
return shift;
}
获取segment序号
先要盘算segment序号对应的掩码。
#define HASH_BITS (sizeof(HASHKEY)*8)
HASHKEY partitionMask = getAlignNum(partNum);
HASHKEY partitionShift = HASH_BITS - getShiftNum(partitionMask)
partitionMask = ~(((HASHKEY)1 << partitionShift) - 1);
[*]先对输入的partNum向上取2的幂次数；
[*]然后盘算对应的二进制位数 partitionShift ；
[*]盘算segment对应bit为1的掩码，比如当segment占8bits时，掩码的十六进制为 0xF000000000000000
根据掩码可以从HashKey中获取到segment序号。
int GetPartitionIndex(HASHKEY key)
{
int partition = key & partitionMask >> partitionShift;
return partition;
}
通过掩码与之后，得到高位为有效数字，低位为0的值，再向右移位得到正常值。
四、hash表操作
分段hash表的操作，与普通hash表操作会多出来获取segment序号，以及对segment加锁的步骤，具体对hash buckets的操作是一样的。
hash bucket序号获取
与segment序号获取一样，先通过掩码与，再根据bucket数目进行散列。
int GetBucketIndex(HASHKEY key, PHashTableInfo hashTableInfo)
{
int bucket = key & (~partitionMask) % hashBucketSize;
return bucket;
}
[*]没有单独记录bucket的掩码，将segment的掩码取反就可以得到；
[*]hashBucketSize是每个segment中buckets数组的巨细，取余后得到bucket的序号；
分段hash的定义
每个segment可以定义位一个结构体，固定命量时，可以直接定义为静态数组；如果数目可变，可以动态申请空间。
hash段数据结构定义
#define HASH_SEGMENT_SIZE (32)
typedef struct HashSegment
{
// SPINLOCK segLock;
HashElement segBuckets;
}HashSegment;
这里的锁可以根据本身需要的类型进行定义，这里暂时注释代替，背面并发分享时再分析。
分段hash表定义
将上面的分散的参数，都可以加到hashTableInfo的数据结构中来。
#define HASH_SEGMENT_NUM (32)
typedef struct HashTableInfo
{
int partitionNum;
HASHKEY partitionMask;
int partitionShift;
int bucketShift;
int hashSegmentSize;
HashSegment segmentArray;
}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企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]