Quicklist

定义

Quicklist是Redis中List(列表)数据类型的底层实现结构,自Redis 3.2版本起取代了压缩列表(ziplist)与双端链表(linkedlist)两种旧编码^[1]。它的设计可以概括为把一个长压缩列表拆成若干个短压缩列表,再把这些短压缩列表用双向指针串成链表。

在源码层面,Quicklist由quicklist结构表示,其中head和tail分别指向头节点与尾节点,count记录所有压缩列表中元素的总数,len记录节点个数^[2]。每个节点由quicklistNode结构描述,内部通过zl指针持有一个压缩列表,当该节点被压缩时zl改指向quicklistLZF结构^[3]。

从对外表现看,包含若干节点的Quicklist就是一个按插入位置维持先后顺序的列表,例如3个节点各含4个数据项,对外即呈现为12个数据项的列表^[1]。

原理

Quicklist的节点是一个压缩列表,节点之间以prev和next两个指针相连,构成双向链表。quicklistNode中的sz记录压缩列表占用的字节数,count记录其中的数据项个数,encoding用2表示已被压缩、1表示未压缩,container当前固定为2表示使用压缩列表存放数据,recompress用于标记被临时解压的节点^[3]。

单个节点内压缩列表的长度由list-max-ziplist-size控制。取正值时表示该节点最多容纳的数据项个数,取-5至-1时表示压缩列表的字节上限,分别对应64 KiB、32 KiB、16 KiB、8 KiB和4 KiB,默认值通常为-2,即单个节点约8 KiB。节点过短会加剧内存碎片,节点过长则难以分配大块连续内存,该参数即为两者之间的折中^[1]。

为节省内存,Quicklist支持对处于中间位置的节点使用LZF无损压缩算法压缩,由list-compress-depth配置压缩深度。该参数默认为0即不压缩;设为1时仅两端各1个节点不压缩;设为2时仅两端各2个节点不压缩,依此类推^[2]。两端节点保留不压缩,是为了保证push和pop操作的效率。

压缩后的节点数据存放在quicklistLZF中,sz为压缩后的字节数,compressed是以柔性数组形式保存的压缩结果^[3]。访问被压缩节点时程序会先将其临时解压并把recompress置位,待合适时机重新压缩。

发展历程

Redis 3.2版本之前,List类型存在两种编码:元素数量较少且单个元素占用空间较小时使用压缩列表,元素数量较多或单个元素较大时改用双端链表^[2]。这种切换式的编码方案需要同时维护两套实现。

双端链表每个节点除数据外还要保存prev和next两个指针,在64位系统上约占16字节,且各节点单独分配内存,容易产生内存碎片,内存管理效率不高^[3]。压缩列表虽然把数据放在一块连续内存中、存储密度高,但每次增删都可能引发内存重分配,列表很长时会带来大量数据拷贝^[1]。

针对上述问题,Redis自3.2版本开始改用Quicklist实现列表,该实现基于Redis源码的3.2分支^[1]。此后Quicklist成为列表类型统一的底层结构,相关结构定义在quicklist.h与quicklist.c中。

应用

Quicklist承载Redis的List类型,而List常被用作队列,两端插入与删除命令lpush、rpush、lpop、rpop均为O(1)时间复杂度^[1]。因此需要从两端高效增删的场景,例如消息队列与任务队列,可以直接使用List类型实现。

列表中间位置的访问与插入,如lindex和linsert,需要对列表进行遍历,时间复杂度为O(N)^[1]。按段切分后,节点内部的压缩列表支持紧凑存储,节点之间的指针又保留了链表的插入删除灵活性,这一组合适合元素数量差异较大的通用列表场景。

局限

Quicklist并未消除压缩列表固有的缺陷。节点内仍然是连续内存,对单个节点内元素做插入或删除仍可能触发内存重分配与数据拷贝,只是影响范围被限制在一个节点之内,不会波及整个列表。

节点的长度需要在内存碎片与连续内存分配难度之间取舍:节点内压缩列表过短会产生更多内存碎片,极端情况下每个节点只含一个元素,结构退化为普通双向链表;节点过长则难以找到足够大的连续空闲空间,极端情况下整个列表只有一个节点,结构退化为单个压缩列表^[1]。

启用LZF压缩后,访问中间节点需要先解压,会带来额外的解压开销,因此压缩深度默认关闭,由使用方根据访问分布自行权衡。

中间位置的读写仍需遍历,时间复杂度为O(N),批量或随机访问中间元素不是该结构擅长的操作^[1]。

参见

• Redis —— Quicklist 是该数据库列表类型的底层实现结构。

• 压缩列表 —— Quicklist 的每个节点内部都使用这一结构存放数据。

• 双向链表 —— Quicklist 在节点之间使用双向指针连接。

• LZF —— Quicklist 对中间节点采用的压缩算法。

• 列表 —— Redis 对外暴露、由 Quicklist 承载的数据类型。