面试题：从源码角度分析Redis字典在缓存系统应用优化的关键技术点

Question

请从Redis源码角度，深入剖析Redis字典在缓存系统应用优化中的关键技术点，如字典的创建、扩容、缩容机制，以及这些机制如何适应缓存系统动态变化的需求。

Answer 1

字典的创建

1. 数据结构：Redis 字典使用哈希表作为底层实现，一个哈希表由 dict.h/dictht 结构体表示，包含数组 table，存储哈希表节点 dictEntry，还有记录已使用节点数 used 和哈希表大小 size 等信息。
2. 哈希函数：Redis 使用 MurmurHash2 算法来计算键的哈希值，将键映射到哈希表的某个槽位。这种哈希函数具有较好的散列性，能减少哈希冲突。
3. 初始化：创建字典时，初始化哈希表的 size 为初始值（通常为 4），used 为 0，table 数组的每个元素初始化为 NULL。

扩容机制

1. 触发条件：当哈希表的负载因子（used / size）大于等于 1，并且 dict_can_resize 标志为真时，会触发扩容。此外，当服务器执行 BGSAVE 或 BGREWRITEAOF 命令时，如果负载因子大于等于 5 也会触发扩容。
2. 扩容过程：分配一个大小为原哈希表 size 两倍的新哈希表，重新计算所有键值对的哈希值和索引，将原哈希表中的所有键值对重新插入到新哈希表中，最后释放原哈希表的内存空间。
3. 渐进式 rehash：为避免一次性 rehash 对服务器性能造成过大影响，Redis 采用渐进式 rehash。在 dict 结构体中使用 rehashidx 记录 rehash 进度，每次对字典执行增删改查操作时，会顺带将 rehashidx 指向的槽位上的所有键值对迁移到新哈希表，并将 rehashidx 加 1。在此期间，字典同时使用新旧两个哈希表，查找操作会在两个表中都进行，直到 rehashidx 等于 -1，表示 rehash 完成，释放旧哈希表。

缩容机制

1. 触发条件：当哈希表的负载因子小于 0.1 时，会触发缩容。
2. 缩容过程：分配一个大小为原哈希表 size 四分之一的新哈希表（如果 size 小于 4 则不改变），重新计算所有键值对的哈希值和索引，将原哈希表中的所有键值对重新插入到新哈希表中，最后释放原哈希表的内存空间。同样采用渐进式 rehash 方式进行，与扩容类似。

对缓存系统动态变化需求的适应

1. 动态数据量变化：扩容和缩容机制能够根据缓存中键值对数量的动态变化，自动调整哈希表的大小，保证负载因子在合理范围内，从而提高哈希表的查找效率。当缓存数据量增加时，及时扩容避免哈希冲突加剧；当数据量减少时，缩容节省内存空间。
2. 避免性能抖动：渐进式 rehash 机制使得哈希表的调整过程分散在多次操作中，避免了一次性大量数据迁移对缓存系统性能造成的瞬间抖动，保证了缓存系统的稳定性和响应及时性，满足缓存系统对高性能和低延迟的要求。