redis之hash解析

Redis底层数据结构之hash

hash是日常开发过程中使用Redis的一个数据结构,其底层实现方式有两种,如下所示。一种是zipList,这种是当hash结构的V值较小的时候使用的编码方式。这个已经在上一篇文章中介绍过了。这篇文章主要讲解一下另外一种实现方式,字典dict,当hash结构的V值较大时采用的编码方式。

1|0  dict

这里又要开始鞭尸C语言了,字典dict作为一种常用的数据结构,C语言内部并不具备,因而Redis的开发人员自己设计和开发了Redis中的dict结构,其定义如下:

typedf struct dict{ dictType *type;//类型特定函数,包括一些自定义函数,这些函数使得key和 //value能够存储 void *private;//私有数据 dictht ht[2];//两张hash表 int rehashidx;//rehash索引,字典没有进行rehash时,此值为-1 unsigned long iterators; //正在迭代的迭代器数量 }dict;
  • typeprivate这两个属性是为了实现字典多态而设置的,当字典中存放着不同类型的值,对应的一些复制,比较函数也不一样,这两个属性配合起来可以实现多态的方法调用;
  • ht[2],两个hash
  • rehashidx,这是一个辅助变量,用于记录rehash过程的进度,以及是否正在进行rehash等信息,当此值为-1时,表示该dict此时没有rehash过程
  • iterators,记录此时dict有几个迭代器正在进行遍历过程

1|1  dictht

由上面可以看出,dict本质上是对哈希表dictht的一个简单封装,dictht的定义如下所示:

typedf struct dictht{ dictEntry **table;//存储数据的数组 二维 unsigned long size;//数组的大小 unsigned long sizemask;//哈希表的大小的掩码,用于计算索引值,总是等于 //size-1 unsigned long used;//// 哈希表中中元素个数 }dictht;

**table是一个dictEntry类型的数组,用于真正存储数据;size表示**table这个数组的大小;sizemask用于计算索引位置,且总是等于size-1used表示dictht中已有的节点数量,其示意图如下所示:
redis之hash解析

1|2  dictEntry

上面分析dictht时说到,真正存储数据的结构是dictEntry数组,其结构定义如下:

typedf struct dictEntry{ void *key;//键 union{ void val; unit64_t u64; int64_t s64; double d; }v;//值 struct dictEntry *next;//指向下一个节点的指针 }dictEntry;

其示意图如下所示:

redis之hash解析

最后整个dict的结构示意图如下所示:

上图是一个没有处于rehash状态下的字典dict,整个dict中有两个哈希表dictht,其中一个哈希表存储数据,另一个哈希表为空。

2|0  扩容与缩容

当哈希表中元素数量逐渐增加时,此时产生hash冲突的概率逐渐增大,且由于dict也是采用拉链法解决hash冲突的,随着hash冲突概率上升,链表会越来越长,这就会导致查找效率下降。相反,当元素不断减少时,元素占用dict的空间就越少,出于对内存的极致利用,此时就需要进行缩容操作。

既然说到扩容和缩容,熟悉Java集合的小伙伴是不是想到了什么。不错,那就是负载因子负载因子一般用于描述集合当前被填充的程度。在Redis的字典dict中,负责因子=哈希表中已保存节点数量/哈希表的大小,即:

load factor = ht[0].used / ht[0].size

Redis中,三条关于扩容和缩容的规则:

  • 没有执行BGSAVE和BGREWRITEAOF指令的情况下,哈希表的负载因子大于等于1时进行扩容;
  • 正在执行BGSAVE和BGREWRITEAOF指令的情况下,哈希表的负载因大于等于5时进行扩容;
  • 负载因子小于0.1时,Redis自动开始对哈希表进行收缩操作;

其中,扩容和缩容的数量大小也有一定的规则:

  • 扩容:扩容后的dictEntry数组数量为第一个大于等于ht[0].used * 22^n
  • 缩容:缩容后的dictEntry数组数量为第一个大于等于ht[0].used2^n

3|0  rehash

Java中的HashMap类似,当Redis中的dict进行扩容或者缩容,会发生reHash过程。JavaHashMaprehash过程如下:新建一个哈希表,一次性将当前所有节点进行rehash然后复制到新哈希表相应的位置上,之后释放掉原有的hash表,而持有新的表,这个过程是一个时间复杂度为O(n)的操作。而对于单线程的Redis而言很难承受这么高时间复杂度的操作,因而其rehash的过程有所不同,使用的是一种称之为渐进式rehash的方式,一点一点地进行搬迁。其过程如下:

  • 假设当前数据在dictht[0]中,那么首先为dictht[1]分配足够的空间,如果是扩容,则dictht[1]大小就按照扩容规则设置;如果是缩减,则dictht[1]大小就按照缩减规则进行设置;
  • 在字典dict中维护一个变量,rehashidx=0,表示rehash正式开始;
  • rehash进行期间,每次对字典执行添加、删除、查找或者更新操作时,程序除了执行指定的操作以外,还会顺带将dictht[0]哈希表在rehashidx索引上的所有键值对rehashdictht[1],当一次rehash工作完成之后,程序将rehashidx属性的值+1。同时在serverCron中调用rehash相关函数,在1ms的时间内,进行rehash处理,每次仅处理少量的转移任务(100个元素);
  • 随着字典操作的不断执行,最终在某个时间点上,dictht[0]的所有键值对都会被rehashdictht[1],这时程序将rehashidx属性的值设为-1,表示rehash操作已完成;

上述就是Redisdict渐进式rehash过程,但在这个过程会存在两个明显问题。第一,第三步说了,每次对字典执行增删改查时才会触发rehash过程,万一某一时间段并没有任何请求命令呢?此时应该怎么办?第二,在维护两个dictht的时候,此时哈希表如何正常对外提供服务?

Redis的设计人员在设计时就已经考虑到了这两个问题。对于第一个问题,Redis在有一个定时器,会定时去判断rehash是否完成,如果没有完成,则继续进行rehash。定时函数如下所示:

// 服务器定时任务 void databaseCron() { ... if (server.activerehashing) { for (j = 0; j < dbs_per_call; j++) { int work_done = incrementallyRehash(rehash_db);//rehash方法 if (work_done) { /* If the function did some work, stop here, we'll do * more at the next cron loop. */ break; } else { /* If this db didn't need rehash, we'll try the next one. */ rehash_db++; rehash_db %= server.dbnum; } } } }

对于第二个问题,对于添加操作,会将新的数据直接添加到dictht[1]上面,这样就可以保证dictht[0]上的数量只减少不增加。而对于删除、更改、查询操作,会直接在dictht[0]上进行,尤其是这三个操作,都会涉及到查询,当在dictht[0]上查询不到时,会接着去dictht[1]上查找,如果再找不到,则表明不存在该K-V值。

3|1  渐进式rehash的优缺点

优点:采用了分而治之的思想,将 rehash 操作分散到每一个对该哈希表的操作上以及定时函数上,避免了集中式rehash 带来的性能压力;

缺点:在 rehash 的时间内,需要保存两个 hash 表,对内存的占用稍大,而且如果在 redis 服务器本来内存满了的时候,突然进行 rehash 会造成大量的 key 被抛弃

4|0  思考题

为什么扩容的时候要考虑BIGSAVE的影响,而缩容时不需要?

  • BIGSAVE时,dict要是进行扩容,则此时就需要为dictht[1]分配内存,若是dictht[0]的数据量很大时,就会占用更多系统内存,造成内存页过多分离,所以为了避免系统耗费更多的开销去回收内存,此时最好不要进行扩容;
  • 缩容时,结合缩容的条件,此时负载因子<0.1,说明此时dict中数据很少,就算为dictht[1]分配内存,也消耗不了多少资源;

5|0  总结

redis之hash解析

 

原文连接:https://www.cnblogs.com/reecelin/p/13362104.html

上一篇:JAVA04类与对象之课后问题解决


下一篇:【牛客面经汇总】——阿里一面面经含答案