我在“redis存储结构”这篇文章中介绍了redis存储数据的方式——字典,redis的字典使用高效的hash table实现,这里详细介绍redis中哈希表的实现和工作原理
redis的哈希表结构
typedef struct dictht { //哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩码,用于计算索引值 unsigned long sizemask; //该哈希表已有的节点数量 unsigned long used; } dictht;
可以看到,redis的哈希表只是比我们常用的哈希表多了size、sizemask、used这三个额外字段,这三个字段是用来支持其它功能的,本文不详细介绍
redis的哈希表节点
typedef struct dictEntry { //键值对中的键 void *key; //键值对中的值 union { void *val; uint64_t u64; int64_t s64; double d; } v; //指向下一个哈希表节点,形成链表 struct dictEntry *next; } dictEntry;
1.next指针是用来解决哈希冲突的,没错,redis解决哈希冲突的方案是链地址法,也就是将哈希值相同的节点用链表组织起来,而redis使用rehash保证了这个链表的长度的不会太长,后面会详细介绍
2.key指向固定的对象string,这一点在“redis存储结构”文章中已经解释过
3.value使用union来实现保存不同类型值的功能,提供了较强的灵活性,且避免了全部使用指针的情况,节约了内存
哈希表的添加过程不再赘述,属于基础数据结构的范畴
解决哈希冲突
一、rehash
上文提到,redis使用链地址法解决哈希冲突,由于哈希表的数组长度在创建时就固定了,当节点数量过多时会造成链表长度过长,导致查询的时间复杂度降为O(N),导致性能降低的一个原因是数组长度,另一个是hash算法
redis的做法是,使用两个哈希表,一个为目前使用的,另一个为空,在当前使用的哈希表节点数等于数组长度时,即将发生哈希冲突,此时将另一个哈希表数组长度设置为当前的2倍,并将旧数组中的节点迁移到新数组中,这样一来,新的哈希表成为当前所使用的,并且数组的长度得到了增长,缓解了数组空间不足造成的哈希冲突
所以redis在使用哈希表时,实际上有两个哈希表,一个供当前使用,另一个供rehash使用
typedef struct dict { … //两个Hash表,交替使用,用于rehash操作 dictht ht[2]; … } dict;
当旧哈希表的数据全部迁移到新哈希表后,旧哈希表的空间会被释放
rehash的过程可以进行多次,基于两个哈希表的交替使用来实现
一次性rehash的缺陷
按照我们的想法,当旧哈希表的节点数等于数组长度时,考虑进行rehash
1.rehash是一次性进行的吗?
2.rehash的过程中如果有新的数据添加进来,该怎么处理?
3.rehash的过程中如果要进行数据查找,去哪找?
当旧哈希表中的节点数量比较庞大时,一次性rehash会造成redis阻塞较长时间,无法响应其他请求,这显然不是redis的风格
渐进式rehash
既然一次性rehash会造成性能下降,那么分批次进行不就好了,
redis的方案是在 rehash 进行期间,每次哈希表元素进行新增、删除、查找或者更新操作时,Redis 除了会执行对应的操作之外,还会顺序将「旧哈希表」中索引位置上的所有 key-value 迁移到「新哈希表」 上;
回到上面的问题
分次rehash的过程中会出现数据分布的情况,也就是一些数据在新哈希表中,另一些数据在旧哈希表中:
Q:
1.rehash的过程中如果有新的数据添加进来,该怎么处理?
2.rehash的过程中如果要进行数据查找,去哪找?
A:
1.如果有新的数据添加进来,将添加到新哈希表中,保证了旧哈希表的节点数只会减少,最终为空
2.先查找旧哈希表,如果没有,再查找新哈希表
rehash触发条件
在上文简单提到,当哈希节点数等于数组长度时,我们认为即将发生哈希冲突(实际上有可能已经发生),那么rehash的具体时机是怎么确定的?
触发 rehash 操作的条件,主要有两个:
- 当负载因子大于等于 1 ,并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令,也就是没有执行 RDB 快照或没有进行 AOF 重写的时候,就会进行 rehash 操作。
- 当负载因子大于等于 5 时,此时说明哈希冲突非常严重了,不管有没有有在执行 RDB 快照或 AOF 重写,都会强制进行 rehash 操作。
- 当负载因子小于0.1时,程序自动进行缩容操作
负载因子 = 哈希表中当前节点数 / 哈希表数组大小