redis 从0到1完整学习 (七):ZipList 数据结构

发布时间:2023年12月25日


1. 引言

前情提要:
《redis 从0到1完整学习 (一):安装&初识 redis》
《redis 从0到1完整学习 (二):redis 常用命令》
《redis 从0到1完整学习 (三):redis 数据结构》
《redis 从0到1完整学习 (四):字符串 SDS 数据结构》
《redis 从0到1完整学习 (五):集合 IntSet 数据结构》
《redis 从0到1完整学习 (六):Hash 表数据结构》
本文主要结合源码来介绍 ZipList 的数据结构

2. redis 源码下载

Redis 源码可以点击这里下载,方便查看其中定义的一些数据结构。
在这里插入图片描述

3. zipList 数据结构

3.1 整体

zipList 是为了提高存储效率而设计的一种特殊编码的双向链表,由一系列特殊编码的连续内存块组成。可以在任意一端进行 push 和 pop 操作,并且该操作的时间复杂度为 O(1)。它可以存储字符串或者整数,存储整数时是采用整数的二进制而不是字符串形式存储。

zipList 数据结构示意图:
在这里插入图片描述

名称类型size用途
zlbytesuint32_t4 字节记录整个 zipList 占用的字节总数,即图中 zlbytes 的起始 到 zlend 的末尾
zltailuint32_t4 字节记录 zipList 尾节点距离起始地址有多少字节,即图中 zlbytes 起始 到 tail 起始的偏移量,通过这个偏移量,可以确定尾节点的地址
zllenuint16_t2 字节记录了压缩列表包含的节点数量。 最大值为 UINT16_MAX (65534)。如果超过这个值,会记录为65535。
entry不定压缩列表包含的各个节点,节点的长度由节点保存的内容决定。
zlenduint8_t1 字节特殊值 0xFF (十进制 255 ),用于标记压缩列表的末端。

3.2 entry 数据结构分析

ziplist 中的每个 entry 都以包含两条信息的元数据作为前缀。首先,存储上一个 entry 的长度,以便能够从后向前遍历列表。其次,提供 entry encoding,表示 entry 类型,整数或字符串,如果是字符串,它还表示字符串有效负载的长度。因此,完整的 entry 存储如下:
在这里插入图片描述

  • prevlen:前一个 entry 的长度,占1个或5个字节。
    • 如果前一个 entry 的长度 < 254字节,则采用1个字节来保存这个长度值
    • 如果前一个 entry 的长度 > 254字节,则采用5个字节来保存这个长度值,第一个字节为 0xfe,后四个字节才是真实长度数据
  • encoding:编码属性,记录数据类型(字符串还是整数)以及长度,占用1个、2个或5个字节
  • entry-data:负责保存 entry 数据,可以是字符串或整数

根据 redis 源码的注解来看,encoding 的编码如下:
(1)字符串编码

encoding 格式编码长度字符串大小
|00pppppp|1 bytes<= 63 bytes
|01pppppp|qqqqqqqq|2 bytes<= 16383 bytes
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|5 bytes<= 4294967295 bytes

例如,下面保存 abbc 字符串示例:

 *  [13 00 00 00] [0e 00 00 00] [02 00] [00 02 61 62] [04 02 62 63] [ff]
 *        |             |          |       	  |       	    |     	 |
 *     zlbytes        zltail     zllen       "ab"         "bc"     end
 * 

a 的 ASCII 码是97,对应的16进制是61
b 的 ASCII 码是98,对应的16进制是62
c 的 ASCII 码是99,对应的16进制是63
ab 的编码是 6162,长度是2字节,所以 encoding 是 00000010 即 16进制02,而前一个 entry 不存在,因而 prevlen 为 0,所以 ab 编码为 00026162;同样的 bc 前一个 entry 为 ab,字节一共为4,所以 bc 编码为 04026263

(2)数字编码

encoding 格式编码长度整数类型
110000001int16_t(2 bytes)
110100001int32_t(4 bytes)
111000001int64_t(8 bytes)
11110000124位有符整数(3 bytes)
1111111018位有符整数(1 bytes)
1111xxxx1在xxxx位置保存数值,范围从0001~1101,减1后结果为实际值

例如,下面是 redis 源码给出的保存 25 整数示例:

 *  [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
 *        |             |          |       |       |     |
 *     zlbytes        zltail     zllen    "2"     "5"   end
 * 

2 的长度在 0001~1101,对应上面表格的最后一种,所以 encoding 为 11110011,即16进制的 f3 (这里的3,实际为2+1);同样 5 encoding 为 11110110,即 f6

3.3 连锁更新

zipList 的每个 entry 都包含 prevlen 来记录上一个节点的大小,长度是1个或5个字节:

  • 如果前一节点的长度 < 254字节,则采用1个字节来保存这个长度值
  • 如果前一节点的长度 >= 254字节,则采用5个字节来保存这个长度值,第一个字节为0xfe,后四个字节才是真实长度数据

当一种边界场景下,插入了一个 entry,entry 的大小超过了 254 字节,导致后续大范围的 entry 的 prevlen 由1字节转为用5个字节来保存,触发了连锁更新,同时删除也可能触发连锁更新。

4. 参考

《redis 从0到1完整学习 (一):安装&初识 redis》
《redis 从0到1完整学习 (二):redis 常用命令》
《redis 从0到1完整学习 (三):redis 数据结构》
《redis 从0到1完整学习 (四):字符串 SDS 数据结构》
《redis 从0到1完整学习 (五):集合 IntSet 数据结构》
《redis 从0到1完整学习 (六):Hash 表数据结构》

文章来源:https://blog.csdn.net/qq_36803941/article/details/135191454
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。