Redis数据结构-字典(dict)

支撑着Redis大量数据的结构就是我们今天要说的字典，先来揭开他神秘的面纱

字典的结构

我们来看一下Redis的源码：

dict:字典的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * 字典
 */
typedef struct dict {//dictCreate创建和初始化
    
    // 类型特定函数：相当于一些通用方法的接口，当dict用于不同地方这些通用方法有不同的实现；通用方法类似：计算hash值，对比键方法等
    dictType *type;

    // 私有数据：类型特定函数的私有数据  privdata 属性则保存了需要传给那些类型type特定函数的可选参数。
    void *privdata;

    // 哈希表：ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
    dictht ht[2];//dictht hash桶初始化创建见dictExpand     

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1  // 记录 rehash 进度的标志，值为-1 表示 rehash 未进行
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict; //dict空间创建初始化在dictExpand，第一次是在_dictExpandIfNeededif->dictExpand(d, DICT_HT_INITIAL_SIZE);

先来看一下dictType，看看有哪些方法可以根据不同场景来进行自定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * 字典类型特定函数
 */ //dictType主要由xxxDictType(dbDictType zsetDictType setDictType等)
typedef struct dictType {//函数privdata参数从dict->privdata中获取

    // 计算哈希值的函数 // 计算键的哈希值函数, 计算key在hash table中的存储位置，不同的dict可以有不同的hash function.
    unsigned int (*hashFunction)(const void *key);//dictHashKey中执行该函数

    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);//dictSetKey
    
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj); //dictSetVal  保存在dictEntry->v->value中，然后在

    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);//dictCompareKeys

    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);//dictFreeKey
    
    // 销毁值的函数 
    void (*valDestructor)(void *privdata, void *obj);//dictFreeVal

} dictType;

再来看下比较重要的一个结构dictht（hash表）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
typedef struct dictht {

    //每个具体table[i]中的节点数据类型是dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：
    // 哈希表节点数组
    dictEntry **table;
    
    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值:总是等于 size - 1
    unsigned long sizemask; //sizemask = size-1 因为具体的桶是从0到size-1

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

} dictht;

/*
 * 哈希表节点
 */
typedef struct dictEntry { 
    
    // 键：这就是k-v中真正存key的地方
    void *key; //对应一个robj
    

    // 值：v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。
    union {
        void *val;
        uint64_t u64;
        int64_t s64;//一般记录的是过期键db->expires中每个键的过期时间  单位ms
    } v;//对应一个robj

    // 有冲突时指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

整体结构如下图：

1625757422875

图来源：《Redis设计与实现》

字典数据的存储

首先根据dict的dictType来确定计算hash值的函数，根据这个函数来计算key的hash值

然后根据hash&ht[0].sizemask来计算处于hash节点数组的哪个位置，如果当前位置有值则插入到表头位置，形成一个链表

字典的扩容与缩容

扩容和缩容标准：

扩容：

  • 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1 ；
  • 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5 ；

缩容：

  • 当负载因子小于0.1时

负载因子计算公式：

load_factor = ht[0].used/ht[0].size

这里的used的数量等于加入元素的数量，而不是hash表节点数组用了几个

如何扩缩容：

前面我们说过字典（dict）是有两个hash表（dictht）的，当需要扩缩容时，先计算出新的ht[1]的大小，然后把ht[0]的数据都挪到ht[1]里面去，在挪的过程中不是一口气全挪过去，因为数量可能会很大，而是渐进式的去挪，每次有操作才去挪一些。

看一下上述操作的一些细节：

细节一：新的ht[1]的大小时如何计算的？

​ 当扩容时，新的大小为第一个大于等于ht[0].used * 2的2^n(2的n次方幂)，例：used = 4 那么第一个大于4*2的2的n次方幂为8（2^3）

​ 当缩容时，新的大小为第一个大于等于ht[0].used 的2^n(2的n次方幂)，例：used = 4 那么第一个大于4的2的n次方幂为4（2^2）

细节二：如何渐进式的扩缩容？

这时rehashidx就起作用了，他记录着当前要处理的index，每次进行添加，删除，或者更新操作的时候，就把ht[0]hash表在redhashidx索引上的所有键值对rehash到ht[1]中，然后rehashidx加一，依次进行，因为redis时单线程，所以不用考虑多线程问题。

在扩缩容过程中，当需要查找，删除，更新操作时，需要两个hash表去操作，先在ht[0]找，然后再在ht[1]找，找到就操作，想添加操作，会直接添加到ht[1]中。

Redis的字典(dict)结构大致就这么些内容，这是最基础的数据类型，之所以基础是因为整个数据库都是基于这个数据结构的，其他redis对象也会用字典作为value值的结构，比如hash对象，set对象，zset对象也有用到，这些我们在后面的文章中都会根据具体的命令进行分析。

参考：《Redis设计与实现》黄健宏 著

源码参考 - github.com