Redis 字典

本文将介绍Redis字典的具体实现。

基本结构

Redis字典和Python的字典（Java中的Map）的性质是一样的，也被称为关联数组或映射，是一种保存键值对的数据结构。

Redis字典使用哈希表作为底层实现，字典中的键不允许相同。

1
2
3
4
5
6
typedef struct dictht {
    dictEntry **table; // 哈希表
    unsigned long size; // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩码
    unsigned long used; // 已使用大小
} dictht;

哈希表中每一个键值对用dictEntry来表示，

1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry {
    void *key; // 键
    union { // 值
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 链表指针
} dictEntry;

其中，next指针是用来解决哈希表的键冲突的，所有key的哈希值相同的节点都会添加在链表上。v`值支持4种格式：指针、unit64_t、int64_t、double类型。

哈希算法

添加新的键值对时，需要先计算键的哈希值和索引值，然后按照索引值把键值对插入到对应的位置。

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
// 查找key在索引中的位置
static int _dictKeyIndex(dict *d, const void *key, unsigned int hash, dictEntry **existing)
{
    unsigned int 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++) { // 遍历两个哈希table
        idx = hash & d->ht[table].sizemask; // 获取table上索引位置
        /* 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;
}

// 添加键值对
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    int index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d); // 如果在rehash，则采用渐进方式

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) // -1代表已存在
        return NULL;

    ...
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index]; // 链表头插法
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

功能实现

rehash

当桶后面的链表不断增长时，访问目标键值变慢，就需要rehash来加快访问速度（减少链表长度）。

此外，随着键值对的添加和删除，需要动态调整哈希表的大小。

在redis中，字典的存储结构如下，

1
2
3
4
5
6
7
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2]; // 默认使用ht[0],ht[1]用于rehash
    long rehashidx; /* 是否执行rehash的标识rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

其中，ht[2]用来存储字典内容，只有在进行rehash操作时，ht[1]才会被用到（默认hash数据都存储在ht[0]上）。

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
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;

        ...
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++; // 如果当前table桶中数据为空，则增加索引值
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx]; // 获取当前哈希桶中的第一个键值对
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) { // 遍历哈希桶中的所有数据
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask; // rehash原有数据到新的哈希表的桶中
            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;
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) { //如果原有hash表中所有数据已转移完成，则释放旧哈希表
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

在进行rehash的过程中，字典会同时在ht的两个table上进行查找、删除、更新操作，而新增只会在ht[1]上操作。

哈希表扩展

redis提供了dictExpand函数来扩展哈希表的大小。

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
// 哈希表扩展
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size); // 计算哈希表的大小

    ...

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) { // 如果哈希表ht[0]没有被初始化，则使用ht[0]
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    // 否则，使用ht[1]用于rehash方式扩展
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX;
    while(1) {
        if (i >= size)
            return i;
        i *= 2; // 2的指数被增大
    }
}