Dict详解

[toc]

Dict：一个key-value型的数据结构。我们知道Redis就是键值对型的数据库，它正是基于Dict来实现的。

Dict和Entry结构体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct dict {
    dictType *type;					// dict类型，内置了不同的哈希函数（不同场景使用不同函数，拓展性强）

    dictEntry **ht_table[2];		// 指向dictEntry数组，两个表一个是当前数据，另一个为空，rehash时使用
    unsigned long ht_used[2];		// 哈希表当前负载

    long rehashidx; 				// rehash的进度，-1表示未进行rehash

    /* Keep small vars at end for optimal (minimal) struct padding */
    unsigned pauserehash : 15; 		// 指示rehash是否暂停，可以防止哈希不一致

    unsigned useStoredKeyApi : 1; 	/* See comment of storedHashFunction above */
    signed char ht_size_exp[2]; 	// 哈希表大小的指数位：例如若为4，则表大小size = 2 ^ 4 = 16
    int16_t pauseAutoResize;  		//用于控制自动Resize
    void *metadata[];				// 存储额外的元数据
};

Entry：键值对，v是联合体中的任意一种

1
2
3
4
5
6
7
8
9
10
struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     //	链表，哈希冲突时拉链法使用
};
Dict添加规则

当向Dict中添加键值对时，Redis首先根据key计算出哈希值h，然后通过h & sizemask计算应该存储到的索引，如果发生冲突，那么采用拉链法解决冲突问题。

  • 此处原理：哈希表的大小都是2的指数次幂；因此在二进制中，模运算其实就是求它二进制最末尾几位的数字。

    比如 110101 % 8其实就是保留最后的3位（2^3 = 8），那它就等价于 110101 & 7 ，因为7 = 000111b，也因此sizemask = size -1

流程示例

Dict初始大小为4，如图：

image-20240919224326635

插入第一个元素,假设hashcode(k1) = 1 => 1 & 3 = 1，因此存储到下标1处，如图

  • 更新了used为1，连接了插入的Entry

image-20240919224451053

插入第一个元素,假设hashcode(k2) = 1 => 1 & 3 = 1，因此发生哈希冲突，采用拉链法存储到下标1处，如图

  • 新元素放在链表的队首，效率高

image-20240919224639242

Dict扩容

Dict在每次新增键值对时都会去检查负载因子loadFactor = used / size，满足以下两种情况时进行扩容：

  • loadFactor>=1 且 服务器没有执行BGSAVE或BGREWRITEAOF等后台进程

  • loadFactor>5且resize未被禁止

    • resize的三种状态
    1
    2
    3
    4
    5
    typedef enum {
        DICT_RESIZE_ENABLE,
        DICT_RESIZE_AVOID,
        DICT_RESIZE_FORBID,
    } dictResizeEnable;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int dictExpandIfNeeded(dict *d) {
    if (dictIsRehashing(d)) return DICT_OK;			// 已经在Rehash,直接返回
    if (DICTHT_SIZE(d->ht_size_exp[0]) == 0) {		// 如果哈希表为空，初始化哈希表（默认大小为4）
        dictExpand(d, DICT_HT_INITIAL_SIZE);
        return DICT_OK;
    }

    if ((dict_can_resize == DICT_RESIZE_ENABLE &&
         d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0])) ||		// 达到了1:1并且dict_can_resize == DICT_RESIZE_ENABLE
        (dict_can_resize != DICT_RESIZE_FORBID &&										// 并且resize未被禁止
         d->ht_used[0] >= dict_force_resize_ratio * DICTHT_SIZE(d->ht_size_exp[0])))	// 达到了dict_force_resize_ratio
    {																					
        if (dictTypeResizeAllowed(d, d->ht_used[0] + 1))
            dictExpand(d, d->ht_used[0] + 1);
        return DICT_OK;
    }
    return DICT_ERR;
}
  • 需要注意的是，哈希表大小始终是$2^n$，因此扩容会扩到满足条件且容量是$2^n$。
Dict收缩

Dict在删除元素时，也会检查负载因子，当loadFactor<0.125且允许resize时，触发哈希表收缩。或者当loadFactor<1/32，且resize未被禁止时收缩。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dictShrinkIfNeeded(dict *d) {
    if (dictIsRehashing(d)) return DICT_OK;				// 已经在Rehash,直接返回
    
    if (DICTHT_SIZE(d->ht_size_exp[0]) <= DICT_HT_INITIAL_SIZE) return DICT_OK;	// 如果已经收缩到初始大小4，不再收缩

    // 低于1:8且dict_can_resize == DICT_RESIZE_ENABLE->收缩，或者低于1:32且dict_can_resize != DICT_RESIZE_FORBID收缩 
    if ((dict_can_resize == DICT_RESIZE_ENABLE &&
         d->ht_used[0] * HASHTABLE_MIN_FILL <= DICTHT_SIZE(d->ht_size_exp[0])) ||
        (dict_can_resize != DICT_RESIZE_FORBID &&
         d->ht_used[0] * HASHTABLE_MIN_FILL * dict_force_resize_ratio <= DICTHT_SIZE(d->ht_size_exp[0])))
    {
        if (dictTypeResizeAllowed(d, d->ht_used[0]))
            dictShrink(d, d->ht_used[0]);
        return DICT_OK;
    }
    return DICT_ERR;
}

最终Dict扩容和收缩最终都由_dictResize函数来完成

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
/* Resize or create the hash table,
 * when malloc_failed is non-NULL, it'll avoid panic if malloc fails (in which case it'll be set to 1).
 * Returns DICT_OK if resize was performed, and DICT_ERR if skipped. */
int  _dictResize(dict *d, unsigned long size, int* malloc_failed)
{
    if (malloc_failed) *malloc_failed = 0;
    assert(!dictIsRehashing(d));			// assert Rehash未在进行中

    // 新哈希表
    dictEntry **new_ht_table;
    unsigned long new_ht_used;
    signed char new_ht_size_exp = _dictNextExp(size);	// 找到最接近的2的指数

    // 溢出检测
    size_t newsize = DICTHT_SIZE(new_ht_size_exp);
    if (newsize < size || newsize * sizeof(dictEntry*) < newsize)
        return DICT_ERR;

    // Rehash前后表大小相同是无用的
    if (new_ht_size_exp == d->ht_size_exp[0]) return DICT_ERR;

    //	分配新的哈希表，并初始化所有指针为NULL
    if (malloc_failed) {
        new_ht_table = ztrycalloc(newsize*sizeof(dictEntry*));
        *malloc_failed = new_ht_table == NULL;
        if (*malloc_failed)
            return DICT_ERR;
    } else
        new_ht_table = zcalloc(newsize*sizeof(dictEntry*));

    new_ht_used = 0;

    // 准备第二个哈希表用于重新散列，将旧表的数据迁移到新表中，第一次初始化也使用了
    d->ht_size_exp[1] = new_ht_size_exp;
    d->ht_used[1] = new_ht_used;
    d->ht_table[1] = new_ht_table;
    d->rehashidx = 0;
    if (d->type->rehashingStarted) d->type->rehashingStarted(d);

    // 如果是第一次初始化而不是真正的扩容，进行以下调整，使得它能够接受keys
    if (d->ht_table[0] == NULL || d->ht_used[0] == 0) {
        if (d->type->rehashingCompleted) d->type->rehashingCompleted(d);
        if (d->ht_table[0]) zfree(d->ht_table[0]);
        d->ht_size_exp[0] = new_ht_size_exp;
        d->ht_used[0] = new_ht_used;
        d->ht_table[0] = new_ht_table;
        _dictReset(d, 1);
        d->rehashidx = -1;
        return DICT_OK;
    }

    return DICT_OK;
}
Dict的Rehash

示例如下：一个哈希表容量为4，并且已经装载了4个键值对，即将插入第五个，触发了扩容。

  • 未插入第五个键值对时：

image-20240920144309297

  • 插入第五个键值对后，进行了重新散列

image-20240920144634170

  • 移动散列表，调整参数并将另一个表重新置为空

image-20240920144926708

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
/*	如果还有key没移动完成返回1，否则返回0
*	重新散列将一个桶从旧的哈希表移动到新的哈希表，由于哈希表的一部分可能是空，因此不能保证此函数至少重新散列一个桶。
*	为保证不会出现长时间阻塞，它将最多访问n*10个空桶。
*/	
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; // 最大的空bucket访问数，防止阻塞时间过长
    unsigned long s0 = DICTHT_SIZE(d->ht_size_exp[0]);
    unsigned long s1 = DICTHT_SIZE(d->ht_size_exp[1]);			// 获取当前和新哈希表大小，分别为s0和s1
    if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0;		// 检查是否可以重新散列
    /* 乳沟dict_can_resize = DICT_RESIZE_AVOID, 要避免rehash. 
     * - 如果扩容, threshold 为 dict_force_resize_ratio = 4.
     * - 如果收缩, threshold 为 1 / (HASHTABLE_MIN_FILL * dict_force_resize_ratio) = 1/32 */
    if (dict_can_resize == DICT_RESIZE_AVOID && 
        ((s1 > s0 && s1 < dict_force_resize_ratio * s0) ||
         (s1 < s0 && s0 < HASHTABLE_MIN_FILL * dict_force_resize_ratio * s1)))
    {
        return 0;
    }

    while(n-- && d->ht_used[0] != 0) {
        // 因为ht[0].used不为0，所以能够确保rehashidx不会溢出
        assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);
        while(d->ht_table[0][d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        // 移动此bucket中的所有key到新的哈希表
        rehashEntriesInBucketAtIndex(d, d->rehashidx);
        d->rehashidx++;
    }

    return !dictCheckRehashingCompleted(d);
}

值得注意的是，Dict的rehash不是一次完成的，如果Dict含有大量元素，那么一次性完成将会造成长时间的阻塞。因此Dict的rehash是多次、分批完成的，也叫作渐进式rehash。

  • 每次增删改查时都会检查是否已经rehash完成，如果未完成则进行一部分的迁移。
  • 在新增时，直接写入新表，而查、改、删会查询两个表，确保旧表数据只减不增，最终能完成rehash任务。