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

快速列表简介

在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时,除了头部、头部的下一个、头部的下一个的下一个、尾部、尾部的上一个、尾部的上一个的上一个之外的结点都会被压缩;以此类推。

最后,谢谢你这么帅,还给我点赞关注

微信公众号:万猫学社

微信扫描二维码

关注后回复「电子书」

获取12本Java必读技术书籍