Redis底层数据结构P4—hash
发布网友
发布时间：2024-10-03 14:43
共1个回答
热心网友
时间：2024-12-15 08:55
  hash在Redis中的底层实现有两种，一种是zipList，这种是当hash结构的V值较小的时候使用的编码方式。这个已经在Redis底层数据结构P3—list这篇文章中介绍过了。这篇文章主要讲解一下另外一种实现方式，字典dict，这是当hash结构的V值较大时采用的编码方式。
dict  这里又要开始鞭尸C语言了，字典dict作为一种常用的数据结构，C语言内部并不具备，因而Redis的开发人员自己设计和开发了Redis中的dict结构，其定义如下：
typedf?struct?dict{????//?类型特定函数，包括一些自定义函数????//?这些函数使得key和value能够存储????dictType?*type;????//?私有数据????void?*private;????//?两张hash表?????dictht?ht[2];????//?rehash索引，字典没有进行rehash时，此值为-1????int?rehashidx;????//?正在迭代的迭代器数量????unsigned?long?iterators;?}dict;  各属性含义如下：
type和private这两个属性是为了实现字典多态而设置的，当字典中存放着不同类型的值，对应的一些复制函数以及比较函数不一样，这两个属性配合起来可以实现多态的方法调用；
ht[2]，两个hash表
rehashidx，这是一个辅助变量，用于记录rehash过程的进度，以及是否正在进行rehash等信息，当rehashidx=-1时，表示该dict此时没有进行rehash过程
iterators，记录此时dict有几个迭代器正在进行遍历过程
dictht  由上面可以看出，dict本质上是对哈希表dictht的一个简单封装，dictht的定义如下所示：
typedf?struct?dictht{????//?存储数据的数组?二维????dictEntry?**table;????//?数组的大小????unsigned?long?size;????//?哈希表的大小的掩码，用于计算索引值????//?总是等于?size-1????unsigned?long?sizemask;????//?哈希表中中元素个数??????????????????????????unsigned?long?used;}dictht;  各属性含义如下：
table是一个dictEntry类型的数组，用于真正存储数据
size表示table这个数组的大小
sizemask用于计算索引位置，且总是等于size-1
used表示dictht中已有的节点数量
  dictht的示意图如下所示：
dictEntry  上面说到了，dictht中真正存储数据的结构是dictEntry数组，dictEntry的结构定义如下：
typedf?struct?dictEntry{????//?键????void?*key;????//?值????union{????????void?val;????????unit64_t?u64;????????int64_t?s64;????????double?d;????}v;????//?指向下一个节点的指针????struct?dictEntry?*next；}dictEntry;  其示意图如下所示：
  最后整个dict的结构示意图引用《Redis 设计与实现》中的图，如下所示：
  上面是一个没有处于rehash状态下的字典dict，整个dict中有两个哈希表dictht，其中一个哈希表存储数据，另一个哈希表则为空，用于rehash状态下的数据存储。
扩容与缩容  当哈希表中元素数量逐渐增加时，此时产生hash冲突的概率逐渐增大，由于dict采用拉链法解决hash冲突的，因此随着元素的增多，链表会越来越长，这就会导致查找效率下降。相反，当元素不断减少时，元素占用dict的空间就越少，出于对内存的极致利用，此时就需要进行缩容操作。
  既然说到扩容和缩容，熟悉Java集合的小伙伴是不是想到了什么。不错，那就是负载因子。负载因子一般用于描述集合当前被填充的程度。在Redis的字典dict中，负责因子=哈希表中已保存节点数量/哈希表的大小，即：
load?factor?=?ht[0].used?/?ht[0].size  Redis中，三条关于扩容和缩容的规则：
没有执行BGSAVE和BGREWRITEAOF指令的情况下，负载因子大于等于1时进行扩容；
正在执行BGSAVE和BGREWRITEAOF指令的情况下，哈希表的负载因大于等于5时进行扩容；
负载因子小于0.1时，Redis自动开始对哈希表进行缩容操作；
  其中，扩容和缩容的数量大小也有一定的规则：
扩容：*扩容后的dictEntry数组数量为之前dictEntry数组的2`ht[0].used2的2^n**，简单点就是新的dictEntry`数组长度是原先的2倍
缩容：缩容后的dictEntry数组数量为第一个大于等于ht[0].used的2^n，简单点就是缩容后的dictEntry数组长度还是跟原先的dictEntry数组长度一致，只是需要移动元素，使得元素在数组中的位置发生改变；
rehash  与Java中的HashMap类似，当Redis中的dict进行扩容或者缩容，会发生reHash过程。   Java中HashMap的rehash过程简单点来说，就是新建一个哈希表，一次性将当前所有节点进行rehash然后复制到新哈希表相应的位置上，之后释放掉原有的hash表，持有新表的引用，这个过程是一个时间复杂度为O(n)的操作。   对于单线程的Redis而言，其很难承受O(n)时间复杂度的rehash操作，因而其rehash的过程有所不同，使用的是一种称之为渐进式rehash的方式，一点一点地进行搬迁，其过程如下：
假设当前数据在dictht[0]中，那么首先为dictht[1]分配足够的空间。如果是扩容，则dictht[1]大小就按照扩容规则设置；如果是缩减，则dictht[1]大小就按照缩减规则进行设置
在字典dict中维护一个变量，rehashidx=0，表示rehash正式开始
rehash进行期间，外界调用Redis执行增删改查操作时，程序除了执行指定的操作以外，还会顺带将dictht[0]哈希表在rehashidx索引上的键值对重新rehash到dictht[1]，每次仅处理少量的转移任务(100个元素)
当一次rehash工作完成之后，程序将rehashidx属性的值+1
随着rehash的不断执行，最终在某个时间点上，dictht[0]的所有键值对都会被rehash至dictht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成
  上述就是Redis中dict的渐进式rehash过程，但在这个过程会存在两个明显问题。
第一，每次对字典执行增删改查时才会触发rehash过程，万一某一时间段并没有任何请求命令呢？此时应该怎么办？
第二，在维护两个dictht的时候，此时哈希表如何正常对外提供服务？
  Redis的设计者在设计时就已经考虑到了这两个问题。对于第一个问题，Redis在有一个定时器，会定时去判断rehash是否完成，如果没有完成，则继续进行rehash。定时函数如下所示：
//?服务器定时任务void?databaseCron()?{?????????...?????????if?(server.activerehashing)?{????????????for?(j?=?0;?j?<?dbs_per_call;?j++)?{?????????????????//?rehash方法?????????????????int?work_done?=?incrementallyRehash(rehash_db);?????????????????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]上查找，如果再找不到，则表明不存在该键值对。
渐进式rehash的优缺点优点：采用了分而治之的思想，将 rehash操作分散到每一个对该哈希表进行的操作上以及定时函数上，避免了集中rehash 带来的性能压力
缺点：在rehash的过程中，需要保存两个hash表，对内存的占用稍大，而且如果在redis服务器本来内存满了的时候，突然进行rehash可能会造成大量的key被抛弃；
BIGSAVE操作对扩容的影响  为什么扩容的时候要考虑BIGSAVE的影响，而缩容时不需要？
BIGSAVE时，dict要是进行扩容，则此时就需要为dictht[1]分配内存，若是dictht[0]的数据量很大时，就会占用更多系统内存，造成内存页过多从而分离，所以为了避免系统耗费更多的开销去回收内存，此时最好不要进行扩容
缩容时，结合缩容的条件，此时负载因子<0.1，说明此时dict中数据很少，就算为dictht[1]分配内存，也消耗不了多少资源
总结ReferenceRedis深度历险：核心原理和应用实践
Redis系列(六)底层数据结构之字典
redis哈希表的rehash分析
图解redis五种数据结构底层实现
