5分钟了解Redis的内部实现快速列表（quicklist）

桃扇骨 2023-09-30 10:33 24阅读 0赞

#### 快速列表简介 ####

在Redis3 .2版本之前，存储列表（list）数据结构使用的是压缩列表（ziplist）和链表（linkedlist），当列表元素个数比较少并且每个元素占用空间比较小的时候，使用压缩列表。当列表元素个数比较多或者某个元素占用空间比较大的时候，使用链表。

考虑到链表的附加空间相对太高，结点的内存也是单独分配的，影响内存管理效率。在Redis3 .2版本开始对列表数据结构进行了改造，使用快速列表（quicklist）代替了压缩列表（ziplist）和链表（linkedlist）。

快速列表（quicklist）是以压缩列表（ziplist）为节点的链表（linkedlist），将链表按段切分，每一段使用压缩列表进行内存的连续存储，多个压缩列表通过prev和next指针组成的双向链表。它结合了压缩列表和链表的优势，进一步压缩了内存的使用量，进一步提高了效率。

下面我们了解一下快速列表的具体实现。

#### 快速列表的实现 ####

在Redis中的快速列表是由`quicklist`结构表示的，`quicklist`结构包含由多个快速列表结点组成的双向链表，每一个快速列表结点都保存了一个压缩列表。下面我们一个一个地详细了解一下。

#### quicklist结构 ####

快速列表是由`quicklist`结构表示的，它包含以下几个属性：

*  `head`属性: 指向头部快速列表结点的指针。
 *  `tail`属性：指向尾部快速列表结点的指针。
 *  `count`属性：在所有压缩列表中元素的个数总和。
 *  `len`属性：快速列表结点的个数。
 *  `fill`属性：压缩列表的最大大小，存放`list-max-ziplist-size`参数的值。当超出了这个配置，就会新建一个压缩列表。
 *  `compress`属性：结点压缩深度，存放`list-compress-depth`参数的值。
 *  `bookmarks`属性：用来快速列表重新分配内存空间时使用的数组，不使用时不占用空间。
 *  `bookmark_count`属性：bookmarks数组的大小。

#### 快速列表结点 ####

快速列表结点使用`quicklistNode`结构表示，它包含以下几个属性：

*  `prev`属性：指向前一个快速列表结点的指针。
 *  `next`属性：指向后一个快速列表结点的指针。
 *  `zl`属性：指向压缩列表的指针，如果当前结点的数据被压缩，那么它指向一个`quicklistLZF`结构。
 *  `sz`属性：压缩列表的所占字节总数。
 *  `count`属性：压缩列表中的元素数量。
 *  `encoding`属性：存储形式，原生字节数组还是LZF压缩存储。
 *  `recompress`属性：当查看了某一项被压缩的数据时，需要把数据暂时解压，这时就设置 recompress = 1 做一个标记，等有机会再把数据重新压缩。

#### quicklistLZF结构 ####

当快速列表结点数据被压缩时，数据会被存放在quicklistLZF结构中，它包含以下几个属性：

*  `sz`属性：表示压缩后的大小。
 *  `compressed`属性：存放压缩后的字节数组。

#### 快速列表的压缩机制 ####

在快速列表中，两端结点的数据被访问的可能性比较高，中间结点的数据被访问的可能性比较低。如果我们的应用场景符合这个特点，可以把中间结点的数据使用 LZF 算法进行压缩，从而进一步节省内存空间。我们可以对`list-compress-depth`参数进行配置。

默认情况下，`list-compress-depth`参数为0，也就是不压缩数据；当该参数被设置为1时，除了头部和尾部之外的结点都会被压缩；当该参数被设置为2时，除了头部、头部的下一个、尾部、尾部的上一个之外的结点都会被压缩；当该参数被设置为2时，除了头部、头部的下一个、头部的下一个的下一个、尾部、尾部的上一个、尾部的上一个的上一个之外的结点都会被压缩；以此类推。

> 最后，谢谢你这么帅，还给我**点赞**和**关注**。