Redis基本数据结构-一一网

前言

Redis的数据类型丰富，我们只有了解他们的底层实现才能在合适的场景使用它们

脉络

在看Redis的基本数据结构之前，我们先了解一下Redis的数据库结构

Redis是一个键值对数据库服务器，我们都知道Redis默认情况下有16个库，每个数据库都由一个RedisDb结构表示，其中RedisDb结构的dict字典保存了数据库中的所有键值对，dict字典的详情下面会说，它的底层是使用哈希表实现，所以可以用O（1）的时间复杂度来快速查找到键值对，我们只需要计算键的哈希值，就可以在dictEntry数组中访问到对应的dictEntry

dictEntry结构保存着一个键值对，key属性保存着键值对中的键，v属性则保存着键值对中的值，键值对的值可以是指针、浮点数、整数，next属性是指向下一个dictEntry节点的指针，是用来解决哈希冲突问题的，如果没有下一个节点，则指向null

Redis一般使用对象来表示数据库中的键和值，我们在Redis数据库中新创建一个键值对时，至少会创建两个对象，键对象和值对象，键总是一个字符串对象，值对象可以是字符串对象、列表对象、哈希对象、集合对象、有序集合对象的其中一种

字符串对象、列表对象、哈希对象、集合对象、有序集合对象在不同的情况下，底层的数据结构也各有不同

对象类型	编码类型
string	raw、int、embstr
list	quicklist
hash	dict、ziplist
set	intset、dict
zset	ziplist、skiplist+dict

基本数据结构

sds

旧版本的Redis很简单地使用了len和free来存放字符串的长度和剩余的容量，这个时候就要思考一个问题，不同长度的字符串是否有必要占用相同大小的头部？一个int占4字节，在实际的应用中，存放于Redis中的字符串往往没有那么长，每个字符串都用4字节存储未免太浪费空间了。所以Redis根据不同的字符串长度，使用不同的方式来存储，并使用了flags来表示存储的类型

struct __attribute__ ((__packed__)) sdshdr5 {
  	// 低三位存储类型，高5位存储长度，可满足存储长度小于32的短字符串
    unsigned char flags; 
  	// 柔性数组，存放实际内容
    char buf[];
};
// 长度大于31的字符串，1个字节存放不下，衍生出了sdshdr8、sdshdr16、sdshdr32、sdshdr64的结构
struct __attribute__ ((__packed__)) sdshdr8 {
  	// 已使用长度，用1字节存储
    uint8_t len; 
    // 总长度，用1字节存储
    uint8_t alloc; 
    // 低三位存储类型，高五位预留
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
  	// 已使用长度，用2字节存储
    uint16_t len; 
    // 总长度，用2字节存储
    uint16_t alloc; 
    // 低三位存储类型，高五位预留
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    // 已使用长度，用4字节存储
    uint32_t len; 
    // 总长度，用4字节存储
    uint32_t alloc;
  	// 低三位存储类型，高五位预留
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    // 已使用长度，用8字节存储
    uint64_t len; 
    // 总长度，用8字节存储
    uint64_t alloc; 
    // 低三位存储类型，高五位预留
    unsigned char flags; 
    char buf[];
};
复制代码

Alloc属性值为8，表示这个SDS总共分配了8个字节的空间
len属性值为5，表示这个SDS保存了一个5字节长的字符串
buf属性是一个char类型的数组，数组的前5个字节分别保存’R’、’e’、’d’、’i’、’s’五个字符，而最后一个字节则保存了空字符’\0′
flag只使用了低三位表示类型，细化了SDS的分类，根据字符串长度的不同选择不同的SDS结构体，不同结构体的主要区别是len和alloc的类型，这样做可以节省一部分的空间大小

注意

SDS遵循C语言字符串以空字符串结尾的惯例是为了重用一部分C语言字符串函数库的函数，保存空字符串的1字节空间不计算在SDS的len属性中，是额外分配的
SDS有空间预分配机制，但是在初始化时是不会预分配空间的，如果对SDS进行了修改，SDS的长度小于1MB，则扩大两倍，大于等于1MB，则增加1MB的冗余空间
SDS字符串指针指向的是字符串内存空间的buf的初始位置

为什么Redis不直接使用C语言字符串，要重新SDS结构？

常数复杂度获取字符串长度。假如字符串不记录自身的长度信息，获取字符串长度时需要遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止，复杂度为O（N），假如记录了SDS本身的长度，获取一个SDS长度的复杂度为O（1）
杜绝缓冲区溢出，缓冲区溢出是指当程序向缓冲区填充数据时超过了缓冲区本身的容量，而导致数据溢出到被分配空间之外的内存空间，使得溢出到数据覆盖了其他内存空间的数据，举个例子，strcat函数可以将src字符串中的内容拼接到dest字符串的末尾

char *strcat(char *dest, const char *src)
复制代码

因为C语言字符串不记录自身的长度，所以执行strcat这个函数时，如果已经为dest分配了足够多的内存，可以容纳src字符串中的所有内容，而一旦这个假定不成立，就会产生缓冲区溢出

举个例子，假设程序里有两个在内存中紧紧相邻的C语言字符串s1和s2，其中s1 = “Redis”，而s2 = “MongoDB”，如下图

执行strcat（s1, ” Cluster”）

将s1的内容修改为”Redis Cluster”，但是做这个操作的程序员忘记在执行strcat之前为s1分配足够多的空间，那么在strcat函数执行之后，s1的的数据将溢出到s2所在的空间，导致s2保存的内容被意外地修改，如下图

而SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性，当需要对SDS进行修改时，Redis会先检查SDS的空间是否满足修改的要求，如果不满足，会先进行扩充，再进行修改

减少修改字符串时带来的内存重分配次数，Redis有空间预分配和惰性空间释放机制
二进制安全

C语言字符串中的字符必须符合某个编码（比如ASCII），并且除了字符串的末尾之外，不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C语言字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据，但是SDS使用len来判断字符串是否结束，就不存在这个问题了，数据在写入时是什么样的，读取时就是什么样的

兼容C语言字符串函数，通过遵循C语言字符串空字符结尾的惯例

字典

Redis中，字典的应用非常广泛，从文章的第一张图也可以看出来，所有的键值对都是存储在一张全局Hash表中，下面我们来看看字典这个数据结构，思想跟Java到Hashmap是差不多的

typedef struct dict {
    dictType *type;
    void *privdata;
  	// Hash表，键值对存储在此
    dictht ht[2];
    // rehash标志，默认值为-1，代表没进行rehash操作，不为-1时，正进行rehash操作，存储的值表示Hash表ht[0]的rehash操作到了哪个		// 索引值
    long rehashidx; 
    unsigned long iterators; /* number of iterators currently running */
} dict;
复制代码

typedef struct dictht {
		// 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值，总是为size-1，跟hashmap获取获取索引的原理是一样的
    unsigned long sizemask;
    // 该哈希表已有节点的数量，包含next单链表的数据
    unsigned long used;
} dictht;
复制代码

typedef struct dictEntry {
  	// 键
    void *key;
  	// 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
  	// 指向下一个节点
    struct dictEntry *next;
} dictEntry;
复制代码

以上三个结构体可以使用下面这张图来表示

最外层是dict结构体，Redis字典这个数据结构，除了数据库的键值对存储之外，还有很多其他地方会用到，比如Redis的哨兵模式，就用字典存储管理所有的Master节点和Slave节点，在不同的应用中，字典中的键值对都可能不同，所以使用type结构体，在不同形态的字典中使用不同的操作函数
privdata字段是配合type字段指向的函数一起使用的私有数据
ht字段，是个大小为2的数组，一般情况下只使用ht[0]，扩容，缩容才会用到ht[1]
rehashidx用于标志字典是否在进行rehash
iterators，用来记录当前运行的安全迭代器数，当有安全迭代器绑定到该字典是，会暂停rehash操作

渐进式rehash

扩容和缩容的时候，需要将ht[0]中的数据迁移到ht[1]中，这个迁移的动作并不是一次性完成，而是分多次，渐进式地完成的，试想一下，Redis服务器中存储了1亿个键值对，集体迁移需要多久？

以下是渐进式rehash的详细步骤

为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
在字典中维护一个变量rehashidx，并将值设置为0，表示rehash工作正式开始
在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值+1
rehash完成后，rehashidx属性值重新设置为-1

跳表

链表的查询效率低，需要遍历所有元素，红黑树等树型数据结构虽然效率高但是实现复杂，Redis采用了跳跃表这种新型的数据结构，查询效率高，实现也比树型结构简单

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
复制代码

typedef struct zskiplistNode {
  	// 用于存储字符串类型的数据
    sds ele;
    // 用户存储排序的分值
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;
复制代码

以上两个结构体可以用下面这张图来表示

跳表由很多层构成，每层最后一个节点指向NULL，表示本层有序链表结束
跳表有一个header节点，header节点中有一个64层的结构，每层的结构包含指向本层的下个节点的指针以及到达本层下个节点需要跨越的节点数（span）
除header节点外，层数最多的节点的层高为跳表的高度（level）
跳表拥有一个tail节点，指向跳表的最后一个节点
最底层的有序链表包含所有节点，节点个数为跳表的长度，图中跳表长度为7
每个节点包含一个后退指针，头节点和第一个节点指向NULL，其他节点指向最底层的前一个节点

压缩列表

zlbytes：压缩列表的字节长度，Ox50（十进制80），表示压缩列表的总长为80字节
zltail：压缩列表尾元素相对于压缩列表其实地址的偏移量0x3c（十进制60），表示如果有一个指向压缩列表起始地址的指针p，那么只要用指针p加上偏移量60，就可以计算出entry3的地址
zllen：压缩列表的元素个数，0x3（十进制3），表示压缩列表包含3个节点
zlend：压缩列表的结尾，占1个字节，恒为0xFF

entry

previous_entry_length字段表示前一个元素的字节长度，占1个或者5个字节，当前一个字节的长度小于254字节时，用1个字节表示，当前一个元素的长度大于或等于254字节时，用5个字节表示，此时previous_entry_length字段的第一个字节是固定的0xFE，后面4个字节才是前一个元素的长度，假设已知当前元素的首地址为p，那么p-previous_entry_length就是前一个元素的首地址，从而可以实现压缩列表的遍历
encoding字段表示当前元素的编码（整型或者字节数组）

content存储数据内容

encoding编码	encoding长度	content类型
00 bbbbbb（6bit表示content长度）	1字节	最大长度为63的字节数组
01 bbbbbb cccccccc （14bit表示content长度）	2字节	最大长度为2^14-1的字节数组
10 bbbbbb cccccccc dddddddd eeeeeeee（32bit表示content长度）	5字节	最大长度为2^32-1的字节数组
11 00 0000	1字节	int 16整数
11 01 0000	1字节	int 32整数
11 10 0000	1字节	int 64整数
11 11 0000	1字节	24位有符号整数
11 11 1110	1字节	8位有符号整数
11 11 xxxx	1字节	没有content字段， xxxx表示0-12的整数

encoding字段第一个字节的前两位表示存储的是整数还是字节数组，当content存储的是字节数组，后续字节表示字节数组的实际长度，当content存储的是整数，可根据3、4位判断整数的类型，而当encoding字段表示当前存储的是0-12位的整数时，数据直接存储在encoding的最后4位，此时没有content字段

压缩列表存在一个连锁更新问题，发生概率较低，在这里就不讲了，有兴趣的同学可以去查查

快表

快表是一个双向链表，链表中的每个节点是一个ziplist结构，快表可以看成是用双向链表将若干个ziplist连接到一起的一种数据结构

typedef struct quicklist {
  	// 头节点
    quicklistNode *head;
  	// 尾节点
    quicklistNode *tail;
  	// 压缩列表节点个数
    unsigned long count;  
  	// quicklistNode节点个数
    unsigned long len;  
  	// 当fill为正数时，表明每个ziplist最多含有的数据项数，fill为负数时，限制的是每个节点的大小
    int fill : QL_FILL_BITS;              
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;
复制代码

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
  	// 压缩列表的大小
    unsigned int sz;             
    unsigned int count : 16;     /* count of items in ziplist */
    // 编码方式，1表示原生，2表示使用LZF压缩
  	unsigned int encoding : 2;   
  	// 该节点指向的容器类型，1表示none，2表示压缩列表
    unsigned int container : 2;  
  	// 这个节点之前是否是压缩节点，若是，则在使用前先解压，使用后重新压缩
    unsigned int recompress : 1; 
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
复制代码

上图是quicklistNode个数为3，compress个数为1的快表

考虑到quicklistNode节点个数较多时，我们经常访问的是两端的数据，为了进一步节省空间，Redis允许对中间的quicklistNode节点进行压缩

对象

Redis使用对象来表示数据库中的键和值，屏蔽了底层使用的数据结构

对象分为字符串对象、列表对象、集合对象、有序集合对象、哈希对象、模块对象和流对象，使用type来区分对象

typedef struct redisObject {
  	// 表示Redis对象，占用4位
    unsigned type:4;
  	// Redis对象使用的编码
    unsigned encoding:4;
  	// lru占用24位，当用于LRU时表示最后一次访问时间，当用于LFU时，高16位记录分钟级别的访问时间，低8位记录访问频率
    unsigned lru:LRU_BITS; 
  	// 记录对象被引用的次数
    int refcount;
  	// 记录存放具体数据的位置
    void *ptr;
} robj;
复制代码

字符串对象

字符串对象的编码可以是int、raw、embstr

127.0.0.1:6379> set k1 10086
OK
127.0.0.1:6379> object encoding k1
"int"
127.0.0.1:6379> set k1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK
127.0.0.1:6379> object encoding k1
"embstr"
127.0.0.1:6379> strlen k1
(integer) 44
127.0.0.1:6379> set k1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK
127.0.0.1:6379> strlen k1
(integer) 45
127.0.0.1:6379> object encoding k1
"raw"
复制代码

如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象的ptr属性里（将void*转换为long），字符串对象编码设置为int，存储的范围为-9223372036854775808~9223372036854775807
Redis的字符串有两种存储方式，字符串长度小于等于44时，使用embstr形式存储，字符串长度大于44时，使用raw形式存储

为什么44是边界线？

// Redis对象头部已经占据了16个字节
typedef struct redisObject {
    // 4bits
    unsigned type:4;
    // 4bits
    unsigned encoding:4;
    // 24bits
    unsigned lru:LRU_BITS; 
		// 4bytes
    int refcount;
		// 8bytes
    void *ptr;
} robj;

// SDS头部占据了至少3个字节
struct __attribute__ ((__packed__)) sdshdr8 {
		// 1bytes
    uint8_t len; 
		// 1bytes
    uint8_t alloc; 
		// 1bytes
    unsigned char flags; 
    char buf[];
};
复制代码

这样意味着分配一个字符串对象至少需要19个字节，内存分配器分配内存大小的单位都是2、4、8、16、32、64等，为了能容纳一个完整的embstr对象，内存分配器最少会分配32字节的空间，如果字符串稍微长一点，就是64字节，64 – 19 = 45，45个字节中，字符串是以字节 \0结尾，就只剩下44个字节了

哈希对象

哈希对象的编码可以是ziplist或hashtable

127.0.0.1:6379> hset hash k1 v1
(integer) 1
127.0.0.1:6379> object encoding hash
"ziplist"

127.0.0.1:6379> hset hash k2 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(integer) 0
127.0.0.1:6379> object encoding hash
"hashtable"
复制代码

当使用压缩列表作为存储结构时，会先将保存了键的压缩列表节点推入到压缩列表表尾，再将保存了值的压缩列表节点推入压缩列表表尾

同时满足以下两个条件时，使用压缩列表作为存储数据结构

哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
哈希对象保存的键值对数量小于512个

列表对象

列表对象的底层数据是快表，上面已经讲过了，这里就不赘述了

值得一提的是，列表对象的使用场景是非常多的，关注列表，粉丝列表，消息队列，取最新N个数据的操作

集合对象

集合对象的编码可以是intset或hashtable

127.0.0.1:6379> sadd k10 1 3 5
(integer) 3
127.0.0.1:6379> object encoding k10
"intset"
127.0.0.1:6379> sadd k10 1 3 abc
(integer) 1
127.0.0.1:6379> object encoding k10
"hashtable"
复制代码

集合对象同时满足以下两个条件时，对象使用intset编码

集合对象保存的所有元素都是整数值
集合对象保存的元素数量不超过512个

当集合对象使用字典作为底层实现时，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部设置为NULL，如下图

值得一提的是，Redis为集合提供了求交集、并集、差集的操作，我们可以使用这些特性实现共同好友、共同喜好等需求

127.0.0.1:6379> sadd zhangsan sing dance rap
(integer) 3
127.0.0.1:6379> sadd lisi sing
(integer) 1
# 差集
127.0.0.1:6379> sdiff zhangsan lisi
1) "dance"
2) "rap"
# 并集
127.0.0.1:6379> sunion zhangsan lisi
1) "dance"
2) "rap"
3) "sing"
# 交集
127.0.0.1:6379> sinter zhangsan lisi
1) "sing"
复制代码

有序集合

有序集合的编码可以是压缩列表或者字典+跳表

127.0.0.1:6379> zadd sort 100 zhangsan 20 lisi
(integer) 2
127.0.0.1:6379> object encoding sort
"ziplist"
127.0.0.1:6379> zadd sort 60 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(integer) 1
127.0.0.1:6379> object encoding sort
"skiplist"
复制代码

当使用压缩列表作为存储结构时，每个集合元素使用两个挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），第二个元素则保存元素的分值（score），压缩列表内的集合元素按分值从小到大进行排序，如下图

同时满足以下两个条件时，对象使用压缩列表编码