本文主要是介绍【Redis深入】字典rehash图解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
引入
在讲rehash之前,我们先回顾一下字典的结构
1.字典dict.h/dict的源码
/** 字典*/
typedef struct dict {// 类型特定函数dictType *type;// 私有数据void *privdata;// 哈希表dictht ht[2];// rehash 索引// 当 rehash 不在进行时,值为 -1int rehashidx; /* rehashing not in progress if rehashidx == -1 */// 目前正在运行的安全迭代器的数量int iterators; /* number of iterators currently running */} dict;
2.哈希表dict.h/dictht的源码
/* This is our hash table structure. Every dictionary has two of this as we* implement incremental rehashing, for the old to the new table. */
/** 哈希表** 每个字典都使用两个哈希表,从而实现渐进式 rehash 。*/
typedef struct dictht {// 哈希表数组dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小掩码,用于计算索引值// 总是等于 size - 1unsigned long sizemask;// 该哈希表已有节点的数量unsigned long used;} dictht;
3.哈希表节点dict.h/dictEntry的源码
/** 哈希表节点*/
typedef struct dictEntry {// 键void *key;// 值union {void *val;uint64_t u64;int64_t s64;} v;// 指向下个哈希表节点,形成链表struct dictEntry *next;} dictEntry;
4.一个普通的字典结构(没有进行rehash)
rehash过程图解
1.进行rehash的原因
随着操作的不断进行,哈希表保存的键值对会逐渐的增多或减少,为了让哈希表的负载因子维持在一个合理的范围内,当哈希表保存的键值对数量太多或太少,就对哈希表进行扩展或收缩。
2.rehash的步骤
(1)为字典的ht[1]哈希表分配空间
- 若是扩展操作,那么ht[1]的大小为>=ht[0].used*2的2^n
- 若是收缩操作,那么ht[1]的大小为>=ht[0].used的2^n
(2)将保存在ht[0]中的所有键值对rehash到ht[1]中,rehash指重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的指定位置上。
(3)当ht[0]的所有键值对都迁移到了ht[1]之后(ht[0]变为空表),释放ht[0],将ht[1]设置为ht[0],新建空白的哈希表ht[1],以备下次rehash使用。
3.rehash图解
(1)执行rehash之前的字典
(2)ht[0].used的值为4,而4*2=8,大于等于它的2^n是8,所以将ht[1]的大小设置为8
(3)将ht[0]的四个键值对都rehash到ht[1]中,这时ht[0]为null
(4)释放ht[0],并将ht[1]设置为ht[0],然后为ht[1]分配一个空白的哈希表,哈希表大小由4扩容为8
4.扩展与收缩的条件
-
当以下条件满足任意一个时,程序就会对哈希表进行扩展操作
- 服务器目前没有执行bgsave或bgrewriteaof命令,并且哈希表的负载因子>=1
- 服务器目前正在执行bgsave或bgrewriteaof命令,并且哈希表的负载因子>=5
-
负载因子的计算
load_factor=ht[0].used/ht[0].size -
当负载因子的值小于0.1时,程序就会对哈希表进行收缩操作
渐进式rehash
1.渐进式rehash的原因
整个rehash过程并不是一步完成的,而是分多次、渐进式的完成。如果哈希表中保存着数量巨大的键值对时,若一次进行rehash,很有可能会导致服务器宕机。
2.渐进式rehash的步骤
- 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表
- 维持索引计数器变量rehashidx,并将它的值设置为0,表示rehash开始
- 每次对字典执行增删改查时,将ht[0]的rehashidx索引上的所有键值对rehash到ht[1],将rehashidx值+1。
- 当ht[0]的所有键值对都被rehash到ht[1]中,程序将rehashidx的值设置为-1,表示rehash操作完成
注:渐进式rehash的好处在于它采取分为而治的方式,将rehash键值对的计算均摊到每个字典增删改查操作,避免了集中式rehash的庞大计算量。
3.渐进式rehash图解
- 渐进式rehash之前的字典
- rehash索引0上的键值对
- rehash索引1上的键值对
- rehash索引2上的键值对
- rehash索引3上的键值对
- 渐进式rehash完成
本人才疏学浅,若有错,请指出,谢谢!
如果你有更好的建议,可以留言我们一起讨论,共同进步!
衷心的感谢您能耐心的读完本篇博文!
参考书籍:《Redis设计与实现(第二版)》—黄健宏
文章转自: https://blog.csdn.net/baiye_xing/article/details/76088425
这篇关于【Redis深入】字典rehash图解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!