Redis数据对象

基本结构图

key和value指向的是redisObject对象

type：标识该对象用的是什么类型（String、List

Redis数据结构

SDS

SDS有4个属性：

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分为这几个部分：

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

entry的构成：

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

prevlen属性的大小：

如果前一个节点的长度小于254字节，那么prevlen属性需要1字节
如果前一个节点的长度大于等于254字节，那么prevlen属性需要5字节

encoding属性的大小：

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

连续更新问题：

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

quicklist

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

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

解决连锁更新：

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

哈希表

dictht有这几个属性：

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

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

解决办法是采用拉链法：

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

解决办法是rehash，分为三步：

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

但是也有问题，迁移的过程很耗时间，因此采用了渐进式rehash：

给哈希表2分配空间，一般比哈希表1大一倍
在rehash期间，每次哈希表元素新增、删除、查找的时候，Redis会执行对应的操作外，还会将哈希表1中索引位置上的所有dictEntry迁移到哈希表2
迁移完成后，哈希表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数组的大小。
在原本的数组上，将每个元素按间隔类型分割，比如如果encoding属性值为INTSET_ENC_INT16，那么间隔就是16位。
比如现在有3个类型为int16_t的元素，每个都是16位长度，然后往整数集合里面加入一个新元素65535，这个新元素类型用int32_t保存，然后对contents扩容，会在原本的空间的大小之上多出80位（4 * 32 - 3 * 16 = 80），这样就能保证可以存下4个int32_t的元素
然后从后往前依次填充，最终再把65535这个元素放到最后。

整数集合升级的好处：

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

跳表

跳表是在链表的基础上改进过来的，是一个多层有序链表。

跳表zskiplist有以下属性：

跳表的头尾节点head，tail
跳表的长度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

quicklist并没有完全解决连锁更新问题，因为quicklist还是使用了压缩列表来保存元素，于是有了listpack

listpack结构：

listpack头包含两个属性，分别记录了listpack总字节数和元素数量。然后listpack也有一个结尾标识。listpack entry是listpack的节点

listpack entry：

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

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

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

Redis数据对象有哪些

概述

常见的对象有以下五种：

String：二进制安全的，特性是可以包含任何数据比如一个序列化的对象，一个键最大能存储512M。适用于简短的字符场景。底层数据结构采用的是SDS或者INT编码
Hash：键值对数据结构，相当于编程语言的Map。适用于存储、读取、修改用户属性。底层数据结构是哈希表或者压缩列表
Set：包含字符串的无序集合，增删查找快。使用于最新消息排行榜，消息队列。底层数据结构是哈希表或者整数集合
Sort Set: 将Set集合加一个权重参数score，元素按照score排序。特性是在插入元素的时候自然排序。适用于排行榜、带权重的消息队列。底层数据结构是跳表或者压缩列表

String

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

int：如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型表示，那么这个字符串对象会被保存在redisObject对象的prt中，同时将encoding设置成int
embstr：如果一个字符串对象保存的是字符串，并且这个字符串对象小于等于32字节。那么字符串对象将用SDS表示，同时encoding设置成embstr
raw：如果一个字符串对象保存的是字符串，并且这个字符串对象大于32字节。那么字符串对象将用SDS表示，同时encoding设置成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，再做修改。