基本结构

在Redis中有一个核心的对象叫做redisObject ，是用来表示所有的key和value的，用redisObject结构体来表示String、Hash、List、Set、ZSet五种数据类型

key和value指向的是redisObject对象

type：标识该对象用的是什么类型（String、List)
encoding：编码方式

Redis数据结构

SDS

属性：

len：记录了字符串长度，因此获取字符串长度的时候时间复杂度O(1)
alloc：分配给字符数组的空间长度。这样在修改字符串的时候，只需要alloc-len来判断剩余空间大小，可以用来判断空间是否满足修改条件，如果不满足就会将SDS扩容。因此不会出现C语言的缓冲区溢出问题
flags：用来表示不同类型的SDS，表示len和alloc的类型不同，进而保存的SDS分配给字节数组的大小不同
buf[]：字节数组，用来保存实际数据。不仅可以保存文本数据，还可以保存二进制数据

Redis底层由C语言实现，那么SDS与C语言字符串对比：

O(1)获得字符串长度：因为SDS有len属性
二进制安全：SDS不仅可以保存文本数据，还能保存二进制数据。SDS的使用len属性来判断是否遍历完成，不会管’\0’的字符
不会发生缓冲区溢出：通过alloc-len来判断剩余空间大小，可以用来判断空间是否满足修改条件，如果不满足就会将SDS扩容。因此不会出现C语言的缓冲区溢出问题

扩容机制：

如果所需的SDS长度小于1MB,则翻倍 + 1
如果所需的SDS长度超过1MB,最后的扩容大小应该是newlen + 1MB + 1

Ziplist（压缩列表）

ziplist构成：

zlbytes：整个压缩列表占用内存字节数
zltail：压缩表尾部节点距离起始地址多少个字节，也就是列表尾的偏移量
zllen：entry节点的个数
entry：存储数据的部分
zlend：压缩列表的结束点，固定在0xFF

entry构成：

prevlen：前一个节点的长度，目的是实现从后往前遍历
encoding：记录当前节点实际的类型和长度，类型主要是字符串和整数
data：记录当前节点的实际存储数据，类型和长度由encoding决定

encdoing构成：

如果当前数据是整数，需要1字节
如果当前的数据是字符串，会根据需要使用1、2、5字节的空间

连续更新问题：
压缩列表新增某一个元素或者修改某一个元素，如果空间不够，压缩列表占用的内存空间需要重新分配。当更新的元素较大，会导致后续的prevlen也都要重新分配，从而引起连锁更新的问题

quicklist

在 Redis 3.0 之前，List 对象的底层数据结构是双向链表或者压缩列表。然后在 Redis 3.2 的时候，List 对象的底层改由 quicklist 数据结构实现

quicklist就是双向链表+ziplist的组合，quicklist链表中的每一个节点是一个压缩列表

解决连锁更新：通过控制链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越小，连锁更新带来的影响就越小，从而性能提升

dictht（哈希表）

属性：

dictEntry **table：数组的每一个元素是指向哈希表节点的指针
size：哈希表大小
sizemask：掩码，用于计算索引值
used：哈希表已有的entry个数

哈希冲突：

当两个key不同，但是索引值相同，就会发生冲突

哈希冲突解决（拉链法）：

被分配到同一个哈希桶上的多个节点用一个单项链表连接起来
但是也有缺点，当链表长度过长的时候，查询效率很低

rehash解决链表长度过长：

给哈希表2分配空间，一般比哈希表1大一倍
将哈希表1数据迁移到哈希表2
迁移完成后，哈希表1的空间释放，并把哈希表2设置为哈希表1，然后在新哈希表2创建出一个空白的哈希表，为下次rehash做准备

渐进式rehash解决rehash迁徙过程耗时久：

给哈希表2分配空间，一般比哈希表1大一倍
在rehash期间，每次哈希表元素新增、删除、查找的时候，Redis会执行对应的操作外，还会将哈希表1中索引位置上的所有dictEntry迁移到哈希表2。查找，更新操作会在两个哈希表上进行。redis会先尝试在 ht[0] 中寻找目标键值对，如果没有找到则会在 ht[1] 再次寻找。但是新增操作就不一样了，新增key只会在新的哈希表 ht[1] 上进行，为的是确保 ht[0] 中的已经被清空的单向链表不会新增元素。在 rehash 被触发后，即使没有收到新请求，Redis 也会定时执行一次 rehash 操作，而且，每次执行时长不会超过 1ms，以免对其他任务造成影响
迁移完成后，哈希表1的空间释放，并把哈希表2设置为哈希表1，然后在新哈希表2创建出一个空白的哈希表，为下次rehash做准备

rehash触发条件：

负载因子 = 哈希表已保存的节点数量 / 哈希表大小
当负载因子大于等于1，并且redis没有进行RDB快照和AOF重写的时候，进行rehash
当负载因子大于等于5，说明哈希冲突非常严重，不管也没用RDB快照和AOF重写，都会强制执行rehash

intset（整数集合）

属性：

encoding：编码方式，比如 INTSET_ENC_INT16，那么contents就是一个int16_t类型的数组
length：集合包含的元素数量
contents：虽然被声明为 int8_t 类型，但是实际上是由保存的数据大小由encoding决定

整数集合升级规则：

当我们将一个新元素加入集合中，如果新元素的类型(int32_t)比现有元素的类型(int16_t)都要长，需要扩宽contents数组的大小。比如现在有3个类型为int16_t的元素，每个都是16位长度，然后往整数集合里面加入一个新元素65535，这个新元素类型用int32_t保存，然后对contents扩容，会在原本的空间的大小之上多出80位（4 * 32 - 3 * 16 = 80），这样就能保证可以存下4个int32_t的元素
扩容完 contents 数组空间大小后，需要将之前的三个元素转换为 int32_t 类型，并将转换后的元素放置到正确的位上面，并且需要维持底层数组的有序性不变：从后往前依次填充，最后再把65535这个元素放到数组末尾

整数集合升级优点：

如果让一个数组保存int16_t、int32_t、int64_t的元素，最好的方式就是用int64_t类型，但是会造成空间的浪费。
整数升级保证了我们只需要int64_t类型的元素再进行扩容，因此可以节约资源内存

最后，整数集合不支持降级

zskiplist（跳表）

zskiplist属性：

跳表的头尾节点head，tail（指向zskiplistNode）
跳表的长度length
跳表的最大层数level

zskiplistNode属性：

ele：SDS结构存储数据
score：节点的分数，浮点型
backward：指向上一个节点的回退指针，支持从表尾向表头遍历，也就是ZREVRANGE命令
level：是个zskiplistLevel数组，zskiplistLevel包含了两个字段，一个是forward，指向下一层能调到哪个节点，span记录了距离下个节点的步数。数据结构就表示每个节点是个多层结构

跳表节点层数设置：

跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)
Redis在创建节点的时候，会生成范围为[0, 1]的随机数，如果这个随机数小于0.25（相当于概率25%），那么层数就增加一层。然后继续生成下一个随机数，直到随机数的结构大于0.25就结束
这样的做法，相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高最大限制是 64

为什么用跳表而不用平衡树？

从内存占用上，跳表比平衡树更灵活：平衡树每个节点包含2个指针，跳表每个节点包含的指针数目为1/（1-p），在redis中p=0.25，平均每个节点包含1.33个指针，内存占用更少
在做范围查询的时候，跳表比平衡树操作更简单：在平衡树中我们找到特定范围的最小值后，还需要以中序遍历的顺序寻找其他不超过大值的节点，所以中序遍历不容易实现。而跳表就很简单，只需要找到最小值后，对第一层的节点进行若干步的遍历即可
在算法实现难度上，跳表更简单。平衡树的插入和删除操作可能引发子树的调整，子树逻辑复杂。而跳表的插入和删除只需要修改相邻的节点，操作简单又迅速

listpack

listpack entry构成：

encoding：定于元素的编码类型，会对不同长度的整数和字符串进行编码
data：实际存放的数据
len：encdong+data的总长度

将prevlen改成len之后能不能从后往前遍历？

答案是可以。lpDecodeBacklen函数已经实现了

Redis数据对象

String

字符串对象的内部编码（encoding）有 3 种：int、raw和embstr：

int：如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型表示，那么这个字符串对象会被保存在redisObject对象的prt中，同时将encoding设置成int
embstr(Embedded string 嵌入式字符串)：如果一个字符串对象保存的是字符串，并且这个字符串对象小于等于32字节。那么字符串对象将用SDS表示，同时encoding设置成embstr
raw：如果一个字符串对象保存的是字符串，并且这个字符串对象大于32字节。那么字符串对象将用SDS表示，同时encoding设置成raw

embstr和raw的区别：

embstr和raw都会用SDS来保存值。
embstr会通过一次内存分配函数来分配一块连续的内存空间来保存redisObject和SDS
而raw编码会调用两次内存分配函数分别分配redisObject和SDS

embstr相比raw好处：

embstr编码创建字符串对象只用调用一次内存分配函数，而raw编码需要两次
释放embstr编码的字符串对象同样也只需要调用一次内存释放函数
因为embstr编码的字符串对象的所有数据都保存在一块连续的内存空间，可以更好的利用cpu缓存提升性能

embstr的缺点：

如果字符串的长度需要重新分配空间时，整个redisObject和sds都需要重新分配空间，所以embstr编码的字符串对象实际上是只读的。redis没有为embstr编码的字符串对象编写任何修改的程序。当我们对embstr编码的字符串对象执行修改的命令，实际上是先将编码从embstr转换成raw，再做修改

List

3.2版本之前是双向链表和压缩列表：

如果列表中的元素小于512个，列表每个元素的值都小于64字节，redis会用ziplist存储
否则用双向链表

3.2版本之后：统一用quicklist

7.0版本之后，统一用listpack

Hash

如果哈希类型元素个数小于512个，并且所有值小于64字节，Redis会用ziplist（7.0版本开始采用listpack）底层数据结构
否则用哈希表

Set

如果集合中的元素都是整数且元素个数小于512使用整数集合
否则用哈希表

Zset

如果有序集合元素小于128个，并且每个元素大小小于64字节，使用ziplist（7.0版本开始采用listpack）
否则用skiplist