Redis数据结构之——hash

写在前面

以下内容是基于Redis 6.2.6 版本整理总结

一、Redis 数据结构hash的编码格式

Redis中hash数据类型使用了两种编码格式:ziplist(压缩列表)、hashtable(哈希表)

在redis.conf配置文件中，有以下两个参数，意思为：当节点数量小于512并且字符串的长度小于等于64时，会使用ziplist编码。

hash-max-ziplist-entries 512    
hash-max-ziplist-value 64  
1
2

二、压缩链表（ziplist）

ziplist 我们整理在下一篇文章。

三、哈希表（hashtable）

Redis中的字典（dict）使用哈希表作为的底层实现，一个哈希表里可以有多个哈希表的节点，每个节点保存字典中的一个键值对。

哈希表结构定义如下：

typedef struct dictht {
    dictEntry **table;  // 哈希表数组 每个元素都是 dictEntry 的指针，指向 dictEntry;
    unsigned long size; // 哈希表大小
    unsigned long sizemask; // 用来计算索引值 always： sizemask = size - 1
    unsigned long used; // 哈希表已有节点的数量
} dictht;
1
2
3
4
5
6

哈希表节点定义如下：
哈希表节点使用 dictEntry 结构表示，每个 dictEntry 结构都保存着一个键值对和冲突后的链表的下一个节点。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 保存下一个 dictEntry 的地址，形成链表
} dictEntry;
1
2
3
4
5
6
7
8
9
10

其中，value 是一个联合体，可以保存多种数据类型。当value类型为 uint64_t 、int64_t 或 double时可以直接存储。其他类型需要在其他位置申请一段空间来存放，并用val指向这段空间来使用。

字典结构定义如下：

// location： dict.h
typedef struct dict {
    dictType *type;  // 指向 dictType 结构的指针
    void *privdata;  // 存储私有数据的指针，在 dictType 里面的函数会用到
    dictht ht[2];    // 两个哈希表，扩容时使用，后面会结合源码详细说明
    long rehashidx;  // 值为-1时，表示没有进行rehash，否则保存rehash执行到那个元素的数组下标 
    int16_t pauserehash; // >0 表示rehash暂停，<0 表示编码错误 
} dict;
1
2
3
4
5
6
7
8

dictType 结构定义如下

dictType 结构体定义了一系列操作key-value键值对的方法的函数指针，在实际运行时传入指定函数，就能实现预期的功能，有点运行时多态绑定的味道。

// 操作特性键值对的函数簇
typedef struct dictType {
    uint64_t (*hashFunction)(const void *key); // 计算哈希值的函数
    void *(*keyDup)(void *privdata, const void *key);  // 复制key的函数
    void *(*valDup)(void *privdata, const void *obj);  // 复制value的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 对比key的函数
    void (*keyDestructor)(void *privdata, void *key);  // 销毁key的函数
    void (*valDestructor)(void *privdata, void *obj);  // 销毁value的函数
    int (*expandAllowed)(size_t moreMem, double usedRatio); // 扩容
} dictType;
1
2
3
4
5
6
7
8
9
10

字典整体结构可以用下图来描述：

3.1 hash冲突

当两个或两个以上的键被分配到哈希数组的同一个索引上面时，我们称这些键发生了冲突。Redis的哈希表使用拉链法解决hash冲突。

3.2 负载因子

负载因子 = used / size ; used 是哈希数组存储的元素个数，size 是哈希数组的长度。
负载因子越小，冲突越小；负载因子越大，冲突越大。

3.3 rehash

随着命令的不断执行，哈希表保存的减值对会逐渐增加或者减少，为了让哈希表的负载因子维持在一个合理的范围内，当哈希表中的键值对过多或过少时，需要对哈希表的大小进行相应的扩展和收缩。而哈希表的扩展和收缩可以通过rehash来执行。rehash 就是将 ht[0] 中的节点，通过重新计算哈希值和索引值放到 ht[1] 哈希表指定的位置上。

扩容

• 如果负载因子大于1，就会触发扩容，扩容的规则是每次翻倍；
• 如果正在fork，执行持久化则不会扩容，但是，如果负载因子大于5，会立马扩容。

缩容
如果负载因子小于0.1，就会触发缩容。缩容的规则是：恰好包含used的2^n。

3.4 渐进式rehash

当哈希表中的元素过多时，如果一次性rehash到ht[1]，庞大的计算量，可能导致redis服务在一段时间不可用。为了避免rehash对服务器带来的影响，redis分多次、慢慢的将ht[0]哈希表中的键值对rehash到ht[1]哈希表，这就是渐进式rehash。

核心思想：将整个rehash过程均摊到每次命令的执行中。

rehash的详细步骤：

1. 为 ht[1] 哈希表分配空间，此时字典同时拥有ht[0] 和 ht[1] 两个字典
2. 将字典中的rehashidx设置为0，表示开始rehash
3. 在rehash期间，每次对字典的增删改查，除了执行指定的命令外，还会顺带将ht[0] 中 rehashidx 索引上的所有键值对都rehash到ht[1]中，执行完rehash，rehashidx属性加一。注意：新增的键值对只能插入到ht[1]哈希表中，保证ht[0]的键值对只减不增。
4. 随着操作的不断进行，最终ht[0]哈希表中的所有键值对都被rehash到ht[1]中。此时，将ht[0]释放掉，让ht[0] 指向ht[1]，并设置rehashidx 为 -1，表示rehash完成。

四、字典常用 API

// 创建字典
dict *dictCreate(dictType *type, void *privDataPtr);
// 将键值对 key-val 插入到字典
int dictAdd(dict *d, void *key, void *val);
// 删除字典中指定 key 的键值对
int dictDelete(dict *d, const void *key);
// 获取指定key的value值
void *dictFetchValue(dict *d, const void *key);
// 将键值对 key-val 插入到字典,如果该key已经存在，则只更新val
int dictReplace(dict *d, void *key, void *val);
1
2
3
4
5
6
7
8
9
10

五、Rehash源码分析

5.1 添加元素步骤

// 1. 通过hash函数得到hash值
hash = dict->type->hashFunction(key);
// 2. 将hash值与对应哈希表的sizemask 进行 & 操作得到index
index= hash & d->ht[x].sizemask; // x = 0 or 1
// 3. 创建 dictEntry 节点，头插法插入到对应哈希表的index的位置
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
1
2
3
4
5
6
7
8

添加元素源码分析

redis使用 dictAdd() 方法往哈希表中添加元素。dictAdd 调用的是 dictAddRaw 方法，它会先通过_dictKeyIndex() 函数计算出table的index；再通过头插法将该节点插入到目标位置。

dictAdd() 函数

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;

	// 将 val 保存到 entry 节点
    dictSetVal(d, entry, val);
    return DICT_OK;
}

1
2
3
4
5
6
7
8
9
10
11
12

dictAddRaw() 函数

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    // 计算index
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    /* Allocate the memory and store the new entry.
     * Insert the element in top, with the assumption that in a database
     * system it is more likely that recently added entries are accessed
     * more frequently. */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    // 头插法 最快
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    // 将 key 保存在 entry 节点中
    dictSetKey(d, entry, key);
    return entry;
}
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

其中，在_dictKeyIndex() 函数计算index的时候，会调用 _dictExpandIfNeeded() 函数判断是否满足扩容的条件。其中有个条件是依赖于 dictTypeExpandAllowed(d) 的返回值。

_dictKeyIndex() 函数

static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    for (table = 0; table <= 1; table++) {
        idx = hash & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

_dictExpandIfNeeded() 函数

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

dictTypeExpandAllowed() 函数

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

可以看到，如果 dictType 中没有设置 expandAllowed 函数，则直接返回真；如果设置了expandAllowed 函数，就需要执行完相应的函数才能确定是否可以扩缩容。这就是 dictType 的一个典型的应用场景。

5.2 rehash 源码分析

该函数每次从rehashidx开始的位置，固定扫描 10 个bucket，如果对应的bucket中有数据就 rehash 到 ht[1]中。

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

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);

        // 跳过空的槽位
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            // 如果 经过 n*10 次，还是为空，本次rehash结束
            if (--empty_visits == 0) return 1;
        }

        // 找到要rehash的bucket
        de = d->ht[0].table[d->rehashidx];
       
        // 遍历该bucket对应的dictEntry链表
        while(de) {
            uint64_t h;

            nextde = de->next;
            // 为该dictEntry 获取在ht[1]中的index 
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;

            // 头插法 de->next 指向 ht[1].table[h]的第一个元素 （可能为NULL，可能有元素）
            de->next = d->ht[1].table[h];

            // 更新ht[1].table[h]的值指向该 dictEntry
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;

            de = nextde; // 更新de，继续遍历，直至为空
        }
        // 将ht[0]中 d->rehashidx 对应的bucket清空
        d->ht[0].table[d->rehashidx] = NULL;
        // 更新rehashidx
        d->rehashidx++;
    }

    // 检查整个ht[0]表，rehash是否完成
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table); // 释放ht[0]
        d->ht[0] = d->ht[1];   // 让ht[0] 指向 rehash后的 ht[1]
        _dictReset(&d->ht[1]); // 重置 ht[0], 以备下次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
50
51
52
53
54
55
56
57
58
59
60
61

文章参考与<零声教育>的C/C++linux服务期高级架构系统教程学习