`

整数集合与压缩列表

阅读更多
    在 Redis 中,当一个普通集合类型只包含整数值元素,并且元素数量不多时,就会使用整数集合(intset)作为集合键的底层实现,它可以保存类型为 int16_t、int32_t 或者 int64_t 的整数值,并且不会重复。这可通过类似下面的命令来看出。
redis> SADD nums 1 3 5 7 9 3 7
(integer)5
redis> OBJECT ENCODING nums
"intset"

    整数集合在 Redis 中的结构定义如下。
typedef struct intset{
    uint32_t encoding;        // 编码方式
    uint32_t length;          // 集合中包含的元素数量
    int8_t contents[];        // 按从小到大的顺序保存元素的底层数组
}intset;

    其中要注意的是,尽管 contents 字段申明为 int8_t 类型,但实际上它并不保存任何 int8_t 类型的值,保存的值的真正类型完全取决于 encoding 属性的值:
    1、如果 encoding 的值为 INTSET_ENC_INT16,则 contents 是一个 int16_t 类型的数组。
    2、如果 encoding 的值为 INTSET_ENC_INT32,则 contents 是一个 int32_t 类型的数组。
    3、如果 encoding 的值为 INTSET_ENC_INT64,则 contents 是一个 int64_t 类型的数组。
    因此,当某个时候新添加的元素的数值范围超出了当前集合的 encoding 属性对应的类型所能表示的范围时,就需要对该整数集合进行升级操作后再添加新元素,这个过程涉及的步骤如下:
    1、根据新元素的类型扩展整数集合底层数组的空间大小。
    2、将原来的元素的类型都转换成新元素的类型,并将它们按原来的大小顺序放到扩展后的空间对应的位上。
    3、将新元素添加到底层数组中合适的位置(要么放在最开头,要么放在最末尾)。
    4、修改 encoding 属性的值,并将 length 属性的值自增 1。
    整数集合一经升级,之后就不能再降级了。

    压缩列表(ziplist)是 Redis 为节约内存而开发,它是由一系列特殊编码的连续内存块组成的顺序型数据结构。
    列表键和哈希键的底层实现都用到了压缩列表。当一个列表键只包含少量列表项,并且每项要么是小整数值,要么是较短的字符串,或者当一个哈希键只包含少量键值对,并且每一个键值对要么是小整数值,要么是较短的字符串时,Redis 就会使用压缩列表来做列表键或者哈希键的底层实现。这两种情况都可分别用“OBJECT ENCODING”命令来验证。
    一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数值。下图展示了压缩列表的各个组成部分和说明。

    为理解这些部分,假设有下图这样一个压缩列表示例。

    其中,
    * 属性 zlbytes 的值为 0x50,表示压缩列表的总长为 80 字节。
    * 属性 zltail 的值为 0x3c,表示若指针 p 指向压缩列表的起始地址,则使用 p + 60 即可计算出表尾节点 entry3 的地址。
    * 属性 zllen 的值为 0x3,表示压缩列表包含 3 个节点。
    接下来再来说说压缩列表节点的构成。
    每个压缩列表节点可以保存一个字节数组或者一个整数值,其中,字节数组的长度可以是以下三种长度的其中之一:
    1、小于等于 63(2^6 - 1)字节。
    2、小于等于 16 383(2^14 - 1)字节。
    3、小于等于 4 294 967 295(2^32 - 1)字节。
    而整数值则可以是以下六种长度的其中一种:
    1、4 位长、介于 0 至 12 之间的无符号整数。
    2、1 字节长的有符号整数。
    3、3 字节长的有符号整数。
    4、int16_t 类型整数。
    5、int32_t 类型整数。
    6、int64_t 类型整数。
    每个节点都由 previous_entry_length、encoding 和 content 三个部分组成,其中:
    * previous_entry_length 属性的长度可以是 1 字节或者 5 字节,它记录了压缩列表中前一个节点的长度。如果前一节点的长度小于 254 个字节,则该属性的长度为 1 字节,否则为 5 字节(其中第一字节会被设置成 0xFE(十进制 254),之后的 4 个字节则用于保存前一节点的长度)。根据该性质,程序可以根据当前节点的起始地址来计算出前一个节点的起始地址,压缩列表的从表尾向表头遍历操作就是使用这一原理实现的。
    * encoding 属性记录了节点的 content 属性所保存数据的类型以及长度。它有以下两种情况:
    1、1 字节、2 字节或者 5 字节长,值的最高位为 00、01 或者 10 的是字节数组编码,表示该节点的 content 属性保存着字节数组,数组的长度由除去最高两位之后的其他位记录。
    2、1 字节长,值的最高位以 11 开头的是整数编码,表示 content 属性保存着整数值,整数值的类型和长度由编码除去最高两位之后的其他位记录。
    下面两张表分别记录了可用的字节数组和整数编码。

    * content 属性负责保存节点的值,节点值可以是字节数组或者整数,其类型和长度由 encoding 属性决定。
    下图展示了一个保存字节数组的节点示例:

    其中,属性 previous_entry_length 的值为 0xFE00002766,最高位字节 0xFE 表示它占用五个字节,之后的四个字节 0x00002766(十进制 10086)才是前一节点的实际长度。属性 encoding 的最高两位 00 表示节点保存的是一个字节数组,后六位 001011 表示该数组的长度是 11。属性 content 保存着节点的值“hello world”。
    此外,由于 previous_entry_length 属性的长度与前一个节点的长度是否小于 254 字节有关,因此当一个压缩列表中存在多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN 时,如果在 e1 之前插入了一个长度大于 254 字节的新节点,将迫使程序对压缩列表执行空间重分配操作,以将 e1 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长,而新增的四个字节又造成 e1 节点的长度变成了介于 254 字节到 257 字节之间,这进而又需要扩展 e2 节点的 previous_entry_length 属性长度,如此下去直到 eN。
    这种在特殊情况下产生的连续多次空间扩展操作在 Redis 中就被称为“连锁更新”(cascade update)。除添加新节点外,删除节点也可能会引发连锁更新。由于连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作,而每次空间重分配的最坏复杂度为 O(N),因此连锁更新的最坏复杂度为 O(N^2)。幸运的是,尽管连锁更新的复杂度较高,但由于其条件特殊,实际中它真正造成性能问题的几率其实是很低的。

参考书籍:
1、《Redis 的设计与实现》第 6 章——整数集合。
2、《Redis 的设计与实现》第 7 章——压缩列表。
  • 大小: 153.6 KB
  • 大小: 21.2 KB
  • 大小: 157.1 KB
  • 大小: 19 KB
分享到:
评论

相关推荐

    redis压缩列表原理与应用

    Redis对压缩列表的应用主要体现在其对字符串、列表、哈希表、集合、有序集合五种数据结构的支持上。每种数据结构根据其应用场景的不同,可以采用不同的编码方式。例如,列表结构可以通过压缩列表编码来存储大量的小...

    35源码 3:挨肩迭背 —— 探索「压缩列表」内部(1).md

    通过以上知识点的整理,我们可以了解到Redis中的压缩列表是一种节省内存的数据结构,它通过连续的内存块和紧凑的编码设计来减少内存消耗,非常适合用于存储小数据集合。同时,它的结构设计支持了高效的双向遍历和对...

    图像压缩编码的研究现状和发展

    根据压缩过程中是否允许信息损失,图像压缩可以分为无损压缩与有损压缩两大类。相较于有损压缩,无损压缩在保持原始图像信息完整性的基础上,其压缩比率通常较低且技术难度更大。近年来,基于小波变换的图像压缩方法...

    redis字节码存压缩对象

    - Redis 支持五种基本数据类型:字符串(String)、哈希表(Hash)、列表(List)、集合(Set)和有序集合(Sorted Set)。每种类型的数据在内部都有特定的表示方式。 - 对于字符串,Redis 可以直接存储原始字节...

    ziplist--redis源码研究笔记-压缩列表ziplist1

    Redis中的压缩列表`ziplist`是一种特殊的内存优化数据结构,主要设计用于存储简化的序列数据,如哈希表和有序集合。它通过紧凑的内存布局和指针位操作来节省内存,尤其适用于小数据量的场景。以下是关于`ziplist`的...

    JPG图像压缩MATLAB代码

    这是JPEG有损压缩的关键步骤,它将DCT得到的系数映射到一个固定的、有限的整数集合。量化表通常是非对称的,以保留更多的低频信息,牺牲高频信息,因为人眼对高频细节的敏感度较低。 量化后的系数按照**Zigzag扫描*...

    redis_3.2.9_内存分布分析

    而整数集合和压缩列表则用于处理键值对中的整数集合和小的对象列表,快速列表则结合了链表和压缩列表的特点,以解决压缩列表在长度较大时性能下降的问题。 在数据类型操作方面,Redis支持多种数据类型,包括字符串...

    Redis的数据结构和对象系统介绍.docx

    集合对象使用整数集合或字典存储,整数集合适用于存储整数,字典适用于存储任意类型元素。 2.5. 有序集合对象 有序集合使用跳跃表和字典联合存储,跳跃表负责元素的排序,字典负责键值对的查找。 3. 数据库键...

    小林的图解系列之一,图解redis数据结构

    这些数据类型是Redis键值对中值的存储形式,而它们的底层数据结构包括SDS、双向链表、压缩列表、哈希表、跳表、整数集合、quicklist、listpack等。 1. SDS(Simple Dynamic String):Redis中的字符串默认采用SDS...

    状态压缩算法

    而状态压缩则通过位运算来表示状态,将多个状态压缩到一个整数的二进制表示中,显著减少了内存占用。 例如,在动态规划问题中,如果状态由多个独立的变量决定,我们可以为每个变量分配一位,这样所有的状态就可以用...

    高光谱图像压缩方法研究

    将二维小波变换、一维低复杂度整数可逆KLT变换与3D-SPIHT相结合,可以构建一个高效的高光谱图像压缩系统。这种组合不仅能够充分利用空间和谱间的相关性,还能在较低的计算复杂度下实现良好的压缩性能。 #### 六、...

    Redis源码解析涵盖数据结构及特性实现

    从源码层面分析Redis的技术架构,详细介绍Redis的核心数据结构,例如字符串、整数集合、压缩列表及其对象类型,事务处理,Pub/Sub系统的运行方式及其实现细节。探讨Redis的两种持久化技术之一——RDB的工作机制。...

    小波光谱图像压缩

    与传统的浮点小波变换相比,整数小波变换具有更好的计算效率和更简单的硬件实现能力,同时避免了因浮点运算带来的量化误差,这对于高光谱图像的无损压缩尤为重要。 ### 高光谱图像的特点 高光谱图像是由多个波段...

    基于连通性状态压缩的动态规划问题ACM NOIP

    对于基于连通性状态压缩的问题,状态可能定义为当前处理到的顶点集合以及这些顶点所构成的连通分量的信息。 3. **状态转移方程**:这是动态规划的核心,描述了如何从一个状态转移到另一个状态。在连通性问题中,...

    《数据压缩》第三章

    如果整数集合中元素的数量未知,或者最大的整数未知,那么就不能使用固定长度的编码,自然而然地,解决方案是为整数分配变长的编码。 变长编码应该满足两个基本要求:第一,对于一个给定的整数,其码字应尽可能短,...

    Python-模型压缩与加速相关文献汇总

    本资料包"Awesome-model-compression-and-acceleration-master"显然是一个关于Python实现模型压缩与加速的资源集合,下面将对这一主题进行深入探讨。 一、模型压缩 1. 参数量化:通过将模型参数(权重)从浮点数...

Global site tag (gtag.js) - Google Analytics