Redis一共支持5种数据结构,hash是其中的一种,在hash扩容的时候采用的是渐进式rehash的方式。要想深入理解渐进式rehash,首先要了解以下Redis中hash的数据结构。
typedef struct dictEntry {
void *key; // 键
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; // 值
struct dictEntry *next; // 下一个节点
} dictEntry;
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
dictEntry **table; // 哈希表数组
unsigned long size; // 哈希表大小
unsigned long sizemask; // 掩码,计算索引值,size-1
unsigned long used; // 哈希表已有节点的数量
} dictht;
typedef struct dict {
dictType *type; // 类型特定函数
void *privdata; // 私有数据
dictht ht[2]; // 哈希表
// rehash索引
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
typedef struct dictType {
// 计算哈希值的函数
uint64_t (*hashFunction)(const void *key);
// 复制键的函数
void *(*keyDup)(void *privdata, const void *key);
// 复制值的函数
void *(*valDup)(void *privdata, const void *obj);
// 对比键的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 销毁键的函数
void (*keyDestructor)(void *privdata, void *key);
// 销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;
redis字典(hash表)当数据越来越多的时候,就会发生扩容,也就是rehash
java中的hashmap,当数据数量达到阈值的时候(0.75),就会发生rehash,hash表长度变为原来的二倍,将原hash表数据全部重新计算hash地址,重新分配位置,达到rehash目的
当向字典中添加一个元素时(假设此时 rehashidx = -1,也就是没有进行rehash),首先通过dict->type->hashFunction计算该元素的hash值,然后通过hash & dict->ht[x].sizemask计算哈希地址index。如果该元素对应的下标没有数据,则直接添加,否则采用链地址法添加到hash对应index元素的链表尾部。
字典中包含一个数据结构dictht的ht数组,一般情况下字典只是用ht[0]用来存储数据,ht[1]在rehash时使用。
随着操作的不断执行,哈希表中的元素会逐渐增加或者减少,为了让哈希表的负载因子维持在一个合理的范围内,程序需要对哈希表的大小进行相应的扩容和收缩。步骤如下:
为ht[1]哈希表分配空间。如果是扩容操作,ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂,如果是收缩操作,ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂
将保存在ht[0]中的所有键值对rehash到ht[1]:rehash指的是重新计算键的哈希值和索引值,然后将键值对放到ht[1]对应位置上
当ht[0]包含的所有键值对都迁移到ht[1]之后,释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备
在扩容和收缩的时候,如果哈希字典中有很多元素,一次性将这些键全部rehash到ht[1]的话,可能会导致服务器在一段时间内停止服务。所以,采用渐进式rehash的方式,详细步骤如下:
为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表
将rehashindex的值设置为0,表示rehash工作正式开始
在rehash期间,每次对字典执行增删改查操作是,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在rehashindex索引上的所有键值对rehash到ht[1],当rehash工作完成以后,rehashindex的值+1
随着字典操作的不断执行,最终会在某一时间段上ht[0]的所有键值对都会被rehash到ht[1],这时将rehashindex的值设置为-1,表示rehash操作结束
渐进式rehash采用的是一种分而治之的方式,将rehash的操作分摊在每一个的访问中,避免集中式rehash而带来的庞大计算量。
需要注意的是在渐进式rehash的过程,如果有增删改查操作时,如果index大于rehashindex,访问ht[0],否则访问ht[1]
redis中的hash表采用的是渐进式hash的方式: 1、redis字典(hash表)底层有两个数组,还有一个rehashidx用来控制rehash
2、初始默认hash长度为4,当元素个数与hash表长度一致时,就发生扩容,hash长度变为原来的二倍
3、redis中的hash则是执行的单步rehash的过程:
每次的增删改查,rehashidx+1,然后执行对应原hash表rehashidx索引位置的rehash
为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表
将rehashindex的值设置为0,表示rehash工作正式开始
在rehash期间,每次对字典执行增删改查操作是,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在rehashindex索引上的所有键值对rehash到ht[1],当rehash工作完成以后,rehashindex的值+1
随着字典操作的不断执行,最终会在某一时间段上ht[0]的所有键值对都会被rehash到ht[1],这时将rehashindex的值设置为-1,表示rehash操作结束
渐进式rehash采用的是一种分而治之的方式,将rehash的操作分摊在每一个的访问中,避免集中式rehash而带来的庞大计算量。
需要注意的是在渐进式rehash的过程,如果有增删改查操作时,如果index大于rehashindex,访问ht[0],否则访问ht[1]。
参考:
Redis中渐进式rehash:https://www.manongdao.com/article-2333291.html
redis中的hash扩容渐进式rehash过程https://blog.csdn.net/qq_38262266/article/details/107727116