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

链表和字典(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;
}