Redis数据结构-QuickList

在《Reids数据结构》这篇文章中，我们说到了Redis的List数据类型底层的数据结构是使用的quicklist，本文简单说下quicklist。

Redis在版本7.0的时候已经将quicklist的节点从ziplist换成了listpack，关于ziplist以及listpack可以看看这篇文章：《Redis数据结构-ZipList与ListPack》。本文主要以quicklist的节点是ziplist来说明。

首先quicklist是一个双向链表结构，像是ziplist以及linkedlist的集合体，每个节点就是一个个ziplist，然后每个节点使用双向指针连接起来。

QuickList结构

结构设计

在源码quicklist.h第105行可以看到quicklist的结构是这样定义的：

/* quicklist是一个 40字节的结构体（在 64 位系统上），用于描述 quicklist。
 * 'count' 是所有节点中的总entry数。
 * 'len' 是quicklist节点的数目。
 * 'compress' 是一个数字，表示不压缩的 quicklist 节点数（如果压缩功能被禁用，则为 0）。
 * 'fill' 是用户请求（或默认）的填充因子。
 * 'bookmarks' 是一个可选特性，用于重新分配此结构体时使用，以避免不使用时占用内存。*/
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* 所有 ziplist 中的entry数 */
    unsigned long len;          /* quicklistNode 的数量 */
    int fill : QL_FILL_BITS;              /* 每个节点的填充因子 */
    unsigned int compress : QL_COMP_BITS; /* 深度不压缩的末尾节点；0=禁用 */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;
  • *head：表示指向头节点的指针。
  • *tail：表示指向尾节点的指针。
  • count： 所有ziplist中的entry数量总和。
  • len：quicklist中quicklistNode的个数。
  • fill：每个节点的填充因子，存放list-max-ziplist-size配置项的值。
  • compress： 每个节点的压缩深度设置，存放list-compress-depth配置项的值。
  • bookmarks：是一个可选特性，用于重新分配此结构体时使用，以避免不使用时占用内存。

quicklistNode的结构

quicklistNode的结构同样在源码quicklist.h中：

/* 我们使用bit filed（位域）将quicklistNode限制在32字节。
 * count：16 位，最大值为 65536（max zl bytes 为 65k，因此实际最大值 < 32k）。
 * encoding：2 位，RAW=1、LZF=2。
 * container：2 位，NONE=1、ZIPLIST=2。
 * recompress：1 位，bool，如果节点临时解压缩以供使用，则为 true。
 * attempted_compress：1 位，boolean，用于测试时验证。
 * extra：10 位，用于未来的自由使用；填充剩余的 32 位 */
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    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; /* 是否对节点进行了临时解压缩 */
    unsigned int attempted_compress : 1; /* 节点无法压缩；太小 */
    unsigned int extra : 10; /* 更多位用于未来使用 */
} quicklistNode

  • *prev：表示指向前一个节点的指针。

  • *next：表示指向后一个节点的指针。

  • *zl：数据指针。如果当前节点的数据没有压缩，那么它指向一个ziplist结构；否则，它指向一个quicklistLZF结构。

  • sz：表示*zl指向的ziplist大小（包括zlbytes, zltail, zllen, zlend和各个数据项），单位是字节，。

    注意：如果ziplist被压缩了，sz的值依然还是压缩之前的ziplist的大小。

  • count：表示ziplist中entry节点数量。只有16bit。

  • encoding：表示ziplist是否被压缩以及使用的什么压缩算法，1代表没有压缩，2代表使用的LZF压缩算法压缩的。

  • container：预留字段，原本是用来表示quicklist节点是直接存数据还是使用ziplist（或者其他数据结构），但是Redis6.0的实现里，这个值固定为2。

  • recompress：表示是否对节点进行了临时解压缩，比如当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这个时候就设置recompress=1做一个标记，等有机会再把数据重新压缩。

上面说到*zl还可能指向一个quicklistLZF结构，这个结构的源码在quicklist.h第64行：

/* quicklistLZF 是一个 4+N 字节的结构体，其中包含了 'sz' 和 'compressed' 两个字段。
 * 'sz' 表示 'compressed' 字段的字节长度。
 * 'compressed' 是一个 LZF 压缩过的数据，它的总长度为 'sz' 字节。
 * 注意：quicklistNode->zl 压缩后的长度存储在 quicklistLZF->sz 中。
 * 当 quicklistNode->zl 被压缩时，node->zl 指向 quicklistLZF */
typedef struct quicklistLZF {
    unsigned int sz; /* LZF 大小，以字节为单位 */
    char compressed[];
} quicklistLZF;
  • sz：表示compressed字段的字节长度。
  • compressed：是一个LZF压缩过的数据，它的总长度为sz个字节。