likes
comments
collection
share

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

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

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
评论
请登录