Redis 学习笔记之字典
一、字典的实现
1.1 字典内部定义
- 哈希表
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
- 哈希表节点定义
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
- 图示
- 字典结构定义
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
type 属性和 privdata 属性是针对不同类型的键值对， 为创建多态字典而设置的：
- type 属性是一个指向 dictType 结构的指针， 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数。
-
privdata 属性则保存了需要传给那些类型特定函数的可选参数。
-
dictType
typedef struct dictType {
// 计算哈希值的函数
unsigned int (*hashFunction)(const void *key);
// 复制键的函数
void *(*keyDup)(void *privdata, const void *key);
// 复制值的函数
void *(*valDup)(void *privdata, const void *obj);
// 对比键的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 销毁键的函数
void (*keyDestructor)(void *privdata, void *key);
// 销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;
- 图示
1.2 哈希算法
Redis 使用 MurmurHash2 算法来计算键的哈希值
MurmurHash 算法请查看 https://github.com/aappleby/smhasher
1.3 解决键冲突问题
这里与 Java HashMap 类似，也是采用链地址法解决键冲突问题
1.4 rehash （重新散列）
-
重新散列步骤：
-
为字典的 ht[1] 哈希表分配空间
- 如果执行的是扩展操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n （2 的 n 次方幂）；
- 如果执行的是收缩操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n 。
- 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面： rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到 ht[1] 哈希表的指定位置上。
-
当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表）， 释放 ht[0] ， 将 ht[1] 设置为 ht[0] ，并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做准备。
-
图示
- 哈希表的扩展与收缩
- 扩展
- 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1
- 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5
- 收缩
- 当哈希表的负载因子小于 0.1 时， 程序自动开始对哈希表执行收缩操作。
负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size
1.5 渐进式 rehash 了解
- 什么是渐进式 rehash？
Redis 字典 rehash 的过程需要把哈希表 ht[0]的元素重新哈希放到 ht[1]中，当数据量庞大的时候，为了性能上的考虑，不能一次性 rehash，只能分批 rehash。 所以 Redis 在对字典的每个添加、删除、查找和更新操作上，都会进行分批 rehash。
- 渐进式 rehash 的步骤
- 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
- 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
- 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
-
随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。
-
渐进式 rehash 的相关问题？
- rehash 进行时又有增删改查如何处理？
- 增加时，直接往新的 1 号哈希表增加。
- 删除、修改、查询时，由于无法确定 entry 在哪块哈希表上，所以只能先查 0 号哈希表，找不到再查 1 号哈希表。
- 什么时候不允许 rehash？
- 如果在 rehash 进行中，上层获取并长久持有了 dict 的迭代器，那么 rehash 需要暂停，以避免迭代器迭代时访问到重复 entry 或丢失 entry。
- 另外 redis 如果正在将数据持久化，也会关闭 rehash 的开关，避免 copy-on-write 受影响。
参考
- 《Redis 设计与实现》
- http://www.redis.cn/
- MurmurHash 算法https://github.com/aappleby/smhasher
- https://www.pengrl.com/p/20010/
Original: https://www.cnblogs.com/JianJianHuang/p/13776762.html
Author: JiaJianHuang
Title: Redis学习笔记之字典
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/573092/
转载文章受原作者版权保护。转载请注明原作者出处！