「Redis数据结构」列表对象（List）

「Redis数据结构」列表对象（List）

一、概述

Redis列表是简单的字符串列表，按照插入顺序排序。你可以添加一个元素到列表的头部（左边）或者尾部（右边）。一个列表最多可以包含 232 - 1 个元素 (4294967295, 每个列表超过40亿个元素)。列表对象的编码可以是ziplist或者linkedlist。ziplist编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点(entry)保存了一个列表元素。

快速回顾：

「Redis数据结构」压缩列表（ZipList）

「Redis数据结构」QuickList

---

二、结构

Redis的List类型可以从首、尾操作列表中的元素：

哪一个数据结构能满足上述特征？

• LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多
• ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低
• QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高

Redis的List结构类似一个双端链表，可以从首、尾操作列表中的元素：

在3.2版本之前，Redis采用ZipList和LinkedList来实现List，当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则采用LinkedList编码。

在3.2版本之后，Redis统一采用QuickList来实现List：

例如使用rpush命令将创建一个列表对象作为numbers键的值。

127.0.0.1:6379> rpush numbers 1 "three" 5
(integer) 3
127.0.0.1:6379> object encoding  numbers
"quicklist"
1
2
3
4

通过上面查看底层数据结构并不是ziplist，而是quicklist结构。 该结构是在redis 3.2版本中新加的数据结构，用在列表的底层实现，由ziplist组成的双向链表。链表中的每一个节点都以压缩列表ziplist的结构保存着数据，而ziplist有多个entry节点，保存着数据。相当与一个quicklist节点保存的是一片数据，而不再是一个数据。

例如：一个quicklist结构有4个quicklistNode节点，每个节点都保存着1个ziplist结构，每个ziplist的大小不超过8kb，ziplist的entry节点中的value成员保存着数据。以后在深入了解quicklist数据结构。

---

三、编码转换

当列表对象可以同时满足以下两个条件时， 列表对象使用 ziplist 编码：

1. 列表对象保存的所有字符串元素的长度都小于 64 字节；
2. 列表对象保存的元素数量小于 512 个；

不能满足这两个条件的列表对象需要使用 linkedlist 编码。

注意

以上两个条件的上限值是可以修改的， 具体请看配置文件中关于 list-max-ziplist-value 选项和 list-max-ziplist-entries 选项的说明。

对于使用 ziplist 编码的列表对象来说， 当使用 ziplist 编码所需的两个条件的任意一个不能被满足时， 对象的编码转换操作就会被执行： 原本保存在压缩列表里的所有列表元素都会被转移并保存到双端链表里面， 对象的编码也会从 ziplist 变为 linkedlist 。

以下代码展示了列表对象因为保存了长度太大的元素而进行编码转换的情况：

# 所有元素的长度都小于 64 字节
redis> RPUSH blah "hello" "world" "again"
(integer) 3

redis> OBJECT ENCODING blah
"ziplist"

# 将一个 65 字节长的元素推入列表对象中
redis> RPUSH blah "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww"
(integer) 4

# 编码已改变
redis> OBJECT ENCODING blah
"linkedlist"
1
2
3
4
5
6
7
8
9
10
11
12
13
14

除此之外， 以下代码展示了列表对象因为保存的元素数量过多而进行编码转换的情况：

# 列表对象包含 512 个元素
redis> EVAL "for i=1,512 do redis.call('RPUSH', KEYS[1], i) end" 1 "integers"
(nil)

redis> LLEN integers
(integer) 512

redis> OBJECT ENCODING integers
"ziplist"

# 再向列表对象推入一个新元素，使得对象保存的元素数量达到 513 个
redis> RPUSH integers 513
(integer) 513

# 编码已改变
redis> OBJECT ENCODING integers
"linkedlist"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

四、总结

• 对于列表对象来说，其有两种底层编码实现方式，压缩列表和双端链表
• 当不在满足压缩列表的两个条件时，redis会发生编码转换，将压缩列表中的所有元素都保存到一个双端链表中

---

参考

Redis 字符串对象

《Redis 设计与实现》