Redis rehash 的触发条件与时机选择

Redis 哈希表基础

在深入探讨 Redis rehash 的触发条件与时机选择之前，我们先来了解一下 Redis 哈希表的基本结构。Redis 采用了一种双哈希表的结构来实现字典（dictionary），这种结构在许多场景下表现出色，能高效地进行查找、插入和删除操作。

Redis 中的字典由 dict 结构体表示，它包含两个 dictht 哈希表：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

这里的 ht[2] 就是两个哈希表，通常情况下，只有 ht[0] 用于存储数据，ht[1] 只有在 rehash 过程中才会发挥作用。

dictht 结构体定义如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

其中，table 是一个数组，数组的每个元素都是一个指向 dictEntry 结构体的指针。dictEntry 结构体用于存储键值对：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

next 指针用于解决哈希冲突，采用链地址法。

Redis rehash 过程概述

Redis 的 rehash 过程主要分为以下几个步骤：

分配空间：为 ht[1] 分配空间，这个空间的大小取决于 ht[0] 中已有元素的数量以及特定的规则。
数据迁移：将 ht[0] 中的所有键值对重新计算哈希值并插入到 ht[1] 中。
切换指针：当 ht[0] 中的所有数据都迁移到 ht[1] 后，将 ht[1] 赋值给 ht[0]，并释放 ht[1] 所占用的空间，同时重置 rehashidx 为 -1，表示 rehash 过程结束。

Redis rehash 触发条件

负载因子过高：Redis 会计算哈希表的负载因子（load factor），负载因子的计算公式为 load_factor = ht[0].used / ht[0].size。当负载因子达到一定阈值时，就会触发 rehash。在 Redis 中，这个阈值默认为 1。也就是说，当 ht[0] 中的元素数量 used 等于 ht[0] 的大小 size 时，就有可能触发 rehash。
主动触发：除了负载因子触发外，Redis 还提供了一些主动触发 rehash 的机制。例如，在 Redis 启动时，如果检测到 ht[0] 中的元素数量过多且负载因子过高，也会触发 rehash。此外，当执行一些特定的管理命令（如 FLUSHDB）时，也可能会触发 rehash 操作。

负载因子触发 rehash 的具体实现

在 Redis 的源码中，dictExpandIfNeeded 函数负责检查是否需要进行 rehash。以下是简化后的代码实现：

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;
}

在这段代码中，首先检查是否正在进行 rehash（dictIsRehashing 函数判断 rehashidx 是否为 -1）。如果没有进行 rehash，并且 ht[0] 为空，则将其扩展为初始大小。如果 ht[0] 的负载因子达到 1 且满足重新调整大小的条件（dict_can_resize 为真或者负载因子超过 dict_force_resize_ratio），则调用 dictExpand 函数进行扩展，这里是将 ht[0] 的大小扩展为当前 used 数量的两倍。

主动触发 rehash 的实现

以 FLUSHDB 命令为例，在执行这个命令时，会调用 dictEmpty 函数。在 dictEmpty 函数中，如果 rehashidx 不为 -1，即正在进行 rehash，会先完成剩余的 rehash 操作，然后再清空哈希表。以下是简化后的代码：

void dictEmpty(dict *d, void(callback)(void *)) {
    unsigned long i;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    for (i = 0; i < d->ht[0].size; i++) {
        dictEntry *he, *nextHe;

        if ((he = d->ht[0].table[i]) == NULL) continue;
        while(he) {
            nextHe = he->next;
            if (callback) callback(he->key);
            dictFreeVal(d, he);
            zfree(he);
            he = nextHe;
        }
        d->ht[0].table[i] = NULL;
    }
    zfree(d->ht[0].table);
    d->ht[0].table = NULL;
    d->ht[0].size = 0;
    d->ht[0].sizemask = 0;
    d->ht[0].used = 0;
    d->rehashidx = -1;
}

在这个过程中，先调用 _dictRehashStep 函数完成剩余的 rehash 步骤，然后再遍历 ht[0] 并释放所有的键值对和相关内存。

Redis rehash 时机选择

渐进式 rehash：为了避免在 rehash 过程中因为一次性迁移大量数据而导致 Redis 服务停顿，Redis 采用了渐进式 rehash 机制。在渐进式 rehash 过程中，Redis 不会一次性将 ht[0] 中的所有数据迁移到 ht[1]，而是每次在执行一些字典操作（如插入、查找、删除）时，顺带迁移一小部分数据。
时机选择的影响因素：渐进式 rehash 的时机选择需要考虑多个因素。一方面，要保证 rehash 能够及时完成，以避免哈希表性能因为负载因子过高而下降。另一方面，又不能因为频繁的 rehash 操作而影响正常的读写性能。
实际应用中的时机考量：在实际应用中，如果 Redis 实例的读写负载较高，应该尽量避免在业务高峰期进行 rehash。可以通过监控 Redis 的负载因子、请求响应时间等指标，选择在负载较低的时间段进行主动触发 rehash。同时，渐进式 rehash 的步长也可以根据实际情况进行调整，如果负载较高，可以适当减小每次迁移的数据量，以降低对正常业务的影响。

渐进式 rehash 的实现

Redis 通过 rehashidx 变量来记录 rehash 的进度。rehashidx 初始值为 -1，表示没有进行 rehash。当开始 rehash 时，rehashidx 被设置为 0，然后每次在执行字典操作时，会调用 _dictRehashStep 函数进行一小步的 rehash。以下是 _dictRehashStep 函数的简化实现：

int _dictRehashStep(dict *d) {
    int empty_visits = 0;
    if (!dictIsRehashing(d)) return 0;

    while(1) {
        dictEntry *de;

        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;
        }

        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (++empty_visits > dict_force_resize_ratio) return 0;
        }
        de = d->ht[0].table[d->rehashidx];
        while(de) {
            dictEntry *next = de->next;
            unsigned int 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 = next;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
        if (d->rehashidx >= d->ht[0].size) return 0;
    }
}

在这个函数中，首先检查是否正在进行 rehash。如果 ht[0] 中的所有数据都已迁移完，则完成 rehash 过程并清理相关资源。否则，从 ht[0] 的 rehashidx 位置开始，迁移该位置链表上的所有键值对到 ht[1]，然后将 rehashidx 指向下一个位置。如果连续遇到多个空桶（超过 dict_force_resize_ratio 定义的数量），则暂时停止本次 rehash 操作。

示例代码模拟 Redis rehash

下面我们用 Python 代码来模拟 Redis 的 rehash 过程，以帮助更好地理解：

class Dict:
    def __init__(self):
        self.ht = [{}, {}]
        self.rehashidx = -1
        self.used = 0

    def add(self, key, value):
        if self.rehashidx != -1:
            self._rehash_step()
        if self.used >= len(self.ht[0]) and self.rehashidx == -1:
            self._start_rehash()
        hash_value = hash(key) % len(self.ht[0])
        self.ht[0][hash_value] = (key, value)
        self.used += 1

    def _start_rehash(self):
        self.rehashidx = 0
        self.ht[1] = {}
        new_size = len(self.ht[0]) * 2
        self.ht[1] = [None] * new_size

    def _rehash_step(self):
        while self.ht[0][self.rehashidx] is None:
            self.rehashidx += 1
            if self.rehashidx >= len(self.ht[0]):
                self._finish_rehash()
                return
        key, value = self.ht[0][self.rehashidx]
        hash_value = hash(key) % len(self.ht[1])
        self.ht[1][hash_value] = (key, value)
        self.ht[0][self.rehashidx] = None
        self.rehashidx += 1
        if self.rehashidx >= len(self.ht[0]):
            self._finish_rehash()

    def _finish_rehash(self):
        self.ht[0] = self.ht[1]
        self.ht[1] = {}
        self.rehashidx = -1

    def get(self, key):
        if self.rehashidx != -1:
            self._rehash_step()
        hash_value = hash(key) % len(self.ht[0])
        return self.ht[0].get(hash_value)

在这段代码中，Dict 类模拟了 Redis 的字典结构。add 方法用于添加键值对，在添加时会检查是否需要进行 rehash，如果需要则开始或继续渐进式 rehash。_start_rehash 方法初始化 rehash 过程，为 ht[1] 分配空间。_rehash_step 方法执行一小步的 rehash 操作，将 ht[0] 中的一个键值对迁移到 ht[1]。_finish_rehash 方法完成 rehash 过程，将 ht[1] 赋值给 ht[0] 并重置相关状态。get 方法在获取值时也会顺带执行 rehash 操作，以确保哈希表的一致性。

不同场景下 rehash 的优化策略

读多写少场景：在这种场景下，由于写操作相对较少，rehash 对整体性能的影响相对较小。可以适当放宽负载因子的阈值，延迟 rehash 的触发，以减少 rehash 的频率。例如，可以将负载因子阈值从 1 调整到 1.2 或更高，这样可以在一定程度上减少 rehash 带来的开销，同时又不会因为负载因子过高而导致哈希表性能急剧下降。
写多读少场景：写操作频繁时，rehash 对性能的影响更为明显。此时应该更加关注渐进式 rehash 的步长。可以适当减小每次迁移的数据量，使得 rehash 过程更加平滑，减少对写操作的阻塞。例如，原本每次迁移一个链表上的所有键值对，可以改为每次只迁移链表上的部分键值对。
高并发场景：在高并发场景下，需要特别注意 rehash 对并发性能的影响。一方面，要避免在高并发时段主动触发 rehash。另一方面，在渐进式 rehash 过程中，要确保 rehash 操作与并发读写操作之间的同步机制合理。可以采用读写锁等方式，在进行 rehash 时，允许读操作并发执行，但对写操作进行一定的限制，以保证数据的一致性。

总结 rehash 触发条件与时机选择要点

触发条件：主要由负载因子过高和主动触发两种方式。负载因子过高是自动触发 rehash 的常见原因，当负载因子达到阈值（默认为 1）时，会根据具体情况决定是否进行 rehash。主动触发则是通过特定命令或启动时的检测来进行。
时机选择：渐进式 rehash 是 Redis 处理 rehash 的关键机制，它能有效避免因一次性迁移大量数据而导致服务停顿。在时机选择上，要综合考虑系统的负载情况，尽量在负载较低的时段进行主动触发 rehash，同时合理调整渐进式 rehash 的步长，以平衡 rehash 进度和正常业务的性能。

通过深入理解 Redis rehash 的触发条件与时机选择，我们可以更好地优化 Redis 的性能，使其在不同的应用场景下都能高效稳定地运行。无论是在开发新的应用，还是对现有 Redis 部署进行调优，这些知识都具有重要的指导意义。