HashTable

我们之前讲的Redis对象Hash这些是一种数据类型而今天这个学习笔记hashtable是这些类型的具体底层实现。注意要辨别。那么第一个问题什么是HASHTABLE?HASHTABLE可以想象成目录要翻看什么内容直接通过目录能找到页数翻过去看。如果没有目录我们需要一页一页往后翻效率很低。在计算机世界里HASHTABLE就扮演着这样一个快速索引的角色通过HASHTABLE我们可以只用O(1)时间复杂度就能快速找到key对应的value。接着我们看第二个问题即HASHTABLE的结构/* This is our hash table structure. */ typedef struct dictt { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictt;最外层是一个封装的dictht结构具体的字段含义如下:table:指向实际hash存储。存储可以看做一个数组所以是*table的表示石C语言中*table可以表示一个数组。size:哈希表大小。实际就是dictEntry有多少元素空间。size是桶数不包含链表上的节点sizemask: 哈希表大小的掩码表示总是等于size-1。这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面规则Indexhashsizemask。used:表示已有节点数量。通过这个字段可以很方便地查询到目前HASHTABLE元素总量。由上述的定义我们可以知道used的数量可能大于size进入第三个知识点Hash表渐进式扩容:渐进式扩容顾名思义就是一点一点慢慢扩容而不是一股脑直接做完那具体流程是怎样的呢?其实为了实现渐进式扩容Redis中没有直接把dictht暴露给上层而是再封装了一层:可以看到dict结构里面包含了两个dictht结构也就是2个HASHTABLE结构。dictEntry是链表结构也就是用拉链法解决Hash冲突用的是头插法。实际上平常使用的就是一个HASHTABLE在触发扩容之后就会两个HASHTABLE同时使用详细过程是这样的:当向字典添加元素时发现需要扩容就会进行Rehash。Rehash的流程大概分成三步:首先为新Hash表ht[1]分配空间。新表大小为第一个大于等于原表2倍used的2次方幂。举个例子原表如果used5002倍就是1000那第一个大于1000的2次方幂则为1024。此时字典同时持有ht[0]和ht[1]两个哈希表。字典的偏移索引rehashidx从静默状态-1设置为0表示Rehash工作正式开始。我们来观察一下rehashidx在途中状态的变化:初始状态在开始 rehash 之前rehashindex被设置为 -1表示没有进行 rehash。当需要开始 rehash 时rehashindex被设置为 0第一个桶索引为0开始移。迁移过程每次执行增、删、查、改等操作时Redis 会顺带迁移rehashindex所指向的桶中的所有键值对到新的哈希表。迁移完一个桶后rehashindex会加1指向下一个桶。这样每次操作只迁移一个桶避免了集中迁移导致的长时间阻塞。完成迁移当rehashindex递增到超过旧哈希表的大小size时表示所有桶都已经迁移完毕。此时rehash 完成旧哈希表被释放新哈希表替换旧哈希表rehashindex被重置为 -1。关于空桶的处理在迁移过程中如果当前rehashindex指向的桶是空的那么 Redis 会跳过这个桶并将rehashindex加1继续检查下一个桶。这样可以确保迁移过程不会因为遇到空桶而停滞直到所有非空桶都被迁移。随着字典操作的不断执行最后会在某个时间点ht[0]的所有键值对被rehash至ht[1],此时h[1]会替代h[0]然后rehashidx被设置为-1代表扩容结束停止时机触发条件rehashidx值ht[0].used正常完成所有键已迁移 size 0提前完成中途used0 size 0空桶限制遇到太多空桶 size 0遍历完成达到size边界 size应该0总结一下渐进式扩容的核心就是操作时顺带迁移。讲了扩容是怎么实现的肯定大家会想着我们啥时候会进行扩容呢?这就是我们最后一个学习的问题扩容与缩容时机是什么时候?Redis提出了一个负载因子的概念负载因子表示目前RedisHASHTABLE的负载情况是游刃有余还是不堪重负了。我们设负载因子为k那么kht[0].used/ht[0].size也就是使用空间和总空间大小的比例。Redis会根据负载因子的情况来扩容:负载因子大于等于1说明此时空间已经非常紧张。新数据是在链表上叠加的越来越多的数据其实无法在0(1)时间复杂度找到还需要遍历一次链表如果此时服务器没有执行BGSAVE或BGREWRITEAOF这两个命令就会发生扩容。负载因子大于5这时候说明HASHTABLE真的已经不堪重负了此时即使是有复制命令在进行也要进行Rehash扩容。Redis的扩容策略基于负载因子和写时复制机制的权衡当负载因子≥1时哈希表性能开始下降本应触发扩容但如果此时正在执行BGSAVE或BGREWRITEAOF会fork子进程并使用写时复制技术扩容将导致内存页被大量修改使内存占用量短时间内近翻倍增长因此Redis选择暂不扩容以优先保证内存稳定而当负载因子≥5时哈希表性能已严重恶化即便有子进程运行Redis也会强制扩容因为此时性能损失已远超内存增长的成本。扩容是数据太多存不下了那如果太富裕呢比如原来可能数据较多发生了扩容但后面数据不再需要被删除了此时多余的空间就是一种浪费。缩容过程其实和扩容是相似的也是渐进式缩容这里不赘述。同样的Redis还是用负载因子来控制什么时候缩容:当负载因子小于0.1即负载率小于10%此时进行缩容新表大小为第一个大于等于原表used的2次方幂。当然如果有BGSAVE或BGREWRITEAOF这两个复制命令缩容也会受影响不会进行。声明: 本篇笔记仅为学习时整理的笔记以及疑问解决点无其他任何商业用途如有侵权联系即删。