【Redis】基础数据结构-字典

Redis 字典

基本语法

字典是Redis中的一种数据结构，底层使用哈希表实现，一个哈希表中可以存储多个键值对，它的语法如下，其中KEY为键，field和value为值（也是一个键值对）：

HSET key field value
1

根据Key和field获取value：

HGET key field
1

哈希表

数据结构

dictht

dictht是哈希表的数据结构定义：

• table：哈希表数组，数组中的元素是dictEntry类型的
• size：哈希表数组的大小
• sizemask：哈希表大小掩码，一般等于size-1
• used：已有节点的数量（存储键值对的数量）

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
1
2
3
4
5
6

dictEntry

dictEntry是哈希表节点的结构定义：

• key：键值对中的键
• v：键值对中的值
• next：由于会出现哈希冲突，所以next是指向下一个节点的指针

typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值
    struct dictEntry *next; // 指向下一个节点的指针
} dictEntry;
1
2
3
4
5
6
7
8
9
10

dict

dict是Redis中字典的结构定义：

• type：指向dictType的指针
• privdata
• ht[2]：一个dictht类型的数组，数组大小为2，保存了两个哈希表，rehash时使用
• rehashidx：记录了当前rehash的进度
• pauserehash：rehash暂停标记，大于0表示没有进行rehash

typedef struct dict {
    dictType *type; // 
    void *privdata; // 私有数据
    dictht ht[2]; // 保存了两个哈希表
    long rehashidx; // rehash的进度标记
    int16_t pauserehash; 
} dict;

typedef struct dictType {
    uint64_t (*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);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

哈希冲突

一个键值对放入哈希表的时候，会根据key的值，计算一个hash值，然后根据hash值与哈希表大小掩码做与运算得到一个索引值，索引值决定元素放入哪个哈希桶中（落入哈希表数组哪个索引位置处）。

 // 计算hash值
 hash = dictHashKey(d,key)
 // 计算索引
 idx = hash & d->ht[table].sizemask;
1
2
3
4

在进行哈希计算的时候，不可避免会出现哈希冲突，出现哈希冲突的时候，Redis采用链式哈希解决冲突，也就是落入同一个桶中的元素，使用链表将这些冲突的元素链起来（dictEntry中的next指针）。

rehash

由于Redis采用链式哈希解决冲突，那么在冲突频繁的场景下，链表会变得越来越长，这种情况下查找效率是比较低下的，需要遍历链表对比KEY的值来获取数据，为了处理效率低下的问题，需要对哈希表进行扩容，扩容的过程称为rehash。

在dict结构替中ht保存了两个哈希表，ht[0]用于数据正常的增删改查，ht[1]用于rehash：

（1）正常情况下，所有的增删改查操作都在ht[0]中进行；

（2）需要进行rehash时，会使用ht[1]建立新的哈希表，并将ht[0]中的数据迁移到ht[1]中；

（3）迁移完成后，ht[0]的空间被释放，然后将ht[1]地址赋给ht[0]，ht[1]的大小被设为0，ht[0]重新接收正常的请求，回到了第（1）步的状态；

rehash的触发条件

/* 判断是否需要扩容 */
static int _dictExpandIfNeeded(dict *d)
{
    /* 如果已经处于rehash状态中直接返回 */
    if (dictIsRehashing(d)) return DICT_OK;

    /* 如果ht[0]的大小为0，意味着哈希表为空，此时做初始化操作 */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /*如果已经存储的节点数量大于或等于哈希表数组的大小，并且跨域扩容或者（节点数量/哈希表数组大小）大于一个比例，同时根据字典的类型判断是否允许分配内存*/
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&
        dictTypeExpandAllowed(d))
    {   
        // 进行扩容
        return dictExpand(d, d->ht[0].used + 1);
    }
    return DICT_OK;
}

/* 由于扩容需要分配内存，这里检查字典类型分配是否被允许*/
static int dictTypeExpandAllowed(dict *d) {
    if (d->type->expandAllowed == NULL) return 1;
    return d->type->expandAllowed(
                    _dictNextPower(d->ht[0].used + 1) * sizeof(dictEntry*),
                    (double)d->ht[0].used / d->ht[0].size);
}
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

d->ht[0].used/d->ht[0].size : 节点数量与哈希表数组大小的比例，称作负载因子。

dict_force_resize_ratio 的默认值是 5。

1. ht[0]的大小为0，此时哈希表是空的，相当于对哈希表做一个初始化的操作。
2. 如果哈希表中存储的节点数量大于或者等于哈希表数组的大小，并且哈希表可以扩容或者负载因子大于dict_force_resize_ratio（默认值为5），根据字典的类型判断允许分配内存，满足这三个条件开始扩容。

dict_can_resize

dict_can_resize用来判断哈希表是否可以扩容，有两种状态，值分别为1和0，1代表可以扩容，0代表禁用扩容：

void dictEnableResize(void) {
    dict_can_resize = 1;
}

void dictDisableResize(void) {
    dict_can_resize = 0;
}
1
2
3
4
5
6
7

updateDictResizePolicy中对dict_can_resize的状态进行了控制，当前没有RDB子进程并且也没有AOF子进程时设置dict_can_resize状态为可扩容：

void updateDictResizePolicy(void) {
    // 没有RDB子进程并且也没有AOF子进程
    if (server.rdb_child_pid == -1 && server.aof_child_pid == -1)
        dictEnableResize(); // 启用扩容
    else
        dictDisableResize(); // 禁用扩容
}
1
2
3
4
5
6
7
8

扩容大小

从代码中可以看到，扩容后哈希表数组的大小为已经存储的节点数量+1：

// 进行扩容
return dictExpand(d, d->ht[0].used + 1);
1
2

一些旧版本中扩容后的大小为已存储节点数量的2倍：

dictExpand(d, d->ht[0].used*2);
1

渐进式hash

当哈希表存储节点内容比较多时，需要将原来的节点一个一个拷贝到新的哈希表中，此时Redis主线程无法执行其他请求，造成阻塞，影响性能，为了解决这个问题，引入了渐进式hash。

渐进式hash并不会一次把旧节点全部拷贝到新的哈希表中，而是分多次渐进式的完成拷贝，其中rehashidx记录了迁移进度，每一次迁移的过程中会更新rehashidx的值，下一次进行数据迁移的时候，从rehashidx的位置开始迁移，在dictRehash中可以看到迁移的处理：

1. 方法传入了一个参数n，代表本次需要迁移几个哈希桶
2. 根据需要迁移哈希桶的数量，循环处理每一个哈希桶：
   • 如果当前哈希桶中为空，继续下一个桶的处理rehashidx++
   • 如果当前哈希桶不为空，将当前桶中的所有节点迁移到新的哈希表中，然后更新rehashidx的值继续处理下一个桶
3. 如果已经处理够了n个桶，或者哈希表的所有数据已经迁移完毕，则结束迁移。

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;
    // 循环处理每一个哈希桶，n为需要迁移哈希桶的数量
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        // 如果当前哈希桶没有存储数据
        while(d->ht[0].table[d->rehashidx] == NULL) {
            // rehashidx的值是哈希表数组的某个索引值（指向了某个哈希桶），意味着当前迁移到数组的哪个索引位置处
            d->rehashidx++; // 继续下一个桶
            if (--empty_visits == 0) return 1;
        }
       
        de = d->ht[0].table[d->rehashidx];
        // 如果当前的哈希桶中存储着数据，将哈希桶存储的所有数据迁移到新的哈希表中
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        // rehashidx，继续迁移下一个哈希桶
        d->rehashidx++;
    }

    /* 判断ht[0]的节点是否迁移完成 */
    if (d->ht[0].used == 0) {
        // 释放ht[0]的空间
        zfree(d->ht[0].table);
        // 将ht[0]指向ht[1]
        d->ht[0] = d->ht[1];
        // 重置ht[1]的大小为0
        _dictReset(&d->ht[1]);
        // 设置rehashidx，-1代表rehash结束
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}
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
38
39
40
41
42
43
44
45
46
47
48
49

_dictRehashStep

_dictRehashStep中可以看到调用dictRehash时，每次迁移哈希桶的数量为1：

static void _dictRehashStep(dict *d) {
    if (d->pauserehash == 0) dictRehash(d,1);
}
1
2
3

总结

1. Redis字典底层使用哈希表实现。

2. 键值对放入哈希表的时候，会根据key的值，计算hash值，出现哈希冲突的时候，Redis采用链式哈希解决冲突，使用链表将这些冲突的元素链起来。

3. 由于Redis采用链式哈希解决冲突，那么在冲突频繁的场景下，链表会变得越来越长，这种情况下查找效率是比较低下的，需要遍历链表对比KEY的值来获取数据，为了处理效率低下的问题，需要对哈希表进行扩容，扩容的过程称为rehash。

4. 当哈希表存储节点内容比较多时，进行rehas的时候主线程无法执行其他请求，造成阻塞，影响性能，所以采用了渐进式hash，渐进式hash并不会一次把旧节点全部拷贝到新的哈希表中，而是分多次渐进式的完成拷贝。

参考

黄健宏《Redis设计与实现》

极客时间 - Redis源码剖析与实战(蒋德钧)

美团针对Redis Rehash机制的探索和实践

Redis版本：redis-6.2.5