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]进行查找并进行相关操作,然后返回