ccran 的个人博客 ccran 的个人博客

记录精彩的程序人生

目录
Redis设计与实现(2)字典
/  

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;

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

  1. 数据默认存储在ht[0],通过rehash到ht[1],释放ht[0]空间,然后交换ht[1]与ht[0]完成扩容和收缩
  2. 扩容后大小size为第一个大于等于used*2的2的n次方,收缩后大小size为第一个大于等于used的2的n次方

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

  1. 负载因子load_factor = used / size
  2. 扩容与收缩的时机

扩容时机:

  1. 没有执行BGSAVE与BGREWRITEAOF命令,负载因子大于等于1
  2. 执行BGSAVE与BGREWRITEAOF命令,负载因子大于等于5

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

收缩时机:

负载因子小于0.1

  1. 在对字典进行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)O(logn)
getO(n)O(logn)
removeO(n)O(logn)

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

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

  1. 相比于HashMap可能存在用户重写hashCode,Redis使用MurmurHash2作为哈希函数,数据更加能均匀的散列到各个槽位上。即使存在冲突,链表的长度也不会很长,是一个短链。
  2. 在短链上,红黑树节点的空间占用是链表节点占用的两倍,但是时间复杂度却提升不了多少,因此不如选择链表。
  3. 更简单。

标题:Redis设计与实现(2)字典
作者:ccran
地址:https://ccran.online/articles/2020/07/22/1595407556481.html