浅析 Redis 数据结构 List 及其底层编码方式
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)。其结构如下图所示,
各个成员变量如下:
- zlbytes,记录整个压缩列表占用内存字节数;
- zltail,记录压缩列表「尾部」节点距离起始地址有多少字节,也就是列表尾的偏移量;
- zllen,记录压缩列表包含的节点数量;
- entry , 压缩列表包含的各个节点,节点的长度由节点保存的内容决定。
- zlend,标记压缩列表的结束点,固定值 0xFF(十进制255)。
在压缩列表中,如果我们要查找定位第一个元素和最后一个元素,可以通过 zltail 直接定位,复杂度是 O(1)。而查找其他元素时,就没有这么高效了,只能逐个查找,此时的复杂度就是 O(N) 了,因此压缩列表不适合保存过多的元素。
ZipListEntry
- ZipList 中的 Entry 并不像普通链表那样记录前后节点的指针,因为记录两个指针要占用16个字节,浪费内存。而是采用下面的结构
-
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 | ||
01pppppp | qqqqqqqq | |
10000000 | qqqqqqqq |
例如,我们要保存字符串:“ab”和 “bc”
整数
- 如果 encoding 是以“11”开始,则证明 content 是整数,且 encoding 固定只占用1个字节。通过 encoding 确认了整数类型,就可以确认整数数据的实际大小了,比如如果 encoding 编码确认了数据是 int16 整数,那么 data 的长度就是 int16 的大小。
编码 | 编码长度 | 整数类型 |
---|---|---|
11000000 | 1 | int16_t(2 bytes) |
11010000 | 1 | int32_t(4 bytes) |
11100000 | 1 | int64_t(8 bytes) |
11110000 | 1 | 24位有符整数(3 bytes) |
11111110 | 1 | 8位有符整数(1 bytes) |
1111xxxx | 1 | 直接在xxxx位置保存数值,范围从0001~1101,减1后结果为实际值 |
例如,一个ZipList中包含两个整数值:“2”和“5”
可以看到,ZipList 使用 previous_entry_length 来进行向前遍历的操作,而向后遍历使用 encoding的长度 + contents 的长度就可以实现,这导致 ZipList 对非首尾节点的查询操作时间复杂度达到 O(n)
ZipList 的连锁更新问题
连锁更新
压缩列表除了查找复杂度高的问题,还有一个问题。
压缩列表新增某个元素或修改某个元素时,如果空间不不够,压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时,可能会导致后续元素的 prevlen 占用空间都发生变化,从而引起「连锁更新」问题,导致每个元素的空间都要重新分配,造成访问压缩列表性能的下降。
前面提到,压缩列表节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配:
- 如果前一个节点的长度小于 254 字节,那么 prevlen 属性需要用 1 字节的空间来保存这个长度值;
- 如果前一个节点的长度大于等于 254 字节,那么 prevlen 属性需要用 5 字节的空间来保存这个长度值;
现在假设一个压缩列表中有多个连续的、长度在 250~253 之间的节点,如下图:
因为这些节点长度值小于 254 字节,所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。
这时,如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点,即新节点将成为 e1 的前置节点,如下图:
因为 e1 节点的 prevlen 属性只有 1 个字节大小,无法保存新节点的长度,此时就需要对压缩列表的空间重分配操作,并将 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。
多米诺牌的效应就此开始。
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 数据结构 | 小林coding (xiaolincoding.com)
- 原理篇-06.Redis数据结构-ZipList_哔哩哔哩_bilibili
- 06 从ziplist到quicklist,再到listpack的启发.md (lianglianglee.com)
- Redis lists | Redis
- redis/redis: Redis is an in-memory database that persists on disk. The data model is key-value, but many different kind of values are supported: Strings, Lists, Sets, Sorted Sets, Hashes, Streams, HyperLogLogs, Bitmaps. (github.com)
转载自:https://juejin.cn/post/7239923199609094202