Redis rehash机制分析介绍

/* 根据相关触发条件扩展字典 */
static int _dictExpandIfNeeded(dict *d)
{
if (dictIsRehashing(d)) return DICT_OK; // 如果正在进行Rehash，则直接返回
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); // 如果ht[0]字典为空，则创建并初始化ht[0]
/* (ht[0].used/ht[0].size)>=1前提下，
当满足dict_can_resize=1或ht[0].used/t[0].size>5时，便对字典进行扩展 */
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
return dictExpand(d, d->ht[0].used*2); // 扩展字典为原来的2倍
}
return DICT_OK;
}

...

/* 计算存储Key的bucket的位置 */
static int _dictKeyIndex(dict *d, const void *key)
{
unsigned int h, idx, table;
dictEntry *he;

/* 检查是否需要扩展哈希表，不足则扩展 */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
/* 计算Key的哈希值 */
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask; //计算Key的bucket位置
/* 检查节点上是否存在新增的Key */
he = d->ht[table].table[idx];
/* 在节点链表检查 */
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key))
return -1;
he = he->next;
}
if (!dictIsRehashing(d)) break; // 扫完ht[0]后，如果哈希表不在rehashing，则无需再扫ht[1]
}
return idx;
}

...

/* 将Key插入哈希表 */
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;

if (dictIsRehashing(d)) _dictRehashStep(d); // 如果哈希表在rehashing，则执行单步rehash

/* 调用_dictKeyIndex() 检查键是否存在，如果存在则返回NULL */
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;

ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry)); // 为新增的节点分配内存
entry->next = ht->table[index]; // 将节点插入链表表头
ht->table[index] = entry; // 更新节点和桶信息
ht->used++; // 更新ht

/* 设置新节点的键 */
dictSetKey(d, entry, key);
return entry;
}

...
/* 添加新键值对 */
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key); // 添加新键

if (!entry) return DICT_ERR; // 如果键存在，则返回失败
dictSetVal(d, entry, val); // 键不存在，则设置节点值
return DICT_OK;
}

int dictExpand(dict *d, unsigned long size)
{
dictht n; // 新哈希表
unsigned long realsize = _dictNextPower(size); // 计算扩展或缩放新哈希表的大小(调用下面函数_dictNextPower())

/* 如果正在rehash或者新哈希表的大小小于现已使用，则返回error */
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;

/* 如果计算出哈希表size与现哈希表大小一样，也返回error */
if (realsize == d->ht[0].size) return DICT_ERR;

/* 初始化新哈希表 */
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*)); // 为table指向dictEntry 分配内存
n.used = 0;

/* 如果ht[0] 为空，则初始化ht[0]为当前键值对的哈希表 */
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}

/* 如果ht[0]不为空，则初始化ht[1]为当前键值对的哈希表，并开启渐进式rehash模式 */
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}
...
static unsigned long _dictNextPower(unsigned long size) {
unsigned long i = DICT_HT_INITIAL_SIZE; // 哈希表的初始值：4

if (size >= LONG_MAX) return LONG_MAX;
/* 计算新哈希表的大小：第一个大于等于size的2的N 次方的数值 */
while(1) {
if (i >= size)
return i;
i *= 2;
}
}