likes
comments
collection
share

浅析 Redis 数据结构 List 及其底层编码方式

作者站长头像
站长
· 阅读数 38

list 基本命令和介绍

Redis中的 List 类型与 Java中的 LinkedList类似,可以看做是一个双向链表结构。既可以支持正向检索也可以支持反向检索。特征也与LinkedList类似:

  • 有序
  • 元素可以重复
  • 插入和删除快
  • 查询速度一般

我们可以用 List 存储一个有序数据,例如:朋友圈点赞列表,评论列表等。

List的常见命令有:

  • LPUSH key element ... :向列表左侧插入一个或多个元素
  • LPOP key:移除并返回列表左侧的第一个元素,没有则返回nil
  • RPUSH key element ... :向列表右侧插入一个或多个元素
  • RPOP key:移除并返回列表右侧的第一个元素
  • LRANGE key star end:返回一段角标范围内的所有元素
  • BLPOP和BRPOP:与LPOP和RPOP类似,只不过在没有元素时等待指定时间,而不是直接返回nil

List 的底层编码方式

为了实现可以从首、尾操作列表中的元素,并且保证查询效率和降低内存占用,在 3.2 版本之前,Redis 采用 ZipList 和 LinkedList 来实现 List,当元素数量小于 512 并且元素大小小于 64 字节时采用 ZipList 编码,超过则采用 LinkedList 编码。在 3.2 版本之后,Redis统一采用 QuickList 来实现 List。

下面我们来看看 ZipList 和 QuickList 的结构分别是怎样的。

ZipList

ZipList 的结构

ZipList 是一种特殊的“双端链表” ,由一系列特殊编码的连续内存块组成(类似于链表) 。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。其结构如下图所示,

浅析 Redis 数据结构 List 及其底层编码方式

各个成员变量如下:

  • zlbytes,记录整个压缩列表占用内存字节数;
  • zltail,记录压缩列表「尾部」节点距离起始地址有多少字节,也就是列表尾的偏移量
  • zllen,记录压缩列表包含的节点数量
  • entry , 压缩列表包含的各个节点,节点的长度由节点保存的内容决定
  • zlend,标记压缩列表的结束点,固定值 0xFF(十进制255)。

在压缩列表中,如果我们要查找定位第一个元素和最后一个元素,可以通过 zltail 直接定位,复杂度是 O(1)。而查找其他元素时,就没有这么高效了,只能逐个查找,此时的复杂度就是 O(N) 了,因此压缩列表不适合保存过多的元素

ZipListEntry

  • ZipList 中的 Entry 并不像普通链表那样记录前后节点的指针,因为记录两个指针要占用16个字节,浪费内存。而是采用下面的结构

浅析 Redis 数据结构 List 及其底层编码方式

  • previous_entry_length:前一节点的长度,占1个或5个字节。

    • 如果前一节点的长度小于 254 字节,则采用1个字节来保存这个长度值
    • 如果前一节点的长度大于 254 字节,则采用5个字节来保存这个长度值,第一个字节为 0xf,后四个字节才是真实长度数据
  • encoding:编码属性,记录 content数据类型(字符串还是整数)以及长度,占用1个、2个或5个字节,详见下一个 part -- Encoding 编码

  • contents:负责保存节点的数据,可以是字符串或整数

Encoding 编码

  • ZipListEntry 中的 encoding 编码分为字符串和整数两种

字符串

  • 如果encoding:是以“00”、“"01”或者“10”开头,则证明 content 是字符串,根据字符串的长度大小,encoding 会使用 1 字节/2字节/5字节的空间进行编码,encoding 编码的前两个 bit 表示数据的类型,后续的其他 bit 标识字符串数据的实际长度,即 data 的长度。
编码编码长度字符串大小
00pppppp
01ppppppqqqqqqqq
10000000qqqqqqqq

例如,我们要保存字符串:“ab”和 “bc”

浅析 Redis 数据结构 List 及其底层编码方式

整数

  • 如果 encoding 是以“11”开始,则证明 content 是整数,且 encoding 固定只占用1个字节。通过 encoding 确认了整数类型,就可以确认整数数据的实际大小了,比如如果 encoding 编码确认了数据是 int16 整数,那么 data 的长度就是 int16 的大小。
编码编码长度整数类型
110000001int16_t(2 bytes)
110100001int32_t(4 bytes)
111000001int64_t(8 bytes)
11110000124位有符整数(3 bytes)
1111111018位有符整数(1 bytes)
1111xxxx1直接在xxxx位置保存数值,范围从0001~1101,减1后结果为实际值

例如,一个ZipList中包含两个整数值:“2”和“5”

浅析 Redis 数据结构 List 及其底层编码方式

可以看到,ZipList 使用 previous_entry_length 来进行向前遍历的操作,而向后遍历使用 encoding的长度 + contents 的长度就可以实现,这导致 ZipList 对非首尾节点的查询操作时间复杂度达到 O(n)

ZipList 的连锁更新问题

连锁更新

压缩列表除了查找复杂度高的问题,还有一个问题。

压缩列表新增某个元素或修改某个元素时,如果空间不不够,压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时,可能会导致后续元素的 prevlen 占用空间都发生变化,从而引起「连锁更新」问题,导致每个元素的空间都要重新分配,造成访问压缩列表性能的下降

前面提到,压缩列表节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配:

  • 如果前一个节点的长度小于 254 字节,那么 prevlen 属性需要用 1 字节的空间来保存这个长度值;
  • 如果前一个节点的长度大于等于 254 字节,那么 prevlen 属性需要用 5 字节的空间来保存这个长度值;

现在假设一个压缩列表中有多个连续的、长度在 250~253 之间的节点,如下图:

浅析 Redis 数据结构 List 及其底层编码方式

因为这些节点长度值小于 254 字节,所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。

这时,如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点,即新节点将成为 e1 的前置节点,如下图:

浅析 Redis 数据结构 List 及其底层编码方式 因为 e1 节点的 prevlen 属性只有 1 个字节大小,无法保存新节点的长度,此时就需要对压缩列表的空间重分配操作,并将 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。

多米诺牌的效应就此开始。

浅析 Redis 数据结构 List 及其底层编码方式

e1 原本的长度在 250~253 之间,因为刚才的扩展空间,此时 e1 的长度就大于等于 254 了,因此原本 e2 保存 e1 的 prevlen 属性也必须从 1 字节扩展至 5 字节大小。

正如扩展 e1 引发了对 e2 扩展一样,扩展 e2 也会引发对 e3 的扩展,而扩展 e3 又会引发对 e4 的扩展.... 一直持续到结尾。

这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」,就像多米诺牌的效应一样,第一张牌倒下了,推动了第二张牌倒下;第二张牌倒下,又推动了第三张牌倒下....,

压缩列表的缺陷

空间扩展操作也就是重新分配内存,因此连锁更新一旦发生,就会导致压缩列表占用的内存空间要多次重新分配,这就会直接影响到压缩列表的访问性能

所以说,虽然压缩列表紧凑型的内存布局能节省内存开销,但是如果保存的元素数量增加了,或是元素变大了,会导致内存重新分配,最糟糕的是会有「连锁更新」的问题

因此,压缩列表只会用于保存的节点数量不多的场景,只要节点数量足够小,即使发生连锁更新,也是能接受的。

虽说如此,Redis 针对压缩列表在设计上的不足,在后来的版本中,新增设计了两种数据结构:quicklist 和 listpack(这个数据结构会单独开一篇文章)。这两种数据结构的设计目标,就是尽可能地保持压缩列表节省内存的优势,同时解决压缩列表的「连锁更新」的问题。

QuickList

为什么需要 QuickList

在 Redis 3.0 之前,List 对象的底层数据结构是双向链表或者压缩列表。然后在 Redis 3.2 的时候,List 对象的底层改由 quicklist 数据结构实现。

其实 Quicklist 就是「双向链表 + 压缩列表」组合,因为一个 quicklist 就是一个链表,而链表中的每个元素又是一个 ZipList。

在上文中中,我们提到压缩列表存在一些不足之处,虽然压缩列表是通过紧凑型的内存布局节省了内存开销,但是因为它的结构设计,如果保存的元素数量增加,或者元素变大了,压缩列表会有「连锁更新」的风险,一旦发生,会造成性能下降。而且, ZipList 对非首尾节点的查询操作时间复杂度是 O(n) ,这在元素数量过多的情况下,同样不可接受。

Quicklist 解决办法,通过控制每个链表节点中的压缩列表的大小或者元素个数,来规避连锁更新的问题。因为压缩列表元素越少或越小,连锁更新带来的影响就越小,对其进行遍历操作所需要的时间代价也变得可以接受,从而提供了更好的访问性能。

所以,QuickList 要做的事情就是

  • 限制 ZipList 的长度和 entry 大小
  • 通过链表的结构来管理每一个 ZipList 节点

QuickList 的结构是什么样的

从本质上来说,QuickList 是一个双端列表,特殊之处在于,它的每一个节点是一个 ZipList。

💡 在向 quicklist 添加一个元素的时候,不会像普通的链表那样,直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素,如果能容纳就直接保存到 quicklistNode 结构里的压缩列表,如果不能容纳,才会新建一个新的 quicklistNode 结构。

QuickList

QuickList 的结构源码如下:

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

这里介绍一下几个重要的变量的含义

  • *quicklistNode head :头结点指针

  • *quicklistNode tail :尾节点指针

  • unsigned long count :节点中所有 entry 的数量之和

  • unsigned long len :节点数量

  • int fill : QL_FILL_BITS :ZipList 中的 entry 数量上限

    • 为了避免 QuickList 中的每个 ZipList 中 entry 过多,Redis提供了一个配置项:list-max-ziplist-size 来限制,也即 QL_FILL_BITS 的值。

    • 如果值为正,则代表 ZipList 的允许的 entry 个数的最大值

    • 如果值为负,则代表ZipList的最大内存大小,分5种情况:(其默认值为 -2)

    • -1:每个ZipList的内存占用不能超过4kb

    • -2:每个ZipList的内存占用不能超过8kb

    • -3:每个ZipList的内存占用不能超过16kb

    • -4:每个ZipList的内存占用不能超过32kb

    • -5:每个ZipList的内存占用不能超过64kb

  • unsigned int compress : QL_COMP_BITS:首尾不压缩的节点数量

QuickListNode

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
  • *struct quicklistNode prev :前一个节点指针
  • *struct quicklistNode next :后一个节点指针
  • *unsigned char zl :当前节点的 ZipList 指针
  • unsigned int sz :当前节点的 ZipList 大小
  • unsigned int count : 16 :当前节点的 ZipList entry 个数
  • unsigned int encoding : 2 :编码方式 1:ZipList ;2:lzf 压缩模式
  • unsigned int container : 2 :数据类型容器(预留)
  • unsigned int recompress : 1 :是否被解压缩 1:被解压了,需要重新压缩

整体结构图

浅析 Redis 数据结构 List 及其底层编码方式

参考资料

转载自:https://juejin.cn/post/7239923199609094202
评论
请登录