共计 10054 个字符，预计需要花费 26 分钟才能阅读完成。
前言
在 Redis- 对象类型一文中曾经对 Redis 中的哈希对象进行了学习，已知哈希对象的底层数据结构应用了字典 dict 数据结构，实际上 Redis 中的数据就是以 key-value 的模式存储在 dict 中，dict数据结构的示意图能够示意如下。
即一个 dict 数据结构持有两张哈希表 dictht，每张dictht 中持有一个存储元素的节点数组，每对键值对会被封装成一个 dictEntry 节点而后增加到节点数组中，当存在哈希抵触时，Redis中应用拉链法解决哈希抵触。然而 dictEntry 数组的默认容量为 4，产生哈希抵触的概率极高，如果不进行扩容，会导致哈希表的工夫复杂度好转为 O(logN)，所以满足肯定条件时，须要进行dictEntry 数组的扩容，即进行 Redis 的扩容，本篇文章将对 Redis 的扩容机制进行学习。
Redis源码版本：6.0.16
注释
一. Redis 的扩容机会
Redis会在如下两种状况触发扩容。
- 如果没有
fork子过程在执行 RDB 或者 AOF 的长久化，一旦满足ht[0].used >= ht[0].size，此时触发扩容； - 如果有
fork子过程在执行 RDB 或者 AOF 的长久化时，则须要满足ht[0].used > 5 * ht[0].size，此时触发扩容。
上面将联合源码对 Redis 的扩容机会进行学习。当向 dict 增加或者更新数据时，对应的办法是位于 dict.c 文件中的 dictReplace() 办法，如下所示。
int dictReplace(dict *d, void *key, void *val) {
dictEntry *entry, *existing, auxentry;
// 如果增加胜利，dictAddRaw()办法会把胜利增加的 dictEntry 返回
// 返回的 dictEntry 只设置了键，值须要在这里调用 dictSetVal()办法进行设置
entry = dictAddRaw(d,key,&existing);
if (entry) {dictSetVal(d, entry, val);
return 1;
}
// 执行到这里，表明在哈希表中曾经存在一个 dictEntry 的键与以后待增加的键值对的键相等
// 此时应该做更新值的操作，且 existing 此时是指向这个曾经存在的 dictEntry
auxentry = *existing;
// 更新值，即为 existing 指向的 dictEntry 设置新值
dictSetVal(d, existing, val);
// 开释旧值
dictFreeVal(d, &auxentry);
return 0;
}dictReplace()办法会执行键值对的增加或更新，如果哈希表中不存在 dictEntry 的键与待增加键值对的键相等，此时会基于待增加键值对新创建一个 dictEntry 并以头插法插入哈希表中，此时返回 1；如果哈希表中存在 dictEntry 的键与待增加键值对的键相等，此时就为曾经存在的 dictEntry 设置新值并开释旧值，而后返回 0。通常要触发扩容，触发机会个别在增加键值对的时候，所以持续剖析 dictAddRaw() 办法，其源码实现如下所示。
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) {
long index;
dictEntry *entry;
dictht *ht;
// 判断是否在进行 rehash，如果正在进行 rehash，则触发渐进式 rehash
//dictIsRehashing()办法在 dict.h 文件中，如果 dict 的 rehashidx 不等于 -1，则表明此时在进行 rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 获取待增加键值对在哈希表中的索引 index
// 如果哈希表曾经存在 dictEntry 的键与待增加键值对的键相等，此时_dictKeyIndex()办法返回 -1
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
// 如果在进行 rehash，待增加的键值对寄存到 ht[1]，否则寄存到 ht[0]
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// 为新 dictEntry 开拓内存，此时 dictEntry 的键和值尚未设置
entry = zmalloc(sizeof(*entry));
// 头插的形式插入哈希表 index 地位的哈希桶中
entry->next = ht->table[index];
ht->table[index] = entry;
// 哈希表的以后大小加 1
ht->used++;
// 为新 dictEntry 设置键
dictSetKey(d, entry, key);
return entry;
}dictAddRaw()办法会首先判断以后是否处于 rehash 阶段（判断以后是否正在扩容），如果正在 rehash，则触发一次哈希桶的迁徙操作（这一点前面再详细分析），而后通过_dictKeyIndex() 办法获取待增加键值对在哈希表中的索引 index，如果获取到的index 为 -1，表明存在 dictEntry 的键与待增加键值对的键相等，此时 dictAddRaw() 办法返回 NULL 以通知办法调用方须要执行更新操作，如果 index 不为 -1，则基于待增加键值对创立新的 dictEntry 并以头插的形式插入哈希表 index 地位的哈希桶中，而后更新哈希表的以后大小以及为新 dictEntry 设置键。扩容的触发在 _dictKeyIndex() 办法中，其源码实现如下所示。
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing) {
unsigned long idx, table;
dictEntry *he;
if (existing) *existing = NULL;
// 在_dictExpandIfNeeded()办法中判断是否须要扩容，如果须要，则执行扩容
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
for (table = 0; table <= 1; table++) {
// 将待增加键值对的键的 hash 值与哈希表掩码相与以失去待增加键值对在哈希表中的索引
idx = hash & d->ht[table].sizemask;
// 遍历哈希表中 idx 索引地位的哈希桶的链表
he = d->ht[table].table[idx];
while(he) {if (key==he->key || dictCompareKeys(d, key, he->key)) {
// 链表中存在 dictEntry 的 key 与待增加键值对的 key 相等
// 此时让 existing 指向这个曾经存在的 dictEntry，并返回 -1
// 表明存在 dictEntry 的 key 与待增加键值对的 key 相等且 existing 曾经指向了这个存在的 dictEntry
if (existing) *existing = he;
return -1;
}
// 持续遍历链表中的下一个节点
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
// 执行到这里，表明哈希表中不存在 dictEntry 的 key 与待增加键值对的 key 相等，返回索引 idx
return idx;
}在 _dictKeyIndex() 办法的一开始，就会调用 _dictExpandIfNeeded() 办法来判断是否须要扩容，如果须要，则会执行扩容逻辑，如果 _dictExpandIfNeeded() 办法在扩容过程中呈现谬误，会返回状态码 1，也就是 DICT_ERR 字段示意的值，此时 _dictKeyIndex() 办法间接返回 -1，如果不须要扩容或者扩容胜利，则将待增加键值对的键的 hash 值与哈希表掩码相与失去待增加键值对在哈希表中的索引，而后遍历索引地位的哈希桶的链表，看是否可能找到一个 dictEntry 的键与待增加键值对的键相等，如果可能找到一个这样的 dictEntry，则返回 - 1 并让existing 指向这个 dictEntry，否则返回之前计算失去的索引。可知判断扩容以及执行扩容的逻辑都在_dictExpandIfNeeded() 办法中，其源码实现如下所示。
static int _dictExpandIfNeeded(dict *d) {
// 如果曾经在扩容，则返回状态码 0
if (dictIsRehashing(d)) return DICT_OK;
// 如果哈希表的容量为 0，则初始化哈希表的容量为 4
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
// 如果哈希表的以后大小大于等于容量，并且 dict_can_resize 为 1 或者以后大小大于容量的五倍
// 此时判断须要扩容，调用 dictExpand()办法执行扩容逻辑，且指定扩容后的容量至多为以后大小的 2 倍
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;
}通过 _dictExpandIfNeeded() 办法的源码可知，要触发扩容，首先须要满足的条件就是哈希表以后大小大于等于了哈希表的容量，而后再判断 Redis 以后是否容许扩容，如果容许扩容，则执行扩容逻辑，如果不容许扩容，那么再判断哈希表以后大小是否曾经大于了哈希表容量的 5 倍，如果曾经大于，则强制执行扩容逻辑。在 _dictExpandIfNeeded() 办法有两个重要的参数，别离是 dict_can_resize 和dict_force_resize_ratio，这两个参数定义在 dict.c 文件中，初始值如下所示。
static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;那么当初最初还须要联合源码剖析一下，什么时候会更改 dict_can_resize 的值，在 dict.c 文件中有如下两个办法，会将 dict_can_resize 的值设置为 1 或者 0，如下所示。
void dictEnableResize(void) {dict_can_resize = 1;}
void dictDisableResize(void) {dict_can_resize = 0;}这两个办法会被 server.c 文件中的 updateDictResizePolicy() 办法调用，如下所示。
void updateDictResizePolicy(void) {// 如果有正在执行 RDB 或 AOF 长久化的子过程，hasActiveChildProcess()办法返回 true
if (!hasActiveChildProcess())
// 没有正在执行 RDB 或 AOF 长久化的子过程时将 dict_can_resize 设置为 1，示意容许扩容
dictEnableResize();
else
// 有正在执行 RDB 或 AOF 长久化的子过程时将 dict_can_resize 设置为 0，示意不容许扩容
dictDisableResize();}至此 Redis 的扩容机会的源码剖析就到此为止，当初进行大节：当向 Redis 增加或者更新数据时，会判断一下存储数据的哈希表的以后大小是否大于等于哈希表容量，如果大于，再判断 Redis 是否容许扩容，而决定 Redis 是否容许扩容的根据就是以后是否存在子线程在执行 RDB 或者 AOF 的长久化，如果存在就不容许扩容，反之则容许扩容，如果 Redis 不容许扩容，那么还须要判断一下是否要强制扩容，判断根据就是存储数据的哈希表的以后大小是否曾经大于哈希表容量的 5 倍，如果大于，则强制扩容。
上面给出流程图，对上述整个触发扩容的源码流程进行示意。
二. Redis 的扩容步骤
当一旦须要进行扩容时，此时会应用到 dict 中的 ht[1]，Redis 的扩容步骤如下所示。
- 计算 ht[1] 的容量 size，即扩容后的容量，ht[1] 的容量为大于等于
ht[0].used * 2且同时为 2 的幂次方的最小值； - 为 ht[1] 设置 size，sizemask 字段的值，初始化 used 字段为 0，并为 dictEntry 数组调配空间；
- 将 dict 的rehashidx字段设置为 0，示意此时开启渐进式 rehash，Redis 会通过渐进式 rehash 的形式逐渐将 ht[0] 上的 dictEntry 迁徙到 ht[1] 上；
- 当 ht[0] 的所有键值对全副寄存到 ht[1] 中后，开释 ht[0] 的内存空间，而后 ht[1] 变为ht[0]。
特地留神，上述的步骤仅针对失常的扩容，如果是 ht[0] 的初始化，则与上述的步骤稍有不同，这里不再赘述。当 dict 中键值对特地多时，rehash会特地耗时，所以 Redis 采纳一种渐进式 rehash 的形式来实现扩容，dict中的 rehashidx 字段用于记录以后曾经 rehash 到的哈希桶的索引，而渐进式 rehash 就是 Redis 不会一次性将 ht[0] 上的键值对迁徙到 ht[1] 上，而是会在某些工夫点迁徙一部分，这些工夫点如下所示。
- 当对数据进行增删改查时会从 ht[0] 迁徙一个哈希桶到 ht[1] 上；
- Redis会定时的从 ht[0] 迁徙一部分哈希桶到 ht[1] 上。
特地留神，如果在渐进式 rehash 的过程中有新的键值对增加，那么会间接增加到 ht[1] 中。
上面将联合 Redis 源码对 Redis 的扩容步骤进行学习。在第一节中已知，执行扩容逻辑的办法是 dict.c 文件的 dictExpand() 办法，其源码实现如下所示。
int dictExpand(dict *d, unsigned long size) {// 如果正在 rehash 或者 ht[0]的以后大小大于了扩容后的大小的最小值
// 此时返回状态码 1，示意扩容产生异样
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
// n 就是扩容后的哈希表
dictht n;
// 失去一个大于等于 size 的满足 2 的幂次方的最小值作为 n 的容量
unsigned long realsize = _dictNextPower(size);
// 如果扩容后的哈希表的容量与老哈希表容量一样
// 此时返回状态码 1，示意扩容产生异样
if (realsize == d->ht[0].size) return DICT_ERR;
// 为 n 设置容量 size
n.size = realsize;
// 为 n 设置掩码 sizemask
n.sizemask = realsize-1;
// 为 n 的数组调配空间
n.table = zcalloc(realsize*sizeof(dictEntry*));
// 初始化 n 的以后大小 used 为 0
n.used = 0;
// 如果是初始化哈希表，那么间接将 ht[0]置为 n
if (d->ht[0].table == NULL) {d->ht[0] = n;
return DICT_OK;
}
// 执行到这里，表明是非初始化哈希表的扩容，将 ht[1]置为 n
d->ht[1] = n;
// 将 dict 的 rehashidx 字段设置为 0，示意开启渐进式 rehash
d->rehashidx = 0;
return DICT_OK;
}dictExpand()办法次要实现的逻辑就是为 ht[1] 设置 size，sizemask 字段的值，初始化 used 字段为 0，并为 dictEntry 数组调配空间，最初将 dict 的rehashidx字段设置为 0 以开启渐进式 rehash。上面再联合源码看一下什么时候进行键值对的迁徙，首先在第一节中剖析dictAddRaw() 办法时有提到，dictAddRaw()办法一开始就会判断以后是否处于 rehash 阶段，如果正在 rehash，则触发一次哈希桶的迁徙操作，这个迁徙操作对应的办法是dict.c 文件的 _dictRehashStep() 办法，其源码实现如下。
static void _dictRehashStep(dict *d) {if (d->iterators == 0) dictRehash(d,1);
}持续看 dictRehash() 办法的实现。
// 参数 n 示意本次 rehash 须要迁徙的哈希桶个数
int dictRehash(dict *d, int n) {
// 容许遍历的最大空桶数
int empty_visits = n*10;
// 如果没有在进行渐进式 rehash，则返回
if (!dictIsRehashing(d)) return 0;
// 在 ht[0]以后大小不为 0 的前提下
// 须要迁徙多少个哈希桶，就循环多少次，每次循环迁徙一个哈希桶
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
//rehashidx 的值不能大于等于 ht[0]的容量
assert(d->ht[0].size > (unsigned long)d->rehashidx);
// 如果哈希表 ht[0]的 rehashidx 地位的哈希桶是空，则持续遍历下一个哈希桶
// 如果遍历的空桶数达到了 empty_visits，则本次 rehash 完结，间接返回
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
// 失去 ht[0]的 rehashidx 地位的哈希桶
de = d->ht[0].table[d->rehashidx];
// 遍历并将 rehashidx 地位的哈希桶的链表上的节点全副迁徙到 ht[1]上
while(de) {
uint64_t h;
nextde = de->next;
// 将链表节点的键的 hash 值与 ht[1]的掩码相与失去以后节点在 ht[1]上的索引
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 应用头插法插入 ht[1]
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
//ht[0]的以后大小减 1
d->ht[0].used--;
//ht[1]的以后大小加 1
d->ht[1].used++;
// 持续迁徙链表的下一节点
de = nextde;
}
// 全副迁徙实现后，将 ht[0]的 rehashidx 地位置为空
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
// 判断是否将 ht[0]上的键值对全副迁徙到了 ht[1]
if (d->ht[0].used == 0) {// 如果 ht[0]上的键值对全副迁徙到了 ht[1]
// 先开释 ht[0]的数组空间
zfree(d->ht[0].table);
// 而后将 ht[0]置为 ht[1]
d->ht[0] = d->ht[1];
// 重置 ht[1]
// 行将 ht[1]的数组置为空，容量，掩码和以后大小全副置为 0
_dictReset(&d->ht[1]);
// 将 dict 的 rehashidx 字段设置为 -1，示意 rehash 完结
d->rehashidx = -1;
return 0;
}
return 1;
}dictRehash()办法有两个参数，第一个是须要进行 rehash 的dict，第二个是须要迁徙的哈希桶的个数，可知如果是对数据的增删改查而触发的 rehash，须要迁徙的哈希桶的个数为 1。在dictRehash() 办法一开始就定义了一个最大空桶数，其值为本次迁徙数的 10 倍，因为在遍历哈希表时，可能会遇到很多空桶，所以为了防止遍历大量空桶而带来的工夫耗费，Redis规定本次 rehash 迁徙时，如果遇到的空桶数达到了本次须要迁徙的哈希桶数的 10 倍，则进行迁徙并返回。在 dictRehash() 办法中对于每一个哈希桶的迁徙，其实就是遍历这个哈希桶上的链表，将每个链表节点从新基于 ht[1] 计算一个索引并迁徙到 ht[1] 上。在 dictRehash() 办法的最初须要判断一下是否将 ht[0] 上的数据全副迁徙到了 ht[1] 上，如果曾经全副实现迁徙，此时须要先开释老的 ht[0] 的数组空间，而后将 ht[0] 置为 ht[1]，接着重置ht[1] 行将其数组置为空，容量，掩码和以后大小全副置为 0，最初将 dict 的rehashidx字段设置为 -1，示意 rehash 完结。
除了对数据的增删改查会调用到 dictRehash() 办法来迁徙哈希桶外，Redis也会定时的调用到 dictRehash() 办法来迁徙哈希桶，这个定时工作办法是 server.c 文件的 serverCron() 办法，在该办法中会调用到 server.c 文件的 databasesCron() 办法，该办法会解决 Redis 数据库中的增量执行的后盾操作，这些操作中就包含渐进式 rehash，所以在databasesCron() 办法中又通过调用 server.c 文件的 incrementallyRehash() 办法来执行 rehash，接着又在incrementallyRehash() 办法中调用到了 dict.c 文件的 dictRehashMilliseconds() 办法，在 dictRehashMilliseconds() 办法中就真正调用到了 dictRehash() 办法来执行迁徙哈希桶的逻辑，dictRehashMilliseconds()办法的源码实现如下所示。
int dictRehashMilliseconds(dict *d, int ms) {long long start = timeInMilliseconds();
int rehashes = 0;
// 在 1 毫秒的工夫内循环进行迁徙
// 每次循环迁徙 100 个哈希桶
while(dictRehash(d,100)) {
rehashes += 100;
if (timeInMilliseconds()-start > ms) break;
}
return rehashes;
}那么至此，Redis的扩容步骤的源码就剖析结束。
总结
Redis中的数据存储在字典 dict 数据结构中，一个 dict 数据结构持有两张哈希表 dictht，每张dictht 中持有一个存储数据的 dictEntry 数组，每份数据会以键值对的模式封装成一个 dictEntry 节点而后增加到 dictEntry 数组中，当存在哈希抵触时，Redis中应用拉链法解决哈希抵触，然而 dictEntry 数组的默认容量为 4，产生哈希抵触的概率极高，如果不进行扩容，会导致哈希表的工夫复杂度好转为 O(logN)，所以满足肯定条件时，须要进行dictEntry 数组的扩容，即进行 Redis 的扩容。
Redis的扩容的机会总结如下。
- 如果没有
fork子过程在执行 RDB 或者 AOF 的长久化，一旦满足ht[0].used >= ht[0].size，此时触发扩容； - 如果有
fork子过程在执行 RDB 或者 AOF 的长久化时，则须要满足ht[0].used > 5 * ht[0].size，此时触发扩容。
Redis的 dict 数据结构通常只会应用两张哈希表中的其中一张，，即 ht[0]，然而当须要进行扩容时，此时会应用到dict 的另外一张哈希表 ht[1]，Redis 的扩容步骤如下所示。
- 计算 ht[1] 的容量 size，即扩容后的容量，ht[1] 的容量为大于等于
ht[0].used * 2且同时为 2 的幂次方的最小值； - 为 ht[1] 设置 size，sizemask 字段的值，初始化 used 字段为 0，并为 dictEntry 数组调配空间；
- 将 dict 的rehashidx字段设置为 0，示意此时开启渐进式 rehash，Redis 会通过渐进式 rehash 的形式逐渐将 ht[0] 上的 dictEntry 以哈希桶为单位逐次迁徙到 ht[1] 上；
- 当 ht[0] 的所有键值对全副寄存到 ht[1] 中后，开释 ht[0] 的内存空间，而后 ht[1] 变为ht[0]。
当 dict 中键值对特地多时，rehash会特地耗时，所以 Redis 采纳一种渐进式 rehash 的形式来实现扩容，dict中的 rehashidx 字段用于记录以后曾经 rehash 到的哈希桶的索引，而渐进式 rehash 就是 Redis 不会一次性将 ht[0] 上的键值对迁徙到 ht[1] 上，而是会在某些工夫点迁徙一部分，这些工夫点如下所示。
- 当对数据进行增删改查时会从 ht[0] 迁徙一个哈希桶到 ht[1] 上；
- Redis会定时的从 ht[0] 迁徙一部分哈希桶到 ht[1] 上。
特地留神，如果在渐进式 rehash 的过程中有新的键值对增加，那么会间接增加到 ht[1] 中。
