Redis底层数据结构之quicklist

2024-04-22 13:20

本文主要是介绍Redis底层数据结构之quicklist,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

    • 一、概述
    • 二、quicklist结构
    • 三、quicklistNode结构
    • 四、优缺点

上一篇 redis底层数据结构之ziplist

一、概述

QuickList是由多个 ziplist 组成的双向链表,每个 ziplist 存储一定数量的元素。优点:结合了 ziplist 和双向链表的优点,既节省空间,又提升了修改操作的性能。使用场景: 在列表键元素较多或包含较大元素时使用。

在这里插入图片描述

ziplist补充(ziplist缺点-链式扩容&级联更新)
当一个entry被插入的时候,我们需要设置下一个entry中的prevlen字段为新插入entry的长度。会发生如下的情况:新插入entry的长度超过了254[>=254],那么下一个entry的prelen需要5个字节记录该长度,但是呢,此时下一个entry的prevlen字段此时只有一个字节,所以需要对下一个entry进行grown[扩容],更糟糕的是,下个entry因为扩容导致长度超过254,还会引起下下个entry的扩容…,这种现象呢就是级联更新,简单点来说就是,因为一个entry的插入导致之后的entry都需要重新扩容和记录前一个entry的prevlen现象称之为“级联更新”

从 Redis 6.2 版本开始,quicklist 的底层实现由原来的 ziplist 改为了 listpack。Listpack 是 ziplist 的升级版本,主要是为了解决ziplist中存在的一些问题,比如,ziplist中扩展元素长度时可能需要进行昂贵的重新分配操作。listpack 提供了更好的性能和内存使用效率,在保持与 ziplist 类似的密集存储方式的同时,允许更大的单个元素大小,并且有更强的扩展性。listpack和ziplist对象结构的不同是,listpack将prevlen替换为了curlen,从而有效避免级联更新。并将且将culen字段放在entry结构的最后面。这样做是为了,能够通过total-bytes定位到最后一个element的末尾位置然后获取到curlen从而找到前一个element的位置,从而实现从后往前遍历。

补充说明listpack和ziplist
参考博客 ziplist和listpack

  • ziplist包括三大部分,<头部,entry,尾部>。头部包含"zlbytes,zltail,zllen";尾部包含"zlend标记ziplist的结尾";entry包括"prevlen,encoding,entry_data"。由于prevlen记录方式存在级联更新的问题,小于254字节需要1字节内存,大于等于254字节需要5字节内存。
  • listpack包括三大部分,<头部,entry,尾部>。头部包含"zlbytes,zllen"相比与ziplist少了zltail;entry包括"encoding,entry_data,curlen";尾部包含"zlend标记listpack的结尾"。由于entry中的prevlen由curlen取代,所以不再有级联更新的问题。
  • 不论是"ziplist"还是"listpack"获取len的方式都是一样的:
    先判断头部中zllen字段存储的数值与UNIT16_MAX的关系
    小于UNIT16_MAX,直接返回zllen
    大于等于UNIT16_MAX需要从头到尾遍历获取元素总数
    如果新得到的元素总数小于UINT16_MAX,重新设置zllen的数值

二、quicklist结构

(直达源码–>src/quicklist.h)

基于listpack(V6.2)

/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
* 'count' is the number of total entries.
* 'len' is the number of quicklist nodes.
* 'compress' is: 0 if compression disabled, otherwise it's the number
*                of quicklistNodes to leave uncompressed at ends of quicklist.
* 'fill' is the user-requested (or default) fill factor.
* 'bookmarks are an optional feature that is used by realloc this struct,
*      so that they don't consume memory when not used. */
typedef struct quicklist {quicklistNode *head;quicklistNode *tail;unsigned long count;        /* total count of all entries in all listpacks */unsigned long len;          /* number of quicklistNodes */signed int fill : QL_FILL_BITS;       /* fill factor for individual nodes */unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */unsigned int bookmark_count: QL_BM_BITS;quicklistBookmark bookmarks[];
} quicklist;

基于ziplist

typedef struct quicklist {// quicklist头结点quicklistNode *head;// quicklist 尾节点quicklistNode *tail;// 所有的ziplist中的entry总数量unsigned long count; /* total count of all entries in all ziplists */// ziplist节点数量unsigned long len;   /* number of quicklistNodes */// ziplist中entry的上限,默认为-2,和redis中配置的 list-max-ziplist-size 一致int fill : QL_FILL_BITS;  /* fill factor for individual nodes */// 首尾节点不压缩的个数,若设置为1,则首尾节点各有一节点不压缩;设置为0,则代表所有节点不压缩unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */// 内存重分配时的书签数量及数组,一般用不到unsigned int bookmark_count: QL_BM_BITS;quicklistBookmark bookmarks[];
} quicklist;

三、quicklistNode结构

基于listpack(V6.2)

/* quicklistNode is a 32 byte struct describing a listpack for a quicklist.
* We use bit fields keep the quicklistNode at 32 bytes.
* count: 16 bits, max 65536 (max lp bytes is 65k, so max count actually < 32k).
* encoding: 2 bits, RAW=1, LZF=2.
* container: 2 bits, PLAIN=1 (a single item as char array), PACKED=2 (listpack with multiple items).
* recompress: 1 bit, bool, true if node is temporary decompressed for usage.
* attempted_compress: 1 bit, boolean, used for verifying during testing.
* dont_compress: 1 bit, boolean, used for preventing compression of entry.
* extra: 9 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {struct quicklistNode *prev;struct quicklistNode *next;unsigned char *entry;size_t sz;             /* entry size in bytes */unsigned int count : 16;     /* count of items in listpack */unsigned int encoding : 2;   /* RAW==1 or LZF==2 */unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */unsigned int recompress : 1; /* was this node previous compressed? */unsigned int attempted_compress : 1; /* node can't compress; too small */unsigned int dont_compress : 1; /* prevent compression of entry that will be used later */unsigned int extra : 9; /* more bits to steal for future usage */
} quicklistNode;

基于ziplist

typedef struct quicklistNode {// 前一个节点(ziplist)指针struct quicklistNode *prev;// 后一个节点(ziplist)指针struct quicklistNode *next;// 当前节点ziplist指针unsigned char *zl;// 当前节点ziplist的字节大小,即zlbytesunsigned int sz;             /* ziplist size in bytes */// 当前节点ziplist中entry的数量unsigned int count : 16;     /* count of items in ziplist */// 编码方式:1-ziplist; 2-lzf压缩模式unsigned int encoding : 2;   /* RAW==1 or LZF==2 */// 数据容器类型:1-其他(预留扩展类型);2-ziplistunsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */// 是否被压缩:1-说明被解压,将来要重新压缩。unsigned int recompress : 1; /* was this node previous compressed? */// 测试字段unsigned int attempted_compress : 1; /* node can't compress; too small */// 预留字段unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

四、优缺点

优点:

  • 快表的节点大小固定,可以有效地避免内存碎片的发生。
  • 快表支持动态增加和删除节点,可以随着数据的增长而自动扩容或缩容,不需要预先分配空间。
  • 快表的节点采用ziplist的紧凑存储方式,使得节点访问和遍历的效率较高。同时,快表支持从头和尾部两个方向同时遍历节点。

缺点:

  • 快表的节点大小固定,如果节点中的元素数量较少,会造成一定的空间浪费。
  • 快表中的元素只能是整数或字节数组,不支持其他数据类型的存储。
  • 快表的插入和删除操作的效率较低,因为在插入或删除元素时,需要移动后面的元素,可能会导致大量的内存复制操作。如果需要频繁进行插入和删除操作,建议使用其他数据结构,例如链表。
  • 当快表中的元素数量较大时,遍历整个快表的效率也可能较低,因为快表是由多个节点组成的链表,需要依次遍历每个节点才能访问所有元素。

这篇关于Redis底层数据结构之quicklist的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/925891

相关文章

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringBoot中配置Redis连接池的完整指南

《SpringBoot中配置Redis连接池的完整指南》这篇文章主要为大家详细介绍了SpringBoot中配置Redis连接池的完整指南,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以... 目录一、添加依赖二、配置 Redis 连接池三、测试 Redis 操作四、完整示例代码(一)pom.

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程

Redis在windows环境下如何启动

《Redis在windows环境下如何启动》:本文主要介绍Redis在windows环境下如何启动的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Redis在Windows环境下启动1.在redis的安装目录下2.输入·redis-server.exe

Redis实现延迟任务的三种方法详解

《Redis实现延迟任务的三种方法详解》延迟任务(DelayedTask)是指在未来的某个时间点,执行相应的任务,本文为大家整理了三种常见的实现方法,感兴趣的小伙伴可以参考一下... 目录1.前言2.Redis如何实现延迟任务3.代码实现3.1. 过期键通知事件实现3.2. 使用ZSet实现延迟任务3.3

Redis分片集群的实现

《Redis分片集群的实现》Redis分片集群是一种将Redis数据库分散到多个节点上的方式,以提供更高的性能和可伸缩性,本文主要介绍了Redis分片集群的实现,具有一定的参考价值,感兴趣的可以了解一... 目录1. Redis Cluster的核心概念哈希槽(Hash Slots)主从复制与故障转移2.

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Redis 中的热点键和数据倾斜示例详解

《Redis中的热点键和数据倾斜示例详解》热点键是指在Redis中被频繁访问的特定键,这些键由于其高访问频率,可能导致Redis服务器的性能问题,尤其是在高并发场景下,本文给大家介绍Redis中的热... 目录Redis 中的热点键和数据倾斜热点键(Hot Key)定义特点应对策略示例数据倾斜(Data S