redis数据结构

概述

Redis数据库里面的每个键值对都是对象组成的，其中

数据库键总是一个字符串对象
数据库键的值可以使字符串对象，列表对象，哈希对象，集合对象，有序集合对象这五种中的一种。

对象由底层数据结构支撑的，底层数据结构有简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表。

简单动态字符串(SDS)

SDS主要作为字符串对象的底层实现和用作缓存区。

SDS的定义

free 记录buf数组中未使用字节的数量
len 记录SDS所保存字符串的长度
buf char类型的数组，用于保存字符串。

SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性内。

SDS与c字符串的区别

主要对比两个api使用上的区别，c比较底层，功能较为原始。

常数复杂度获取字符串长度

C字符串获取字符串长度的方式是通过遍历，这个操作的复杂度为O(n);

SDS直接读取len，复杂度为O(1);

杜绝缓冲区溢出

strcat(s1,”abc”);
c的字符串增加字符时，需要确保s1分配的空间足够大，否则会导致溢出。

SDS记录了空间大小，可用空间是否足够，不够的话API会自己扩充。

修改字符串时带来的内存重分配次数

每次增长或缩短一个c字符串，程序都要对这个c字符串数组进行一次内存重置分配操作：

增长字符串操作(append)，需要先扩展底层数组空间的大小–否则可能产生缓冲区溢出
缩短字符串操作（trim），需要通过内存重新分配，释放不再使用的那部分空间–可能产生内存泄漏

内存重分配涉及复杂算法，并且可能需要执行系统调用，是一个比较耗时的操作。

redis对速度要求严格，如果每次修改字符串都需要内存重新分配，会对性能造成影响。

SDS通过未使用空间，解除了字符串长度和底层数组长度之间的关联，并实现了空间预分配和惰性空间释放两种优化策略。

空间预分配：空间预分配用于优化SDS字符串增长的操作，当对SDS进行修改并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须的空间，还会为SDS分配额外的未使用空间。

如果对SDS进行修改之后，SDS的长度(len)小于1MB，额外分配的空间和len大小相同，此时len和free值相同。
当大于等于1mb，会额外多分配1mb未使用空间。

惰性空间释放：用于优化SDS字符串缩短操作，当需要缩短SDS字符串时，程序不会立即释放空间，只是修改free属性记录空间，等待下次使用。

二进制安全

C字符串除了字符串末尾之外，不能使用空字符，否则读入的空字符会被误认为字符串的末尾，后面的字符无法无法读取。
这使得C字符串只能保存文本数据，不能保存图片等二进制数据。
SDS支持保存二进制数据。

兼容部分C字符串函数

区别总结

位图

SDS支持保存二进制数据。
位图不是特殊的数据结构，他的内容就是普通字符串，即byte数组。

3. 链表

在redis中的使用场景有链表键，发布与订阅、慢查询、监视器等功能也用到了链表。redis服务器本身用链表保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区域。

3.1 链表和链表节点的数据结构

typedef struct listNode{
	struct listNode *prev;
	struct listNode *next;
	void *value;
}

typedef struct list{
	struct listNode *head;
	struct listNode *tail;
	//节点数量
	unsigned long len;
	
	//复制链表节点所保存的值
	void *(*dup)(void *ptr);
	
	//释放链表节点所保存的值
	void (*free)(void *ptr);
	
	//用于对比链表节点的值和另一个输入值是否相等
	int (*match)(void *ptr,void *key);
	
}

Redis链表特点如下：

双端：双向链表，获取前后节点复杂度都是O(1)。
无环：表头节点的prev指针和表尾节点的next指针都指向NULL。
带表头指针和表尾指针：获取表头或者表尾的节点，复杂度都是O(1)。
带链表长度计数器：获取链表长度复杂度为O(1)
多态:链表可以保存各种不同类型的值

字典

字典，又称为符号表、关联数组、或者map，是一种用于保存键值对的抽象数据结构。
redis数据库就是使用字典作为底层实现的，同时字典还是哈希对象的底层实现之一。

字典的实现

Redis的字典使用哈希表作为底层实现。

哈希表

哈希表结构定义:

typedef struct dictht{

	//哈希表数组
	dictEntry **table
	
	//哈希表大小 2的n次方
	unsigned long size;
	
	//哈希表大小掩码，用与计算索引值，总是等于size-1
	unsigned long sizemask;
	
	//该哈希表已有节点数量
	unsigned long used;
} dictht;

哈希表节点

哈希表节点用dictEntry表示，每个dictEntry结构都保存一个键值对

typedef struct dictEntry{

	//键
	void *key
	
	//值
	union{
		void *val;
		uint64_t u64;
		int64_t s64;
	} v;
	
	//指向下个哈希表节点，形成链表
	struct dictEntry *next;
} dictEntry;

键值对的值可以是一个指针，一个uint64_t整数或者一个int64_t整数。

字典

typedef struct dict{

	//类型特定函数
	dictType *type;
	
	//私有数据
	void *privdata;
	
	//哈希表数组
	dictht ht[2];
	
	//reshash索引
	//当rehash不进行时，值为-1
	int trehashidx;
} dict;

type和privdata属性是针对不同类型的键值对，为创建多态字典而设置的。

ht是一个长度为2的哈希表数组，一般情况只用ht[0]哈希表，ht[1]哈希表再rehash的时候使用，trehashidx记录了rehash的进度，没有rehash的时候为-1。

哈希算法

redis哈希过程类似java中的hashmap，使用的算法是MurmurHash2算法。

解决键冲突

和java中的hashmap类似，使用链表解决，称为链地址法。

dictEntry没有指向表尾的指针，为了速度考虑，程序总是将新节点添加到表头的位置(复杂度O(1))

排在尾部需要遍历链表

rehash

扩展和收缩哈希表的工作可以通过执行rehash操作来完成，redis对字典的哈希表执行rehash的步骤如下：

为ht[1]分配空间(这会导致满容状态下大量key被驱逐，详见美团博客)，表空间大小取决于要执行的操作和ht[0].used属性值
- 扩展操作，ht[1]大小为第一个大于等于ht[0].used * 2的 2的N次方幂
- 收缩操作，ht[1]大小为第一个大于等于ht[0].used的 2的N次方幂
将保存在ht[0]中的所有键值对rehash到ht[1]上面。
全部迁移以后，释放ht[0],将ht[1]设置为ht[0]，并为ht[1]创建一个空白哈希表。

哈希表的扩展与收缩

1 2	# 负载因子 load_fator = ht[0].used/ht[0].size;

load_fator>1 && 服务器没有在执行BGSAVE或者BGREWITEAOF命令，哈希表扩展
load_fator>5 && 服务器正在在执行BGSAVE或者BGREWITEAOF命令，哈希表扩展
load_fator<0.1 收缩

扩展阅读
美团针对Redis Rehash机制的探索和实践

当在rehash收缩过程中，突然插入大量key，会发生什么？
理论上是性能大幅下降，直到收缩完成后，又再开始扩展rehash。

为什么要判断BGSAVE或者BGREWITEAOF是否正在执行，才决定是否扩展哈希表？

因为子进程使用的写时复制技术，避免大规模修改内存，避免不必要的内存写入操作，最大限度节约内存。

渐进式rehash

详细步骤：

为ht[1]分配空间，让字典同时持有两个哈希表
将rehashidx置为0，表示rehash工作开始
在rehash期间，对字典进行增、删、改、查、更新，程序除了执行指定操作外，还会顺带将ht[0]在rehashidx索引上的所有键值对(遍历对应index的列表进行rehash) rehash到ht[1]，然后rehashidx属性增一。
当ht[0]上所有键值对都被转移到ht[1]，rehashidx置为-1，rehash全部完成。

将rehash键值对所需要的计算工作均摊到多次操作上，避免集中式rehash而带来的庞大计算量

渐进式rehash执行期间的哈希表操作

删、找、更新会在两个表上同时操作，增只会在新表操作。

跳跃表

跳跃表支持平均O(logN)、最坏O(N)复杂度的查找，大部分情况下效率可以和平衡树媲美，而跳跃表实现更加简单。
跳跃表的基础知识参考：
Redis-跳表
 跳表：为什么Redis一定要用跳表来实现有序集合？

跳跃表的实现

redis跳表实现由zskiplit和zskiplistNode两个结构组成，前者保存跳表信息，后者表示跳表节点。

zskiplist结构包含以下属性：

header指向跳表的表头节点
tail指向跳表的表尾节点
level 记录目前跳表除表头节点外，其他节点层数最大值
length 除表头节点外，跳表节点数量。

zskiplistNode结构包含以下属性

层 level，每一层带有两个属性 向前指针和跨度
后退指针指向前一个节点
分值，在跳表中，节点按各自分值从小到大排列
成员对象

跳表节点

typedef struct zskiplistNode{

	//后退指针
	struct zskiplistNode *backward;
	
	//分值
	double score;
	
	//成员对象
	robj *obj;
	
	//层 数组
	//每次创建一个跳跃表节点，会根据幂次定律(越大的数出现的概率越小)
	//随机生成1-32之间的数，作为level数组的大小，即层的高度
	struct zskiplistLevel{
		//前进指针
		struct zskiplistNode *forward;
		//跨度 记录两个节点之间的距离
		unsigned int span;
	} level[];
} zskiplistNode;

整数集合

整数集合的实现

整数集合是redis用于保存整数值的集合抽象数据结构，他可以保存的类型为int16_t、int32_t、int64_t的整数值，并保证集合内不会出现重复元素。

typedef struct intset{

	//编码方式
	uint32_t encoding;
	
	//集合包含的元素数量
	uint32_t length;
	
	//保存元素的数组
	int8_t  contents[];
	
} intset;

contents数组并不保存任何int8_t类型的值，真正类型取决于encoding的值。

升级

当一个新元素添加到整数集合里面，新元素类型比当前集合类型大的时候，整数集合会进行升级。(int16_t -> int32_t -> int64_t)

根据新元素类型，扩展底层数组空间大小，并为新元素分配空间
将底层数组所有元素的类型进行转换升级，并放在正确的位置上
将新元素添加到末尾(新元素需要进行升级，说明比原来的元素都大(负数则比所有元素都小))

每次向集合中添加元素都可能引起升级，所以时间复制度为O(N)。

升级的好处

提升灵活性，能随意地将int16_t、int32_t、int64_t类型的整数添加到集合中，不必担心类型错误。
尽可能节约内存，只在必要的时候升级

6.4 降级整数集合不支持降级操作

压缩列表

压缩列表是列表对象和哈希对象的底层实现之一。

压缩列表的构成

压缩列表是redis为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。

压缩列表节点的构成

每个压缩列表节点都可以保存一个字节数组或者一个整数值

字节数组
1. 长度小于等于63($2^6$ -1)的字节数组
2. 长度小于等于16383($2^{14}$ -1)的字节数组
3. 长度小于等于($2^{32}$ -1)的字节数组
整数值
1. 4位长 0-12之间的无符号整数
2. 1字节长有符号整数
3. 3字节长有符号整数
4. int16_t整数
5. int32_t整数
6. int64_t整数

每个节点都由 previous_entry_length、encoding、content三个部分组成。

previous_entry_length

previous_entry_length：用于记录前一个节点的长度，长度为1或5字节。因为记录了前一节点的长度，程序可以通过指针运算，从当前节点的起始地址计算出前一个节点的起始地址。用于压缩列表从表尾向前遍历。

1字节如果前一节点长度小于254字节，直接保存
5字节如果前一节点长度大于等于254字节，第一字节会被设置为254，后面4字节用于记录前一节点长度

encoding

记录了节点的content属性保存的数据类型和长度。

整数编码都是一字节长度，最高两位为11用于标识整数编码。
字节数组编码长度为一字节、二字节或五字节长，最高两位分别为00、01、10。

“_”表示留空，b、x表示实际二进制数据。

content

content负责保存节点的值。

连锁更新

添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，需要注意！

每个节点的 previous_entry_length 属性都记录了前一个节点的长度：

如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
如果前一节点的长度大于等于 254 字节，那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。

在一个压缩列表中，有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN ，此时如果在表头加入一个大于254长度的新节点，这样原来的e1的previous_entry_length由1字节增加到5字节，这会导致e1本身的长度超过254，所以e2的previous_entry_length也由1增加到5，引起e3的改变。

因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作，而每次空间重分配的最坏复杂度为 O(N) ，所以连锁更新的最坏复杂度为 O(N^2) 。

quicklist

Redis中的列表对象在版本3.2之前，列表底层的编码是ziplist和linkedlist实现的，但是在版本3.2之后，重新引入了一个 quicklist 的数据结构，列表的底层都由quicklist实现。

每一个quicklist node都包含一个 ziplist，由多个ziplist连成一个quicklist。

list-max-ziplist-size -2

-5: 每个quicklist节点上的ziplist大小不能超过64 Kb。（注：1kb => 1024 bytes） 

-4: 每个quicklist节点上的ziplist大小不能超过32 Kb。  

-3: 每个quicklist节点上的ziplist大小不能超过16 Kb。

-2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（-2是Redis给出的默认值）

-1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

当取正值的时候，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成5的时候，表示每个quicklist节点的ziplist最多包含5个数据项。

当取负值的时候，表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时，它只能取-1到-5这五个值。

list-compress-depth 0

0: 是个特殊值，表示都不压缩。这是Redis的默认值。

1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。

2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。

这个参数表示一个quicklist两端不被压缩的节点个数。注：这里的节点个数是指quicklist双向链表的节点个数，而不是指ziplist里面的数据项个数。实际上，一个quicklist节点上的ziplist，如果被压缩，就是整体被压缩的。

紧凑列表listpack(5.0之后)

ziplist 在极小的概率下有可能发生级联更新，当连续规模较大的级联更新发生时，对 Redis 的性能有比较大的影响。因此在 5.0 版本中新引入了一个数据结构，名叫 listpack, 大家都将它翻译为紧凑列表.

它的定义和 ziplist 极其相似，只是通过一些新的设计，来解决 ziplist 中的痛点问题。目前只在5.0 版本引入的 Stream 数据结构中使用。

struct listpack<T> {
    int32 total_bytes; // 占用的总字节数
    int16 size; // 元素个数
    T[] entries; // 紧凑排列的元素列表
    int8 end; // 同 zlend 一样，恒为 0xFF
}

listpack 的定义和上方基本一致，只是去掉了 zltail 属性。

listpack节点的定义如下：

1
2
3

int<var> encoding;
optional byte[] content;
int<var> length;

相比于 ziplist 的定义，它有两点改动：

记录的长度不再是前一个节点的长度，而是自己的长度。
将记录自己的长度放到了节点的尾部。(这很重要！这也是为什么能去掉zltail_offset的原因)

这样做的好处是：

不再需要 zltail 属性也可以快速定位到最后一个节点。用 listpac 的总长度-最后一个节点的长度.(因为total_bytes知道了，节点的length位置固定在尾端，且为固定类型，可以直接获取最后一个节点的length)
每个节点记录自己的长度，当本节点的值发生了改变，只需要更改自己的长度即可。不再需要更改别的节点的属性，也就彻底的解决掉了级联更新问题。