Redis 字典 rehash 的底层原理揭秘

Redis 字典简介

Redis 是一个高性能的键值对存储系统，其中字典（dict）是 Redis 中非常重要的数据结构，它被广泛应用于 Redis 的数据库实现以及各种数据结构的底层存储，例如 Redis 的哈希表（Hash）结构就是基于字典实现的。

Redis 的字典实现采用了哈希表（Hash Table）结构，哈希表是一种根据关键码值（Key Value）直接进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

在 Redis 中，字典结构定义在 dict.h 头文件中，主要包含以下关键部分：

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;

type：一个指向 dictType 结构的指针，dictType 定义了针对不同类型键值对的操作函数，例如计算哈希值的函数、比较键的函数等。
privdata：私有数据指针，配合 type 字段使用，用于传递一些特定于应用场景的数据。
ht：是一个包含两个 dictht 类型的数组，dictht 代表哈希表，在 rehash 过程中，会使用这两个哈希表来完成数据迁移。
rehashidx：记录 rehash 进度，如果值为 -1，表示当前没有进行 rehash 操作。
iterators：记录当前正在运行的迭代器数量，用于确保在迭代字典时不会进行 rehash 操作，避免数据不一致。

而 dictht 结构定义如下：

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

table：是一个指向 dictEntry 指针数组的指针，dictEntry 代表哈希表中的一个节点，存储了键值对数据。
size：哈希表的大小，即 table 数组的长度。
sizemask：用于计算哈希值在 table 数组中的索引位置，值为 size - 1。
used：记录哈希表中已使用的节点数量。

哈希冲突与解决办法

在哈希表的使用过程中，不可避免地会出现哈希冲突，即不同的键通过哈希函数计算得到相同的哈希值，从而映射到哈希表的同一个位置。Redis 采用链地址法（Separate Chaining）来解决哈希冲突。

在 Redis 的字典实现中，当发生哈希冲突时，多个 dictEntry 会以链表的形式连接在一起，这些节点都映射到哈希表数组的同一个位置。dictEntry 结构定义如下：

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

key：键指针，指向存储的键。
v：一个联合体，用于存储值，可以是指针、整数或者浮点数。
next：指向下一个 dictEntry 节点的指针，用于解决哈希冲突，形成链表。

rehash 触发条件

Redis 字典的 rehash 操作并不是随时都会发生的，它是在满足一定条件下才会触发。主要的触发条件与哈希表的负载因子（load factor）有关，负载因子的计算公式为： load factor = used / size

扩展（Expansion）：当负载因子大于等于 1 且 Redis 没有在执行 BGSAVE 或 BGREWRITEAOF 命令时，会触发扩展操作。这是因为当负载因子达到 1 时，说明哈希表已经接近满负荷状态，继续插入新元素可能会导致哈希冲突加剧，降低查询性能，所以需要扩展哈希表以提高性能。
收缩（Shrinkage）：当负载因子小于 0.1 时，会触发收缩操作。这是为了释放不必要的内存空间，提高内存利用率。

rehash 过程解析

分配新的哈希表空间：当触发 rehash 时，如果是扩展操作，会分配一个大小为原哈希表 ht[0] 大小两倍的新哈希表 ht[1]；如果是收缩操作，则会分配一个大小为原哈希表 ht[0] 大小四分之一的新哈希表 ht[1]。
迁移数据：将 ht[0] 中的所有键值对逐步迁移到 ht[1] 中。在迁移过程中，Redis 并不是一次性将所有数据迁移完，而是采用渐进式 rehash 的方式。这是因为 Redis 是单线程模型，如果一次性迁移大量数据，可能会导致 Redis 在一段时间内无法处理其他客户端请求，影响性能。

渐进式 rehash 通过 rehashidx 字段来记录当前的迁移进度。rehashidx 初始值为 0，表示从 ht[0] 的第一个桶开始迁移。每次执行字典相关操作（如插入、删除、查找等）时，除了执行原操作外，还会顺带将 ht[0] 中 rehashidx 指向的桶中的所有键值对迁移到 ht[1] 中，并将 rehashidx 加 1。当 rehashidx 等于 ht[0].size 时，说明 ht[0] 中的所有键值对都已迁移完毕，此时将 ht[1] 赋值给 ht[0]，释放 ht[1] 的空间，并将 rehashidx 设为 -1，表示 rehash 操作完成。

调整指针：在迁移完成后，将 ht[0] 指向新的哈希表（即原来的 ht[1]），并释放 ht[1] 原来的空间。同时，将 rehashidx 设为 -1，标志着 rehash 操作结束。

代码示例

以下是一个简化版的 Redis 字典 rehash 过程的模拟代码示例，以 C 语言为例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DICT_OK 0
#define DICT_ERR 1

// 定义字典节点
typedef struct dictEntry {
    char *key;
    int value;
    struct dictEntry *next;
} dictEntry;

// 定义哈希表
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

// 定义字典
typedef struct dict {
    dictht ht[2];
    int rehashidx;
} dict;

// 初始化字典
int dictInit(dict *d) {
    d->ht[0].size = 4;
    d->ht[0].sizemask = d->ht[0].size - 1;
    d->ht[0].used = 0;
    d->ht[0].table = (dictEntry **)malloc(d->ht[0].size * sizeof(dictEntry *));
    if (!d->ht[0].table) return DICT_ERR;
    memset(d->ht[0].table, 0, d->ht[0].size * sizeof(dictEntry *));

    d->ht[1].size = 0;
    d->ht[1].sizemask = 0;
    d->ht[1].used = 0;
    d->ht[1].table = NULL;

    d->rehashidx = -1;
    return DICT_OK;
}

// 计算哈希值
unsigned long dictHashFunction(const char *key) {
    unsigned long hash = 5381;
    int c;
    while ((c = *key++))
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    return hash;
}

// 插入键值对
int dictAdd(dict *d, const char *key, int value) {
    unsigned long h;
    dictEntry *entry;

    if (d->rehashidx != -1) return DICT_ERR;

    h = dictHashFunction(key) & d->ht[0].sizemask;
    entry = d->ht[0].table[h];
    while (entry) {
        if (strcmp(entry->key, key) == 0) return DICT_ERR;
        entry = entry->next;
    }

    entry = (dictEntry *)malloc(sizeof(dictEntry));
    if (!entry) return DICT_ERR;
    entry->key = strdup(key);
    entry->value = value;
    entry->next = d->ht[0].table[h];
    d->ht[0].table[h] = entry;
    d->ht[0].used++;

    // 检查是否需要 rehash
    if (d->ht[0].used >= d->ht[0].size) {
        d->rehashidx = 0;
        d->ht[1].size = d->ht[0].size * 2;
        d->ht[1].sizemask = d->ht[1].size - 1;
        d->ht[1].used = 0;
        d->ht[1].table = (dictEntry **)malloc(d->ht[1].size * sizeof(dictEntry *));
        if (!d->ht[1].table) return DICT_ERR;
        memset(d->ht[1].table, 0, d->ht[1].size * sizeof(dictEntry *));
    }

    return DICT_OK;
}

// 渐进式 rehash
void dictRehashStep(dict *d) {
    if (d->rehashidx == -1) return;

    while (d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;

    dictEntry *entry = d->ht[0].table[d->rehashidx];
    dictEntry *next;
    while (entry) {
        next = entry->next;
        unsigned long h = dictHashFunction(entry->key) & d->ht[1].sizemask;
        entry->next = d->ht[1].table[h];
        d->ht[1].table[h] = entry;
        d->ht[0].used--;
        d->ht[1].used++;
        entry = next;
    }

    d->ht[0].table[d->rehashidx] = NULL;
    d->rehashidx++;

    if (d->rehashidx == d->ht[0].size) {
        free(d->ht[0].table);
        d->ht[0] = d->ht[1];
        d->ht[1].size = 0;
        d->ht[1].sizemask = 0;
        d->ht[1].used = 0;
        d->ht[1].table = NULL;
        d->rehashidx = -1;
    }
}

// 查找键值对
int dictFind(dict *d, const char *key) {
    unsigned long h;
    dictEntry *entry;

    if (d->rehashidx != -1) {
        h = dictHashFunction(key) & d->ht[1].sizemask;
        entry = d->ht[1].table[h];
        while (entry) {
            if (strcmp(entry->key, key) == 0) return entry->value;
            entry = entry->next;
        }
    }

    h = dictHashFunction(key) & d->ht[0].sizemask;
    entry = d->ht[0].table[h];
    while (entry) {
        if (strcmp(entry->key, key) == 0) return entry->value;
        entry = entry->next;
    }

    return -1;
}

// 释放字典
void dictRelease(dict *d) {
    int i;
    dictEntry *entry, *next;

    for (i = 0; i < d->ht[0].size; i++) {
        entry = d->ht[0].table[i];
        while (entry) {
            next = entry->next;
            free(entry->key);
            free(entry);
            entry = next;
        }
    }
    free(d->ht[0].table);

    if (d->ht[1].table) {
        for (i = 0; i < d->ht[1].size; i++) {
            entry = d->ht[1].table[i];
            while (entry) {
                next = entry->next;
                free(entry->key);
                free(entry);
                entry = next;
            }
        }
        free(d->ht[1].table);
    }
}

int main() {
    dict d;
    if (dictInit(&d) != DICT_OK) {
        printf("Dict init failed\n");
        return 1;
    }

    dictAdd(&d, "key1", 1);
    dictAdd(&d, "key2", 2);
    dictAdd(&d, "key3", 3);
    dictAdd(&d, "key4", 4);
    dictAdd(&d, "key5", 5);

    printf("Find key1: %d\n", dictFind(&d, "key1"));

    // 执行渐进式 rehash
    for (int i = 0; i < 4; i++) {
        dictRehashStep(&d);
    }

    printf("Find key2: %d\n", dictFind(&d, "key2"));

    dictRelease(&d);
    return 0;
}

rehash 过程中的注意事项

迭代器：在 Redis 字典中，当存在活跃的迭代器时，是不允许进行 rehash 操作的。这是因为迭代器是基于当前哈希表结构进行遍历的，如果在遍历过程中进行 rehash，可能会导致迭代器遍历到错误的数据或者出现数据遗漏、重复遍历等问题。所以，只有当 iterators 为 0 时，才会触发 rehash 操作。
数据一致性：由于采用渐进式 rehash，在 rehash 过程中，字典的部分数据在 ht[0] 中，部分数据在 ht[1] 中。因此，在执行查找、删除等操作时，需要同时在 ht[0] 和 ht[1] 中进行查找，以确保数据的一致性和正确性。
性能影响：虽然渐进式 rehash 避免了一次性迁移大量数据带来的性能问题，但在 rehash 过程中，每次字典操作都会额外增加迁移数据的开销。因此，在高并发场景下，频繁的 rehash 操作可能会对 Redis 的整体性能产生一定影响。为了减少这种影响，合理设置哈希表的初始大小，避免频繁触发 rehash 是非常重要的。

总结

Redis 字典的 rehash 机制是其高效运行的关键之一。通过渐进式 rehash，Redis 在扩展和收缩哈希表时，既能保证数据的平稳迁移，又能最大程度地减少对正常操作的性能影响。理解 rehash 的底层原理，对于优化 Redis 的性能、合理使用 Redis 以及排查相关性能问题都具有重要意义。无论是在应用开发中对 Redis 的使用，还是对 Redis 自身进行深入研究和优化，掌握 rehash 原理都是必不可少的。通过本文的介绍以及代码示例，希望读者能够对 Redis 字典 rehash 的底层原理有更深入、清晰的认识。