Redis数据结构——dict（字典）

向着百万年薪努力的小赵

发布于 2022-12-02 10:26:39

2910

发布于 2022-12-02 10:26:39

文章被收录于专栏：小赵的Java学习小赵的Java学习

字典在Redis中的作用是非常巨大的，对Redis数据库的增删改查等操作都构建在对字典的操作之上，因此，了解字典的底层实现能让我们对Redis有更深的理解。下面分4个模块讲解Redis的字典实现（基本所有实现细节和重点都会谈到）：

字典的数据结构

Redis的字典是用哈希表实现的，一个哈希表里面有多个哈希表节点，每个节点表示字典的一个键值对，其中哈希表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;    //uint64_t整数
        int64_t s64;    //int64_t整数
    }v;
    struct dictEntry *next;    //指向下个哈希表节点
}dictEntry;

需要说明的一点是，这里的next指针主要用于防止hash值冲突，通过开链法将多个hash值相同的键值对连到一起。

事实上，完整的字典dict实现是由2个哈希表dictht加上几个变量构成的，具体如下:

typedef struct dict {
    dictType *type;    //类型特定函数
    void *privdata;    //私有数据
    dictht ht[2];    //2个哈希表，哈希表负载过高进行rehash的时候才会用到第2个哈希表
    int rehashidx;    //rehash目前进度，当哈希表进行rehash的时候用到，其他情况下为-1
}dict;

dict的type属性是一个指向dictType结构的指针，而每个dictType结构保存了一些用于操作特定类型键值对的函数，dictType的定义如下:

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;

dict的privdata属性，则是需要传给类型特定函数的可选参数，Redis借助type和privdata这两个字段来实现多态字典。

介绍了这么多数据结构，下面展示一个没有进行rehash时的字典状态图，这样可以对字典有个比较清晰的理解：

字典的插入过程

下面介绍Redis将一个键值对插入字典dict的过程：

先用哈希函数计算键key的哈希值（Redis使用的是MurMurHash2算法来计算哈希值）

hash = dict->type->hashFunction(key)

借助sizemask和哈希值，计算出索引值（下面的x可以是0或者1）

index = hash & dict->ht[x].sizemask

上面计算出来index的值其实就是对应dictEntry*数组的下标，如果对应下标没有存放任何键值对，则直接存放，否则借助开链法，从链表头插入新的键值对（因为链表没有记录指向链表尾部的指针，所以从链表头插入效率更高，可以达到O(1)）

假如k0的索引值为0，k1的索引值为1，k2的索引值为2，把(k0，v0)、(k1，v1)、(k2，v2)这3个键值对按顺序插入到字典后的状态图就如上面第二模块中最后的例子所示

字典的rehash过程

大家知道，当哈希表的冲突率过高时链表会很长，这时查询效率就会变低，所以有必要进行哈希表扩展，而如果哈希表存放的键值对很少的时候把size设的很大，又会浪费内存，这时就有必要进行哈希表收缩。这里扩展和收缩的过程，其实就是rehash的过程。

Redis对字典的哈希表进行rehash的步骤如下：

为dict的哈希表ht[1]分配空间，分配的空间大小取决于操作类型和当前键值对数量ht[0].used (1)如果是扩展操作，ht[1]的大小为第一个大于等于ht[0].used22^{n}的整数 (2)如果是收缩操作，ht[1]的大小为第一个大于等于ht[0].used*2^{n}的整数
重新计算ht[0]中所有键的哈希值和索引值，将相应的键值对迁移到ht[1]的指定位置中去，需要注意的是，这个过程是渐进式完成的，不然如果字典很大的话全部迁移完需要一定的时间，这段时间内Redis服务器就不可用了哟
当ht[0]的所有键值对都迁移到ht[1]中去后（此时ht[0]会变成空表），把ht[1]设置为ht[0]，并重新在ht[1]上新建一个空表，为下次rehash做准备

上面说到字典的哈希表rehash的过程是渐进式的，这里渐进的过程具体如下：

为ht[1]分配空间，此时字典同时持有ht[0]和ht[1]
将rehashidx设为0，表示rehash正式开始
在rehash期间，每次对字典执行任意操作时，程序除了执行对应操作之外，还会顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]，操作完后将rehashidx的值加一
在rehash期间，对字典进行ht[0].size次操作之后，rehashidx的值会增加到ht[0].size，此时ht[0]的所有键值对都已经迁移到ht[1]了，程序会将rehashidx重新置为-1，以此表示rehash完成

这里需要注意的是，在rehash的过程中，ht[0]和ht[1]可能同时存在键值对，因此在执行查询操作的时候两个哈希表都得查，而如果是执行插入键值对操作，则直接在ht[1]上操作就行。

最后说下Redis在什么条件下会对哈希表进行扩展或收缩：

服务器当前没有在执行BGSAVE或BGREWRITEAOF命令且哈希表的负载因子大于等于1时进行扩展操作
服务器正在执行BGSAVE或BGREWRITEAOF命令且哈希表的负载因子大于等于5时进行扩展操作

（这里负载因子的计算公式为：负载因子=哈希表当前保存节点数/哈希表大小，而之所以在服务器进行BGSAVE或BGREWRITEAOF的时候负载因子比较大才进行扩展操作是因为此时Redis会创建子进程，而大多数操作系统采取了写时复制的技术来优化子进程使用效率，不适合在这种时候会做大规模的数据迁移活动，说白了就是为了节约内存和提升效率）