关于redis:Redis扩容机制

前言

在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]中。

关于redis:Redis扩容机制

前言

注释

一. Redis的扩容机会

二. Redis的扩容步骤

总结

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于redis:Redis扩容机制

前言

注释

一. Redis的扩容机会

二. Redis的扩容步骤

总结

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复