Redis源码剖析——链表和字典

发表于 | 分类于 | 阅读次数:
字数统计: 2,113 字

链表和字典（dict）是比较常用的数据结构，但是C语言在底层并没有内置这种数据结构，这里通过源码查看这两个数据结构在Redis底层的实现

链表结构

Redis底层使用的是一个双端链表

链表节点结构定义：

1
2
3
4
5
6
// 双端链表节点
typedef struct listNode {
    struct listNode *prev;  // 前置节点
    struct listNode *next;  // 后置节点
    void *value;   // 节点值
} listNode;

链表迭代器结构定义：

1
2
3
4
5
// 双端链表迭代器
typedef struct listIter {
    listNode *next; // 迭代的指针
    int direction;  // 迭代的方向
} listIter;

通过迭代器可以比较容易对整个链表进行遍历，从而轻松实现查找等功能。

链表结构定义

1
2
3
4
5
6
7
8
9
// 双端链表
typedef struct list {
    listNode *head;  // 头结点
    listNode *tail;  // 尾节点
    void *(*dup)(void *ptr);  // 节点值复制函数，可指定复制的方法
    void (*free)(void *ptr);  // 节点值释放函数
    int (*match)(void *ptr, void *key);  // 节点值对比函数
    unsigned long len;   // 链表中所包含的节点数量
} list;

Redis底层中所包含的链表API都是对链表常用功能的实现，比如说插入、删除、搜索等，这里不在解释。

Redis的链表实现的特点有如下几个：

  • 双端，方便向前和向后便利
  • 多态，链表节点使用void*指针来保存节点值,并且可以通过1ist结构的dup、free、 match三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。

字典

字典,又称为符号表( symbol table)、关联数组( associative array)或映射(map),是种用于保存键值对(key- value pair)的抽象数据结构。

字典在Reds中的应用相当广泛,比如 Redis的数据库就是使用字典来作为底层实现的,对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

字典的实现

Redis的字典用哈希表作为底层实现，哈希表中含有哈希表节点，而每一个哈希表节点就保存了字典中的一个键值对。

哈希表

1
2
3
4
5
6
typedef struct dictht {
    dictEntry **table;  // 哈希表的节点数组
    unsigned long size; // 哈希表大小
    unsigned long sizemask;  // 哈希表的大小掩码，用于计算索引值，总等于size-1
    unsigned long used; // 哈希表中含有的节点数
} dictht;

sizemask属性的值总是等于size-1,这个属性和哈希值一起决定一个键应该被放到tab1e数组的哪个索引上面。

哈希表节点

1
2
3
4
5
6
7
8
9
10
11
// 哈希表节点
typedef struct dictEntry {
    void *key;  // 键  
    union {  
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;   // 值
    struct dictEntry *next;  // 下一个哈希表结点，形成链表
} dictEntry;

Redis中哈希表解决冲突的方法是拉链法，所以其中有next属性指向另一个哈希表节点的指针,这个指针可以将多个哈希值相同的键值对连接在一次,以此来解决键冲突( collision)的问题。

字典

1
2
3
4
5
6
7
typedef struct dict {
    dictType *type;  // 类型特定函数
    void *privdata;  // 私有数据
    dictht ht[2];   // 含有两个哈希表
    long rehashidx; // rehash 索引，当rehash不再运行的时候，值为-1
    int iterators;  // 现在正在运行的迭代器数量
} dict;

type属性和 privata属性是针对不同类型的键值对,为创建多态字典而设置的；ht属性是一个包含两个项的数组,数组中的每个项都是一个 dictht哈希表,一般情况下,字典只使用ht[0]哈希表,ht[1]哈希表只会在对ht[0]哈希表进行 rehash时使用。

哈希算法

把一个新的键值对加入到字典中，首先要根据key计算出哈希值和索引值，然后把新的哈希节点加到哈希表数组的指定索引上面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 计算哈希值
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        // 计算索引值
        idx = h & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        // 查找key是否存在
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }

Redis使用的是Murmur算法计算哈希值的，这种算法的优点在于,即使输人的键是有规律的,算法仍能给出一个很好的随机分布性,并且算法的计算速度也非常快。

解决键冲突

Redis采用的是链地址法( separate chaining)解决键冲突的，每个哈希表节点都有个next指针,多个哈希表节点可以用next指针构成一个单向链表,被分配到同一个索引上的多个节点可以用这个单向链表连接起来,这就解决了键冲突的问题。

1
2
3
4
5
6
/* Allocate the memory and store the new entry */
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];  // 把新的哈希节点加入到哈希数组索引处，并放在链表的头结点处
ht->table[index] = entry;
ht->used++;

重新散列（rehash）

当dict不断进行添加或删除等操作的时候，所保存的键值对也会不断的增加或者减少。为了使哈希表的负载因子（load factor）维持在合理的范围内，此时就需要对哈希表的大小进行相应的扩展或者收缩。

这个工作通过重新散列（rehash）来进行，执行的主要步骤如下：

  • 为dict的ht[1]哈希表分配合适的空间，空间的大小取决于要执行的操作和ht[0]哈希表中键值对的数量
  • 对所有在ht[0]中的键值对重新计算哈希索引值，将他们转移到ht[1]中
  • 释放ht[0]，将ht[1]设置为ht[0]

其中负载因子的计算公式为：load_factor = ht[0].used / ht[0].size

渐进式rehash

在进行rehash的过程中需要将所有的键值对从ht[0]迁移到ht[1]中，如果键值对的数量比较大的话，就会导致Redis需要停止一段时间的服务才能够完成这些操作，所以为了避免对服务性能造成影响，rehash并不是一次性的、集中式地完成的，而是分多次、渐进式完成的。

具体的步骤如下：

  • 为ht[1]分配空间，同时保留ht[0]和ht[1]两个哈希表
  • 在dict中维持一个索引计数变量rehashldx，将其值设为0，表示开始rehash（不工作是为-1）
  • 在rehash是，每对dict进行一次操作的时候，除了进行制定操作外还要ht[0]哈希表中rehashldx索引上的索引键值对转移的ht[1]上，完成以后将rehashldx加一
  • 当完成了所有ht[0]到ht[1]键值对的转移工作时，表示完成了rehash，此时将rehashldx的值设为-1

在渐进式rehash的过程中，dict同时拥有两个hash表，所以dict的删除、查找、更新等操作会在两个哈希表上同时进行。

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
// 在rehash期间每进行一次操作，迁移一个索引中所有的键值对
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++;
            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 */
        // 对每一个键值对重新计算hash值、index值，进行迁移
        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;
            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++; // 将rehashldx的值加一
    }

    /* Check if we already rehashed the whole table... */
    // 完成渐进式rehash工作
    if (d->ht[0].used == 0) {
        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;
}