redis字典dict——Part3：rehash

随着redis不断插入或者删除数据，dict保存的键值对也会增多或者减少，此时dict也会进行相对应的扩容和缩容，这些操作主要通过rehash来完成的。

dict的扩容

如果是扩容，首先判断是否需要进行扩容

• 1，如果在重哈希的过程中，则直接返回
• 2，如果此时dict的容量为0，也就是才进行了初始化，则将其容量扩容从DICT_HT_INITIAL_SIZE，默认为4
• 3，如果dict装载因子used/size>1.0且此时可以进行扩容，或者装载因子大于dict_force_resize_ratio（设置为5）时，此时强制进行扩容
• 4，扩容过程中，容量提升一倍，此时初始化ht[1]，同时更新rehashidx为0，代表要进行重哈希过程了

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    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. */
    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);
    }
    return DICT_OK;
}

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

/* Resize the table to the minimal size that contains all the elements,
 * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
int dictResize(dict *d)
{
    int minimal;

    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    minimal = d->ht[0].used;
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(d, minimal);
}

dict的缩容

dict不光有扩容，也有缩容，当删除元素时，会检测装载因子是否小于HASHTABLE_MIN_FILL（默认10%），此时进行缩容，通过调用dictResize函数将size缩小为最接近used的数组2的n次方的大小。

int htNeedsResize(dict *dict) {
    long long size, used;

    size = dictSlots(dict);
    used = dictSize(dict);
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}

rehash的过程

dictRehash每次将重哈希至少向前推进n步（除非不到n步整个重哈希就结束了），
每一步都将ht[0]上某一个bucket（即一个dictEntry链表）上的所有dictEntry移动到ht[1]上，在ht[1]上的新位置根据ht[1]的sizemask进行重新计算。
每次移动的dictEntry都会插入ht[1]的链表上的第一个位置
rehashidx记录了当前尚未迁移（有待迁移）的ht[0]的bucket位置。
如果dictRehash被调用的时候，rehashidx指向的bucket里一个dictEntry也没有，那么它就没有可迁移的数据。这时它尝试在ht[0].table数组中不断向后遍历，直到找到下一个存有数据的bucket位置。如果一直找不到，则最多走n*10步，本次重哈希暂告结束。
最后，如果ht[0]上的数据都迁移到ht[1]上了（即d->ht[0].used == 0），那么整个重哈希结束，ht[0]变成ht[1]的内容，而ht[1]重置为空。

三种情况下会结束这个rehash的过程：

• 1，移动了ht[0]上n个dictEntry链表
• 2，虽然没有移动ht[0]上n个dictEntry链表，但是遍历空的ht[0]的bucket已经达到n*10
• 3，整个ht[0]所有的dictEntry已经重哈希到ht[1]

int dictRehash(dict *d, int n) {
    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;
            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;
        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;
}

在前面介绍dict的添加，删除，查找和更新操作时，替代rehash的步骤都会穿插在其中进行，因此redis的rehash的过程是一个渐进式的过程，所有元素的rehash均衡分摊到各个操作中去，这样可以避免集中式rehash对机器带来的计算尖峰以及对redis功能的影响。

参考：

http://zhangtielei.com/posts/blog-redis-dict.html
《redis设计与实现》第二版