Redis 数据结构 quicklist 蔚落 2023-10-03 11:21 2阅读 0赞 ## 回顾 ## 在上篇博客 [Redis 数据结构 intset][Redis _ intset] 中，了解了 Redis 的 intset（整数集合），今天再来了解下 Redis 的 quicklist（快速链表）。 ## Version 3.2 ## > 以版本为 3.2 的 Redis 分析，此前版本的 Redis 无此结构。 源码地址：[redis/quicklist.h][redis_quicklist.h] 与 [redis/quicklist.c][redis_quicklist.c]。 ### 概述 ### 在 [redis/quicklist.c][redis_quicklist.c] 中说到了 `A doubly linked list of ziplists`， 翻译过来就是「quicklist 是 ziplist 的双向链表」（[Redis 数据结构 ziplist][Redis _ ziplist]）。 ### 结构 ### 对应源码地址：[redis/quicklist.h][redis_quicklist.h] 。 #### quicklist #### > quicklist 主结构 typedef struct quicklist { // 头结点 quicklistNode *head; // 尾结点 quicklistNode *tail; // 所有 ziplist 的结点数（可以理解为数据项） unsigned long count; /* total count of all entries in all ziplists */ // quicklist 结点的个数 unsigned int len; /* number of quicklistNodes */ // 单个 ziplist 的大小设置，存放 「list-max-ziplist-size」的值，16bit int fill : 16; /* fill factor for individual nodes */ // 结点压缩程度的值，0 为不压缩，存放「list-compress-depth」的值，16bit unsigned int compress : 16; /* depth of end nodes not to compress;0=off */ } quicklist; #### quicklistNode #### > quicklist 结构中的结点 typedef struct quicklistNode { // 指向前一个结点的指针 struct quicklistNode *prev; // 指向后一个结点的指针 struct quicklistNode *next; // 指向 ziplist 的指针 unsigned char *zl; // 被指向的 ziplist 的总大小 unsigned int sz; /* ziplist size in bytes */ // ziplist 中包含的数据项个数 unsigned int count : 16; /* count of items in ziplist */ // 表示 ziplist 是否被压缩：2->使用 LZF 算法压缩、1 原生未被压缩 unsigned int encoding : 2; /* RAW==1 or LZF==2 */ // 预留字段，存放数据的方式，1--NONE，2--ziplist unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */ // 当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=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; #### quicklistLZF #### > 此结构表示一个被压缩过的 ziplist /* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'. * 'sz' is byte length of 'compressed' field. * 'compressed' is LZF data with total (compressed) length 'sz' * NOTE: uncompressed length is stored in quicklistNode->sz. * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */ typedef struct quicklistLZF { // 被压缩后的 ziplist 大小 unsigned int sz; /* LZF size in bytes*/ // 存放被压缩后的 ziplist 字节数组 char compressed[]; } quicklistLZF; #### 整理 #### 通过上面三段代码的解释，大概知道了 quicklist 的结构，大概就是下图所示： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70] #### 备注 #### > 参考：[从ziplist到quicklist，再到listpack的启发][ziplist_quicklist_listpack] quicklist 并没有解决 ziplist 中的「连锁更新」问题，只是减少了在 [压缩链表 ziplist][Redis _ ziplist] 中新增或修改元素发生连锁更新的情况。 **过程如下：** 当插入一个新的元素时，quicklist 首先就会检查插入位置的 ziplist 是否能容纳该元素，这是通过 `_quicklistNodeAllowInsert` 函数来完成判断的。 `_quicklistNodeAllowInsert` 函数会计算新插入元素后的大小（new\_sz），这个大小等于 quicklistNode 的当前大小（node->sz）、插入元素的大小（sz），以及插入元素后 ziplist 的 prevlen 占用大小。 计算完大小之后，`_quicklistNodeAllowInsert` 函数会依次判断新插入的数据大小（sz）是否满足要求，即单个 ziplist 是否不超过 8KB，或是单个 ziplist 里的元素个数是否满足要求。 只要这里面的一个条件能满足，quicklist 就可以在当前的 quicklistNode 中插入新元素，否则 quicklist 就会新建一个 quicklistNode，以此来保存新插入的元素。 unsigned int new_sz = node->sz + sz + ziplist_overhead; if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz, fill))) return 1; else if (!sizeMeetsSafetyLimit(new_sz)) return 0; else if ((int)node->count < fill) return 1; else return 0; quicklist 通过控制每个 quicklistNode 中，ziplist 的大小或是元素个数，就有效减少了在 ziplist 中新增或修改元素后，发生连锁更新的情况，从而提供了更好的访问性能。 ### 分析 ### 在 Redis 3.2 之前，在选用了 list 的情况下： 1. 元素较少的情况下，比较适合用 `ziplist`，毕竟创建双向链表浪费空间，而且此时元素较少，修改 `ziplist` 中的元素的效率也不会低到哪里去； 2. 元素较多的情况下，比较适合用 `adlist(linkedlist)`，元素较多，修改的效率也不会太低。 有了 `quicklist`，算是在 `ziplist` 和 `adlist(linkedlist)` 之间有了折衷的方案。 还可以通过 list-max-ziplist-size 配置： > * 当取正值的时候，表示按照数据项个数来限定每个 quicklist 节点上的 ziplist 长度。比如，当这个参数配置成5的时候，表示每个 quicklist 节点的 ziplist 最多包含 5 个数据项。 > * 当取负值的时候，表示按照占用字节数来限定每个 quicklist 节点上的 ziplist 长度。这时，它只能取 -1 到 -5 这五个值，每个值含义如下： > \-5: 每个 quicklist 节点上的 ziplist 大小不能超过 64Kb。（注：1kb => 1024 bytes） > \-4: 每个 quicklist 节点上的 ziplist 大小不能超过 32Kb。 > \-3: 每个 quicklist 节点上的 ziplist 大小不能超过 16Kb。 > \-2: 每个 quicklist 节点上的 ziplist 大小不能超过 8Kb。（-2 是 Redis 给出的默认值） > \-1: 每个 quicklist 节点上的 ziplist 大小不能超过 4 Kb。 ## 关联阅读 ## [Redis 基础][Redis] [Redis 数据结构 SDS][Redis _ SDS] [Redis 数据结构 linkedlist][Redis _ linkedlist] [Redis 数据结构 hashtable][Redis _ hashtable] [Redis 数据结构 skiplist][Redis _ skiplist] [Redis 数据结构 ziplist][Redis _ ziplist] [Redis 数据结构 intset][Redis _ intset] [Redis 数据结构 quicklist][Redis _ quicklist] [Redis 对象 RedisObject][Redis _ RedisObject] [Redis _ intset]: https://mindartisan.blog.csdn.net/article/details/118196924 [redis_quicklist.h]: https://github.com/redis/redis/blob/3.2/src/quicklist.h [redis_quicklist.c]: https://github.com/redis/redis/blob/3.2/src/quicklist.c [Redis _ ziplist]: https://mindartisan.blog.csdn.net/article/details/117387561 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/963ea11f974c4f6aac555093858230d1.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4,size_16,color_FFFFFF,t_70 [ziplist_quicklist_listpack]: https://time.geekbang.org/column/article/405387 [Redis]: https://mindartisan.blog.csdn.net/article/details/110290715 [Redis _ SDS]: https://mindartisan.blog.csdn.net/article/details/115283999 [Redis _ linkedlist]: https://mindartisan.blog.csdn.net/article/details/116384345 [Redis _ hashtable]: https://mindartisan.blog.csdn.net/article/details/116562596 [Redis _ skiplist]: https://mindartisan.blog.csdn.net/article/details/117194957 [Redis _ quicklist]: https://mindartisan.blog.csdn.net/article/details/118884060 [Redis _ RedisObject]: https://mindartisan.blog.csdn.net/article/details/119521399
还没有评论，来说两句吧...