redis底层结构-Dict

'# Redis底层结构-Dict

一、背景与问题

在分布式系统中，键值对存储是核心的存储方式。Redis 作为高性能的内存数据库，其核心数据结构之一就是 dict（字典）。在实际开发中，我们经常遇到需要快速查找、插入和删除键值对的场景，例如缓存系统、会话管理、配置存储等。

然而，开发人员往往只关注如何使用 Redis 的 API（如 set、get 等），而对其底层结构和实现原理缺乏深入理解。这可能导致对性能瓶颈、内存占用、并发安全等问题的误判。例如：

为什么 Redis 在高并发场景下会存在性能瓶颈？
为什么 HSET 操作在某些情况下会比 SET 更快？
为什么 Redis 的 EXPIRE 命令会引发内存泄漏风险？

本文将深入剖析 Redis 的 dict 结构，从底层实现原理出发，结合代码示例和实际场景，揭示其工作原理和使用技巧。

二、基本原理

1. Redis 的 `dict` 架构

Redis 的 dict 是一个基于哈希表的键值对存储结构，其核心结构包含以下几个关键组件：

哈希表（HashTable）：核心数据存储结构，由多个 dictEntry 节点组成。
哈希函数：将键转换为数组下标的函数（Redis 使用 MurmurHash3）。
冲突处理机制：采用链地址法处理哈希冲突。
扩容机制：当负载因子超过阈值时，自动扩容哈希表。

2. 哈希表的结构

Redis 的哈希表由两个数组组成：

typedef struct dict {
    dictEntry **table; // 哈希表数组
    dictEntry *rehashidx; // 重哈希索引
    int size; // 当前哈希表大小
    int size_used; // 已使用的节点数
    // 其他字段...
} dict;

每个 dictEntry 包含键值对：

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next; // 冲突链表的下一个节点
};

3. 哈希函数与冲突处理

Redis 使用 MurmurHash3 作为默认的哈希函数，其优点是：

分布均匀：避免哈希碰撞。
计算速度快：适用于高性能场景。

当发生哈希冲突时，Redis 采用链地址法，将冲突的键值对存入链表中。

三、环境准备

为了便于理解，我们使用 C 语言模拟 Redis 的 dict 结构。以下是环境准备：

编译器：支持 C11 标准的编译器（如 GCC）。
开发工具：VSCode 或任何支持 C 的 IDE。
代码结构：包含哈希表的创建、插入、查找和扩容操作。

四、核心实现

1. 哈希表的初始化

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;

typedef struct dict {
    dictEntry **table;
    int size;
    int size_used;
    int rehashidx;
    // 其他字段...
} dict;

dict *dictCreate(int size) {
    dict *d = (dict *)malloc(sizeof(dict));
    d->size = size;
    d->size_used = 0;
    d->rehashidx = -1;
    d->table = (dictEntry **)calloc(size, sizeof(dictEntry *));
    return d;
}

关键代码解释：

size：哈希表的容量。
rehashidx：重哈希索引，用于标记是否正在进行扩容。
calloc：初始化哈希表数组为 NULL，避免野指针。

2. 哈希函数实现

unsigned int dictHashKey(dict *d, const void *key) {
    return MurmurHash3(key, 1, 0); // 使用 MurmurHash3 哈希函数
}

关键代码解释：

MurmurHash3 是一个高效的哈希函数，其性能比 CRC32 更好。
哈希值用于计算键在哈希表中的索引位置。

3. 插入操作（`dictSet`）

int dictSet(dict *d, void *key, void *val) {
    unsigned int h = dictHashKey(d, key);
    dictEntry *entry = d->table[h];
    while (entry) {
        if (entry->key == key) {
            entry->val = val;
            return 0;
        }
        entry = entry->next;
    }
    entry = (dictEntry *)malloc(sizeof(dictEntry));
    entry->key = key;
    entry->val = val;
    entry->next = d->table[h];
    d->table[h] = entry;
    d->size_used++;
    return 1;
}

关键代码解释：

通过哈希函数计算 key 的索引 h。
遍历链表查找是否存在相同键，若存在则更新值。
若不存在，则创建新节点并插入链表。

五、完整案例

场景：缓存系统实现

需求：实现一个缓存系统，支持快速存取用户信息，并处理高并发。

代码实现：

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

// 模拟 MurmurHash3 哈希函数
unsigned int MurmurHash3(const void *key, int len, unsigned int seed) {
    unsigned int h = seed;
    unsigned char *p = (unsigned char *)key;
    int i = 0;
    while (i < len) {
        h ^= (p[i] << (i & 3));
        h *= 0x9E3779B9;
        i++;
    }
    return h;
}

// 哈希表结构
typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;

typedef struct dict {
    dictEntry **table;
    int size;
    int size_used;
    int rehashidx;
} dict;

// 初始化哈希表
dict *dictCreate(int size) {
    dict *d = (dict *)malloc(sizeof(dict));
    d->size = size;
    d->size_used = 0;
    d->rehashidx = -1;
    d->table = (dictEntry **)calloc(size, sizeof(dictEntry *));
    return d;
}

// 插入键值对
int dictSet(dict *d, void *key, void *val) {
    unsigned int h = MurmurHash3(key, 1, 0);
    dictEntry *entry = d->table[h];
    while (entry) {
        if (entry->key == key) {
            entry->val = val;
            return 0;
        }
        entry = entry->next;
    }
    entry = (dictEntry *)malloc(sizeof(dictEntry));
    entry->key = key;
    entry->val = val;
    entry->next = d->table[h];
    d->table[h] = entry;
    d->size_used++;
    return 1;
}

// 查找键值对
void *dictGet(dict *d, void *key) {
    unsigned int h = MurmurHash3(key, 1, 0);
    dictEntry *entry = d->table[h];
    while (entry) {
        if (entry->key == key) {
            return entry->val;
        }
        entry = entry->next;
    }
    return NULL;
}

// 主函数
int main() {
    dict *cache = dictCreate(10); // 创建大小为10的哈希表

    // 插入键值对
    char *key1 = "user:1001";
    char *val1 = "Alice";
    dictSet(cache, key1, val1);

    char *key2 = "user:1002";
    char *val2 = "Bob";
    dictSet(cache, key2, val2);

    // 查找键值对
    printf("User 1001: %s\n", (char *)dictGet(cache, key1));
    printf("User 1002: %s\n", (char *)dictGet(cache, key2));

    // 清理
    free(cache->table);
    free(cache);

    return 0;
}

关键代码解释：

模拟了 MurmurHash3 哈希函数，确保键的分布均匀。
使用链地址法处理冲突，避免哈希碰撞。
在高并发场景下，通过哈希表实现 O(1) 的时间复杂度。

六、源码解析

1. Redis 源码中的 `dict` 实现

Redis 的 dict 实现位于 src/dict.c，其核心逻辑如下：

// 在 dict.c 中的 dictCreate 函数
dict *dictCreate(dictType *type, void *privdata) {
    dict *d = (dict *)malloc(sizeof(*d));
    d->type = type;
    d->privdata = privdata;
    d->ht[0].size = 16;
    d->ht[0].table = (dictEntry **)malloc(sizeof(dictEntry *) * 16);
    d->ht[0].used = 0;
    d->ht[1].size = 0;
    d->ht[1].table = NULL;
    d->rehashidx = -1;
    return d;
}

关键代码解析：

Redis 使用两个哈希表（ht[0] 和 ht[1]）实现渐进式扩容。
rehashidx 用于标记当前正在重哈希的索引位置。
通过 rehash 函数逐步迁移数据到新哈希表，避免一次性扩容导致的性能下降。

七、进阶使用

1. 自定义哈希函数

在 Redis 中，可以通过 dictType 结构自定义哈希函数：

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void (*keyDup)(void *privdata, void *key);
    void (*keyDel)(void *privdata, void *key);
    void (*valDup)(void *privdata, void *obj);
    void (*valDel)(void *privdata, void *obj);
    int (*expand)(dict *d);
    int (*rehash)(dict *d);
} dictType;

使用场景：

对于自定义数据类型（如结构体），需要实现 hashFunction 来计算哈希值。
对于敏感数据，可以使用 keyDup 和 keyDel 实现数据安全处理。

八、性能与工程实践

1. 性能优化

调整哈希表大小：根据数据量选择合适的初始大小，避免频繁扩容。
渐进式扩容：Redis 的 rehash 机制将扩容操作分解到多个步骤，避免单次操作导致的性能下降。
内存回收：定期清理过期键，避免内存碎片。

2. 安全风险

缓存穿透：未处理的非法键可能导致系统崩溃。解决方案：使用布隆过滤器（Bloom Filter）。
缓存雪崩：大量缓存同时失效，导致系统负载激增。解决方案：设置随机过期时间。

九、常见问题与踩坑

1. 常见错误

错误1：未处理哈希冲突，导致性能下降。

// 错误代码：未处理冲突
int dictSet(dict *d, void *key, void *val) {
    unsigned int h = dictHashKey(d, key);
    d->table[h] = (dictEntry *)malloc(sizeof(dictEntry));
    d->table[h]->key = key;
    d->table[h]->val = val;
    return 1;
}

解决方法：使用链地址法处理冲突。

错误2：未考虑并发安全，导致数据竞争。

// 错误代码：未加锁
int dictSet(dict *d, void *key, void *val) {
    // 没有加锁，多线程环境下可能覆盖数据
}

解决方法：使用 pthread_mutex_t 加锁。

十、最佳实践

合理设置哈希表大小：初始大小应略大于最大键数，避免频繁扩容。
使用渐进式扩容：避免一次性扩容导致的性能瓶颈。
监控内存使用：定期清理过期键，防止内存泄漏。
结合布隆过滤器：防止缓存穿透。
避免大键值对：防止内存占用过高，影响系统稳定性。

十一、总结

Redis 的 dict 结构是其高性能的核心原因之一。通过深入理解其底层实现，开发人员可以更好地应对实际场景中的性能瓶颈、内存占用和并发安全等问题。在使用过程中，需要注意以下几点：

何时使用：需要快速查找、插入和删除的场景（如缓存、会话管理）。
何时不使用：需要有序性或范围查询的场景（如数据库索引）。
性能优化：合理设置哈希表大小，结合渐进式扩容。
安全风险：防范缓存穿透和雪崩。

通过本文的深入解析，希望读者能够更好地理解 Redis 的 dict 结构，并在实际项目中灵活应用。

redis底层结构-Dict

一、背景与问题

二、基本原理

1. Redis 的 `dict` 架构

2. 哈希表的结构

3. 哈希函数与冲突处理

三、环境准备

四、核心实现

1. 哈希表的初始化

2. 哈希函数实现

3. 插入操作（`dictSet`）

五、完整案例

场景：缓存系统实现

六、源码解析

1. Redis 源码中的 `dict` 实现

七、进阶使用

1. 自定义哈希函数

八、性能与工程实践

1. 性能优化

2. 安全风险

九、常见问题与踩坑

1. 常见错误

十、最佳实践

十一、总结

评论已关闭

推荐阅读

一、背景与问题

二、基本原理

1. Redis 的 dict 架构

2. 哈希表的结构

3. 哈希函数与冲突处理

三、环境准备

四、核心实现

1. 哈希表的初始化

2. 哈希函数实现

3. 插入操作（dictSet）

五、完整案例

场景：缓存系统实现

六、源码解析

1. Redis 源码中的 dict 实现

七、进阶使用

1. 自定义哈希函数

八、性能与工程实践

1. 性能优化

2. 安全风险

九、常见问题与踩坑

1. 常见错误

十、最佳实践

十一、总结

评论已关闭

推荐阅读

1. Redis 的 `dict` 架构

3. 插入操作（`dictSet`）

1. Redis 源码中的 `dict` 实现