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,再做修改。
List
底层是双向链表和压缩列表
- 如果列表中的元素小于512个,列表每个元素的值都小于64字节,redis会用压缩列表存储
- 否则用双向链表
在redis3.2之后,使用quicklist作为底层数据结构
Hash
- 如果哈希类型元素个数小于512个,并且所有值小于64字节,Redis会用压缩列表底层数据结构
- 否则用哈希表
在redis7.0,压缩列表结构被抛弃,使用listpack
Set
- 如果集合中的元素都是整数且元素个数小于512使用整数集合
- 否则用哈希表
Zset
- 如果有序集合元素小于128个,并且每个元素大小小于64字节,使用压缩列表
- 否则用跳表
Redis7.0已经将压缩列表废弃使用listpack