Redis列表[4]数据结构之quicklist

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

然而，由于链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。在redis3.2版本之后，对列表的数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist.

2，数据结构

quicklist 是 ziplist 和 linkedlist 的混合体。它仍然是一个双向链表，它将 linkedlist 按段切分，每一段成为一个quicklist节点，每个quicklist节点，都使用 ziplist 来紧凑存储，多个quicklist节点之间使用双向指针串接起来。

quicklist.c 和 quicklist.h 文件中分别是这样定义的

A doubly linked list of ziplists
//一个双向连接的由ziplist构成的列表

A generic doubly linked quicklist implementation

2.2.1 整体

 * quicklist is a 32 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: -1 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. 
 *
typedef struct quicklist {
    quicklistNode *head; //指向quicklist的头部
    quicklistNode *tail; //指向quicklist的尾部
    unsigned long count; //列表中所有数据项的个数总和
    unsigned int len;    //quicklist节点的个数，即ziplist的个数
    int fill : 16;       //ziplist数据项个数限制，由list-max-ziplist-size给定
    unsigned int compress : 16; //节点压缩深度设置，由list-compress-depth给定 0表示不压缩
} quicklist;

可以看到，这边其实有两个统计值，count用来统计所有数据项的个数总和，len用来统计quicklist的节点个数， 因为每个节点ziplist都能存储多个数据项，所以有了这两个统计值。

另外，quicklist的这个结构体在源码中说是占用了32byte的空间，怎么计算的呢？这边涉及到了位域的概念，所谓”位域“是把一个字节中的二进位划分为几个不同的区域，并说明每个区域的位数。每个域有一个域名，允许在程序中按域名进行操作。比如这个 "int fill : 16" 表示不用整个int存储fill，而是只用了其中的16位来存储。

2.2.1.1 fill

这个参数它可以是正值，也可以是负值。当是正值的时候，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成3的时候，表示每个quicklist节点的ziplist最多包含3个数据项。当取负值的时候，表示按照占用字节数来限定每个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大小不能超过4KB。

产生原因：

  • 每个quicklist节点上的ziplist越短，则内存碎片越多。内存碎片多了，有可能在内存中产生很多无法被利用的小碎片，从而降低存储效率。这种情况的极端是每个quicklist节点上的ziplist只包含一个数据项，这就蜕化成一个普通的双向链表了。

  • 每个quicklist节点上的ziplist越长，则为ziplist分配大块连续内存空间的难度就越大。有可能出现内存里有很多小块的空闲空间（它们加起来很多），但却找不到一块足够大的空闲空间分配给ziplist的情况。这同样会降低存储效率。这种情况的极端是整个quicklist只有一个节点，所有的数据项都分配在这仅有的一个节点的ziplist里面。这其实蜕化成一个ziplist了。

可见，一个quicklist节点上的ziplist要保持一个合理的长度。那到底多长合理呢？Redis提供了配置参数list-max-ziplist-size，就是为了让使用者可以来根据实际应用场景进行调整优化。

2.2.1.2 list-compress-depth

表示列表两头不压缩的节点的个数

  • 0 特殊值，表示不压缩

  • 1 表示quicklist两端各有一个节点不压缩，中间的节点压缩

  • 2 表示quicklist两端各有两个节点不压缩，中间的节点压缩

  • 3 表示quicklist两端各有三个节点不压缩，中间的节点压缩

产生原因：当表list存储大量数据的时候，最容易被访问的很可能是两端的数据，中间的数据被访问的频率比较低（访问起来性能也很低）。如果应用场景符合这个特点，那么list还提供了一个选项，能够把中间的数据节点进行压缩，从而进一步节省内存空间。Redis的配置参数list-compress-depth就是用来完成这个设置的。

2.2.2 节点

每个链表节点使用一个adlist.h/listNode结构来表示

 * quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 12 bits, free for future use; pads out the remainder of 32 bits
typedef struct quicklistNode {
    struct quicklistNode *prev; //指向上一个ziplist节点
    struct quicklistNode *next; //指向下一个ziplist节点
    unsigned char *zl; //数据指针，如果没有被压缩，就指向ziplist结构，反之指向quicklistLZF结构
    unsigned int sz; //表示指向ziplist结构的总长度(内存占用长度)
    unsigned int count : 16; //表示ziplist中的数据项个数
    unsigned int encoding : 2; //编码方式 RAW 1, LZF 2
    unsigned int container : 2;  //存放数据的方式 NONE 1, ZIPLIST 2
    unsigned int recompress : 1; // 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为1，之后再重新进行压缩
    unsigned int attempted_compress : 1; //测试相关，是否尝试压缩过
    unsigned int extra : 10; //扩展字段，留待使用
} quicklistNode;

图上显示了两种ziplist的结构，一种是经过压缩的，一种是未经压缩的。

2.2.3 quicklistLZF

 * 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 {
    unsigned int sz; // LZF压缩后占用的字节数
    char compressed[]; // 柔性数组，存放压缩后的ziplist字节数组
} quicklistLZF;

 

3， 总结

quicklist将双向链表和ziplist两者的优点结合起来，在时间和空间上做了一个均衡，能较大程度上提高Redis的效率。push和pop等操作操作的时间复杂度也都达到了最优。

 

参考文章：

https://blog.csdn.net/u012748735/java/article/details/82792478
https://blog.csdn.net/harleylau/java/article/details/80534159

以上是 Redis列表[4]数据结构之quicklist 的全部内容， 来源链接： utcz.com/z/516617.html

回到顶部