本文共 2697 字,大约阅读时间需要 8 分钟。
在讲rehash之前,我们先回顾一下字典的结构
1.字典dict.h/dict的源码
/* * 字典 */typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时,值为 -1 int 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 - 1 unsigned 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)
1.进行rehash的原因
随着操作的不断进行,哈希表保存的键值对会逐渐的增多或减少,为了让哈希表的负载因子维持在一个合理的范围内,当哈希表保存的键值对数量太多或太少,就对哈希表进行扩展或收缩。
2.rehash的步骤
(1)为字典的ht[1]哈希表分配空间
(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.扩展与收缩的条件
当以下条件满足任意一个时,程序就会对哈希表进行扩展操作
负载因子的计算
当负载因子的值小于0.1时,程序就会对哈希表进行收缩操作
1.渐进式rehash的原因
整个rehash过程并不是一步完成的,而是分多次、渐进式的完成。如果哈希表中,保存着数量巨大的键值对时
,若一次进行rehash
,很有可能会导致服务器宕机
。
2.渐进式rehash的步骤
为ht[1]分配空间
,让字典同时持有
ht[0]和ht[1]两个哈希表
索引计数器变量 rehashidx
,并将它的值设置为0
,表示rehash开始
每次对字典执行增删改查时
,将ht[0]的rehashidx索引上 的所有键值对
rehash到ht[1]
,将rehashidx值+1
。将rehashidx的值设置为-1
,表示rehash操作完成注:渐进式rehash的好处在于它采取分为而治的方式,将rehash键值对的计算 均摊到每个字典增删改查操作
,避免了集中式rehash的庞大计算量。
3.渐进式rehash图解
rehash的主要过程就是遍历ht[0]
,取得key
,然后将该key按ht[1]的 桶的大小重新rehash
,并在rehash完后将ht[0]指向ht[1]
,然后将ht[1]清空
。在这个过程中rehashidx非常重要,它表示上次rehash时在ht[0]的下标位置
。 可以看到,redis对dict的rehash是分批进行的
,这样不会阻塞请求
,设计的比较优雅。
但是在调用dictFind的时候
,可能需要对两张dict表做查询
。唯一的优化判断是,当key在ht[0]不存在 且 不在rehashing状态时
,可以速度返回空
。如果在rehashing状态,当在ht[0]没值的时候,还需要在ht[1]里查找。
dictAdd的时候
,如果状态是rehashing
,则把值插入到ht[1]
,否则ht[0]。
转载地址:http://ggbrb.baihongyu.com/