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

相关文章

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

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

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

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

redis+lua实现分布式限流的示例

《redis+lua实现分布式限流的示例》本文主要介绍了redis+lua实现分布式限流的示例,可以实现复杂的限流逻辑,如滑动窗口限流,并且避免了多步操作导致的并发问题,具有一定的参考价值,感兴趣的可... 目录为什么使用Redis+Lua实现分布式限流使用ZSET也可以实现限流,为什么选择lua的方式实现

Redis中管道操作pipeline的实现

《Redis中管道操作pipeline的实现》RedisPipeline是一种优化客户端与服务器通信的技术,通过批量发送和接收命令减少网络往返次数,提高命令执行效率,本文就来介绍一下Redis中管道操... 目录什么是pipeline场景一:我要向Redis新增大批量的数据分批处理事务( MULTI/EXE

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

Redis中的常用的五种数据类型详解

《Redis中的常用的五种数据类型详解》:本文主要介绍Redis中的常用的五种数据类型详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Redis常用的五种数据类型一、字符串(String)简介常用命令应用场景二、哈希(Hash)简介常用命令应用场景三、列表(L

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Redis中如何实现商品秒杀

《Redis中如何实现商品秒杀》:本文主要介绍Redis中如何实现商品秒杀问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录技术栈功能实现步骤步骤一:准备商品库存数据步骤二:实现商品秒杀步骤三:优化Redis性能技术讲解Redis的List类型Redis的Set

Redis如何实现刷票过滤

《Redis如何实现刷票过滤》:本文主要介绍Redis如何实现刷票过滤问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录引言一、概述二、技术选型三、搭建开发环境四、使用Redis存储数据四、使用SpringBoot开发应用五、 实现同一IP每天刷票不得超过次数六

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente