redis底层数据结构

总所周知，redis支持五种数据类型String、Hash、List、Set、ZSet。在支持这些复杂数据结构的同时，redis不仅需要保证读写的性能，还能提供各种微操作，比如直接修改Hash字典中的某个field的值，或者直接往ZSet中插入某个值，redis也能快速地放到它对应顺序的位置，那么redis是如何做到的呢。
首先上面所说的操作其实分两步，第一步基于key找到对应的value，即整个hash字典对象或整个ZSet的对象，然后第二步再在hash字典中找到对应的field，或者在ZSet中按权重顺序找到对应的位置插入数据。
上面两步也是基于两个不同的数据结构来实现快速访问的，第一步是基于全局hash表来实现的，所有redis的key->value都是通过这样的方式。第二步则有很多种情况，底层的数据结构有这么些种类：SDS(simple dynamic string)简单动态字符串、字典dict、压缩列表ziplist、快速列表quickList、inset、跳跃表skiplist，对外表现的五种数据类型的底层会对应地使用其中的一种或两种来实现。

一、key的存储结构：全局Hash表

Key的存储结构：全局hash表，读写检索到对应key的位置的时间复杂度都是O(1)。再通过rehash避免key的hash冲突，保证不会存在链表过长的情况导致检索性能下降。
rehash参考：《Redis中Rehash浅析》

二、Value存储结构

1. SDS(simple dynamic string)：

redis中默认的字符串表示，key和String类型的value都是用这个数据结构。有几个优点：

1. len字段保证了获取字符串长度时，时间复杂度是O(1)，不用遍历计数。
2. 空间可以预分配，开辟空间或者字符串变更需要增加空间时，需要字符串长度len小于1M时，预分配空间free长度=len。len大于1M时，free=1M。
3. 空间惰性释放，当字符串长度变小时，不立即回收内存，而是只调整len和free的大小。
4. 二进制安全，针对一些二进制文件，可能包含\0符号，SDS不以\0为字符串结束符判断，而是len+\0作为字符串是否结束判断。
5. 如果一个String类型的value的值是数字，那么Redis内部会把它转成long类型来存储，从而减少内存的使用。

//SDS数据结构
struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;
     //记录 buf 数组中未使用字节的数量
     int free;
     //字节数组，用于保存字符串
     char buf[];
}
1
2
3
4
5
6
7
8
9
10

为了节省内存空间，Redis 还做了如下优化：
当保存 Long 类型整数，RedisObject 中的指针直接赋值为整数数据，这样就不用额外的指针指向整数。这种方式称为 int 编码方式。
当保存字符串数据，且字符串小于等于 44 字节时，RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域，这样可以避免内存碎片。这种方式称为 embstr 编码方式。
当保存字符串数据，且字符串大于 44 字节时，Redis 不再把 SDS 和 RedisObject 放在一起，而是给 SDS 分配独立的空间，并用指针指向 SDS 结构。这种方式称为 raw 编码模式。
下图为 int、embstr 和 raw 这三种编码模式的对比：

2. 字典dict：

字典dict就是类似hashmap key-value的方式，也就是数组+链表的方式。

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;    
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;
typedef struct dictEntry {
    // key：键
    void *key;
    // v：值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;
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

3. ziplist压缩列表：

压缩列表ziplist是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。元素的检索定位是通过偏移量来完成的。
压缩列表为了支持双向遍历，所以才会有 ztail_offset 这个字段，用来快速定位到最后一 个元素，然后倒着遍历。

//ziplist数据结构
struct ziplist<T> {
	int32 zlbytes; // 整个压缩列表占用字节数
	int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
	int16 zllength; // 元素个数
	T[] entries; // 元素内容列表，挨个挨个紧凑存储
	int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}
//entry数据结构
struct entry {
	int<var> prevlen; // 前一个 entry 的字节长度，当压缩列表倒着遍历时，需要通过这个字段来快速定位到下一个元素的位置
	int<var> encoding; // 元素类型编码
	optional byte[] content; // 元素内容
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4. 快速列表quickList：

快速列表就是一个一个小的压缩列表串起来的双向链表， quicklist【quicklist = 链表+ziplist】

1. quickList就是一个标准的双向链表的配置，有head 有tail;
2. 每一个节点是一个quicklistNode，包含prev和next指针。
3. 每一个quicklistNode 包含 一个ziplist，*zp 压缩链表里存储键值。
4. 所以quicklist是对ziplist进行一次封装，使用小块的ziplist来既保证了少使用内存，减少附加的指针空间，并减少内存的碎片化，也保证了性能。

5. 整数数组inset：

typedf struct inset{
    uint32_t encoding;//编码方式 有三种 默认 INSET_ENC_INT16
    uint32_t length;//集合元素个数
    int8_t contents[];//实际存储元素的数组 
                      //元素类型并不一定是ini8_t类型，柔性数组不占intset结构体大小
                      //并且数组中的元素从小到大排列
}inset;
1
2
3
4
5
6
7

编码格式encoding：共有三种，INTSET_ENC_INT16、INSET_ENC_INT32和INSET_ENC_INT64三种，分别对应不同的范围。Redis为了尽可能地节省内存，会根据插入数据的大小选择不一样的类型来进行存储。会且只在必要的时候进行升级操作，节省内存，升级过程耗费系统资源，还有就是不支持降级，一旦升级就不可以降级
元素数量length：记录了保存数据的数组contents中共有多少个元素，这样获取个数的时间复杂度就是O(1)。
数组contents：真正存储数据的地方，数组是按照从小到大有序排列的，并且不包含任何重复项。

6. 跳跃表skiplist：

跳跃表的逻辑类似于“树”型结构，是将一个链表其中的元素间隔几个就向上抽取一层，这样实现检索的过程时间复杂度达到O(logN)。

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;//跳表节点 ，头节点 ， 尾节点
    unsigned long length;//节点数量
    int level;//目前表内节点的最大层数
} zskiplist;
 
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

typedef struct zskiplistNode{
	struct zskiplistLevel{
		struct zskiplistNode *forward; // 前进指针
		unsigned int span;	// 跨度 这个层跨越的节点数量
	} level[];
	struct zskiplistNode *backward;// 后退指针
	double score;// 分值
	robj *obj;// 成员对象
} zskiplistNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Redis跳跃表常用操作的时间复杂度：

三、五种数据分别对应的数据结构

从上图可以看出除了string，其它四种类型在底层实现上都有两种选择。

1. String只有一个中数据类型：SDS，但是可以选择整数的编码方式方便计数类操作。
2. Hash的底层实现中，当数据量较小的时候，采用zipList作为hash的底层实现，否则使用字典dict来实现的。使用压缩列表的满足条件是：
   ①哈希对象保存的所有键值对的键和值的字符串长度都小于64字节。
   ②哈希对象保存的键值对数量小于512个
3. list底层数据结构ziplist和quicklist，首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist ，即压缩列表 . 它将所有的元素紧挨着一起存储，分配的是一块连续的内存当数据量比较多才会改成 quicklist。
4. set底层数据结构inset和dict，当value是整数值时，且数据量不大时使用inset来存储，其他情况都是用字典dict来存储。
5. zset底层数据结构压缩列表ziplist和跳表skiplist，有两个配置来判断使用哪一个数据结构：
   ①zset-max-ziplist-entries 128：zset采用压缩列表时，元素个数最大值。默认值为128。
   ②zset-max-ziplist-value 64：zset采用压缩列表时，每个元素的字符串长度最大值。默认值为64。
   zset插入第一个元素时，会判断下面两种条件，zset-max-ziplist-entries的值是否等于0；zset-max-ziplist-value小于要插入元素的字符串长度，满足任一条件Redis就会采用跳跃表作为底层实现，否则采用压缩列表作为底层实现方式。一般情况下，不会将zset-max-ziplist-entries配置成0，元素的字符串长度也不会太长，所以在创建有序集合时，默认使用压缩列表的底层实现。zset新插入元素时，会判断以下两种条件：zset中元素个数大于zset_max_ziplist_entries；插入元素的字符串长度大于zset_max_ziplist_value。当满足任一条件时，Redis便会将zset的底层实现由压缩列表转为跳跃表。转换为跳跃表后，即使元素被逐渐删除，也不会重新转为压缩列表。

参考：一、redis原理之string底层数据结构SDS
二、redis原理之hash底层数据结构ziplist dict
三、redis原理之list底层数据结构
四、redis原理之set底层数据结构
五、redis原理之sort set底层数据结构
Redis的五种数据结构的底层实现原理