redis Dict

<think>我们正在讨论Redis中的Dict（字典）实现原理和使用方法。根据提供的引用，特别是引用[1]和引用[2]，我们可以了解到Redis Dict的基本结构和实现机制。 Redis的Dict是一个键值对集合，采用哈希表作为底层实现。它使用两个哈希表（ht[0]和ht[1]）来实现渐进式rehash，以解决哈希冲突和扩展或收缩哈希表时的性能问题。 ### Redis Dict的结构 根据引用[1]和[2]，Dict的结构定义如下（这里综合两个引用的描述）： ```c typedef struct dict { dictType *type; // 类型特定函数（用于实现多态） void *privdata; // 私有数据 dictht ht[2]; // 两个哈希表，平常只使用ht[0]，rehash时使用ht[1] long rehashidx; // rehash进度，没有rehash时为-1 int16_t pauserehash; // rehash暂停标志（引用[2]中新增） } dict; ``` 其中，哈希表`dictht`的结构（在引用[1]中给出）： ```c typedef struct dictht { dictEntry **table; // 哈希表数组（桶） unsigned long size; // 哈希表大小 unsigned long sizemask; // 哈希表大小掩码，用于计算索引值，总是等于size-1 unsigned long used; // 该哈希表已有节点的数量 } dictht; ``` 每个键值对由`dictEntry`结构表示： ```c typedef struct dictEntry { void *key; // 键 union { void *val; uint64_t u64; int64_t s64; double d; } v; // 值（可以是多种类型） struct dictEntry *next; // 指向下一个节点，形成链表（解决哈希冲突） } dictEntry; ``` ### Redis Dict的工作原理 1. **哈希函数**：Redis使用MurmurHash2等算法计算键的哈希值。 2. **索引计算**：通过哈希值 & sizemask（即取模运算）确定元素在哈希表中的位置。 3. **解决哈希冲突**：采用链地址法（引用[1]中提到），每个哈希桶是一个链表，冲突的元素被放在同一个桶中，通过链表连接。 4. **rehash**：当哈希表的负载因子（load factor）超过一定阈值时，会触发rehash过程。负载因子计算公式为：负载因子 = used / size。 - 扩展操作：当负载因子大于1（或大于某个阈值）时，会进行扩展（如果当前正在执行BGSAVE或BGREWRITEAOF，则负载因子大于5时才扩展）。 - 收缩操作：当负载因子小于0.1时，会进行收缩。 - rehash过程是渐进式的（incremental rehashing），并不是一次性完成，而是分多次、渐进式地将ht[0]中的键值对rehash到ht[1]中。这样避免长时间的阻塞。 ### 渐进式rehash步骤 1. 为ht[1]分配空间（大小通常为第一个大于等于ht[0].used*2的2的幂次，或者收缩时根据ht[0].used计算）。 2. 将rehashidx设置为0，表示rehash开始。 3. 在每次对字典执行添加、删除、查找或更新操作时，除了执行指定的操作，还会将ht[0]中rehashidx索引上的所有键值对rehash到ht[1]中（然后rehashidx加1）。 4. 随着操作的进行，最终ht[0]的所有键值对都会被rehash到ht[1]，此时将ht[1]设置为ht[0]，并创建一个新的空白哈希表作为ht[1]，同时将rehashidx设置为-1。 ### 使用Dict的注意事项 - 在rehash期间，新添加的键值对会直接保存到ht[1]中，而不会放入ht[0]。 - 查找操作会同时查找ht[0]和ht[1]。 - 删除和更新操作也会同时在两个哈希表上进行。 ### Dict的使用场景 在Redis中，Dict被广泛用于实现各种数据类型，例如： - 作为Redis数据库的键空间（key space）的底层实现。 - 作为Hash数据类型的底层实现之一（当Hash元素较多时，会使用Dict而不是ziplist）。 - 作为Set数据类型的底层实现之一（当Set元素较多且元素为字符串时，使用Dict，其中值设为NULL）。 - 作为Sorted Set的底层实现之一（当使用跳跃表时，内部也使用Dict来存储成员到分数的映射，以便快速查找分数）。 ### 示例：添加键值对 当向Dict中添加一个键值对时： 1. 计算键的哈希值。 2. 如果正在rehash，则将该键值对添加到ht[1]中（并可能执行一步rehash）。 3. 否则，添加到ht[0]中，并检查是否需要扩展哈希表（触发rehash）。 ### 总结 Redis的Dict是一个高效的键值对数据结构，它通过哈希表实现，并使用链地址法解决冲突。其独特的渐进式rehash机制使得在扩展或收缩哈希表时能够保持高效的操作性能。 §§相关问题§§ 1. Redis Dict的rehash过程是同步还是异步的？ 2. 在rehash过程中，如果发生服务器重启，数据会如何恢复？ 3. Redis Dict的负载因子阈值是多少？在什么情况下会触发扩展或收缩？ 4. Redis中除了Dict，还有哪些数据结构使用了哈希表？</think>### Redis Dict 实现原理 Redis 的 Dict（字典）是一种高效的键值对数据结构，其核心实现基于**哈希表**和**渐进式 rehash**机制，主要原理如下： #### 1. **数据结构** ```c // 字典结构（引用[1][2]） typedef struct dict { dictType *type; // 类型特定函数（多态支持） void *privdata; // 私有数据 dictht ht[2]; // 两个哈希表（ht[0]主表，ht[1]用于rehash） long rehashidx; // rehash进度（-1表示未进行rehash） int16_t pauserehash; // rehash暂停标志（引用[2]新增） } 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]），冲突的键通过链表连接。 - **渐进式 rehash**（关键设计）： - 当负载因子 $ \text{load\_factor} = \frac{\text{used}}{\text{size}} $ 超过阈值时触发扩展（默认 $\geq 1$），或低于 $0.1$ 时触发收缩。 - 将数据从 `ht[0]` 分批迁移到 `ht[1]`，迁移期间： - 新数据直接写入 `ht[1]` - 查询同时访问 `ht[0]` 和 `ht[1]` - 每执行一次增删改查操作，迁移一个桶（`rehashidx` 记录进度） - 迁移完成后，`ht[1]` 替换为 `ht[0]`，重置 `rehashidx = -1` #### 3. **性能特点** - 平均时间复杂度：$O(1)$（查找/插入/删除） - 最坏情况：$O(n)$（所有键哈希冲突） - 自动扩容/缩容：避免频繁 rehash 影响性能 --- ### Redis Dict 使用方法 #### 1. **基础操作** - **添加键值对**：`HSET mydict field1 "value1"` - **获取值**：`HGET mydict field1` - **删除键**：`HDEL mydict field1` - **遍历所有键值**：`HGETALL mydict` #### 2. **应用场景** 1. **存储对象属性**（如用户信息）： ```bash HSET user:1001 name "Alice" age 30 email "[email protected]" ``` 2. **实现缓存**：快速读写键值数据。 3. **Hash 数据类型底层**：当元素数量超过 `hash-max-ziplist-entries` 配置时，自动转为 Dict 存储（引用[3]）。 #### 3. **高级特性** - **事务支持**：通过 `MULTI`/`EXEC` 保证操作原子性（引用[4]）。 - **Lua 脚本扩展**：使用 `EVAL` 执行复杂操作（引用[5]）。 - **监视键**：`WATCH` 指令实现乐观锁（引用[4]）。 --- ### 性能优化建议 1. **避免大 Key**：单个 Dict 不宜超过 1MB，防止 rehash 阻塞。 2. **合理配置哈希表**：调整 `hash-max-ziplist-entries` 和 `hash-max-ziplist-value` 平衡内存与性能。 3. **监控负载因子**：通过 `DEBUG HTSTATS` 查看负载情况。