Redis数据对象

embedded/2024/12/27 2:18:49/

基本结构图

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,分为三步:

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

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

  1. 给哈希表2分配空间,一般比哈希表1大一倍
  2. 在rehash期间,每次哈希表元素新增、删除、查找的时候,Redis会执行对应的操作外,还会将哈希表1中索引位置上的所有dictEntry迁移到哈希表2
  3. 迁移完成后,哈希表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 


http://www.ppmy.cn/embedded/149060.html

相关文章

Webpack学习笔记(5)

1.拆分开发环境和生产环境配置 很多配置在开发环境和生产环境存在不一致的情况,比如开发环境没有必要设置缓存,生产环境需要设置公共路径等等。 2.公共路径 使用publicPath配置项,可以通过它指定应用程序中所有资源的基础路径。 webpack.…

SpringBoot3——基础特性

SpringApplication 自定义banner 类路径添加banner.txt或设置spring.banner.location就可以定制banner推荐网站:Spring Boot banner 在线生成工具,制作下载英文 banner.txt,修改替换 banner.txt 文字实现自定义,个性化启动 bann…

【Spring】Spring的模块架构与生态圈—Spring Boot、Spring Cloud与Spring Security

随着互联网的发展,企业对快速开发和高可用性的需求不断增加,Spring生态系统(包括Spring Boot、Spring Cloud和Spring Security)应运而生,为Java开发提供了强大的支持。 在实际应用中,Spring Boot使得开发者…

【git】git命令

目录 1. 在当前目录下创建一个新的git仓库2. 克隆一个远程仓库到本地3. 显示工作目录和暂存区的状态4. 将文件添加到暂存区,准备提交5. 将暂存区的文件提交到本地仓库6. 显示提交历史记录7.版本回退8.查所有操作记录(包括删除记录)9.添加文件到忽略列表10.列出所有本…

【理解机器学习中的过拟合与欠拟合】

在机器学习中,模型的表现很大程度上取决于我们如何平衡“过拟合”和“欠拟合”。本文通过理论介绍和代码演示,详细解析过拟合与欠拟合现象,并提出应对策略。主要内容如下: 什么是过拟合和欠拟合? 如何防止过拟合和欠拟…

运动控制卡网络通讯的心跳检测之C#上位机编程

本文导读 今天,正运动小助手给大家分享一下如何使用C#上位机编程实现运动控制卡网络通讯的心跳检测功能。 01 ECI2618B硬件介绍 ECI2618B经济型多轴运动控制卡是一款脉冲型、模块化的网络型运动控制卡。控制卡本身最多支持6轴,可扩展至12轴的运动控制…

芯科科技蓝牙、Wi-Fi、Wi-SUN产品广获业界认可,技术创新引领行业潮流

物联网领军企业领跑未来无线开发平台发展 2024年,Silicon Labs(亦称“芯科科技“,NASDAQ:SLAB)在物联网(IoT)领域持续深耕,凭借创新的企业发展理念与实践、行业领先的技术与产品&am…

No.27 笔记 | RCE远程命令执行基础

一、RCE概述 (一)定义 RCE指攻击者可以通过远程方式在目标系统上执行恶意代码的漏洞或攻击技术,范围广泛,包括代码执行、文件包含、反序列化、命令执行、写文件Getshell等情况。 (二)危害 攻击者可继承…