Redis 设计与实现 (2) 字典

Redis 设计与实现(2)字典

1. 字典

Hash 值基本使用：

127.0.0.1:6379> hmset user:1 name ccran age 18
OK
127.0.0.1:6379> hgetall user:1
1) "name"
2) "ccran"
3) "age"
4) "18"

Redis 使用字典来保存键值对与 Hash 类型的值。

字典 dict：

typedef struct dict {
    dictType *type;// 类型特定函数
    void *privdata;// 私有数据
    dictht ht[2];// 哈希表
    int rehashidx;// rehash 索引，不在进行时，值为 -1
} dict;

哈希表 dictht:

typedef struct dictht {
    dictEntry **table;// 哈希表数组
    unsigned long size; // 哈希表大小
    unsigned long sizemask;// 哈希落槽计算掩码，总是等于size-1
    unsigned long used;// 哈希表已有节点数
} dictht;

哈希表节点 dictEntry:

typedef struct dictEntry {
    void *key;// 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v; // 值
    struct dictEntry *next;// 下一个哈希表节点，形成链表
} dictEntry;

1、通过 MurmurHash2 算法计算哈希 hash

2、通过拉链法的方式解决 hash 冲突

3、哈希表的大小 size 总是 2 的 n 次方，掩码大小 sizemask 总是 size-1，这样通过 hash & sizemask 才能保证落到所有槽位

以 size 为 4 为例，sizemask 为 3

4 二进制为 0100，3 二进制为 0011

hash & 0011 保证能落到所有槽位 0~3

4、数据默认存储在 ht[0]，通过 rehash 到 ht[1]，释放 ht[0]空间，然后交换 ht[1]与 ht[0]完成扩容和收缩

5、扩容后大小 size 为第一个大于等于 used*2 的 2 的 n 次方，收缩后大小 size 为第一个大于等于 used 的 2 的 n 次方

如 used 为 3，扩容后为大于等于 3*2=6 的 2 的 n 次方，选择 8

6、负载因子 load_factor = used / size

7、扩容与收缩的时机

扩容时机：

1）没有执行 BGSAVE 与 BGREWRITEAOF 命令，负载因子大于等于 1

2）执行 BGSAVE 与 BGREWRITEAOF 命令，负载因子大于等于 5

执行 BGSAVE 与 BGREWRITEAOF 命令时，Redis 会 fork 子进程进行持久化，通过增大扩容阈值减少扩容机会来减少内存消耗。

收缩时机：

负载因子小于 0.1

8、在对字典进行 CRUD 时，通过 rehashidx 来遍历 ht[0]的每个槽位进行渐进式 rehash。将一次大 hash 分担到每次 CURD 的小 hash 从而提高服务性能。

对于查找来说，查找会在 ht[0]和 ht[1]中进行，因为 ht[1]中存在部分从 ht[0]中 rehash 过来的数据

对于添加来说，会直接添加到 ht[1]中

2. HashMap 比较

经过以上分析，总的来说，Redis 字典的结构类似于 Java 中的 HashMap（jdk1.8）。

相同：

1、在哈希冲突处理的方式上都是采用的拉链法

2、引入 load_factor 负载因子的概念来合理的扩容

3、槽位的个数都是 2 的 n 次方，落槽方式都是采取的 hash & (size-1)

不同：

1、Redis 采取渐进式 hash 来均分性能消耗

2、HashMap 会在某个槽位上冲突大于 8 个时进行节点的转换，从链表节点转换为红黑树节点

3、Redis 存在收缩时机，而 HashMap 不会；并且 Redis 扩容的负载因子 1.0 比 HashMap 默认的 0.75 大。

4、Redis 通过 MurmurHash2 作为哈希函数；HashMap 可以通过重写 hashCode 方法自定义哈希函数，并且会通过移位运算进行一次扰动。

3. 疑问

比较了 Redis 的字典与 Java 中的 HashMap 以后，自然会有一些疑问。

为什么 Redis 不采用和 HashMap 一样的链表转红黑树策略呢？

对字典和 map 的操作无疑就是 put、get、remove，这里顺带分析下链表与红黑树这些操作的平均时间复杂度。

可以看到，红黑树在时间复杂度上明显优于链表，为何不选择红黑树呢？

看完这篇文章后《阿里面试题：为什么 Map 桶中个数超过 8 才转为红黑树》，个人有所理解：

1、相比于 HashMap 可能存在用户重写 hashCode，Redis 使用 MurmurHash2 作为哈希函数，数据更加能均匀的散列到各个槽位上。即使存在冲突，链表的长度也不会很长，是一个短链。

2、在短链上，红黑树节点的空间占用是链表节点占用的两倍，但是时间复杂度却提升不了多少，因此不如选择链表。

3、更简单。