MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Redis 字典实现机制深度剖析

2024-10-085.2k 阅读

Redis 字典数据结构基础

Redis 的字典（dict）是其内部实现的一种非常重要的数据结构，用于实现 Redis 的各种数据类型，比如哈希表（Hash）。字典为 Redis 提供了一种键值对（key - value）的存储方式，这种存储方式允许快速地根据键找到对应的值。

在 Redis 中，字典是基于哈希表实现的。哈希表是一种根据键的哈希值直接访问数据的数据结构，它能在平均情况下以常数时间复杂度 O(1) 完成查找、插入和删除操作。

哈希表结构

Redis 的哈希表结构定义在 dict.h 头文件中，其核心结构如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
  • table：是一个数组，数组的每个元素都是一个指向 dictEntry 结构的指针。dictEntry 结构用于存储键值对数据。
  • size：表示哈希表的大小，即 table 数组的长度。
  • sizemask：是 size - 1 的值，用于计算键的哈希值在 table 数组中的索引位置。通过 hash & sizemask 可以将哈希值映射到 table 数组的有效索引范围内。
  • used：记录哈希表中已使用的节点数量。

字典结构

字典结构 dict 包含了两个哈希表，主要用于实现渐进式 rehash，定义如下：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;
  • type：指向一个 dictType 结构的指针，该结构定义了一系列操作函数，用于处理不同类型的键值对，比如计算键的哈希值、复制键和值、释放键和值等操作。
  • privdata：是一个指针，用于传递一些私有数据给 dictType 结构中定义的函数。
  • ht：是一个包含两个 dictht 结构的数组，通常情况下，只有 ht[0] 会被使用，当需要进行 rehash 操作时，ht[1] 会被用来协助完成 rehash。
  • rehashidx：用于记录 rehash 进行的进度。当 rehashidx == -1 时，表示当前没有进行 rehash 操作；否则，它记录了当前正在 rehash 的 ht[0] 数组的索引位置。
  • iterators：记录当前正在运行的迭代器数量，用于防止在迭代过程中进行 rehash 操作，避免数据一致性问题。

键值对存储 - dictEntry 结构

dictEntry 结构用于实际存储键值对数据，它在哈希表中以链表的形式解决哈希冲突。定义如下：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
  • key：指向键的指针，键可以是任意类型，具体取决于使用的 dictType 中的操作函数。
  • v：是一个联合体，用于存储值。它可以存储指针类型的值（void *val），也可以存储整数类型（uint64_t u64 和 int64_t s64）或双精度浮点数（double d），这使得 dictEntry 能够灵活地存储不同类型的值。
  • next：指向下一个 dictEntry 结构的指针，用于处理哈希冲突。当多个键的哈希值映射到哈希表的同一位置时，这些键值对会通过 next 指针链接成一个链表。

哈希函数与哈希值计算

Redis 使用 MurmurHash2 算法来计算键的哈希值。MurmurHash2 是一种非加密型哈希函数，具有较高的运算速度和较好的哈希分布特性。在 Redis 中，哈希函数的调用是通过 dictType 结构中的 hashFunction 函数指针来实现的。

在 dict.c 文件中，哈希函数的调用逻辑大致如下：

unsigned int dictGenHashFunction(const void *key, int len) {
    // 通过dict->type->hashFunction获取具体的哈希函数
    return dict->type->hashFunction(key, len);
}

这里 dict->type->hashFunction 会指向 MurmurHash2 实现的哈希函数，比如在默认的字符串键值对处理中，会使用如下方式计算哈希值：

// 假设这里的dict是已初始化的字典
unsigned int hash = dictGenHashFunction(key, strlen(key));

计算得到的哈希值 hash 会进一步与 sizemask 进行按位与操作，以确定键值对在哈希表 table 数组中的存储位置：

unsigned int index = hash & dict->ht[x].sizemask;

其中 x 通常为 0，除非正在进行 rehash 操作。

哈希冲突解决 - 链地址法

当不同的键通过哈希函数计算得到相同的哈希值，即发生哈希冲突时，Redis 使用链地址法来解决。在 Redis 的哈希表中，每个 table 数组元素都是一个链表头指针，当有多个键值对映射到同一个数组位置时，这些键值对会通过 dictEntry 结构的 next 指针链接成一个链表。

例如，假设有三个键 key1、key2 和 key3，它们通过哈希函数计算得到的哈希值都映射到哈希表 table 数组的第 i 个位置。那么，哈希表的存储结构如下：

table[i] -> dictEntry(key1, value1) -> dictEntry(key2, value2) -> dictEntry(key3, value3)

在查找某个键时，首先根据哈希值计算出数组索引位置，然后沿着链表逐个比较键，直到找到目标键或链表结束。插入新键值对时，新的 dictEntry 会被插入到链表头部，这样可以在 O(1) 的时间复杂度内完成插入操作。

Rehash 机制

随着数据的不断插入和删除，哈希表的负载因子（load factor = used / size）会发生变化。当负载因子过高时，哈希表的性能会下降，因为链表会变得更长，查找、插入和删除操作的时间复杂度会趋近于 O(n)。为了保持哈希表的高性能，Redis 引入了 rehash 机制。

Rehash 触发条件

  • 当哈希表的负载因子大于等于 1 且 redis.hz（Redis 的运行频率，默认 10）大于 0 时，会触发 rehash。这意味着当哈希表中已使用的节点数量达到或超过哈希表大小时，并且 Redis 正在以一定频率运行，就会开始 rehash 操作。
  • 当哈希表的负载因子小于 0.1 时，也会触发 rehash，这种情况通常是在大量删除操作后，哈希表变得非常稀疏，通过 rehash 可以减少内存占用。

Rehash 过程

  1. 分配新的哈希表：根据当前哈希表的情况，为 ht[1] 分配一个合适大小的哈希表。如果是因为负载因子过高触发的 rehash，新哈希表的大小通常是原哈希表大小的两倍；如果是因为负载因子过低触发的 rehash，新哈希表的大小通常是原哈希表大小的一倍。
  2. 将旧哈希表数据迁移到新哈希表：逐步将 ht[0] 中的所有键值对重新计算哈希值并插入到 ht[1] 中。这个过程不是一次性完成的，而是分多次进行，每次处理一小部分数据，以避免在 rehash 过程中阻塞 Redis 服务器。
  3. 切换哈希表：当 ht[0] 中的所有键值对都迁移到 ht[1] 后，将 ht[1] 赋值给 ht[0]，并释放 ht[1]，同时将 rehashidx 设为 -1，表示 rehash 操作完成。

渐进式 Rehash

为了避免在 rehash 过程中长时间占用 CPU，影响 Redis 的正常服务，Redis 采用渐进式 rehash 方式。在渐进式 rehash 过程中，rehashidx 记录了当前正在 rehash 的 ht[0] 数组的索引位置。每次执行哈希表相关操作（如查找、插入、删除）时，除了执行正常的操作外，还会顺便将 ht[0] 中 rehashidx 位置的键值对迁移到 ht[1] 中，并将 rehashidx 加 1。这样，随着时间的推移，ht[0] 中的所有键值对会逐步迁移到 ht[1] 中。

例如，在执行查找操作时，Redis 会先在 ht[0] 中查找键，如果找不到，再在 ht[1] 中查找。在插入操作时，如果 rehashidx != -1，表示正在进行 rehash，新的键值对会被插入到 ht[1] 中。

字典操作函数实现

Redis 提供了一系列操作字典的函数，包括创建字典、插入键值对、查找键值对、删除键值对等。

创建字典

dict *dictCreate(dictType *type, void *privDataPtr) {
    dict *d = zmalloc(sizeof(*d));
    if (!d) return NULL;
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;
    if (dictExpand(d, DICT_HT_INITIAL_SIZE) == DICT_ERR) {
        zfree(d);
        return NULL;
    }
    return d;
}

该函数首先为字典分配内存空间，然后初始化字典的各个字段，包括 type、privdata、rehashidx 和 iterators。最后通过 dictExpand 函数为 ht[0] 分配初始大小的哈希表。

插入键值对

int dictAdd(dict *d, void *key, void *val) {
    dictEntry *entry = dictAddRaw(d, key);
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictAdd 函数首先调用 dictAddRaw 函数尝试在哈希表中插入键。dictAddRaw 函数会检查键是否已存在，如果不存在，则分配一个新的 dictEntry 并插入到哈希表中。如果键已存在，则返回 NULL。如果插入成功，dictAdd 函数会调用 dictSetVal 函数设置键对应的值。

查找键值对

dictEntry *dictFind(dict *d, const void *key) {
    dictEntry *he;
    unsigned int h, idx, table;
    if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while (he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (d->rehashidx == -1) break;
    }
    return NULL;
}

dictFind 函数首先计算键的哈希值 h，然后在 ht[0] 和 ht[1] 中查找键。在每个哈希表中，通过 h & sizemask 计算出索引位置 idx，然后沿着链表查找键。如果在 ht[0] 中没有找到，并且正在进行 rehash（rehashidx != -1），则继续在 ht[1] 中查找。

删除键值对

int dictDelete(dict *d, const void *key) {
    return dictGenericDelete(d, key, 0);
}

dictDelete 函数调用 dictGenericDelete 函数来删除键值对。dictGenericDelete 函数首先查找要删除的 dictEntry，如果找到，则从哈希表链表中删除该节点，并释放相关内存。在删除过程中，如果正在进行 rehash，会对 ht[0] 和 ht[1] 进行相应处理。

字典在 Redis 中的应用

Redis 的哈希数据类型（Hash）就是基于字典实现的。当用户执行 HSET、HGET、HDEL 等命令时，Redis 内部实际上是调用字典的操作函数来完成这些操作。

例如，执行 HSET myhash field1 value1 命令时，Redis 会将 myhash 作为外层键，field1 作为内层键，value1 作为值，通过字典的插入操作将这个键值对存储起来。在执行 HGET myhash field1 命令时，Redis 会通过字典的查找操作获取对应的值。

此外，Redis 的数据库也是一个字典结构，每个数据库都包含一个字典，用于存储所有的键值对。这使得 Redis 能够快速地根据键找到对应的值，实现高效的数据存储和检索。

通过深入了解 Redis 字典的实现机制，我们可以更好地理解 Redis 的性能特点、内存管理以及数据处理方式，为优化 Redis 应用和深入开发提供有力的支持。无论是在高并发场景下的数据存储，还是在大数据量情况下的性能调优，对字典实现机制的掌握都至关重要。同时，了解这些底层实现细节，也有助于我们更好地理解其他基于哈希表的数据结构和算法，提升在计算机开发领域的技术水平。