rehash的作用
随着我们的redis操作不断执行,哈希表保存的键值对会逐渐地增多或者减少,当字典内数据过大时,会导致更多的键冲突,造成查询数据的成本增加。当数据减少时,已经分配的内存还在占用,会造成内存浪费。为了让哈希表的负载因子维持在一个合理的范围之内,程序需要对哈希表的大小进行相应的扩展或者收缩
rehash的原理
- rehash:首先我们看下字典、跟哈希表的结构定义
/*
* 字典
*/
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;
复制代码
// 哈希表
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
复制代码
通过看结构定义我们先大概了解到,判断一个字段是否正在rehash通过判断if rehashidx == -1
, rehash是在ht[1]
上从新分配内存,将ht[0]
的数据迁移到ht[1]
- 渐进式: rehash的过程不是一次完成的,而是在字典的读写操作,以及定时事件中每次完成一定量的迁移
扩容流程源码分析
因此是字典相关的操作,并且扩容一般存在于需要设置键值的时候,因此我们先直奔dict.c
文件看下是否有Add或者Set字符串内容的函数,通过搜索跟代码查看,我们发现有一个函数的逻辑还是挺像的
int dictAdd(dict *d, void *key, void *val)
{
// 尝试添加键到字典,并返回包含了这个键的新哈希节点
// T = O(N)
dictEntry *entry = dictAddRaw(d,key);
// todo ...
}
复制代码
这个函数会调用dictAddRaw(...)
方法给dict
分配内存继续查看dictAddRaw(...)
的代码
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
// 如果条件允许的话,进行单步 rehash
// T = O(1)
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or -1 if
* the element already exists. */
// 计算键在哈希表中的索引值
// 如果值为 -1 ,那么表示键已经存在
// T = O(N)
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
// T = O(1)
/* Allocate the memory and store the new entry */
// 如果字典正在 rehash ,那么将新键添加到 1 号哈希表
// 否则,将新键添加到 0 号哈希表
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// 为新节点分配空间
entry = zmalloc(sizeof(*entry));
// 将新节点插入到链表表头
entry->next = ht->table[index];
ht->table[index] = entry;
// 更新哈希表已使用节点数量
ht->used++;
/* Set the hash entry fields. */
// 设置新节点的键
// T = O(1)
dictSetKey(d, entry, key);
return entry;
}
复制代码
继续查看_dictKeyIndex
内的代码
static int _dictKeyIndex(dict *d, const void *key)
{
unsigned int h, idx, table;
dictEntry *he;
/* Expand the hash table if needed */
// 单步 rehash
// T = O(N)
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
/* Compute the key hash value */
// 计算 key 的哈希值
h = dictHashKey(d, key);
// T = O(1)
for (table = 0; table <= 1; table++) {
// 计算索引值
idx = h & d->ht[table].sizemask;
/* Search if this slot does not already contain the given key */
// 查找 key 是否存在
// T = O(1)
he = d->ht[table].table[idx];
while(he) {
if (dictCompareKeys(d, key, he->key))
return -1;
he = he->next;
}
// 如果运行到这里时,说明 0 号哈希表中所有节点都不包含 key
// 如果这时 rehahs 正在进行,那么继续对 1 号哈希表进行 rehash
if (!dictIsRehashing(d)) break;
}
// 返回索引值
return idx;
}
复制代码
通过查看上述代码,我们可以发现几处关键点,字典内索引值的计算时通过
// 计算 key 的哈希值
h = dictHashKey(d, key);
idx = h & d->ht[table].sizemask;
复制代码
算出来的,同时我们也能看到,当存在键冲突时,查找键的成本
he = d->ht[table].table[idx];
while(he) {
if (dictCompareKeys(d, key, he->key))
return -1;
he = he->next;
}
复制代码
最关键的是_dictExpandIfNeeded
通过函数名我们就觉得这个跟扩容有关
static int _dictExpandIfNeeded(dict *d)
{
/* Incremental rehashing already in progress. Return. */
// 渐进式 rehash 已经在进行了,直接返回
if (dictIsRehashing(d)) return DICT_OK;
/* If the hash table is empty expand it to the initial size. */
// 如果字典(的 0 号哈希表)为空,那么创建并返回初始化大小的 0 号哈希表
// T = O(1)
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
/* If we reached the 1:1 ratio, and we are allowed to resize the hash
* table (global setting) or we should avoid it but the ratio between
* elements/buckets is over the "safe" threshold, we resize doubling
* the number of buckets. */
// 一下两个条件之一为真时,对字典进行扩展
// 1)字典已使用节点数和字典大小之间的比率接近 1:1
// 并且 dict_can_resize 为真
// 2)已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
// 新哈希表的大小至少是目前已使用节点数的两倍
// T = O(N)
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
复制代码
通过上述代码可以看到,最根本的内存分配操作是在_dictExpandIfNeeded(...)
函数内执行的。该函数会判断当哈希表上已使用键值数比分配内存大dict_force_resize_ratio
(代表常量5)倍时,会重新分配内存,内存大小时原来已使用数的2倍
总结
- 整个源码流程看完,我们发现在执行
dictAdd(...)
向字典内增加键值时,会调用_dictExpandIfNeeded(...)
查看ht[0].used/ht[0].size > 5
是否为true
,如果是则重新分配内存,大小为ht[0].used * 2
- 在查看
dictAddRaw(...)
函数代码时,有一处命令
// 如果条件允许的话,进行单步 rehash
// T = O(1)
if (dictIsRehashing(d)) _dictRehashStep(d);
复制代码
_dictRehashStep
的作用是,执行一个键值从h[0]
到h[1]
的迁移,在dict.c
内搜索该函数,会发现跟dict相关的读写操作都会调用该函数,这也验证rehahs的过程不是一步完成的,是渐进式的
收缩流程源码分析
字典内存的收缩主要是在定时事件内,定时检查,判断,相关代码如下
void databasesCron(void) {
// todo ...
// 在没有 BGSAVE 或者 BGREWRITEAOF 执行时,对哈希表进行 rehash
if (server.rdb_child_pid == -1 && server.aof_child_pid == -1) {
/* We use global counters so if we stop the computation at a given
* DB we'll be able to start from the successive in the next
* cron loop iteration. */
static unsigned int resize_db = 0;
static unsigned int rehash_db = 0;
unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
unsigned int j;
/* Don't test more DBs than we have. */
// 设定要测试的数据库数量
if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;
/* Resize */
// 调整字典的大小
for (j = 0; j < dbs_per_call; j++) {
tryResizeHashTables(resize_db % server.dbnum);
resize_db++;
}
/* Rehash */
// 对字典进行渐进式 rehash
if (server.activerehashing) {
for (j = 0; j < dbs_per_call; j++) {
int work_done = incrementallyRehash(rehash_db % server.dbnum);
rehash_db++;
if (work_done) {
/* If the function did some work, stop here, we'll do
* more at the next cron loop. */
break;
}
}
}
}
}
复制代码
上述代码除了循环和判断外,有两个比较特别的函数
tryResizHashTables
,相关源码
void tryResizeHashTables(int dbid) {
if (htNeedsResize(server.db[dbid].dict))
dictResize(server.db[dbid].dict);
if (htNeedsResize(server.db[dbid].expires))
dictResize(server.db[dbid].expires);
}
//htNeedsResize
int htNeedsResize(dict *dict) {
long long size, used;
size = dictSlots(dict);
used = dictSize(dict);
return (size && used && size > DICT_HT_INITIAL_SIZE &&
(used*100/size < REDIS_HT_MINFILL));
}
复制代码
通过分析源码,我们可以看到该函数会首先调用htNeedsResize
,判断used* 100 / size < REDIS_HT_MINFILL
如果是true则会调用dictResize
重新分配内存
incrementallyRehash
,相关源码
int incrementallyRehash(int dbid) {
/* Keys dictionary */
if (dictIsRehashing(server.db[dbid].dict)) {
dictRehashMilliseconds(server.db[dbid].dict,1);
return 1; /* already used our millisecond for this loop... */
}
/* Expires */
if (dictIsRehashing(server.db[dbid].expires)) {
dictRehashMilliseconds(server.db[dbid].expires,1);
return 1; /* already used our millisecond for this loop... */
}
return 0;
}
//dictRehashMillisecnods
/* 在给定毫秒数内,以 100 步为单位,对字典进行 rehash 。
*
* T = O(N)
*/
int dictRehashMilliseconds(dict *d, int ms) {
// 记录开始时间
long long start = timeInMilliseconds();
int rehashes = 0;
while(dictRehash(d,100)) {
rehashes += 100;
// 如果时间已过,跳出
if (timeInMilliseconds()-start > ms) break;
}
return rehashes;
}
复制代码
通过分析,可以看出该函数的作用,是对正在rehash的字典,每次执行1毫秒,每次循环100次的哈希表数据迁移。
总结
- 哈希表的收缩主要是在定时事件内执行
- 当已使用的键值占比不到分配内存的0.1时,就进行内存收缩
- 除了在上面扩容中说到的在进行读写时会进行数据迁移,在定时件事内也会进行数据迁移。同时可以避免,长时间没有读写操作,数据一直无法迁移的问题
近期评论