redis-哈希表自动扩容
@(架构说)[redis]
为了回答上次遗留问题 哈希表如何扩容问题? 重点内容： 1 注释代码：最新版本 https://github.com/aleafboat/redis.git 2 扩容函数
结构定义
typedef struct dict
{
dictType *type;
void *privdata;
dictht ht[2];//哈希表
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;
typedef struct dictht
{ //字典hash table
dictEntry **table;
//可以看做字典数组，俗称桶bucket
unsigned long size;
//指针数组的大小，即桶的层数
unsigned long sizemask;
unsigned long used;
//字典中当前的节点数目
} dictht;
typedef struct dictEntry {
void *key;
void *val;
struct dictEntry *next;
} dictEntry;扩容过程
何时需要扩容 --触发的条件很多
每次增加dictEntry时，都会调用一次_dictExpandIfNeeded()这个函数。
1.如果dict正在扩容，则返回正常DICT_OK
2.如果dict刚刚初始化，也就是两个dictht都为NULL，则调用dictExpand()函数初始化。dictExpand()同样会做一次判断两个dictht都为NULL，然后直接赋给ht[0]。
3.如果可以扩容(dict_can_resize=1)，那么只要现在表中键总数大于表的长度就开始扩容。如果不能扩容(也就是dict_can_resize=0)， 但是如果表中键总数与表的长度的比值大于某一个阀值(由dict_force_resize_ratio静态变量决定)，那么就强制扩容。
扩容是怎么进行的？
之前所说的每个dict中都有两个哈希表结构dictht *ht[2]。 当开始扩容时，把第一个ht作为原始表， 第二个作为扩容后的表
dict中rehashidx决定了目前扩容的进度。
扩容过程什么时候执行？ 当决定开始扩容后
int dictRehash(dict d, int n); int dictRehashMilliseconds(dict d, int ms);
第一个函数中n决定每次rehash(也就是转移dictEntry)的次数， 第二个函数决定调用rehash函数的时间。 每次执行查找，增加，删除操作都会执行一次dictRehash(1)(如果正在扩容)，使得整个漫长的扩容过程隐含在每一次简单的操作中。
函数：可以跳过不看
int dictRehashMilliseconds(dict *d, int ms) {
long long start = timeInMilliseconds();
int rehashes = 0;
//超过1ms刷新一次
while(dictRehash(d,100)) {
rehashes += 100;
if (timeInMilliseconds()-start > ms) break;
}
return rehashes;
}
int dictRehash(dict *d, int n)
{ //移动n*10层(buckets)从d->ht[0] 到d->ht[1]
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
//判读结束条件：没有通过指针是否为空 而是通过位置和总数来判读
while(n-- && d->ht[0].used != 0)
{
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long)d->rehashidx);
//没有数据不移动，数组哈希表
while(d->ht[0].table[d->rehashidx] == NULL)
{
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
/* 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[1].sizemask;
//前插 例如head -- B -C--D insert A A->B-C>D, head-A
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;//第rehashidx层移动完毕
d->rehashidx++;//继续下一层
}
/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0)
{
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;//扩容完毕
return 0;
}
/* More to rehash... */
return 1;
}总结：
扩容步骤
- 业务操作触发扩容 计算扩容大小，然后申请table[1]空间
- 后台进程,间隔时间移动数据，从old-->new table[0]-->table[1]
QA
1 在扩容期间如果有新元素插入进来怎么办？
插入扩容的的哈希表 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
2 每次扩容多少？什么时候扩容
如果原数组大小为零 扩容：dictExpand(d, DICT_HT_INITIAL_SIZE) 默认为4 如果原来数组的个数大于数组的大小 扩容： dictExpand(d, d->ht[0].used*2) 记录个数的倍数 当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作： 1）服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。 2）服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。 load_factor = ht[0].used / ht[0].size
3 如何实现慢慢扩容 ？
解决办法通过开辟一个新的线程来处理，Rehash 在1ms内。 serverCron函数来调度