本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!