redis底层数据结构之dict 字典1-chhquan
//rehash函数，逐步对dict进行rehash//redis并没有一次性完成对dict的rehash，而是把整个rehash过程分成许多小的rehash操作去完成，
//每一次rehash都会处理至多一定数量的桶，由参数n指定。由于部分桶是空的，为防止rehash一直都访问
//到空的桶使rehash过程耗时过多，函数里面设定最多访问 n*10 个桶。
//redis为保持性能的稳定，会把一些有机会耗时较比多的操作，分成放多小的操作，rehash便是其中一个例子。
/* Performs N steps of incremental rehashing. Returns 1 if there are still
* keys to move from the old to the new hash table, otherwise 0 is returned.
*
* Note that a rehashing step consists in moving a bucket (that may have more
* than one key as we use chaining) from the old to the new hash table, however
* since part of the hash table may be composed of empty spaces, it is not
* guaranteed that this function will rehash even a single bucket, since it
* will visit at max N*10 empty buckets in total, otherwise the amount of
* work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
//访问ht中的桶，如果桶非空，把桶中的元素放进ht里。
while(n-- && d->ht.used != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht.used != 0 */
//从rehashidx开始，rehashidx便是用来记录rehash过程状态的变量
assert(d->ht.size > (unsigned long)d->rehashidx);
//找出一个非空桶，总的访问次数受到 empty_visits 的限制
while(d->ht.table == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1; //返回1表示rehash还没完成，需要进行进行
}
de = d->ht.table;
//移动桶中所有条目到ht中
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {
unsigned int h;
nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht.sizemask; //对桶号
de->next = d->ht.table;
d->ht.table = de;
d->ht.used--;
d->ht.used++;
de = nextde;
}
d->ht.table = NULL;
d->rehashidx++; //已经处理了rehashidx 号桶，下一个桶
}
//如果ht已经没有条目了，可以把ht切换到ht，并重置ht。
/* Check if we already rehashed the whole table... */
if (d->ht.used == 0) {
zfree(d->ht.table); //释放ht的桶空间
d->ht = d->ht;
_dictReset(&d->ht);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
页:
[1]