全局字典

redis的全局字典在其源码中定义在dict.h文件中：

// 哈希表 其中ht就是hash table的缩写
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

dictht是哈希表的定义，其中的table是一个哈希桶数组，数组中的每一项都为NULL或者指向一条哈希冲突链的头结点。

size表示table这个数组的长度，也就是总共有多少个哈希桶。

sizemask可能不太好理解。简单来讲，redis的代码保证了哈希桶的数量一定是2的整数次幂。当size为16时，sizemask为15，当给定一个下标时，将其与sizemask进行位与运算，保证下标一定会落在0-15这一个范围内。这种方式可以保证不会存在越界操作。

最后的used表示的是已经拥有的键值对数量。

再来看一下其中的dict结构体。

// 全局字典 dict也就是dictionary
typedef struct dict {
    dictType *type
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

type中存储了一些函数指针，包括哈希函数、键和值的拷贝函数、键之间的比较函数、键和值的析构函数、检查是否允许分配巨大内存块的函数。

privdata是一些私有数据，type中的大部分函数都需要用到这些数据。

ht属性是真实的哈希表，一般情况下ht[0]存储的就是真实的数据。当键值对的数量过大，扩充哈希表的桶数量后，会进入rehash状态。在rehash状态下，ht[0]和ht[1]各存储一部分的键值对。

rehashidx：出于对性能的考虑，redis将rehash过程均摊到了每一次的键值对操作以及后台任务中，这一过程称为渐进式rehash。而rehashidx变量用来标识rehash的进度。默认值为-1，表示当前并不处于rehash状态中，所有数据都在ht[0]。

pauserehash表示rehash过程是否被暂停。一些耗时操作可能会暂停rehash，比如SCAN命令。实际上也只有6.0.0版本之后才在SCAN命令中添加了暂停rehash的操作，之前的版本中，SCAN命令还是在主线程中完成的。

unsigned long dictScan(dict *d,
                       unsigned long v,
                       dictScanFunction *fn,
                       dictScanBucketFunction* bucketfn,
                       void *privdata)
{
    dictht *t0, *t1;
    const dictEntry *de, *next;
    unsigned long m0, m1;
    if (dictSize(d) == 0) return 0;
    // 暂停rehash（注意，从6.2.0版本开始才开始封装了这个宏，更早的版本直接操作的变量，可读性较差）
    /* This is needed in case the scan callback tries to do dictFind or alike. */
    dictPauseRehashing(d);
    // ......
    // 恢复rehash
    dictResumeRehashing(d);
    return v;
}

如何进入rehash状态

在每一次的扩容后，都会直接进入rehash状态，进入rehash状态就是将rehashidx赋值为0。这些操作在函数_dictExpand中：

// 这个函数的作用就是实现扩容并且将字典d调整为rehash状态
// size表明期望的哈希桶数量
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{
    // 参数校验...
    // 准备好一个新的哈希表
    dictht n; /* the new hash table */
    // 根据期望的数量计算出实际扩容后的尺寸，这一操作可以保证尺寸为2的整数次幂
    unsigned long realsize = _dictNextPower(size);
    // 错误状态检查...
    // 准备属性和实际申请扩容后的内存空间
    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    if (malloc_failed) {
        n.table = ztrycalloc(realsize*sizeof(dictEntry*));
        *malloc_failed = n.table == NULL;
        if (*malloc_failed)
            return DICT_ERR;
    } else
        n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    // 这是第一次初始化的话，并不需要进行rehash，只需要设置ht[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;
    }
    // 大多数情况下，ht[0]已经存储了数据，扩容后的哈希表设置给ht[1]
    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    // 这一行就表明进入了rehash状态
    d->rehashidx = 0;
    return DICT_OK;
}

何时扩容并进入rehash状态

关于何时进行扩容，并进入rehash状态，主要是在_dictExpandIfNeeded中判断的：

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    // 如果已经处于rehash状态，返回
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;
    // 如果哈希表是空的，没有任何数据，那么就扩充为4个哈希桶
    /* 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 || // 当前可以进行rehash
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) && // 已经拥有的键值对数量与哈希桶数量的比值大于dict_force_resize_ratio
        dictTypeExpandAllowed(d)) // 当前允许进行扩容，内部是通过type中的一个函数来进行判断
    {
        // 这里传进去的数量保证至少扩容一个哈希桶，由第一个判断条件可知，第二个参数一定大于size
        // 在_dictExpand内部会将尺寸调整为大于等于第二个参数的最小的2的整数次幂
        return dictExpand(d, d->ht[0].used + 1);
    }
    return DICT_OK;
}

最后的一个if如果忽略最后一个判断条件，其实它只包含了两种情况，再加上前面的判断，我们可以总结出三种情况：

如果哈希表是空的，没有任何数据，那么就扩充为4个哈希桶，这个其实也对应_dictExpand函数中最后一次的判断。
已经拥有的键值对数量达到了哈希桶的数量并且当前可以进行rehash，就进行扩容。其中的dict_can_resize只有在后台执行持久化任务时，它才会为0。也就可以认为是如果没有正在执行的后台任务，并且键值对数量超过桶数量，就进行扩容。
已经拥有的键值对数量与哈希桶数量的比值大于dict_force_resize_ratio，就进行扩容。换一种说法就是，就算现在已经处于不可扩容的状态，只要键值对数量超出一定范围，就强制进行扩容。其中的dict_force_resize_ratio是可以配置的，默认值是5。即默认情况下键值对数量达到哈希桶数量的五倍，强制扩容。

由于在函数_dictExpand中，会将扩容后的尺寸调整为2的整数次幂。所以再看一下第二种情况，有可能扩容为原来的二到八倍，第三种情况则是至少扩容为原来的八倍。

至于调用_dictExpandIfNeeded的时机，对应的调用链为：dictAddRaw->_dictKeyIndex->_dictExpandIfNeeded。其中的dictAddRaw就是添加或者更新一个键值对，也就是在每一次添加一个键值对的时候都会判断是否需要进行扩容。

rehash过程都做了什么

实际完成rehash过程的函数dictRehash，出于对性能的考虑，并不会一次性迁移全部的键值对，具体迁移多少，由第二个参数n来决定。redis的这种处理方式被称为渐进式rehash。源码如下：

// 其中n就是期望迁移的哈希桶的数量
// 当完全迁移时返回0，如果只迁移了一部分返回1
int dictRehash(dict *d, int n) {
    // 由于有的哈希桶中可能没有键值对，为了避免一次访问过多的空哈希桶，设定最大允许访问的空哈希桶数量
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    // 当前并不处于rehash状态，直接退出
    if (!dictIsRehashing(d)) return 0;
    // 还没迁移完期望的桶数量并且ht[0]中还有键值对 
    while(n-- && d->ht[0].used != 0) {
        // 准备两个键值对的指针，用来操作rehashidx指向的哈希桶中的哈希冲突链
        dictEntry *de, *nextde;
        // rehashidx不应该超出ht[0]的尺寸，used!=0的话此条件不会成立
        /* 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);
        // 如果当前rehashidx指向的哈希桶是空的
        while(d->ht[0].table[d->rehashidx] == NULL) {
            // 就向后迁移一个哈希桶
            d->rehashidx++;
            // 记录访问了一个空哈希桶，如果空哈希桶访问数量达到了设定值，就直接结束
            if (--empty_visits == 0) return 1;
        }
        // 能走到这里就说明rehashidx指向的哈希桶一定有结点
        // de指向链表中第一个结点
        de = d->ht[0].table[d->rehashidx];
        // 这个循环体实际完成结点的迁移
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            // h用来记录结点迁移后在ht[1]中的下标。
            uint64_t h;
            nextde = de->next;
            // 这里体现了两点，一个是dictHashKey宏调用了结构体中type的哈希函数，一个是用sizemask保证下标范围
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            // 剩下这一段就是将ht[0]中的一个哈希冲突链的头结点迁移到了ht[1]中指定位置的头结点
            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++;
    }
    // ht[0]如果空了，说明迁移完了，让ht[0]指向迁移后的哈希表，并将ht[1]初始化为一个空表。
    /* 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;
}

何时完成rehash

定时任务

在server.c文件中的serverCron函数会在每一秒钟被调用server.hz次，也就是配置文件中的hz，它的默认值是10，也就是每100ms调用一次。然后按照serverCron->databasesCron->incrementallyRehash->dictRehashMilliseconds->dictRehash的顺序调用到实际工作的函数。

serverCron就是redis的后台任务，它做的事情有很多，比如检查每一个字典是否需要进行expand，比如更新统计信息，比如删除一些过期的key，关闭超时的客户端连接，执行RDB快照和AOF日志，以及完成实际进行的rehash操作。（有点跑题了，以后再说吧）

在dictRehashMilliseconds函数中：

// 其中传入的ms参数是1，也就是期望执行1ms的rehash
/* Rehash in ms+"delta" milliseconds. The value of "delta" is larger 
 * than 0, and is smaller than 1 in most cases. The exact upper bound 
 * depends on the running time of dictRehash(d,100).*/
int dictRehashMilliseconds(dict *d, int ms) {
    if (d->pauserehash > 0) return 0;
    long long start = timeInMilliseconds();
    int rehashes = 0;
    // 每一次完成100个哈希桶的迁移
    while(dictRehash(d,100)) {
        rehashes += 100;
        // 检查是否超时
        if (timeInMilliseconds()-start > ms) break;
    }
    // 感觉这个rehashes的统计并不精确，像是以100为精度向下取整了
    // 不过incrementallyRehash并未处理这个返回值，可能在其他调用处有用吧
    return rehashes;
}

看到这里，我们可以得到一个结论，每一次定时任务都会迁移ht[0]中100个哈希桶中地数据到ht[1]中，迁移完后判断是否超过了1ms，没超时就再迁移100个。当然如果dictRehash返回0的话，表明当前这次的调用已经迁移完了所有的键值对，自然可以结束循环。

每一次的键值对操作

在dict.c中还有一个函数叫做_dictRehashStep，它也会调用dictRehash：

static void _dictRehashStep(dict *d) {
    if (d->pauserehash == 0) dictRehash(d,1);
}

在dict.c中共有五个函数调用了_dictRehashStep，分别是：dictAddRaw、dictGenericDelete、dictFind、dictGetRandomKey、dictGetSomeKeys。

这些函数都是对键值对的操作，分别表示添加或覆盖一个键值对，删除一个键值对、根据key查找一个键值对、随机获取一个键值对、获取一些键值对。如果只看针对rehash的操作，这些函数可以总结为每一次对键值对的操作都会顺带完成一个哈希桶的迁移。

总结

关于何时进行扩容并进入rehash状态，会在每一次添加新的键值对时进行判断，总共有三种可能性：

哈希桶是空的，扩容为四个哈希桶；
已经拥有的键值对数量达到了哈希桶的数量，并且没有正在执行的后台持久化任务，扩容后的哈希桶数量为原来的两倍到八倍；
如果键值对的数量达到了哈希桶数量的五倍（对应配置项为：dict_force_resize_ratio，五倍只是默认值），强制进行扩容，至少扩容为原来的八倍。

关于何时进行rehash过程的节点迁移，总共有两种情况：

每一次后台任务（默认100ms执行一次，可通过配置hz来修改执行频率），会迁移ht[0]中的100个哈希桶到ht[1]中，判断总耗时是否超过了1ms，没超时的话再迁移100个哈希桶，直到某一次迁移后超时。
每一次针对键值对的操作，迁移ht[0]中的1个哈希桶到ht[1]中。

Redis的渐进rehash机制