Redis 数据结构之字典(渐进式rehash)
Redis字典结构
哈希表结构
Redis字典使用的哈希表由dict.j/dictht结构定义,如下:
其中table属性是一个数组,数组元素为dict.h/dictEntry结构(key-value结构,类似于java中hashMap中的Node<K,V>结构)
????思考:结构中哈希表为ht[2],容量为2的dictht数组,为什么是2个?
ht[2]:一般情况下只会用到ht[0],ht[1]只会在ht[0]哈希表进行rehash的时候使用
rehashidx:记录rehash目前的进度,如果目前没有进行rehash,那么它的值为-1
未进行rehash结构如下
????思考:如何获取值?
程序先根据键值对的键计算出哈希值和索引值,然后再根据索引值,将包含新键值对的哈希表节点放到哈希表数组的指定索引上面
Redis计算键的hash值使用MurmurHash2算法(注:优点在于即使输入的键有规律,也能有很好的随机分布性,并且计算速度也很快,最新已到了MurmurHash3)
????思考:键冲突?如何解决?
当两个或以上数量的键被分配到哈希表数组的统一索引上,就产生了键冲突,
Redis解决键冲突 使用的是 链表地址法(注:还有很多其他方案)
渐进式rehash
????思考:当数据量过于庞大,链表长度会非常长,那么性能就会急剧下降(链表查询效率低),怎么办?
因此为了保证查询的性能,redis再一定条件下会对字典的哈希表进行rehash(此时就用到了ht[1]),Redis中进行rehash的时候使用的是 渐进式rehash(为了避免rehash对服务器性能造成影响,服务器并不是一次性将ht[0]里面的键值对全部迁移到ht[1]中,而是渐进式的将ht[0]里面的键值对慢慢rehash到ht[1]中),步骤如下
1 为字典的ht[1]哈希表分配空间,该哈希表的空间大小取决于要执行的操作以及ht[0]当前包含的数量(一般是2的n次幂)
2.在字典中位置一个索引器变量rehashidx,并将它值设置为0,表示rehash开始
3.将ht[0]中的所有键值对渐进式的rehash到ht[1]中:rehash指重新计算哈希值和索引值,并放置到ht[1]哈希表中
在rehash进行中,每次对字典进行添加、删除或者更新的时候,程序除了执行指定的操作以外,还会顺带将键值对迁移到ht[1]中,当rehash工作完成之后,程序将rehashidx属性增加一
4.随着不断的执行,最终全部迁移完成,将程序的rehashidx设置为-1,表示完成
5当ht[0]包含的所有键值对都迁移到ht[1]中(ht[0]为空表),释放ht[0],当ht[1]设置为ht[0],并再ht[1]新创建一个空白哈希表,为下一次rehash做准备
注:因此有的时候会发现Redis内存暴增,有可能就是Redis 进行rehash操作
????思考:什么情况下能进行rehash呢?
1.服务器目前没有执行BGSAVE(RDB持久化)命令或者BGREWRITEAOF(AOF重写)命令,并且哈希表的负载因子大于等于1
2.服务器目前正在执行BGSAVE或者BGREWRITEAOF命令,并且哈希表的负载因此大于等于5
负载因子 = 哈希表已保存的节点数量/哈希表的大小
????思考:为什么BGSAVE和BGREWRITEAOF命令执行与否,服务器要求负载因子不一样?
因为BGSAVE和BGREWRITEAOF执行的时候程序会创建子进程,而大多数操作系统都采用写时复制(copy-on-write)技术来优化紫禁城的使用效率,提高负载因子,是为了尽可能避免在子进程存在期间进行哈希表扩展操作,避免不必要的内存写入操作,最大限制上节约内存
????思考:在进行rehash的时候,要对数据进行操作怎么办?
渐进式rehash期间操作:
(1)添加操作:在渐进式rehash期间,新添加的键值对一律会保存到ht[1]里面,而ht[0]不进行任何添加操作,保证ht[0]只减不增。
(2)更新、删除、查找操作:先去ht[0]查找并进行相关操作操作,再去ht[1]进行查找并进行相关操作,然后返回