分析Redis中的字典、哈希算法和ReHash原理

发布时间：2021-11-05 10:33:38 作者：iii
来源：亿速云阅读：228

# 分析Redis中的字典、哈希算法和ReHash原理

## 一、Redis字典概述

### 1.1 字典在Redis中的核心地位
Redis作为高性能键值数据库，其键空间（Key Space）底层实现依赖于字典结构。字典不仅是Redis数据库的基石，还支撑着哈希键（Hash Key）等复杂数据类型的实现。在Redis源码中，字典的实现主要位于`dict.h`和`dict.c`文件中。

### 1.2 字典数据结构定义
Redis字典采用典型哈希表实现，核心结构体如下：

```c
typedef struct dict {
    dictType *type;  // 类型特定函数
    void *privdata; // 私有数据
    dictht ht[2];   // 哈希表数组（2个）
    long rehashidx; // rehash索引（-1表示未进行）
    unsigned long iterators; // 当前迭代器数量
} dict;

typedef struct dictht {
    dictEntry **table;      // 哈希表数组
    unsigned long size;     // 表大小
    unsigned long sizemask; // 大小掩码（=size-1）
    unsigned long used;     // 已使用节点数
} dictht;

typedef struct dictEntry {
    void *key;              // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;                   // 值
    struct dictEntry *next; // 链地址法解决冲突
} dictEntry;

二、哈希算法实现原理

2.1 Redis哈希函数选择

Redis默认使用SipHash算法（1-2变体），该算法在防止哈希碰撞和抵抗哈希洪水攻击方面表现优异：

uint64_t siphash(const uint8_t *in, const size_t inlen, 
                const uint8_t *k);

关键特性： - 输入敏感：微小变化导致输出完全不同 - 64位输出减少碰撞概率 - 密钥随机化防止预测攻击

2.2 哈希槽计算

Redis通过位运算快速定位槽位：

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

其中sizemask总是等于size-1（保证为2^n-1形式），使得模运算可以转化为高效的位与操作。

2.3 哈希冲突解决

采用链地址法处理冲突，新节点总是添加到链表头部（时间复杂度O(1)）：

entry->next = ht->table[index];
ht->table[index] = entry;

三、渐进式ReHash机制

3.1 ReHash触发条件

Redis在以下情况下触发rehash： 1. 扩容条件：used/size > dict_force_resize_ratio（默认5） 2. 缩容条件：used/size < 10%（BGSAVE时不缩容）

3.2 渐进式ReHash流程

Redis采用渐进式rehash避免服务阻塞：

准备阶段：
- 分配ht[1]空间（扩容时大小为第一个≥used*2的2^n）
- 设置rehashidx=0（标识rehash开始）
执行阶段（每次操作分步迁移）： “`c if (dictIsRehashing(d)) _dictRehashStep(d);

int _dictRehashStep(dict *d) { return dictRehash(d,1); // 每次迁移1个桶 }


3. 完成条件：
   - `ht[0]`所有元素迁移完成
   - 交换`ht[0]`和`ht[1]`
   - 重置`rehashidx=-1`

### 3.3 操作期间的哈希表访问
特殊处理逻辑保证操作正确性：
```c
dictEntry *dictFind(dict *d, const void *key) {
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    // 同时查找两个哈希表
    for (int table = 0; table <= 1; table++) {
        idx = hash & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) { /* 遍历链表 */ }
    }
    return NULL;
}

四、性能优化策略

4.1 扩容因子权衡

Redis的默认扩容因子为： - 写操作触发：used >= size*5 - 读操作触发：used > size*10

这种差异设计避免了写密集场景下的频繁扩容。

4.2 增量迁移策略

每次操作最多迁移n*10个桶（n为单次操作迁移的基本单位），避免长时间阻塞。

4.3 安全迭代器

当存在活跃迭代器时暂停rehash，保证遍历一致性：

typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
} dictIterator;

五、实战案例分析

5.1 哈希键存储实现

当存储HSET命令时：

HSET user:1000 name "Alice" age 30

Redis会创建一个字典结构，其中： - 键：field名（”name”, “age”） - 值：对应数据（”Alice”, 30）

5.2 内存优化技巧

对于小哈希（≤512元素且值≤64字节），Redis会采用ziplist编码，超过阈值才转为字典存储。

六、与其他组件对比

特性	Redis字典	Java HashMap	Go map
哈希算法	SipHash	hashCode()	硬件AES哈希
冲突解决	链地址法	链表转红黑树	链地址法
扩容方式	渐进式rehash	一次性rehash	增量扩容
线程安全	单线程模型保证	ConcurrentHashMap	内置互斥锁

七、常见问题排查

7.1 大Key问题

通过redis-cli --bigkeys可识别大字典键，表现为： - 单个哈希键包含数百万field - 内存占用异常高

解决方案： - 拆分大键为多个小键 - 使用HSCAN渐进式处理

7.2 ReHash阻塞

监控指标：

redis-cli info | grep rehash

出现rehash_blocked:1时需要检查是否有长时间运行的Lua脚本。

八、未来优化方向

弹性哈希表：根据负载动态调整哈希函数
更高效的内存布局：尝试紧凑型结构减少内存碎片
并发ReHash：在Redis多线程版本中实现并行迁移

参考文献

Redis 6.2源码 dict.c
《Redis设计与实现》——黄健宏
SipHash论文：https://www.aumasson.jp/siphash/siphash.pdf

本文基于Redis 6.2版本分析，总字数约2250字。实际实现可能随版本演进有所调整，建议读者结合最新源码进行验证。 “`

该文章完整涵盖了Redis字典的核心实现，包含： 1. 详细的数据结构定义 2. 哈希算法实现细节 3. 渐进式rehash的完整流程 4. 性能优化策略和实战案例 5. 对比分析和问题排查指南

文章采用技术深度与可读性平衡的写法，适合中高级开发者阅读。可通过调整案例部分的详细程度来精确控制字数。