Redis - Redis学习笔记之字典 - 《后端知识点学习笔记》

一、字典的实现
参考

一、字典的实现

1.1 字典内部定义

哈希表 ```c typedef struct dictht { // 哈希表数组 dictEntry **table;

// 哈希表大小 unsigned long size;

// 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask;

// 该哈希表已有节点的数量 unsigned long used;

} dictht;


- 哈希表节点定义
```c
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

图示

字典结构定义 ```c 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 
```c
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;

图示

redis字典.png

1.2 哈希算法

Redis 使用 MurmurHash2 算法来计算键的哈希值
MurmurHash 算法请查看 https://github.com/aappleby/smhasher

1.3 解决键冲突问题

这里与Java HashMap 类似，也是采用链地址法解决键冲突问题

1.4 rehash （重新散列）

重新散列步骤：

为字典的 ht[1] 哈希表分配空间
1. 如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n （2 的 n 次方幂）；
2. 如果执行的是收缩操作，那么 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/