中间件 | Redis - [全局 hash & 渐进 rehash]

'# 中间件 | Redis - [全局 hash & 渐进 rehash]

一、背景与问题

在分布式系统中，Redis 作为最流行的内存数据库之一，其核心数据结构设计直接决定了性能表现。其中，哈希表（Hash Table）是 Redis 实现高效键值存储的关键组件，而其特有的"渐进 rehash"机制则是解决内存扩容与并发访问矛盾的核心方案。

传统哈希表存在两个关键问题：

1. 内存浪费：当哈希表的负载因子（元素数量/桶数量）过高时，会导致大量内存碎片
2. 阻塞风险：直接扩容或缩容会导致主线程阻塞，影响高并发场景下的响应性能

Redis 通过全局哈希表和渐进 rehash 机制，在保持高性能的同时，实现了动态内存管理，这是其能支持百万级并发访问的核心技术之一。

二、基本原理

1. 全局哈希表结构

Redis 的哈希表由两个核心数据结构组成：

• dict：主哈希表（ht[0]）和备用哈希表（ht[1]）
• dictEntry：每个哈希表项的结构体

typedef struct dict {
    dictType type;
    void *privdata;
    dictEntry *ht[HT_HASH_SIZE]; // 哈希表数组
    // ...其他字段
} dict;

每个 dictEntry 包含：

• key：键值（支持字符串、整数等类型）
• val：值（支持字符串、整数、对象等）
• ht：指向哈希表的指针

2. 渐进 rehash 机制

Redis 采用渐进式扩容/缩容策略，核心思想是：

• 在每次操作（如 HSET、HGET）时，逐步迁移数据
• 避免一次性复制全部数据导致的阻塞

具体步骤：

1. 增加新哈希表（ht[1]）并初始化
2. 使用 rehashidx 记录当前迁移进度
3. 每次操作时，将 ht[0] 的数据迁移到 ht[1]
4. 当迁移完成时，释放 ht[0] 内存

三、环境准备

1. 开发环境

• Redis 6.2.6（支持渐进 rehash）
• 编译环境：gcc 9.3 / clang 12.0
• 测试工具：redis-cli、valgrind

2. 代码准备

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dict.h" // Redis 原生哈希表实现

// 模拟 Redis 哈希表操作
void simulate_rehash() {
    dict *d = dictCreate(NULL, NULL);
    dictSetHashFunction(d, dictDefaultHashFunction);
    
    // 模拟大量数据插入
    for (int i = 0; i < 100000; i++) {
        char key[20];
        snprintf(key, sizeof(key), "key%d", i);
        dictSet(d, key, (void*)malloc(100));
    }
    
    // 模拟扩容过程
    dictExpand(d, 200000); // 增加哈希表容量
    
    // 模拟数据查询
    for (int i = 0; i < 100000; i++) {
        char key[20];
        snprintf(key, sizeof(key), "key%d", i);
        void *val = dictGet(d, key);
        if (val) free(val);
    }
    
    dictRelease(d);
}

四、核心实现

1. 哈希表初始化

// Redis 哈希表初始化函数
void dictInitialize(dict *d, dictType *type, void *privdata) {
    d->type = type;
    d->privdata = privdata;
    d->ht[0] = (dictEntry**)malloc(HT_HASH_SIZE * sizeof(dictEntry*));
    d->ht[1] = NULL;
    d->rehashidx = -1;
    memset(d->ht[0], 0, HT_HASH_SIZE * sizeof(dictEntry*));
}

关键点：

• 使用 HT_HASH_SIZE（默认 4096）作为哈希表大小
• 初始状态下只存在主哈希表 ht[0]

2. 渐进 rehash 过程

// Redis 渐进 rehash 实现
void dictRehash(dict *d, int delta) {
    int i = d->rehashidx;
    int j, k;
    dictEntry *rehash_tmp;
    
    while (delta--) {
        // 找到未处理的桶
        if (i >= HT_HASH_SIZE) {
            // 全部迁移完成
            d->rehashidx = -1;
            return;
        }
        
        // 处理当前桶
        j = 0;
        while (d->ht[0][i] != NULL) {
            rehash_tmp = d->ht[0][i];
            d->ht[0][i] = rehash_tmp->next;
            
            // 计算新哈希桶位置
            j = dictHashKey(d, rehash_tmp->key) & HT_HASH_SIZE - 1;
            
            // 如果新表不存在，创建
            if (d->ht[1] == NULL) {
                d->ht[1] = (dictEntry**)malloc(HT_HASH_SIZE * sizeof(dictEntry*));
                memset(d->ht[1], 0, HT_HASH_SIZE * sizeof(dictEntry*));
            }
            
            // 将数据迁移到新表
            d->ht[1][j] = rehash_tmp;
            j++;
        }
        
        d->rehashidx++;
    }
}

关键点：

• 使用 rehashidx 跟踪迁移进度
• 每次迁移一个桶中的所有元素
• 新表创建时使用 HT_HASH_SIZE（与原表相同）

3. 数据迁移策略

// Redis 数据迁移函数
void dictRehash(dict *d, int delta) {
    // ...（如上）
    
    // 扩容时的特殊处理
    if (d->ht[1] == NULL && d->ht[0] != NULL) {
        // 创建新表时需要调整大小
        d->ht[1] = (dictEntry**)malloc(HT_HASH_SIZE * sizeof(dictEntry*));
        memset(d->ht[1], 0, HT_HASH_SIZE * sizeof(dictEntry*));
    }
    
    // 增加新表时的迁移
    if (d->ht[1] != NULL) {
        for (int i = 0; i < HT_HASH_SIZE; i++) {
            while (d->ht[1][i] != NULL) {
                dictEntry *entry = d->ht[1][i];
                d->ht[0][i] = entry;
                d->ht[1][i] = entry->next;
            }
        }
    }
}

关键点：

• 扩容时新表大小与原表相同
• 缩容时会动态调整哈希表大小
• 通过 delta 控制每次迁移的数据量

五、完整案例

1. 缓存热点数据案例

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

// 模拟 Redis 缓存热点数据
void cache_hot_data() {
    dict *cache = dictCreate(NULL, NULL);
    dictSetHashFunction(cache, dictDefaultHashFunction);
    
    // 模拟大量热点数据
    for (int i = 0; i < 100000; i++) {
        char key[20];
        snprintf(key, sizeof(key), "product%d", i);
        dictSet(cache, key, (void*)malloc(100));
    }
    
    // 模拟高并发访问
    for (int i = 0; i < 100000; i++) {
        char key[20];
        snprintf(key, sizeof(key), "product%d", i);
        void *val = dictGet(cache, key);
        if (val) free(val);
    }
    
    // 模拟扩容
    dictExpand(cache, 200000);
    
    // 清理缓存
    dictRelease(cache);
}

2. Redis 源码分析

// Redis 哈希表扩容函数（简化版）
void dictExpand(dict *d, unsigned long new_size) {
    // 创建新哈希表
    dictEntry **new_ht = (dictEntry**)malloc(new_size * sizeof(dictEntry*));
    memset(new_ht, 0, new_size * sizeof(dictEntry*));
    
    // 迁移数据
    for (int i = 0; i < HT_HASH_SIZE; i++) {
        while (d->ht[0][i] != NULL) {
            dictEntry *entry = d->ht[0][i];
            d->ht[0][i] = entry->next;
            
            // 计算新位置
            int j = dictHashKey(d, entry->key) & new_size - 1;
            new_ht[j] = entry;
        }
    }
    
    // 释放旧表
    free(d->ht[0]);
    d->ht[0] = new_ht;
    d->ht[1] = NULL;
}

关键点：

• 使用 new_size 控制新表大小
• 通过位运算计算新位置
• 释放旧表时采用 free 函数

六、源码解析

1. 哈希函数设计

Redis 使用以下哈希函数（默认）：

unsigned long dictDefaultHashKey(dict *d, const void *key) {
    return (unsigned long) key ^ (unsigned long)(key >> 32);
}

关键点：

• 使用异或运算提高哈希分布均匀性
• 处理 64 位整数的哈希

2. 冲突处理机制

Redis 采用链地址法处理冲突：

dictEntry *dictAddKey(dict *d, void *key, void *val) {
    // 计算哈希位置
    unsigned long h = dictHashKey(d, key) & HT_HASH_SIZE - 1;
    
    // 遍历链表
    dictEntry *entry = d->ht[0][h];
    while (entry != NULL) {
        if (entry->key == key) {
            // 存在相同键，更新值
            entry->val = val;
            return entry;
        }
        entry = entry->next;
    }
    
    // 插入新节点
    entry = (dictEntry*)malloc(sizeof(*entry));
    entry->key = key;
    entry->val = val;
    entry->next = d->ht[0][h];
    d->ht[0][h] = entry;
    return entry;
}

关键点：

• 链表结构处理冲突
• 保证每个桶最多一个头节点

七、进阶使用

1. 哈希表优化策略

• 负载因子控制：通过 HT_HASH_SIZE 控制负载因子（建议保持在 1:2）
• 内存预分配：提前分配足够容量的哈希表
• 渐进迁移控制：通过 delta 参数控制每次迁移的数据量

2. 实际应用场景

1. 缓存系统：处理百万级键值对时的动态扩容
2. 会话管理：存储用户会话信息的高并发访问
3. 消息队列：实现基于哈希的队列结构

八、性能与工程实践

1. 性能优化

• 预分配内存：避免频繁内存分配
• 调整负载因子：保持负载因子在 1:2 范围
• 批量迁移：在低峰时段进行大规模迁移

2. 异常处理

• 内存不足：使用 malloc 失败时的处理
• 哈希冲突：链表过长时的优化（如转换为平衡树）
• 数据一致性：确保迁移过程中的数据完整性

3. 安全风险

• 数据丢失：迁移过程中发生异常导致数据丢失
• 并发访问：多线程环境下哈希表的操作同步问题
• 内存泄漏：未正确释放旧哈希表的内存

九、常见问题与踩坑

1. 常见错误

1. 内存碎片问题：频繁扩容导致内存碎片

   • 解决：采用分段迁移策略，减少内存碎片

2. 哈希冲突过多：导致链表过长影响性能

   • 解决：适当增大 HT_HASH_SIZE

3. 迁移不完整：rehashidx 未正确更新

   • 解决：确保在每次操作后更新 rehashidx

2. 特殊场景处理

• 缩容场景：当哈希表利用率低于 10% 时
• 写入瓶颈：在高并发写入时的性能优化
• 冷热数据分离：将不常访问的数据移到备用哈希表

十、最佳实践

1. 使用场景：适用于需要动态扩容的缓存系统
2. 性能指标：保持负载因子在 1:2 范围
3. 迁移策略：每次迁移 100-1000 个桶
4. 内存管理：提前分配足够容量的哈希表
5. 异常处理：确保迁移过程中的数据一致性

十一、总结

Redis 的全局哈希表和渐进 rehash 机制是其高性能的核心保障。通过分段迁移、动态扩容和链地址法，Redis 在保证高并发访问的同时，有效避免了内存碎片和阻塞问题。在实际开发中，需要根据业务场景选择合适的哈希表大小和迁移策略，同时注意处理可能出现的内存碎片、哈希冲突和数据一致性问题。理解这些机制，不仅能帮助我们更好地使用 Redis，也能在开发自定义缓存系统时提供有益的参考。