Redis底层对象实现原理分析

由于在项目中需要用到scrapy-redis这个库,所以这里额外学习一下redis的原理。我将直接根据github上的unstable分支代码分析,因为它的代码比较好读,并且质量很高。这里还推荐《Redis设计与实现》一书,它介绍了Redis中部分比较有趣的设计思路,可惜还有些没有覆盖到,需要自己去领悟。
Redis中包含了字符串STRING、列表LIST(双向链表)、集合SET、哈希表HASH、有序集合ZSET五种对象。这些对象依赖于一些内部结构,包括SDS、哈希表、链表、跳表等。注意出于性能原因,一个对象的实现往往根据具体的内容而选择不同的实现。本文主要分析了Redis使用的这些内部结构的实现原理。

SDS

SDS(simple dynamic string)是Redis中的动态字符串实现,没错,Redis又重复了C/C++的传统,自己造了套轮子。我们考虑一下设计一个字符串的几个方面,复制/移动效率、空间效率、编码问题。例如在std::string中就会进行一些短串优化(SSO)(对每个字符串对象内部维护一段较短的buffer,当buffer不够用时再向堆请求空间)、写时拷贝(COW)的方法来进行优化,这会导致不同STL下c_str不同行为。但在字符串设计时,常将其实现成immutable的,以Java为例,这是为了防止在外部对容器(如Hashset)中对象的更改破坏容器的特性(Hashset的唯一性)、并发、便于进行常量池优化考虑。但是SDS却是可变的,并且被用在实现键和值中。例如SET hello world中,键hello和值world的底层都是SDS。此外,由于其可变性,SDS还被用作缓冲区。
SDS实现在sds相关文件中,提供了支持不同最大长度的sdshdr类型,和sds开头的C-style的字符串函数。

1
2
3
4
5
6
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};

这里的len表示了字符串的长度,所以我们省去了strlen的开销(虽然我们还是可以用)。特别地,Redis的buf实际上是一个二进制数组,\0可以出现在中间,Redis只保证buf最终以\0结尾。

list

【暂略】

dict

dict的基本实现与Rehash机制

dict的实现在dict.h中,注意在deps/hiredis中也有另一个实现,注意不要搞混。

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;
// next指针
struct dictEntry *next;
} dictEntry;

dictEntry是一个KV结构,可以看到Redis以链表的形式存储KV,并且使用union来优化空间存储。我们不能从dictEntry获得任何的类型信息,所以它是依赖dictht的。

1
2
3
4
5
6
7
8
typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;

dicthtdictEntry组织起来,它维护了长度和节点数等信息,但并没有描述这个哈希表的行为、类型等信息,它将被进一步封装。

1
2
3
4
5
6
7
8
9
typedef struct dictht {
// 外面一维是哈希的**桶**,里面一维是开链表
dictEntry **table;
// 表示桶的数量,注意`dictSize`函数表示`dict`中两个ht钟所有的元素数量而不是桶的数量
unsigned long size;
unsigned long sizemask; // === size-1
// 表示哈希表中装载的元素数量,也就是每个桶中所有链表的长度之和
unsigned long used;
} dictht;

就和我在libutp里面看到的环状缓冲区一样,这里sizesizemask已经是老套路了,我们已经可以想象size一定是按照2的级数增长的,然后sizemask一定全是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
// 这些宏用来封装调用`dictType`中定义的方法
#define dictHashKey(d, key) (d)->type->hashFunction(key)
#define dictCompareKeys(d, key1, key2) \
(((d)->type->keyCompare) ? \
(d)->type->keyCompare((d)->privdata, key1, key2) : \
(key1) == (key2))

// dictAddRaw <- dictAdd
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;

// _dictKeyIndex <- dictAddRaw <- dictAdd
// 给定key,返回可以填充的slot的index。如果key已经在哈希表中存在,返回-1,并设置existing
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循环将在下文讲解
for (table = 0; table <= 1; table++) {
// 对每个表都搜索,但如果在rehash过程中返回的一定是ht[1]对应的索引值。
idx = hash & d->ht[table].sizemask;
// 注意Redis使用开链法解决哈希冲突,所以要搜完`d->ht[table].table[idx]`这条链。
he = d->ht[table].table[idx];
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key)) {
// 如果key和he->key相等(指针相等或者值相等)
if (existing) *existing = he;
return -1;
}
he = he->next;
}
// 如果不在Rehash过程中,我们不找ht[1],这个机制在后面的`dictFind`等函数中也会出现
if (!dictIsRehashing(d)) break;
}
// 我们返回idx即可,在后面插入的时候我们从**链表头**插入,
// 这样的好处是一方面我们只要记录一个链表头,
// 另一方面是Redis假设最近被添加的字段会被频繁访问
return idx;
}

在刚才的代码中出现了dict这个结构,它也就是我们真正提供的完备的哈希表。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct dict {
// `type`和`privdata`被用来实现类似继承的机制,这样我们可以自定义`dict`的行为。
dictType *type;
void *privdata;
// 这里的`ht[1]`在rehash的时候用。
dictht ht[2];
// 用来表示此时Rehash的过程(具体机制查看后文):
// -1表示未在Rehash;
// >=0表示Rehash开始,将要移动`ht[0].table[rehashidx]`这个桶。
long rehashidx;
// 表示这个字典上的**安全**迭代器的个数。
unsigned long iterators;
} dict;

当哈希表容量不够时就需要进行扩容,同时需要进行Rehash。扩容需要满足几个条件:

  1. used >= size
    回忆一下,used是会大于size的,因为开链表。
  2. dict_can_resize
    根据updateDictResizePolicy函数,在一些情况下dict_can_resizefalse,这时候不会扩张。根据《Redis设计与实现》,这种情况发生在BGSLAVE或者BGREWRITEAOF命令运行时针对COW机制的一个优化。
  3. 但是当used/size大于一个比例,默认是5,会强制扩张(注意扩张还是按照2倍)。
    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
    #define dictIsRehashing(d) ((d)->rehashidx != -1)
    static int _dictExpandIfNeeded(dict *d)
    {
    // 此时正在进行Rehash(有没有很奇怪为啥会有个正在进行中的状态?请看下文)
    if (dictIsRehashing(d)) return DICT_OK;

    // 哈希表是空的
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    // Hash表扩张条件:
    if (d->ht[0].used >= d->ht[0].size &&
    (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
    return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
    }
    /* Expand or create the hash table */
    int dictExpand(dict *d, unsigned long size)
    {
    // size是要扩张到的大小,在计算时是按照used成比例放大的,所以肯定比used要大。
    if (dictIsRehashing(d) || d->ht[0].used > size)
    return DICT_ERR;

    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;

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

    // 假如ht[0]是空的,那这是一次初始化,直接将新的hash表`n`给ht[0]。
    if (d->ht[0].table == NULL) {
    d->ht[0] = n;
    return DICT_OK;
    }

    // 否则将`n`给ht[1]。
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
    }

我们看到扩容操作只是创建了一个空的哈希表,并没有真正移动ht[0]的元素到ht[1]对应的位置上(这个过程被称作桶转移),难道这里又是COW了?通过优秀的英文能力,我们猜到了真正做Rehash的函数int dictRehash(dict *d, int n),这个函数在dictRehashMilliseconds_dictRehashStep中被调用。这个函数表示对dn步的Rehash,其中一步表示将ht[0]中的一个桶d->ht[0].table[d->rehashidx]移到ht[1]上。容易看出ht[0].size > rehashidx是始终成立的,因为ht[0].size就是桶的最多数量。注意这个n不包括空桶,Redis每次哈希可以跳过empty_visits个空桶,这时候我们要做的仅仅是自增d->rehashidx

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
62
// 这是一个时间相关的函数,表示在ms毫秒的时间里面rehash尽可能多的桶
int dictRehashMilliseconds(dict *d, int ms) {
long long start = timeInMilliseconds();
int rehashes = 0;

while(dictRehash(d,100)) {
rehashes += 100;
if (timeInMilliseconds()-start > ms) break;
}
return rehashes;
}
static void _dictRehashStep(dict *d) {
// 只有当
if (d->iterators == 0) dictRehash(d,1);
}
int dictRehash(dict *d, int n) {
int empty_visits = n*10;
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;
}
// 开始移动非空桶。
// 注意我们不能直接将这个非空桶整个移植过去,因为里面的key在Rehash之后可能会去到其他的桶里面,
// 所以我们用de来遍历这个开链表。
de = d->ht[0].table[d->rehashidx];
while(de) {
uint64_t 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++;
}

// 当ht[0].used为0时过程终止,将d->rehashidx设为-1。
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
// 将ht[1]按指针赋值给ht[0]。
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}

// 否则Rehash还没有结束。
return 1;
}

我们发现在Rehash的过程中,调用dictRehash都将ht[0]掏空一点给ht[1],直到最后过程结束后将ht[1]指针赋值给ht[0],因此在Rehash的过程中我们插入必须对ht[1],而查找删除优先在ht[0]操作,然后再ht[1]。Rehash在对哈希表每一次的增删改查中渐进进行,我们查看相关代码。

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
// dictAddRaw
if (dictIsRehashing(d)) _dictRehashStep(d);
...
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// dictFind
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
// 如果不在Rehash过程中,我们找完ht[0]就不找了
if (!dictIsRehashing(d)) return NULL;
}
// dictGenericDelete
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
...
// _dictKeyIndex
见前面

遍历机制

Redis中的遍历分为两块,第一个是dictScan函数,第二个是借助dictIterator这个迭代器。
由于Redis中哈希表的动态扩展和缩小中有渐进Rehash的过程,所以做到恰巧一遍的遍历是非常难的,函数dictScan的实现确保了每个元素都能遍历到,但可能存在元素被重复遍历。函数dictScan接受一个cursor即参数v,并移动这个cursor,返回其新值,初始情况下我们传入v为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
#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)
// 进行位反转
static unsigned long rev(unsigned long v) {
unsigned long s = 8 * sizeof(v); // bit size; must be power of 2
unsigned long mask = ~0;
while ((s >>= 1) > 0) {
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
return v;
}
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction* bucketfn, void *privdata){
dictht *t0, *t1;
const dictEntry *de, *next;
unsigned long m0, m1;

// 如果没有元素,直接返回0,表示遍历完毕
if (dictSize(d) == 0) return 0;
if (!dictIsRehashing(d)) {
// 假设不在Rehash过程中,此时只有ht[0]中有元素
t0 = &(d->ht[0]);
m0 = t0->sizemask;

// 下面这一串表示对桶和桶中所有元素调用bucketfn和fn回调函数
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) {
next = de->next;
fn(privdata, de);
de = next;
}

v |= ~m0;
v = rev(v);
v++;
v = rev(v);
} else {
...
}
return v;
}

这里对v的更新十分奇妙,按照理想情况,我们完全可以去直接v++然后遍历完所有的桶,但是那四行代码的行为却很奇特,这种遍历方法被称为reverse binary iteration。首先第一行将v的高位0全部置为1,第二行将v按比特反转,这时候高位填充的1就到了最低位上。接着后面两行进行自增,再倒回去。以mask = (uint8_t) 15v = (uint8_t) 2为例查看一下这个过程。

00000010(2) -> 11110010 -> 01001111 -> 01010000 -> 00001010(10)

我们从v=0开始迭代,发现值依次是

0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0
0b0000 0b1000 0b0100 0b1100 0b0010 0b1010 0b0110 0b1110 0b0001 0b1001 0b0101 0b1101 0b0011 0b1011 0b0111 0b1111

为什么要做这样的设计呢?我们考虑将数字[0,7]哈希到2和4的不同情况,可以发现哈希到4时每个slot里数字的后2位都相同,而哈希到2时每个slot里数字的后1位相同。我们可以认为从$2^i$到$2^{i+1}$,我们将每个slot中的数按照第i位的值分成两个slot。

0(00):0(000),4(100)
1(01):1(001),5(101)
2(10):2(010),6(110)
3(11):3(011),7(111)
===
0:0(000),2(010),4(100),6(110)
1:1(001),3(011),5(101),7(111)

在上面讨论了更通用的情形,特别用了slot而不是之前提到的桶的概念。在这篇文章中,一个桶指的是ht中哈希值相同的所有元素组成的链表,现在讨论的dictScan是针对桶的扫描而不是元素的扫描。特别地,我们将哈希表中的N个桶合并成N/2个桶时,相当于做一次针对桶的哈希。考虑一个8个桶的哈希表,其桶的遍历顺序是0 4 2 6 1 5 3 7 0。假设遍历6(110)前我们将8个桶缩小到4个桶,那么桶6中的元素应当被映射到新桶2(10)中了,因此我们应当遍历2(10)这个桶,此时我们已经遍历过的桶如下示意

新桶      原桶
0(00):0(000),4(100)
1(01):
2(10):2(010)
3(11):

容易发现此时我们重复遍历了原来桶2(010)中的元素。这个过程结束时新的mask为3,v会更新到1(01),我们发现下面要遍历的1 5两个就桶被合并到了1(01)这个新桶里面。如果考虑遍历2(010)前发生了缩小,那么我们就不要重复遍历元素。

迭代器

迭代器的声明如下,容易看出通过dindextable我们可以确定一个桶。safe表示这个迭代器是否是一个安全的迭代器。我们刚在Rehash机制中看到,在存在safe迭代器的情况下

1
2
3
4
5
6
7
8
typedef struct dictIterator {
dict *d;
long index;
int table, safe;
dictEntry *entry, *nextEntry;
/* unsafe iterator fingerprint for misuse detection. */
long long fingerprint;
} dictIterator;

zskiplist

zskiplist是跳表,Redis用它来实现有序集合。跳表的查找复杂度是平均$O(lg n)$最坏$O(n)$。

Redis内存管理

Redis在内部自己实现了一套zmalloc系列函数进行内存管理。