风澜

V1

2022/06/23阅读:15主题:灵动蓝

【Redis进阶之ZipList】如果再有人问你什么是压缩列表?请把这篇文章直接甩给他。

我们在工作、学习中接触Redis时,基本都听说过压缩列表这个数据结构,但是具体它是做什么的?它是如何实现的?并没有多少人深入的了解过,但是...面试官可能会问。

以下内容均基于Redis6.0

一、 什么是ZipList

Redis对内存的使用极其苛刻,当你阅读Redis源码的时候,你就会发现,当我们用同一个数据结构存储数据时,数据量小时可能会是一个内存很紧凑的数据结构,正是因为内存紧凑,所以我们在插入数据时,往往需要重新申请内存,然后将元数据移动到新内存中再进行插入,当数据量大时,这个结构因复制原有数据带来的开销就远远大于其内存上的优势了。

ZipList就是当【zset】和【hash】容器对象在元素个数较少或元素长度较短时采用的数据结构。它是一块连续的内存空间,每一个元素都前后挨着,中间没有内存空隙。同时它也是一个经过特殊编码的双向链表,它的设计目标就是为了提高内存存储效率,

ziplist可以用于存储字符串或整数,其中整数是按真正的二进制表示进行编码的,而不是编码成字符串序列。它能以O(1)的时间复杂度在表的两端提供push和pop操作

Redis使用ZipList的默认条件

  • 键值对数量少于128个
  • 所有键值对中每个元素值的长度【小于或等于】64字节

这里我们只对第二个条件【所有键值对中每个元素值的长度小于或等于64字节】做个演示,键值对数量少于128个可以自己试一试。下图所示,当字节数key为fenglan的这个zset结构插入的value超过64字节时,zset的数据结构就会升级为跳跃表SkipList。

升级为SkipList
升级为SkipList

二、ZipList数据结构

ZipList数据结构
ZipList数据结构

uint32_t表示一个int类型,占32位,也就是4字节。 uint16_t占16位,只用到了int的低16位,2字节。这样定义比较节省内存空间。

上图就是ZipList的整体数据结构

  • zlbytes:ZipList整体占勇的字节数
  • zltail:最后一个元素的偏移量,用于快速定位到最后一个节点
  • zllen:一共有多少个元素,也就是元素的长度。
  • zlend:ZipList结束标志位,值恒为255

其中zltail这个字段就是为了实现双链表结构才使用的,它可以快速定位最后一个元素,从最后一个元素往前遍历。

Redis创建ZipList的源码如下,我们从源码里能看到,Redis申请了1个uint32_t、1个uint16_t、1个uint8_t的内存空间,正符合我们上面图中除了entry外的其他数据所需的所有内存空间。

创建ZipList
创建ZipList

接下来我们一起看看具体的数据存储结构 【entry】

typedef struct zlentry {
    unsigned int prevrawlensize; /* 前一个entry的prevrawlen字段(也就是下面那个字段)的大小*/
    unsigned int prevrawlen;     /* 前一个entry的字节长度 */
    unsigned int lensize;        /* 当前entry的len字段大小*/
    unsigned int len;            /* 当前entrty的字节长度 */
    unsigned int headersize;     /* prevrawlensize + lensize的大小*/
    unsigned char encoding;      /* 元素类型编码*/
    unsigned char *p;            /* 指向具体数据内容首地址的指针*/
} zlentry;

为什么要ZipList要记录前一个entry的长度?答案是因为当ZipList倒着遍历的时候,通过这个字段可以快速定位到下一个元素的位置。

其中prevrawlen是一个变长的int类型数据,当字符串长度小于254时,使用一个字节表示,大于或等于254时 使用5个字节来表示,第一个地接是254,剩余四个字节表示字符串的长度。

三、更新元素

1. 新增元素

因为ZipList是内存紧凑的,所以新插入一个元素就需要扩展内存,Redis会调用ziplistResize方法重新申请内存空间,然后将原先的列表一次性放入新的内存空间中。

2.级联更新

entry中有保存了前一个元素的长度(prevrawlen),它是一个变长的整数,所以如果当前元素的前一个元素发生变化(例如删除),那么,当前元素的prevrawlen字段也会发生改变。当前元素的prevrawlen发生改变,那当前元素下一个元素的prevrawlen也会发生变化,这就触发了大规模的级联更新,当元素很多时,甚至会影响到Redis是否能正常对外提供服务。所以ziplist不适合存放的元素过多。

四、总结

  • Redis 为了节约内存空间才使用的ZipList,zset 和 hash 容器对象在系统默认键值对数量少于512个或所有键值对中每个元素值的长度【小于或等于】64字节,采用压缩列表 (ziplist) 进行存储,否则会升级为SkipList。
  • ZipList是一个双向链表。
  • 压缩列表是一块连续的内存空间,每一个元素都前后挨着,中间没有内存空隙
  • ziplist可以用于存储字符串或整数,其中整数是按真正的二进制表示进行编码的,而不是编码成字符串序列。它能以O(1)的时间复杂度在表的两端提供push和pop操作
  • ZipList的Entry中记录前一个元素的长度是为了双向链表可以倒着遍历。
  • 因为内存非常紧凑,所以新增元素时需要重新申请内存。
  • 可能在元素变更时,会发生级联更新。

原创不易,给个三连吧!!

微信搜一搜:云下风澜 学习、面试资料、深度内容、源码阅读、性能优化、行业秘闻、职业规划应有尽有。

分类:

后端

标签:

后端

作者介绍

风澜
V1