当前位置: 首页 > news >正文

Redis设计与实现之整数集合

目录

一、内存映射数据结构

二、整数集合

1、整数集合的应用

2、数据结构和主要操作

3、intset运行实例

创建新intset

添加新元素到 intset

添加新元素到 intset(不需要升级)

添加新元素到 intset (需要升级)

4、升级

升级实例

5、关于升级

第一,从较短整数到较长整数的转换,并不会更改元素里面的值。

第二,集合编码元素的方式,由元素中长度最大的那个值来决定。

6、 关于元素移动

7、 其他操作

读取

写入

删除

降级

三、小结


一、内存映射数据结构

虽然内部数据结构非常强大,但是创建一系列完整的数据结构本身也是一件相当耗费内存的工作,当一个对象包含的元素数量并不多,或者元素本身的体积并不大时,使用代价高昂的内部数据结构并不是最好的办法。

为了解决这一问题, Redis在条件允许的情况下,会使用内存映射数据结构来代替内部数据结构。

内存映射数据结构是一系列经过特殊编码的字节序列,创建它们所消耗的内存通常比作用类似的内部数据结构要少得多,如果使用得当,内存映射数据结构可以为用户节省大量的内存。

不过,因为内存映射数据结构的编码和操作方式要比内部数据结构要复杂得多,所以内存映射数据结构所占用的 CPU时间会比作用类似的内部数据结构要多。

这一部分将对 Redis目前正在使用的两种内存映射数据结构进行介绍。

二、整数集合

整数集合( intset)用于有序、无重复地保存多个整数值,它会根据元素的值,自动选择该用什么长度的整数类型来保存元素。

举个例子,如果在一个 intset里面,最长的元素可以用 int16_t 类型来保存,那么这个 intset的所有元素都以 int16_t 类型来保存。

另一方面,如果有一个新元素要加入到这个 intset,并且这个元素不能用 int16_t 类型来保存——比如说,新元素的长度为 int32_t ,那么这个 intset就会自动进行“升级”:先将集合中现有的所有元素从 int16_t 类型转换为 int32_t 类型,接着再将新元素加入到集合中。

根据需要, intset可以自动从 int16_t 升级到int32_t 或int64_t ,或者从 int32_t 升级到int64_t 。

1、整数集合的应用

Intset是集合键的底层实现之一,如果一个集合:

1.只保存着整数元素;

2.元素的数量不多;

那么 Redis就会使用 intset来保存集合元素。

2、数据结构和主要操作

以下是intset.h/intset 类型的定义:

typedef structintset {//保存元素所使用的类型的长度uint32_t encoding;//元素个数uint32_t length;//保存元素的数组int8_tcontents[];} intset;

encoding 的值可以是以下三个常量的其中一个(定义位于 intset.c ) :

#define INTSET_ENC_INT16 (sizeof(int16_t))#define INTSET_ENC_INT32 (sizeof(int32_t))#define INTSET_ENC_INT64 (sizeof(int64_t))

contents 数组是实际保存元素的地方,数组中的元素有以下两个特性:

•没有重复元素;

•元素在数组中从小到大排列;

contents 数组的int8_t类型声明比较容易让人误解,实际上, intset并不使用 int8_t类型来保存任何元素,结构中的这个类型声明只是作为一个占位符使用:在对 contents 中的元素进行读取或者写入时,程序并不是直接使用 contents 来对元素进行索引,而是根据 encoding的值,对 contents 进行类型转换和指针运算,计算出元素在内存中的正确位置。在添加新元素,进行内存分配时,分配的容量也是由 encoding 的值决定。

下表列出了处理 intset的一些主要操作,以及这些操作的算法复杂度:

3、intset运行实例

让我们跟踪一个 intset的创建和添加过程,籍此了解 intset的运作方式。

创建新intset

intset.c/intsetNew 函数创建一个新的 intset,并为它设置初始化值:

intset*is=intsetNew();// intset->encoding = INTSET_ENC_INT16;// intset->length 0;// intset->contents = [];

注意encoding 使用INTSET_ENC_INT16 作为初始值。

添加新元素到 intset

创建intset之后,就可以对它添加新元素了。

添加新元素到 intset的工作由 intset.c/intsetAdd 函数完成,它需要处理以下三种情况:

1.元素已存在于集合,不做动作;

2.元素不存在于集合,并且添加新元素并不需要升级;

3.元素不存在于集合,但是要在升级之后,才能添加新元素;

并且,intsetAdd 需要维持 intset->contents 的以下性质:

1.确保数组中没有重复元素;

2.确保数组中的元素按从小到大排序;

整个intsetAdd 的执行流程可以表示为下图:

以下两个小节分别演示添加操作在升级和不升级两种情况下的执行过程。

添加新元素到 intset(不需要升级)

如果 intset现有的编码方式适用于新元素,那么可以直接将新元素添加到 intset,无须对 intset进行升级。

以下代码演示了将三个 int16_t 类型的整数添加到集合的过程,以及在添加过程中,集合的状 态:

intset*is=intsetNew();intsetAdd(is, 10,NULL);// is->encoding = INTSET_ENC_INT16;// is->length = 1;// is->contents = [10];intsetAdd(is, 5,NULL);// is->encoding = INTSET_ENC_INT16;// is->length = 2;// is->contents = [5, 10];intsetAdd(is, 12, NULL);// is->encoding = INTSET_ENC_INT16;// is->length = 3;// is->contents = [5, 10, 12]

因为添加的三个元素都可以表示为 int16_t ,因此 is->encoding 一直都是 INTSET_ENC_INT16 。

另一方面,is->length 和 is->contents 的值则随着新元素的加入而被修改。

添加新元素到 intset (需要升级)

当要添加新元素到 intset ,并且 intset 当前的编码并不适用于新元素的编码时,就需要对 inset 进行升级。

以下代码演示了带升级的添加操作的执行过程:

intset *is = intsetNew();
intsetAdd(is, 1, NULL);
// is->encoding = INTSET_ENC_INT16;
// is->length = 1;
// is->contents = [1];
intsetAdd(is, 65535, NULL);
// is->encoding = INTSET_ENC_INT32;
// is->length = 2;
// is->contents = [1, 65535];
intsetAdd(is, 70000, NULL);
// is->encoding = INTSET_ENC_INT32;
// is->length = 3;
// is->contents = [1, 65535, 70000];
intsetAdd(is, 4294967295, NULL);
// is->encoding = INTSET_ENC_INT64;
// is->length = 4;
// is->contents = [1, 65535, 70000, 4294967295];
// 所有值使用 int16_t 保存
// 升级
// 所有值使用 int32_t 保存
// 升级
// 所有值使用 int64_t 保存

在添加 65535 和 4294967295 之后,encoding 属性的值,以及 contents 数组保存值的方式, 都被改变了。

4、升级

在添加新元素时,如果 intsetAdd 发现新元素不能用现有的编码方式来保存,它就会将升级集

合和添加新元素的任务转交给 intsetUpgradeAndAdd 来完成:

intsetUpgradeAndAdd 需要完成以下几个任务:

  1. 对新元素进行检测,看保存这个新元素需要什么类型的编码;

  2. 将集合encoding属性的值设置为新编码类型,并根据新编码类型,对整个contents数 组进行内存重分配。

  3. 调整contents数组内原有元素在内存中的排列方式,让它们从旧编码调整为新编码。

  4. 将新元素添加到集合中。

整个过程中,最复杂的就是第三步,让我们用一个例子来理解这个步骤。 

升级实例

假设有一个 intset ,里面包含三个用 int16_t 方式保存的数值,分别是 1 、2 和 3 ,它的结 构如下: 

intset->encoding = INTSET_ENC_INT16;
intset->length = 3;
intset->contents = [1, 2, 3];

其中,intset->contents 在内存中的排列如下:

bit     0  15  31  47 
value   | 1 | 2 | 3 |

现在,我们要要将一个长度为 int32_t 的值 65535 加入到集合中,intset 需要执行以下步骤:

1. 将encoding属性设置为INTSET_ENC_INT32。
2. 根据encoding属性的值,对contents数组进行内存重分配。

重分配完成之后,contents 在内存中的排列如下:

bit     0  15  31 47  63  95  127 
value   | 1 | 2 | 3 | ? | ? | ? |

3.因为原来的 3 个 int16_t 值还“挤在”contents 前面的 48 个位里,所以程序需要对它们

进行移动和类型转换,从而让它们适应集合的新编码方式。 首先是移动 3 :

 接着移动2:

 最后,移动 1 :

4.最后,将新值 65535 添加到数组:

将 intset->length 设置为 4 。

至此,集合的升级和添加操作完成,现在的 intset 结构如下:

intset->encoding = INTSET_ENC_INT32;
intset->length = 4;
intset->contents = [1, 2, 3, 65535];

5、关于升级

关于升级操作,还有两点需要提醒一下:

第一,从较短整数到较长整数的转换,并不会更改元素里面的值。

在 C 语言中,从长度较短的带符号整数到长度较长的带符号整数之间的转换(比如从 int16_t 转换为 int32_t )总是可行的(不会溢出)、无损的。

另一方面,从较长整数到较短整数之间的转换可能是有损的(比如从 int32_t 转换为 int16_t )。

因为 intset 只进行从较短整数到较长整数的转换(也即是,只“升级” ,不“降级” ),因此, “升 级”操作并不会修改元素原有的值。

第二,集合编码元素的方式,由元素中长度最大的那个值来决定。

就像前面演示的例子一样,当要将一个 int32_t 编码的新元素添加到集合时,集合原有的所有 int16_t 编码的元素,都必须转换为 int32_t 。

尽管这个集合真正需要用 int32_t 长度来保存的元素只有一个,但整个集合的所有元素都必须 转换为这种类型。

6、 关于元素移动

在进行升级的过程中,需要对数组内的元素进行“类型转换”和“移动”操作。

其中,移动不仅出现在升级(intsetUpgradeAndAdd)操作中,还出现其他对 contents 数组内 容进行增删的操作上,比如 intsetAdd 和 intsetRemove ,因为这种移动操作需要处理 intset 中的所有元素,所以这些函数的复杂度都不低于 O(N) 。

7、 其他操作

以下是一些关于 intset 其他操作的讨论。

读取

有两种方式读取 intset 的元素,一种是 _intsetGet ,另一种是 intsetSearch :
• _intsetGet 接受一个给定的索引 pos ,并根据 intset->encoding 的值进行指针运算,

计算出给定索引在 intset->contents 数组上的值。
• intsetSearch 则使用二分查找算法,判断一个给定元素在 contents 数组上的索引。

写入

除了前面介绍过的 intsetAdd 和 intsetUpgradeAndAdd 之外,_intsetSet 也对集合进行写 入操作:它接受一个索引 pos ,以及一个 new_value ,将 contents 数组 pos 位置的值设为 new_value 。

删除

删除单个元素的工作由 intsetRemove 操作,它先调用 intsetSearch 找到需要被删除的元素 在 contents 数组中的索引,然后使用内存移位操作,将目标元素从内存中抹去,最后,通过 内存重分配,对 contents 数组的长度进行调整。

降级

Intset 不支持降级操作。

Intset 定位为一种受限的中间表示,只能保存整数值,而且元素的个数也不能超过 redis.h/REDIS_SET_MAX_INTSET_ENTRIES (目前版本值为 512 )这些条件决定了它被保 存的时间不会太长,因此对它进行太复杂的操作,没有必要。

当然,如果内存确实十分紧张的话,给 intset 添加降级功能也是可以实现的,不过这可能会让 intset 的代码增长一倍。

三、小结

  • Intset 用于有序、无重复地保存多个整数值,它会根据元素的值,自动选择该用什么长度的整数类型来保存元素。

  • 当一个位长度更长的整数值添加到 intset 时,需要对 intset 进行升级,新 intset 中每个 元素的位长度都等于新添加值的位长度,但原有元素的值不变。

  • 升级会引起整个 intset 进行内存重分配,并移动集合中的所有元素,这个操作的复杂度 O(N) 

  • Intset 只支持升级,不支持降级。

  • Intset 是有序的,程序使用二分查找算法来实现查找操作,复杂度为 O(lgN) 。

相关文章:

Redis设计与实现之整数集合

目录 一、内存映射数据结构 二、整数集合 1、整数集合的应用 2、数据结构和主要操作 3、intset运行实例 创建新intset 添加新元素到 intset 添加新元素到 intset(不需要升级) 添加新元素到 intset (需要升级) 4、升级 升级实例 5、关于升级 …...

[Kubernetes]2. k8s集群中部署基于nodejs golang的项目以及Pod、Deployment详解

一. 创建k8s部署的镜像 1.部署nodejs项目 (1).上传nodejs项目到节点node1 (2).压缩nodejs项目 (3).构建nodejsDockerfile 1).创建nodejsDockerfile 具体可参考:[Docker]十.Docker Swarm讲解,在/root下创建nodejsDockerfile,具体代码如下: FROM node #把压缩文件COPY到镜像的…...

讯飞星火大模型api调用

讯飞星火大模型,通过websocket方式通信传递协议要求的报文,然后将流式返回的报文拼接为完整的响应内容,status2时是最后一条消息。因为是websocket方式所以是异步响应的,如果想要同步需要使用CountDownLatch控制下线程等待最后一条…...

TCP与UDP:网络世界中的“顺丰快递”与“广播电台”

随着互联网的普及,我们每天都在与网络打交道。而在这背后,数据的传输离不开TCP和UDP这两种传输协议。它们就像网络世界中的“顺丰快递”和“广播电台”,各自有着不同的工作方式和特点。让我们一起来了解一下它们吧! 一、TCP&…...

升级Xcode15,iOS17后问题解决

1、Could not build module ‘WebKit’ 报错 解决方案: 编辑文件 /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS17.0.sdk/System/Library/Frameworks/WebKit.framework/Headers/WKWebsiteDataStore.h 将里面…...

RabbitMQ搭建集群环境、配置镜像集群、负载均衡

RabbitMQ集群搭建 Linux安装RabbitMQ下载安装基本操作命令开启管理界面及配置 RabbitMQ集群搭建确定rabbitmq安装目录启动第一个节点启动第二个节点停止命令创建集群查看集群集群管理 RabbitMQ镜像集群配置启用HA策略创建一个镜像队列测试镜像队列 负载均衡-HAProxy安装HAProxy…...

leetcode:457. 环形数组是否存在循环

环形数组是否存在循环 存在一个不含 0 的 环形 数组 nums ,每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数: 如果 nums[i] 是正数,向前(下标递增方向)移动 |nums[i]| 步 如果 nums[i] 是负数&…...

Kafka集成springboot

安装kafka,直接到官网下载bin文件,本文使用windows进行使用kafka。 下载之后,第一步,启动zookeeper: zookeeper-server-start.bat ..\..\config\zookeeper.properties 第二步,启动kafka: kafka…...

Unity中实现ShaderToy卡通火(移植篇)

文章目录 前言一、准备好我们的后处理基础脚本1、C#:2、Shader: 二、开始逐语句对ShaderToy进行转化1、首先,找到我们的主函数 mainImage2、其余的方法全部都是在 mainImage 函数中调用的方法3、替换后的代码(已经没报错了,但是效…...

指针相关知识(进阶)

前面的入门中已经介绍了指针的基础知识,接下来,让我们继续学习吧! 一. 字符指针变量 char* 一般形式 int main() {char n w;char* pa &n;*pa w;return 0; } 这并不是把字符串hello world放在n中,而是把第一个字符的地址…...

怎么将文件变为可执行文件

怎么将文件变为可执行文件 在Unix/Linux系统中,要将一个文件变为可执行文件,你需要使用chmod命令。以下是基本的步骤: 打开终端:使用你系统中的终端或命令行界面。 使用 cd 命令切换到包含你的文件的目录。例如: bash …...

5373. 中等计算

文章目录 QuestionIdeasCode Question 给定一个长度为 n 的非负整数序列 a1,a2,…,an 。 对于 1≤i≤n ,有 biai⊕(imod1)⊕(imod2)⊕…⊕(imodn) 。 请你计算并输出 b1⊕b2⊕…⊕bn 的值。 ⊕ 表示按位异或。 输入格式 第一行包含整数 n 。 第二行包含 n 个整…...

极智一周 | 两系列汇总、MI300X、H100、特供芯片、GPT-4、火灾检测、酷睿Ultra And so on

欢迎关注我的公众号 [极智视界],获取我的更多技术分享 大家好,我是极智视界,带来本周的 [极智一周],关键词:两系列汇总、MI300X、H100、特供芯片、GPT-4、火灾检测、酷睿Ultra And so on。 邀您加入我的知识星球「极智…...

leetcode刷题日志-383赎金信

思路:分别用两个map记录ransomNote和magazine中的字符以及出现的次数。最后遍历记录ransomNote的map,如果ransomNote的map中出现的magazine的map中没有出现或者出现的次数小于ransomNote的map则返回false,否则返回true; class So…...

K8s(九)—volume.md

目录 volumeconfigMap介绍官网例子基于文件生成 ConfigMap使用 ConfigMap 数据定义容器环境变量使用单个 ConfigMap 中的数据定义容器环境变量 EmptyDirhostPathhostPath 配置示例 nfspersistentVolumeClaim volume https://kubernetes.io/zh-cn/docs/concepts/storage/volume…...

python N个人围成一圈报数 报到3出列 直到只剩下最后一人

公司聚会上&#xff0c;N名员工围成一圈&#xff0c;按1—N顺序编号(要求N<40)。 然后从队头开始1&#xff0c;2&#xff0c;3报数&#xff0c;数3的出列&#xff0c;剩下的员工再从头开始1&#xff0c;2&#xff0c;3报数……直到剩下最后一名员工时&#xff0c; 这员工就是…...

RFC4861 中文版下

10. 协议常量 路由器常量: MAX_INITIAL_RTR_ADVERT_INTERVAL 16 秒MAX_INITIAL_RTR_ADVERTISEMENTS 3 次发送MAX_FINAL_RTR_ADVERTISEMENTS 3 次发送MIN_DELAY_BETWEEN_RAS 3 秒MAX_RA_DELAY_TIME .5 秒主机常量: MAX_RTR_SOLICITATION_…...

用友时空 KSOA 多处SQL注入漏洞复现

0x01 产品简介 用友时空 KSOA 是建立在 SOA 理念指导下研发的新一代产品,是根据流通企业前沿的 IT 需求推出的统一的IT基础架构,它可以让流通企业各个时期建立的 IT 系统之间彼此轻松对话。 0x02 漏洞概述 用友时空 KSOA 系统 PayBill、QueryService、linkadd.jsp等接口处…...

[AutoSar]基础部分 RTE 介绍

目录 关键词平台说明一、什么是RTE二、RTE的主要功能 关键词 嵌入式、C语言、autosar、EcuM、wakeup、flex 平台说明 项目ValueOSautosar OSautosar厂商vector芯片厂商TI编程语言C&#xff0c;C编译器HighTec (GCC) 一、什么是RTE RTE&#xff08;Run-Time Environment&…...

Logstash访问安全访问Elasticsearch集群

生成logstash证书: opensal pkcs12 -in elastic-stack-ca.p12 -clcerts -nokeys > logafash.cer openssl x509 -in logstash.cer -out logstash.pem 编排配置文件...

加密的艺术:对称加密的奇妙之处(下)

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…...

异常检测 | MATLAB实现BiLSTM(双向长短期记忆神经网络)数据异常检测

异常检测 | MATLAB实现BiLSTM(双向长短期记忆神经网络)数据异常检测 目录 异常检测 | MATLAB实现BiLSTM(双向长短期记忆神经网络)数据异常检测效果一览基本介绍模型准备模型设计参考资料效果一览 基本介绍 训练一个双向 LSTM 自动编码器来检测机器是否正常工作。 自动编码器接受…...

2023“楚怡杯”湖南省赛“信息安全管理与评估“--数字取证调查(高职组)

2023“楚怡杯”湖南省“信息安全管理与评估”(高职组)任务书 2023“楚怡杯”湖南省“信息安全管理与评估”(高职组)任务书第一阶段竞赛项目试题第二阶段竞赛项目试题第二部分 数字取证调查:需要环境私聊博主:2023“楚怡杯”湖南省“信息安全管理与评估”(高职组)任务书…...

C++ list常用操作

目录 一、介绍 二、list的常用操作 1、构造 2、迭代器 3、元素访问 4、容量操作 一、介绍 std::list文档链接 list是可以在常数范围内在任意位置进行插入和删除的序列式容器&#xff0c;并且该容器可以前后双向迭代。list的底层是双向链表结构&#xff0c;双向链表中每个…...

MILP加速运算技巧——模型对称性的预处理

文章目录 整数规划的对称性什么是对称性对称性的影响 对称性的预处理方法 整数规划的对称性 什么是对称性 许多整数规划问题存在对称性&#xff0c;这种对称性是指问题解空间的对称&#xff0c;即在对称的解空间当中解的优化目标值上是相同的。这种对称性并不会改变问题的最优…...

JavaScript中的生成器与迭代器详解

一、迭代器与可迭代对象 1.什么是迭代器 迭代器&#xff08;iterator&#xff09;&#xff0c;使用户在容器对象&#xff08;container&#xff0c;例如链表或数组&#xff09;上遍访的对象&#xff0c;使用该接口无需关心对象的内部实现细节。 其行为像数据库中的光标&…...

WebLangChain_ChatGLM:结合 WebLangChain 和 ChatGLM3 的中文 RAG 系统

WebLangChain_ChatGLM 介绍 本文将详细介绍基于网络检索信息的检索增强生成系统&#xff0c;即 WebLangChain。通过整合 LangChain&#xff0c;成功将大型语言模型与最受欢迎的外部知识库之一——互联网紧密结合。鉴于中文社区中大型语言模型的蓬勃发展&#xff0c;有许多可供利…...

hive常用SQL函数及案例

1 函数简介 Hive会将常用的逻辑封装成函数给用户进行使用&#xff0c;类似于Java中的函数。 好处&#xff1a;避免用户反复写逻辑&#xff0c;可以直接拿来使用。 重点&#xff1a;用户需要知道函数叫什么&#xff0c;能做什么。 Hive提供了大量的内置函数&#xff0c;按照其特…...

分页操作中使用LIMIT和OFFSET后出现慢查询的原因分析

事情经过 最近在做批量数据处理的相关业务&#xff0c;在和下游对接时&#xff0c;发现拉取他们的业务数据刚开始很快&#xff0c;后面会越来越慢&#xff0c;40万数据一个小时都拉不完。经过排查后&#xff0c;发现对方用了很坑的分页查询方式 —— LIMIT OFFSET&#xff0c;…...

Java八股文面试全套真题【含答案】- Redis篇

请看下面列举的50个关于Redis的经典面试问题和简短答案&#xff1a; Redis是什么&#xff1f;简要介绍一下Redis的特点。 Redis是一个开源的高性能键值存储数据库&#xff0c;支持多种数据结构&#xff0c;如字符串、列表、集合、哈希和有序集合等。 特点包括快速、可持久化、支…...