首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >Redis源码学习之压缩列表

Redis源码学习之压缩列表

原创
作者头像
里奥搬砖
修改于 2018-10-12 09:58:24
修改于 2018-10-12 09:58:24
5980
举报

压缩列表是列表对象、哈希对象和有序集合对象的底层实现之一。以列表对象为例,当列表节点都是比较小的整数或者比较短的字符串的时候,Redis就会选择压缩列表来做底层实现。其实,压缩列表就是一个字节数组,我们知道,在虚拟存储器中以连续的形式存放数据,可以避免产生内存碎片,提高存储器利用率,而压缩列表正是因此而设计的。当然,这种存储结构也有其局限性,这也是为什么高级对象是有选择的使用它的原因。

压缩列表的实现

1.数据结构

前文中提到,压缩列表就是一块连续的内存空间,是一个字节数组。

所有的操作都是基于这块内存进行编排,比如压缩列表初始化会申请一块空间:

注释中可以看出,一个空的压缩列表占用了11个字节的内存空间。

  1. 前4个字节分配给zlbytes,表示整个压缩列表所占字节数(空列表就是11)
  2. 接着4个字节分配给zltail,表示从压缩列表第一个字节距离表尾节点的字节数(空列表是10)
  3. 两个字节分配给zllen,表示压缩列表的节点个数(空列表是0),由于只有两个字节的空间,所以最大只能存储到65535,如果节点数大于65535,那么只能遍历整个列表求长度了,复杂度将从O(1)升至O(N);
  4. 最后的一个字节作为表尾标志位,写死为0xFF。

所以,一个空列表在存储器中是这样分布的:

这里的一个小方格代表1个字节,我们可以看到指针p指向压缩列表头部,将zltail中的值取出来与p相加就是尾节点了,由于目前是空列表,所以指向的是zlend。

2.节点

节点分为3个区块,分别为前置节点长度prevEntryLength,当前节点编码及长度encoding,以及当前节点内容content。例如,一个前置节点长度为255,当前节点长度16384的节点在内存中是这样分布的:

其中,content部分比较简单,就是存储了具体的数据,可以叫做节点体部。而prevEntryLength和encoding所占字节数是根据其本身存储的数据大小而变化的,这两部分放到可以称为节点头部。下面我们着重说一下这两个部分的设计。

  1. prevEntryLength 为什么要单独存放每个节点的前置节点大小呢?主要是压缩列表实现的也是一个双端链表,不仅要能够从头向尾遍历,也要能够反过来进行列表遍历,有了前置节点长度,我就可以先通过zltail找到尾节点,然后通过【当前节点指针减去前置节点所占字节数】一步一步向前遍历了。编码代码如下:

为了便于理解,我对源码稍作了修改。这里可以看出,prevEntryLength有两种情况: i.第一种占用1个字节空间,即当前置节点长度小于254的时候,直接把长度存到这个字节里即可,这里可能会有点迷惑,1个字节是8位,无符号整数范围是[0,255],所以最大应该可以存255,为什么这里特意避开呢?主要是因为前文说到了zlend标志位已经占用0xFF(255)了,所以这里再用会产生冲突,导致程序判断错误,同理0xFE(254)也被当前判断占用,所以这两个数字被放进了另一种情况, ii.第二种占用5个字节空间,这里的第一个字节会放进标志位0xFE(254),后面4个字节存放实际长度,比如我之前给出的例子中,5个字节是[254,255,0,0,0]就是这样的出来的。 相对应的解码代码如下,传入preEncodeLength起始地址,即可解析出长度所占字节数以及长度数值。

  1. encoding 这部分主要表示当前节点content部分的长度,以及这个长度值所使用的编码。这里也有两种情况,通过判断存储的数据是整数类型还是字符串类型。 i.如果是整数类型,判断其编码类型的代码如下:

可以看出encoding用一个字节作为编码类型的存储空间。其中,当存入的节点数值在[0,12]这个区间时,直接将该值融合到这一个字节的后4位,也就不需要content部分了。例如,前置节点长度为1,当前节点值为11的节点内存分布如下图所示:

可以看出,这种情况下,整个节点只需要两个字节的内存空间。如果节点值大于12,比如前置节点长度为1,当前节点值为128的节点,我们会判断出他在8位有符号整数中会溢出,在16位有符号整数范围内,因此encoding编码为0b11110000,content占用两个字节空间,分布如下:

可见,该节点占用4个字节空间,比简单使用类型int64(8字节)节省了5个字节(抛出前置节点长度部分)。所以这也是为什么压缩列表更适合存储数值较小的节点了。 ii.如果是字符串类型,判断其编码类型代码如下:

可以看出,通过字符串长度将其分为3种情况,对应encoding部分占用1个字节、2个字节和5个字节。比如前置节点长度为1,当前节点值为字符串hello的内存布局示意图为:

可以看出,该节点总共占用7个字节。 iii.encoding部分解码代码如下:

iiii.将头部转换为zlEntry结构,我们可以通过把连续空间中的字节拆分转换为一个节点结构,这样更加直观的看到各个字段的值:

以前文中的前置节点长度为255,当前节点长度为16384为例,编写测试用例如下:

输出为: prevrawlen:255 prevrawlensize:5 length:16384 lensize:5 headersize:10 encoding:128 p:0 iiii.对比后可以发现,整数值长度部分编码字节的前两位为11,字符串值长度部分编码类型是00、01、或10,再通过该直接剩余部分或者其他字节获取真实长度。

  1. 级联更新 想象这样一种场景,从某一段开始,连续的若干个节点的前置节点长度均为253字节,如下图所示:

此时我在节点1前面插入一个长度为254字节的节点值会发生什么样的事情呢?

由于插入节点由253变成254,导致节点1的前置节点长度从253变成254,从前文知道,253的前置节点长度编码只需要1个字节空间,而254需要5个字节空间,所以节点1需要进行内存重分配。节点1增长的这4个字节又会导致节点2的内存重分配,节点2导致节点3,直到节点n,Redis将其称之为【级联更新】(CascadeUpdate),形象一点更像是多米诺骨牌,一个节点的变更导致后面连接的节点都变更,因为内存分配的复杂度是O(n),那么发生级联更新将导致该插入操作的复杂度达到O(n^2)。同理,删除操作也有可能导致这样的情况发生。

总结

压缩列表可以说是Redis追求内存节约的极致,大量的字节、位操作虽然牺牲了代码的可读性,却降低了内存开销,减少了内存碎片的产生。在使用的时候我们也要小心级联更新现象的发生,让它在最适合的业务场景中发挥其作用。总的来说,压缩列表的实现有以下几个特点:

  1. 为节省内存而生的顺序型存储结构
  2. 基于位和字节构建内部协议
  3. 以程序复杂度换取内存的空间压缩
  4. ​有可能触发级联更新

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Redis 内存压缩原理
Redis 无疑是一个大量消耗内存的数据库,因此 Redis 引入了一些设计巧妙的数据结构进行内存压缩来减轻负担。ziplist、quicklist 以及 intset 是其中最常用最重要的压缩存储结构。
用户1289394
2020/12/18
1.1K0
压缩列表的源码实现
压缩列表ziplist本质上就是一个字节数组,是Redis为了节约内存而设计的一种线性数据结构,可以包含多个元素,每个元素可以是一个字节数组或一个整数。 Redis的有序集合、散列和列表都直接或者间接使用了压缩列表。当有序集合或散列表的元素个数比较少,且元素都是短字符串时,Redis便使用压缩列表作为其底层数据存储结构。列表使用快速链表(quicklist)数据结构存储,而快速链表就是双向链表与压缩列表的组合。 ziplist 压缩列表是一个特殊编码的双端链表(内存上连续),为了尽可能节省内存而设计的。ziplist 可以存储字符串或者整数值,其中整数被编码保存为实际的整数,而不是字符数组。ziplist 支持 O(1) 的时间复杂度在列表的两端进行 push 和 pop 操作。然而因为这些操作都需要对整个 ziplist 进行内存重分配(因为是一块连续的内存),所以操作的实际复杂度和 ziplist 占用的内存大小有关。在 7.0 版本里,ziplist 已经全面被 listpack 替换了(主要是因为连锁更新较影响性能)
zeekling
2022/12/10
4610
从根上理解ziplist为什么要牺牲速度而进行压缩!
正常情况下我们选择使用 Redis 就是为了提升查询速度,然而让人意外的是,Redis 当中却有一种比较有意思的数据结构,这种数据结构通过牺牲部分读写速度来达到节省内存的目的,这就是 ziplist(压缩列表),Redis 为什么要这么做呢?难道真的是觉得自己的速度太快了,牺牲一点速度也不影响吗?
业余草
2021/12/06
6950
从根上理解ziplist为什么要牺牲速度而进行压缩!
走近源码:压缩列表是怎样炼成的
经过前面对Redis源码的了解,令人印象深刻的也许就是Redis各种节约内存手段。而Redis对于内存的节约可以说是费尽心思,今天我就再来介绍一种Redis为了节约内存而创造的存储结构——压缩列表(ziplist)。
Jackeyzhe
2020/03/11
6560
走近源码:压缩列表是怎样炼成的
Redis压缩列表原理与应用分析
Redis是一款著名的key-value内存数据库软件,同时也是一款卓越的数据结构服务软件。它支持字符串、列表、哈希表、集合、有序集合五种数据结构类型,同时每种数据结构类型针对不同的应用场景又支持不同的编码方式。这篇文章主要介绍压缩列表编码,在理解压缩列表编码原理的基础上介绍Redis对压缩列表的应用,最后再对Redis压缩列表应用进行分析。
美的让人心动
2019/07/01
1.2K0
Redis压缩列表原理与应用分析
Redis的设计与实现(6)-压缩列表
压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型 (sequential) 数据结构.
仁扬
2023/06/27
2170
内存节省到极致!!!Redis中的压缩表,值得了解...
前面几周我们一起看了Redis底层数据结构,如动态字符串SDS,双向链表Adlist,字典Dict,跳跃表,整数集合intset,如果有对Redis常见的类型或底层数据结构不明白的请看上面传送门。
陈琛
2020/07/07
1.1K0
6、Redis数据结构——压缩列表-ziplist
压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么是小整数值,要么是长度比较短的字符串,那么redis就会使用压缩列表来作为列表键的底层实现。
CodingCode
2021/06/05
9360
6、Redis数据结构——压缩列表-ziplist
【Redis】三、Redis整数集合和压缩列表
contents 数组是整数集合的底层实现: 数组中的各个项按值大小有序排列,并且数组中不包含任何重复项;
石臻臻的杂货铺[同名公众号]
2021/07/14
5600
Redis系列(三)底层数据结构之压缩列表
Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?
呼延十
2020/02/13
5550
《Redis设计与实现》读书笔记(六) ——Redis中的压缩列表
《Redis设计与实现》读书笔记(六) ——Redis中的压缩列表 (原创内容,转载请注明来源,谢谢) 一、概述 压缩列表(ziplist)是列表键(list)和哈希键(hash)底层的实现之一。当列表项较少,且每项要么是小的整数值,要么是长度比较短的字符串,则使用ziplist。当哈希的键值对较少,且每个键值对都是小整数或短字符串,也是使用ziplist。 二、压缩列表构成 压缩列表是redis为了节约内存开发的,由一系列特殊编码的连续内存块组成的顺序型数据结构。每个压缩列表有多个节点(entry),节点
用户1327360
2018/03/07
1.2K0
《Redis设计与实现》读书笔记(六)  ——Redis中的压缩列表
Redis中压缩列表的数据结构和储数据的方式
Redis中的压缩列表(ziplist)是一种特殊类型的数据结构,用于在列表和哈希表中存储小型元素。
一凡sir
2023/09/18
9690
Redis中压缩列表的数据结构和储数据的方式
Redis数据结构详解(4)-为了节约内存的数据结构(压缩列表ziplist)
前面几个文章里我们介绍到了字典dict和跳表skiplist,它们都是redis为了追求性能而开发的基本数据结构,里面或多或少都借助了一些辅助的元素;例如字典dict在rehash时会同时存在两个哈希表,又或者跳表skiplist里节点多了层的结构,这些设计都是为了追求性能而牺牲了内存空间。
苏易困
2022/04/06
5800
Redis剖析——Redis列表实现原理之ZipList
列表类型可以存储一组按插入顺序排序的字符串,它非常灵活,支持在两端插入、弹出数据,可以充当栈和队列的角色。
binecy
2021/12/15
9570
Redis剖析——Redis列表实现原理之ZipList
Redis 的底层数据结构(压缩列表)
上一篇我们介绍了 redis 中的整数集合这种数据结构的实现,也谈到了,引入这种数据结构的一个很大的原因就是,在某些仅有少量整数元素的集合场景,通过整数集合既可以达到字典的效率,也能使用远少于字典的内存达到同样的效果。
Single
2019/11/14
5800
Redis数据结构为什么既省内存又高效?
「Redis所有的数据结构都是在内存占用和执行效率之间找一个比较好的均衡点,不一味的节省内存,也不一味的提高执行效率」
Java识堂
2022/04/06
6470
Redis数据结构为什么既省内存又高效?
redis 6源码解析之 ziplist
ziplist中的每个entry都使用一个元数据作为前缀,该元数据包含两部分的信息:首先保存了前一个entry的长度,用于倒序查找;再者保存了entry的编码类型,表示entry的类型,如整数或字符串,当编码类型为字符串时,该字段也表示了字符串的长度。字符串的entry-data的长度就等同于该字符串的长度,而整数的entry-data的长度需要根据编码类型进行判断,并不一定等同于其entry-data字符串的长度(见下文encoding)。一个完整的entry为:
charlieroro
2020/05/08
4680
快速整透Redis中的压缩列表到底是个啥
压缩列表(ziplist)是由一个连续内存组成的顺序型数据结构。一个压缩列表可以包含任意多个节点,每个节点上可以保存一个字节数组或整数值。它是Redis为了节省内存空间而开发的。
万猫学社
2022/04/22
3890
redis源码 -ziplist
拷贝了一张图【http://blog.csdn.net/u012658346/article/details/51321337】,整个结构分为三部分;
全栈程序员站长
2022/07/25
2910
redis源码 -ziplist
redis6.0 源码学习(五)ziplist
ziplist是经过特殊编码的双向链接列表,该列表具有很高的内存效率。 它存储字符串和整数值,其中整数被编码为实际整数,而不是一系列个字符。 它允许对列表的两侧进行push和pop操作且复杂度为O(1)。 但是由于每个操作都需要重新分配ziplist使用的内存,实际复杂度与ziplist使用的内存量有关。
全栈程序员站长
2022/07/30
6280
redis6.0 源码学习(五)ziplist
推荐阅读
相关推荐
Redis 内存压缩原理
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档