Go back

Redis渐进式rehash

Redis 渐进式 rehash：一张表存不下时如何不卡主线程？

一句话结论（30s）

渐进式 rehash 的本质是把 O(n) 的一次性全量迁移拆成 n 次 O(1) 的微步，从而避免哈希表扩容阻塞 Redis 的单线程主进程。关键设计：因为维护了 ht[0]/ht[1] 双表 + rehashidx 游标，每次读写命令顺带迁移 1 个桶，空闲期间再由 serverCron 用 1ms 时间预算兜底推进。权衡：rehash 期间「读先 ht[0] 后 ht[1]、写只写 ht[1]」保证不漏也不白写，且 fork 子进程（bgsave/bgrewriteaof）期间尽量不扩容以避免 COW 内存暴涨，除非负载因子 ≥ 4 强制触发。

核心原理（2min）

dict 维护两张哈希表 ht[0]/ht[1] 和 rehashidx 游标（-1 表示未在 rehash）。扩容时分配 2 的幂次容量（通常是 2 倍）的新表，之后每次 dictAdd/dictFind/dictDelete 前先 _dictRehashStepIfNeeded 迁移 1 个桶（桶内冲突链通常只有 1-2 个 key，单步 O(1)）；空闲期间 serverCron 每 100ms 按 1ms 时间预算批量迁移 100 个桶。读操作先查 ht[0] 再查 ht[1] 不漏数据，写操作 rehash 期间只写 ht[1] 避免被清空。迁移完成后释放 ht[0]、ht[1] 升格为正式表、rehashidx 置 -1。触发条件是负载因子 ≥1（无子进程时）或 ≥4（强制触发），缩容在负载因子低于 1/8 时同理渐进进行。

底层深入（5-10min）

下面所有代码均逐字摘自 Redis 源码 src/dict.h 与 src/dict.c。

问题：哈希表扩容是 O(n)

Redis 用全局哈希表（dict）存所有 KV。当 key 越来越多，哈希冲突加剧，需要扩容——把旧表的所有 key 重新计算哈希、迁移到新表。这个过程是 O(n)，如果一次性完成，n 是一个亿，主线程被阻塞数秒，线上服务不可用。

Redis 的解法：渐进式 rehash——把 O(n) 的一次性工作拆成 n 次 O(1) 的零碎工作。

思考一下：rehash 为什么非得「渐进式」，直接一次性迁完不行吗？ 因为 Redis 是单线程处理命令的主进程，任何一次命令都不能占用主线程太久。一次性迁 n 个 key 是 O(n)，当 n 大到千万、上亿级时，这一下就是数秒的阻塞——期间所有 GET/SET 全部排队，等价于线上「宕机」几秒。所以「渐进式」不是优雅炫技，而是单线程模型下的硬约束：把大迁移切成 n 个「每人只多花几十微秒」的微步，摊到后续成千上万次命令里，主线程每次几乎无感。理解了这一条，后面「双表 + rehashidx」的设计就顺理成章了。

数据结构：维护两张表

struct dict {
    dictType *type;

    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    /* Note: pauserehash is a full unsigned so iterator increments
     * don't perform RMW on the same storage unit as other bitfields. */
    unsigned pauserehash; /* If >0 rehashing is paused */

    /* Keep small vars at end for optimal (minimal) struct padding */
    signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */
    int16_t pauseAutoResize;  /* If >0 automatic resizing is disallowed (<0 indicates coding error) */
    void *metadata[];
};
#define DICTHT_SIZE(exp) ((exp) == -1 ? 0 : (unsigned long)1<<(exp))
#define DICTHT_SIZE_MASK(exp) ((exp) == -1 ? 0 : (DICTHT_SIZE(exp))-1)
#define dictIsRehashing(d) ((d)->rehashidx != -1)

真实源码里没有独立的结构体 dictht，而是把两张表的「桶指针、元素计数、容量指数」拆成三个长度为 2 的数组：ht_table[2]、ht_used[2]、ht_size_exp[2]（size = 1<<exp，容量恒为 2 的幂次）。rehashidx 是渐进迁移的游标：-1 表示不在 rehash（宏 dictIsRehashing 就是判断它 != -1），>=0 时表示 ht_table[0] 中「索引 < rehashidx」的桶都已经迁到了新表。pauserehash 用于遍历期间暂停 rehash，pauseAutoResize 用于手动禁用自动扩容——它们和「渐进」策略配套，保证迁移随时可以插队、暂停、恢复。

思考一下：为什么要保留两张表 + 一个游标，而不是在旧表上原地搬？ 因为渐进迁移是「跨多次命令」完成的，中间会穿插无数读写。如果只有一张表，搬一半时读命令根本不知道该去哪半边找 key——旧桶里剩一半、新位置放一半，数据就「丢了」或「找不着」。双表的妙处在于：旧表永远完整保留「还没搬走的部分」，新表持续接收「已搬来的部分」，rehashidx 精确记录搬到哪了。于是任意时刻一个 key 要么还在 ht[0]，要么已在 ht[1]，绝不会悬空——这就是渐进式能正确工作的根基。

        ht_table[0]                          ht_table[1]
    ht_size_exp[0]=2(容量4)             ht_size_exp[1]=3(容量8)
┌───┬───┬───┬───┐            ┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │            │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │
└─┬─┴───┴───┴───┘            └───┴───┴───┴───┴───┴───┴───┴───┘
  │                               新表：容量是 2 的幂次（这里是 2 倍），当前为空
  ▼
旧表：容量=4，rehashidx=0（正在迁移桶 0）

迁移的触发与执行

rehash 不是由单独线程做的——是在每次读写命令中顺带推进的。

/* This function performs just a step of rehashing, and only if hashing has
 * not been paused for our hash table. When we have iterators in the
 * middle of a rehashing we can't mess with the two hash tables otherwise
 * some elements can be missed or duplicated.
 *
 * This function is called by common lookup or update operations in the
 * dictionary so that the hash table automatically migrates from H1 to H2
 * while it is actively used. */
static void _dictRehashStep(dict *d) {
    if (d->pauserehash == 0) dictRehash(d,1);
}
static void _dictRehashStepIfNeeded(dict *d, uint64_t visitedIdx) {
    if ((!dictIsRehashing(d)) || (d->pauserehash != 0))
        return;
    /* rehashing not in progress if rehashidx == -1 */
    if ((long)visitedIdx >= d->rehashidx && d->ht_table[0][visitedIdx]) {
        /* If we have a valid hash entry at `idx` in ht0, we perform
         * rehash on the bucket at `idx` (being more CPU cache friendly) */
        _dictBucketRehash(d, visitedIdx);
    } else {
        /* If the hash entry is not in ht0, we rehash the buckets based
         * on the rehashidx (not CPU cache friendly). */
        dictRehash(d,1);
    }
}

只迁移 1 个桶——不管这个桶里是空的、有 1 个 key、还是有 100 个 key（冲突链）。因为 100 个 key 集中在同一个桶的概率极低（哈希均匀分布时），所以几乎每次迁移都只是搬迁 1-2 个 key，单步 O(1)。_dictRehashStepIfNeeded 还有一个 CPU 缓存友好的优化：如果本次要访问的桶恰好还没迁移，就直接迁它，否则退回按 rehashidx 顺序迁下一个桶。

真正的迁移逻辑在 dictRehash：

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    unsigned long s0 = DICTHT_SIZE(d->ht_size_exp[0]);
    unsigned long s1 = DICTHT_SIZE(d->ht_size_exp[1]);
    dictResizeEnable can_resize;
    atomicGet(dict_can_resize, can_resize);
    if (can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0;
    /* If dict_can_resize is DICT_RESIZE_AVOID, we want to avoid rehashing.
     * - If expanding, the threshold is dict_force_resize_ratio which is 4.
     * - If shrinking, the threshold is 1 / (HASHTABLE_MIN_FILL * dict_force_resize_ratio) which is 1/32. */
    if (can_resize == DICT_RESIZE_AVOID &&
        ((s1 > s0 && s1 < dict_force_resize_ratio * s0) ||
         (s1 < s0 && s0 < HASHTABLE_MIN_FILL * dict_force_resize_ratio * s1)))
    {
        return 0;
    }

    while(n-- && d->ht_used[0] != 0) {
        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);
        while(d->ht_table[0][d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        /* Move all the keys in this bucket from the old to the new hash HT */
        rehashEntriesInBucketAtIndex(d, d->rehashidx);
        d->rehashidx++;
    }

    return !dictCheckRehashingCompleted(d);
}

一次调用迁移 n 个桶，每迁完一个桶 rehashidx++，while(n-- && ht_used[0] != 0) 在旧表清空前持续推进。最关键的细节是 empty_visits = n*10：哈希表里大量位置是空桶，若不设上限，跳空桶这件事本身就可能把单次操作拖到不可控，所以最多跳过 10n 个空桶就 return 1（表示还有活没干完），把余量留给下一次调用。这就是「把 O(n) 全量迁移摊到每次操作」的核心实现——每次只动极少数桶，单步 O(1)，主线程几乎无感。

serverCron 兜底

如果某段时间没有任何读写命令触发迁移，rehash 就停顿了吗？不会。Redis 的定时任务 serverCron（默认 hz=10，约每 100ms 一次）会主动推进：

/* Rehash in us+"delta" microseconds. The value of "delta" is larger
 * than 0, and is smaller than 1000 in most cases. The exact upper bound
 * depends on the running time of dictRehash(d,100).*/
int dictRehashMicroseconds(dict *d, uint64_t us) {
    if (d->pauserehash > 0) return 0;

    monotime timer;
    elapsedStart(&timer);
    int rehashes = 0;

    while(dictRehash(d,100)) {
        rehashes += 100;
        if (elapsedUs(timer) >= us) break;
    }
    return rehashes;
}

dictRehashMicroseconds 用一个微秒级时间预算限制每次推进的上限：循环里 dictRehash(d,100) 一次批量迁 100 个桶，超过预算就 break。serverCron 通过 databasesCron 调用它，预算常量是 INCREMENTAL_REHASHING_THRESHOLD_US = 1000（即 1ms）：

        /* Rehash */
        if (server.activerehashing) {
            uint64_t elapsed_us = 0;
            for (j = 0; j < dbs_per_call; j++) {
                redisDb *db = &server.db[rehash_db % server.dbnum];
                elapsed_us += kvstoreIncrementallyRehash(db->keys, INCREMENTAL_REHASHING_THRESHOLD_US - elapsed_us);
                if (elapsed_us >= INCREMENTAL_REHASHING_THRESHOLD_US)
                    break;
                elapsed_us += kvstoreIncrementallyRehash(db->expires, INCREMENTAL_REHASHING_THRESHOLD_US - elapsed_us);
                if (elapsed_us >= INCREMENTAL_REHASHING_THRESHOLD_US)
                    break;
                rehash_db++;
            }
        }

每次最多按 1ms 的时间预算推进，到点立刻停下——用一个毫秒级的时间预算限制了 rehash 对主线程的最大影响。

rehash 期间的读写正确性

先设个问：迁移搬到一半，来了个读，Redis 怎么保证不读漏？来了个写，又怎么保证不白写？ 这是渐进式 rehash 最容易被追问的点。答案藏在一组「不对称」规则里——读要扫两张表（因为 key 可能在新表也可能还在旧表），写却只进新表（因为旧表即将被清空）。下面看源码如何把这两条规则落地。

读操作（dictFind）

static dictEntryLink dictFindLinkInternal(dict *d, const void *key, dictEntryLink *bucket) {
    dictCmpCache cmpCache = {0};
    dictEntryLink link;
    uint64_t idx;
    int table;

    if (bucket) {
        *bucket = NULL;
    } else {
        /* If dict is empty and no need to find bucket, return NULL */
        if (dictSize(d) == 0) return NULL;
    }

    const uint64_t hash = dictGetHash(d, key);
    idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[0]);
    keyCmpFunc cmpFunc = dictGetCmpFunc(d);

    /* Rehash the hash table if needed */
    _dictRehashStepIfNeeded(d,idx);

    int tables = (dictIsRehashing(d)) ? 2 : 1;
    for (table = 0; table < tables; table++) {
        if (table == 0 && (long)idx < d->rehashidx) continue;
        idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);

        link = &(d->ht_table[table][idx]);
        if (bucket) *bucket = link;
        while(link && *link) {
            const void *visitedKey = dictStoredKey2Key(d, dictGetKey(*link));

            if (key == visitedKey || cmpFunc( &cmpCache, key, visitedKey))
                return link;

            link = dictGetNextLink(*link);
        }
    }
    return NULL;
}

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntryLink link = dictFindLink(d, key, NULL);
    return (link) ? *link : NULL;
}

查找先算 hash，然后 for(table=0; table<tables; table++) 循环：没在 rehash 时 tables=1 只查 ht_table[0]，rehash 进行中 tables=2 依次查 ht_table[0] 和 ht_table[1]，保证已迁到新表的 key 不会被漏掉。if (table == 0 && idx < rehashidx) continue; 是精妙的一笔：ht_table[0] 里索引小于 rehashidx 的桶已经被迁空了，直接跳过，不在已迁移的旧桶上空找。正式查表之前先调 _dictRehashStepIfNeeded(d,idx)——读操作顺带推进一次 rehash，这正是「迁移摊到每次读写」的体现。

写操作（dictAdd）

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key __stored_key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    if (!d->type->no_value) dictSetVal(d, entry, val);
    return DICT_OK;
}
dictEntry *dictAddRaw(dict *d, void *key __stored_key, dictEntry **existing)
{
    /* Get the position for the new key or NULL if the key already exists. */
    void *position = dictFindLinkForInsert(d, dictStoredKey2Key(d, key), existing);
    if (!position) return NULL;

    /* Dup the key if necessary. */
    if (d->type->keyDup) key = d->type->keyDup(d, key);

    return dictInsertKeyAtLink(d, key, position);
}

真正干活的是 dictFindLinkForInsert，写路径的「顺带迁移 + 顺带扩容 + 双表查重」都在这里：

dictEntryLink dictFindLinkForInsert(dict *d, const void *key, dictEntry **existing) {
    unsigned long idx, table;
    dictCmpCache cmpCache = {0};
    dictEntry *he;
    uint64_t hash = dictGetHash(d, key);
    if (existing) *existing = NULL;
    idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[0]);

    /* Rehash the hash table if needed */
    _dictRehashStepIfNeeded(d,idx);

    /* Expand the hash table if needed */
    _dictExpandIfNeeded(d);
    keyCmpFunc cmpFunc = dictGetCmpFunc(d);

    for (table = 0; table <= 1; table++) {
        if (table == 0 && (long)idx < d->rehashidx) continue;
        idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        /* Search if this slot does not already contain the given key */
        he = d->ht_table[table][idx];
        while(he) {
            const void *he_key = dictStoredKey2Key(d, dictGetKey(he));
            if (key == he_key || cmpFunc(&cmpCache, key, he_key)) {
                if (existing) *existing = he;
                return NULL;
            }
            he = dictGetNext(he);
        }
        if (!dictIsRehashing(d)) break;
    }

    /* If we are in the process of rehashing the hash table, the bucket is
     * always returned in the context of the second (new) hash table. */
    dictEntry **bucket = &d->ht_table[dictIsRehashing(d) ? 1 : 0][idx];
    return bucket;
}

dictAdd → dictAddRaw → dictFindLinkForInsert，这条路径在正式插入前先 _dictRehashStepIfNeeded 推进一次 rehash，再 _dictExpandIfNeeded 判断是否要扩容——写命令同时承担了「顺带迁移」和「顺带扩容」两件事。查重循环同样查两张表，最后一行是灵魂：bucket = &d->ht_table[dictIsRehashing(d) ? 1 : 0][idx]，rehash 进行中时新 key 一律插进 ht_table[1]，绝不落进即将被清空的 ht_table[0]——这就是「写只写 ht[1]」，保证新 key 不会被误清。

rehash 完成的收尾

/* This checks if we already rehashed the whole table and if more rehashing is required */
static int dictCheckRehashingCompleted(dict *d) {
    if (d->ht_used[0] != 0) return 0;

    if (d->type->rehashingCompleted) d->type->rehashingCompleted(d);
    if (d->type->bucketChanged)
        d->type->bucketChanged(d, -(long long)DICTHT_SIZE(d->ht_size_exp[0]));
    zfree(d->ht_table[0]);
    /* Copy the new ht onto the old one */
    d->ht_table[0] = d->ht_table[1];
    d->ht_used[0] = d->ht_used[1];
    d->ht_size_exp[0] = d->ht_size_exp[1];
    _dictReset(d, 1);
    d->rehashidx = -1;
    return 1;
}

当 ht_used[0] 归零，说明旧表所有 key 都迁完了：释放 ht_table[0]、把 ht_table[1] 整体拷到 ht_table[0] 升格为正式表、_dictReset(d,1) 清空 ht_table[1]、rehashidx 复位 -1。这个收尾由 dictRehash 的 return !dictCheckRehashingCompleted(d) 触发——迁移推进与完成判定耦合在同一条路径上，每迁完一批就顺手检查一次。

触发 rehash 的条件

不是负载因子 > 1 就触发，判断逻辑里有一个三档开关 dict_can_resize：

#define HASHTABLE_MIN_FILL        8      /* Minimal hash table fill 12.5%(100/8) */
static const unsigned int dict_force_resize_ratio = 4;
/* Returning DICT_OK indicates a successful expand or the dictionary is undergoing rehashing,
 * and there is nothing else we need to do about this dictionary currently. While DICT_ERR indicates
 * that expand has not been triggered (may be try shrinking?)*/
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 (DICTHT_SIZE(d->ht_size_exp[0]) == 0) {
        dictExpand(d, DICT_HT_INITIAL_SIZE);
        return DICT_OK;
    }

    /* 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. */
    dictResizeEnable can_resize;
    atomicGet(dict_can_resize, can_resize);
    if ((can_resize == DICT_RESIZE_ENABLE &&
         d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0])) ||
        (can_resize != DICT_RESIZE_FORBID &&
         d->ht_used[0] >= dict_force_resize_ratio * DICTHT_SIZE(d->ht_size_exp[0])))
    {
        if (dictTypeResizeAllowed(d, d->ht_used[0] + 1))
            dictExpand(d, d->ht_used[0] + 1);
        return DICT_OK;
    }
    return DICT_ERR;
}
/* return DICT_ERR if expand was not performed */
int dictExpand(dict *d, unsigned long size) {
    return _dictExpand(d, size, NULL);
}

dict_can_resize 有三档：ENABLE（无子进程，放心扩容）、AVOID（有子进程，尽量不扩）、FORBID（彻底禁止）。ENABLE 档只要负载因子 ≥ 1（ht_used[0] >= 桶数）就扩容；AVOID 档要负载因子 ≥ dict_force_resize_ratio = 4 才强制扩——4 就是那个「不扩容的后果已经比 COW 更严重」的安全阀。真正分配新表、开启渐进迁移的动作在 dictExpand → _dictResize，它会分配新表并把 rehashidx 置 0：

    /* Prepare a second hash table for incremental rehashing.
     * We do this even for the first initialization, so that we can trigger the
     * rehashingStarted more conveniently, we will clean it up right after. */
    d->ht_size_exp[1] = new_ht_size_exp;
    d->ht_used[1] = new_ht_used;
    d->ht_table[1] = new_ht_table;
    d->rehashidx = 0;

为什么有子进程时不扩容？ 如果正在进行 bgsave 或 bgrewriteaof，子进程通过 COW（Copy-On-Write）共享父进程的内存。这时候触发 rehash → 分配 ht[1] 会触发 COW → 父进程的内存瞬间膨胀，大量内存页被复制。所以 Redis 在有子进程时把 dict_can_resize 置为 AVOID 尽量不扩容，除非负载因子飙升到 4 以上（此时不扩容的后果比 COW 更严重）。

缩容

当大量 key 被删除后，表空间需要回收，逻辑是扩容的镜像：

/* Returning DICT_OK indicates a successful shrinking or the dictionary is undergoing rehashing,
 * and there is nothing else we need to do about this dictionary currently. While DICT_ERR indicates
 * that shrinking has not been triggered (may be try expanding?)*/
int dictShrinkIfNeeded(dict *d) {
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the size of hash table is DICT_HT_INITIAL_SIZE, don't shrink it. */
    if (DICTHT_SIZE(d->ht_size_exp[0]) <= DICT_HT_INITIAL_SIZE) return DICT_OK;

    /* If we reached below 1:8 elements/buckets ratio, and we are allowed to resize
     * the hash table (global setting) or we should avoid it but the ratio is below 1:32,
     * we'll trigger a resize of the hash table. */
    dictResizeEnable can_resize;
    atomicGet(dict_can_resize, can_resize);
    if ((can_resize == DICT_RESIZE_ENABLE &&
         d->ht_used[0] * HASHTABLE_MIN_FILL <= DICTHT_SIZE(d->ht_size_exp[0])) ||
        (can_resize != DICT_RESIZE_FORBID &&
         d->ht_used[0] * HASHTABLE_MIN_FILL * dict_force_resize_ratio <= DICTHT_SIZE(d->ht_size_exp[0])))
    {
        if (dictTypeResizeAllowed(d, d->ht_used[0]))
            dictShrink(d, d->ht_used[0]);
        return DICT_OK;
    }
    return DICT_ERR;
}

ENABLE 档负载因子降到 1/8（HASHTABLE_MIN_FILL = 8）以下就缩容，AVOID 档降到 1/32 以下才强制缩。缩容同样走 dictShrink → _dictResize 的渐进路径，只是新表更小；rehashidx 游标与读写双表的逻辑完全复用，不需要另写一套。

总结

Redis 渐进式 rehash 的设计精髓：

  1. 拆大为小：O(n) 全量迁移 → n 次 O(1) 微步迁移，单步影响极小
  2. 顺带执行：读写命令顺便迁一个桶，无需额外调度开销
  3. 定时兜底：serverCron 按时间预算推进，防止空闲期间进展太慢
  4. 读写双表：读先 ht[0] 后 ht[1]（不漏），写只写 ht[1]（不白写）
  5. 子进程友好：fork 期间不扩容，避免 COW 引发的大规模内存复制

章末提问

追问 1：渐进式 rehash 凭什么能把 O(n) 摊成 O(1)？ 回答思路：结论——把一次性全量迁移拆成 n 个「每次只搬 1 个桶」的微步。因为每个桶的冲突链在哈希均匀时通常只有 1-2 个 key，单步就是 O(1)；这 n 步被摊到后续一次次读写命令（顺带迁）和 serverCron 的定时推进里，主线程单次只多花几十微秒，所以从每次操作的角度看代价是常数级的。

追问 2：rehash 进行到一半，读和写分别怎么处理？为什么不对称？ 回答思路：结论——读先查 ht[0] 再查 ht[1]（不漏），写只写 ht[1]（不白写）。因为读时 key 可能还没迁（在 ht[0]）也可能已迁（在 ht[1]），所以两张表都要扫；写时若还写进 ht[0]，那个桶马上要被迁走/清空，等于白写，所以新 key 一律落进 ht[1]。不对称的根源是「旧表终将被释放、新表才是归宿」。

追问 3：如果一段时间没有任何请求，rehash 会卡住吗？ 回答思路：结论——不会，有 serverCron 兜底。因为 serverCron（默认 hz=10，约每 100ms 一次）会调用 dictRehashMicroseconds，按 1ms 的时间预算批量推进（每次 dictRehash(d,100)），到点立刻 break。这样即使完全空闲，迁移也在后台慢慢推进，且主线程每次最多被占用 1ms，无感。

追问 4：为什么 bgsave/bgrewriteaof 期间要尽量避免扩容？什么时候才会强制扩？ 回答思路：结论——为了躲 COW 内存暴涨，负载因子 ≥ 4 时强制扩。因为 fork 出的子进程通过 Copy-On-Write 与父进程共享内存，此时扩容会分配新表、改写大量内存页，触发 COW 让父进程内存瞬间翻倍式膨胀。所以有子进程时 dict_can_resize 置为 AVOID 尽量不扩；但若负载因子飙到 4（dict_force_resize_ratio），说明冲突已经严重到「不扩的代价 > COW 的代价」，此时仍要强制扩。

追问 5：rehashidx 的 -1、0、中间值、完成分别代表什么？ 回答思路：结论——-1 表示不在 rehash，>=0 表示正在迁移且「ht[0] 中索引小于它的桶都已迁完」。因为 dictIsRehashing 就是判断 rehashidx != -1；开启迁移时 _dictResize 把它置 0，表示从桶 0 开始搬；每迁完一个桶 rehashidx++；当 ht[0] 的 used 归零、收尾函数 dictCheckRehashingCompleted 释放旧表并把 ht[1] 升格后，再把它复位为 -1。它是「渐进进度」的唯一权威记录。

Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
ZipList连锁更新到listpack——Redis压缩列表的演进
Next Post
Redisson分布式锁的Lua脚本实现