雷火电竞
目录
- 本章重点
- 简单动态字符串SDS
- 集合底层实现原理
- zipList
- listPack
- skipList
- quickList
- Key 与Value中元素的合底数量
本章重点
- 掌握Redis简单动态字符串
- 了解Redis集合底层实现原理
简单动态字符串SDS
我们Redis中无论是key还是value其数据类型都是字符串.我们Redis中的字符串是如何存储的呢?虽然我们的Redis是用C语言开发的,但是并没有直接套用其字符串形式.自定义了一种字符串.这种字符串结构简单,功能强大,称为简单动态字符串(Simple Dynamic String) 简称SDS Redis中的字符串并非都是SDS,字面常量是C字符串
SDS是一个结构体,定义在Redis安装目录下的src/sds.h中
sturct sdshdr{//字节数组,用于保存字符串char buf[];//buf[]中已使用的字节数量,称为SDS长度int len;//buf[]中尚未使用的字节数量int free;}
我们可以查看src/sds.h定义 
例如我们执行一个set name "hello redis"命令时,这里的字符串是字面常量,在Redis存储方式如下:
这里的\0是需要储存在buf中的,但是不记录长度len!
- 字符串长度获取性能高,无需遍历字符串
- 保证二进制安全,我们的C字符串真能在字符串结尾出现\0,而在图片,音频,视频等二进制文件数据以\0作为分隔符情况很是常见,所以C字符串无法保存其二进制数据,而SDS可以通过len判断字符串结尾位置.读取到什么,就存储,无需其他过滤操作即可!
- 减少内存再分配次数,SDS采用了空间预分配策略和惰性空间释放策略,来避免再分配空间问题! 1.如果len<1M,那么free空间大小和len相同. 2.len>=1M,free固定大小=1M 如果sds长度len减小,那么free也不会释放,等到后期再次分配使用 如需释放可以手工调用函数释放
- 兼容C函数 因为保留的C语言的\0我们的SDS也可以使用C语言字符串函数 strcmp等
集合底层实现原理
Redis中对于Set类型底层的实现,直接采用了hashTable,但是对于Hash,Zset,List集合的底层进行了特殊设计,保证Redis的高性能
对于Hash和Zset集合,其底层实现实际有2种:压缩zipList和跳跃列表skipList 这两种实现,用户都是透明的,系统会根据用户写入数据的不同,选择不同的的实现.只有同时满足了配置文件redis.conf中配置d相关集合元素个阈值和元素大小阈值两个条件使用的就是压缩链表zipList.例如Zset集合满足下面2个条件就是zipList
- 集合元素个数小于 redis.conf 中zset-max-ziplist-entries属性的值，其默认值为 128
- 每个集合元素大小都小于 redis.conf 中 zset-max-ziplist-value 属性的值，其默认值为 64字节
zipList
zipList 
zipList通常称为压缩链表,是经过特殊编码的用于存储字符串或整数的的双向链表.其底层由3部分构成! head,entries,end.这3部分在空间上是连续存放的.
head由3部分构成:
- zlbytes:占4个字节,用于存放整个ziplist的数据结构所占字节数,包括zlbytes本身长度!
- zltail:占用4个字节,用于存放最后一个entry在整个数据结构的偏移量(字节)可以快速定位列表尾位置,以便操作!
- zllen:占2个字节,用于存放列表包含的entry个数,由于只有16位,所有最多ziplist只能有65535个entry
entries是真正的列表,由很多的entry元素构成,由于不同的元素类型,数值的不同,从而导致entries的长度不同,entry也由3部分构成
- prevlength:记录上一个entry的长度,用于实现逆序遍历,默认长度为1个字节,如果上一个entry长度大于了254字节,prevlength就会扩展到3个字节
- encoding:该部分用于标志后面的data数据类型,如果data是整数,encoding部分长度为1个字节,如果是字符串类型,那么可能为1个字节/2/5个字节长度,由于data数据长度的不同对应的encoding长度也不同.
end自包含一部分zlend占1个字节,是ziplist的结束标志. 二进制8个1固定255!
listPack
对于我们的ziplist的entry结构,由于其实现的逆序遍历,保存了前一个entry的大小,如果进行了中间修改或者插入操作,会导致级联更新,影响性能.为了实现更紧凑,更快解析,更简单的实现,重写了实现了ziplist命名为listPack. 在Redis7.0已经将zipList全部替换成了listPack,为了兼容保留了zipList的相关属性!
listPack结构
listPack是经过特殊编码的用于存储字符串或整数的双向链表.底层数据结构也由其3部分构成!
head由2部分构成:
- totalBytes:占4个字节,用于存放listPack整个数据结构包含其本身长度,单位是字节
- elemNum:占2个字节,用于保存entry元素个数,最多为65535个!
这里就是和zipList的区别之处,这里没有了prevlength,增加了记录当前长度的element-total-len也可实现逆序遍历.而不会引发级联更新
- encoding:该部分用于标志后面的data的具体类型。如果data为整数类型，encoding 长度可能会是层实1 、2 、现原3 、合底4 、层实5或9字节。现原不同的合底字节长度，其标识位不同。如果data 为字符串类型，则encoding长度可能会是层实1 、2或5字节
。现原data字符串不同的合底长度，对应着不同的encoding长度 。
- data:真正存储数据的层实位置,整数或者字符串类型,不同数据占用的字节长度不同
- element-total-len:记录当前entry长度,用于实现逆序遍历.可能的值[1,5]字节
这里的end和zlend一样,都是结束标志,255,8个二进制1构成
skipList
跳跃列表,简称跳表,是一种随机化的数据结构,基于并联的链表.实现简单,查询效率高.就是链表的一种不过在此基础上实现了跳跃功能.使得在查找元素具有较高的速率!
skipList就是在list基础上随机增加一些高层指针,高层指针遍历效率高,层级越高,查找效率越高!我们可以先在高层遍历,然后再向下层级遍历查找指定位置
这里的层级采用随机的方式,就有效的避免了按照指定规定元素个数的层级方式,插入或修改元素需要对链表的层级指针进行修改!而采用随机层级的方式就插入元素就随机层级,然后插入即可,删除也修改前后指针即可!
quickList
快速链表,quickList本身是一个双向无循环链表.他的每一个节点都是一个zipList.由于zipList和linkedList都有明显不足,而quickList就进行了改进操作! 
我们的quickList可以通过zipList中head部分记录的totalNum进行检索!对其遍历的zipList的entry进行求和从而定位到指定的zipList的entry元素
//设插入元素大小为: insertB//查找到的插入位置元素大小为: zlB //zipList最大值: zpMax //前(后)一个元素大小: plB/nlB1. insertB+zlB<=zpMax://直接插入zipList相应位置即可2. insertB+zlB>zpMax 并且插入的位置位于元素首部位置//2.1 insertB+plB<=zpMax:直接插入前一个元素尾部//2.2 insetB+plB >zpMax: 构建一个新元素zipList然后连接到quickList3. insertB+zlB>zpMax 并且插入的位置位于元素尾部位置//3.1 insertB+nlB<=zpMax:直接插入前一个元素首部//3.2 insetB+nlB >zpMax: 构建一个新元素zipList然后连接到quickList4. insertB+zlB>zpMax 并且插入位置位于中间//将当前zipList分割为2个zipList连接到quickList中,然后将元素插入到分割后的前一个元素的尾部位置
直接删除即可,如果当前zipList已经没有元素了,就将当前zipList删除即可,然后修改指针连接
Key 与Value中元素的数量
- Redis最多可以处理2^32个key(42亿) 实际每个Redis实例可以处理至少2.5亿个key
- 每个Hash,List,Set,ZSet集合都可以包含2^32个元素
