Redis 设计与实现 (2) 字典

本贴最后更新于 1346 天前,其中的信息可能已经时移世易

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;

dict.png

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,这里顺带分析下链表与红黑树这些操作的平均时间复杂度。

操作 链表 红黑树
put(先查找找有没有重复 key,找到则 update,没有则 insert) O(n/2) O(logn)
get O(n/2) O(logn)
remove O(n/2) O(logn)

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

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

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

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

3、更简单。

  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    284 引用 • 247 回帖 • 211 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...