Redis进阶-List底层数据结构精讲

2023-07-22 08:01:34

文章目录

Pre
list 列表
压缩列表 ziplist
快速列表 quicklist
- ziplist 存多少元素?
- 压缩深度
延伸

Pre

Redis进阶-核心数据结构进阶实战

Algorithms_基础数据结构(03)_线性表之链表_双向链表

Redis 有 5 种基础数据结构，分别为：string (字符串)、list (列表)、set (集合)、hash (哈希) 和 zset (有序集合) 。

Redis 所有的数据结构都是以唯一的key 字符串作为名称，然后通过这个唯一 key 值来获取相应的 value 数据。不同类型的数据结构的差异就在于 value 的结构不一样。

list 列表

Redis 的列表相当于 Java 语言里面的 LinkedList，是链表而不是数组。

这意味着list 的插入和删除操作非常快，时间复杂度为 O(1)，但是查找数据很慢，时间复杂度为 O(n) 。
当列表弹出了最后一个元素之后，该数据结构自动被删除，内存被回收。
Redis 的列表结构常用来做异步队列使用

将需要延后处理的任务结构体序列化成字符串塞进 Redis 的列表，另一个线程从这个列表中轮询数据进行处理

队列 O(1)

右边进左边出：队列

192.168.18.131:8001> rpush artisan art1 art2 art3 art4
(integer) 4
192.168.18.131:8001> llen artisan
(integer) 4
192.168.18.131:8001> LRANGE artisan 0 999
1) "art1"
2) "art2"
3) "art3"
4) "art4"
192.168.18.131:8001> LPOP artisan
"art1"
192.168.18.131:8001> LPOP artisan
"art2"
192.168.18.131:8001> LPOP artisan
"art3"
192.168.18.131:8001> LPOP artisan
"art4"
192.168.18.131:8001> LPOP artisan
(nil)
192.168.18.131:8001>

当然了，你也可以左边进，右边出，保证FIFO就行。

除了rpush 和 lpop, 还可以使用 lpush 和 rpop 结合使用，效果是一样的。

栈 O(1)

右边进右边出：栈

192.168.18.131:8001> rpush artisan art1 art2 art3 art4
(integer) 4
192.168.18.131:8001> RPOP artisan
"art4"
192.168.18.131:8001> RPOP artisan
"art3"
192.168.18.131:8001> RPOP artisan
"art2"
192.168.18.131:8001> RPOP artisan
"art1"
192.168.18.131:8001> RPOP artisan
(nil)
192.168.18.131:8001>

查询 O(n)

lindex & ltrim

lindex 相当于 Java 链表的 get(int index)方法，它需要对链表进行遍历，性能随着参数index 增大而变差.
ltrim : 两个参数 start_index 和 end_index 定义了一个区间，在这个区间内的值， ltrim 要保留，区间之外统统砍掉。
我们可以通过 ltrim 来实现一个定长的链表，这一点非常有用。
index 可以为负数，index=-1 表示倒数第一个元素，同样 index=-2 表示倒数第二个元素。

192.168.18.131:8001> rpush artisan art1 art2 art3 art4
(integer) 4
192.168.18.131:8001> LINDEX artisan 0   # O(n) 慎用
"art1"
192.168.18.131:8001> LINDEX artisan 3
"art4"
192.168.18.131:8001> LTRIM artisan 0 2
OK
192.168.18.131:8001> LRANGE artisan 0 999
1) "art1"
2) "art2"
3) "art3"

192.168.18.131:8001> LRANGE artisan 0 -1   # 获取所有元素，O(n) 慎用
1) "art1"
2) "art2"
3) "art3"

192.168.18.131:8001> LTRIM artisan 1 -1   # O(n) 慎用
OK
192.168.18.131:8001> LRANGE artisan 0 -1  # 获取所有元素，O(n) 慎用
1) "art2"
2) "art3"
192.168.18.131:8001> 


192.168.18.131:8001> LTRIM artisan 1 0   # 这其实是清空了整个列表，因为区间范围长度为负
OK
192.168.18.131:8001> LLEN artisan
(integer) 0
192.168.18.131:8001>

快速列表 quicklist

Redis 底层存储的还不是一个简单的 linkedlist，而是称之为快速链表 quicklist 的一个结构。

首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist ，即压缩列表 . 它将所有的元素紧挨着一起存储，分配的是一块连续的内存
当数据量比较多才会改成 quicklist.

因为普通的链表需要的附加指针空间太大，会比较浪费空间，而且会加重内存的碎片化 .

比如这个列表里存的只是 int 类型的数据，结构上还需要两个额外的指针 prev 和 next 。所以 Redis 将链表和 ziplist 结合起来组成了 quicklist。也就是将多个ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。

压缩列表 ziplist

Redis 为了节约内存空间使用，zset 和 hash 容器对象在元素个数较少的时候，采用压缩列表 (ziplist) 进行存储。

压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。

使用DEBUG OBJECT 查看内部存储结构

192.168.18.131:8001> ZADD artisan 1.0 java 2.0 go 3.0 python
(integer) 3
192.168.18.131:8001> DEBUG OBJECT artisan  # 查看内部存储结构 
Value at:0x7f131e2ba5d0 refcount:1 encoding:ziplist serializedlength:36 lru:9895943 lru_seconds_idle:6
192.168.18.131:8001>

192.168.18.131:8001> HMSET artisan2 name ysw sex male 
-> Redirected to slot [6066] located at 192.168.18.132:8002
OK
192.168.18.132:8002> DEBUG OBJECT artisan2
Value at:0x7fb74eaba5f0 refcount:1 encoding:ziplist serializedlength:34 lru:9896028 lru_seconds_idle:9
192.168.18.132:8002>

观察 debug object 输出的 encoding 字段都是 ziplist，这就表示内部采用压缩列表结构进行存储。

ziplist 源码

struct ziplist<T> {
	int32 zlbytes; // 整个压缩列表占用字节数
	int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
	int16 zllength; // 元素个数
	T[] entries; // 元素内容列表，挨个挨个紧凑存储
	int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

压缩列表为了支持双向遍历，所以才会有 ztail_offset 这个字段，用来快速定位到最后一个元素，然后倒着遍历。

entry

entry 块随着容纳的元素类型不同，也会有不一样的结构

struct entry {
	int<var> prevlen; // 前一个 entry 的字节长度
	int<var> encoding; // 元素类型编码
	optional byte[] content; // 元素内容
}

它的 prevlen 字段表示前一个 entry 的字节长度，当压缩列表倒着遍历时，需要通过这个字段来快速定位到下一个元素的位置。

它是一个变长的整数，当字符串长度小于254(0xFE) 时，使用一个字节表示；
如果达到或超出 254(0xFE) 那就使用 5 个字节来表示。
第一个字节是 0xFE(254)，剩余四个字节表示字符串长度。

用 5 个字节来表示字符串长度，是不是太浪费了?

我们可以算一下，当字符串长度比较长的时候，其实 5个字节也只占用了不到(5/(254+5))<2%的空间。

encoding 字段存储了元素内容的编码类型信息，ziplist 通过这个字段来决定后面的content 内容的形式。

增加元素

因为 ziplist 都是紧凑存储，没有冗余空间 (对比一下 Redis 的字符串结构)。意味着插入一个新的元素就需要调用 realloc 扩展内存。

取决于内存分配器算法和当前的 ziplist 内存大小，realloc 可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也可能在原有的地址上进行扩展，这时就不需要进行旧内容的内存拷贝。

如果 ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist不适合存储大型字符串，存储的元素也不宜过多。

快速列表 quicklist

Redis 早期版本存储 list 列表数据结构使用的是压缩列表 ziplist 和普通的双向链表linkedlist，也就是元素少时用 ziplist，元素多时用 linkedlist。

// 链表的节点
struct listNode<T> {
	listNode* prev;
	listNode* next;
	T value;
}
// 链表
struct list {
	listNode *head;
	listNode *tail;
	long length;
}

考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。

192.168.18.132:8002> RPUSH test artisan1 artisan2 artisan3
(integer) 3
192.168.18.132:8002> DEBUG OBJECT test
Value at:0x7fb74eaba610 refcount:1 encoding:quicklist serializedlength:36 lru:9897276 lru_seconds_idle:4 ql_nodes:1 ql_avg_node:3.00 ql_ziplist_max:-2 ql_compressed:0 ql_uncompressed_size:41
192.168.18.132:8002>

观察上面输出字段 encoding 的值。quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。

struct ziplist {
	...
}
struct ziplist_compressed {
	int32 size;
	byte[] compressed_data;
}


struct quicklistNode {
	quicklistNode* prev;
	quicklistNode* next;
	ziplist* zl; // 指向压缩列表
	int32 size; // ziplist 的字节总数
	int16 count; // ziplist 中的元素数量
	int2 encoding; // 存储形式 2bit，原生字节数组还是 LZF 压缩存储
	...
}
struct quicklist {
	quicklistNode* head;
	quicklistNode* tail;
	long count; // 元素总数
	int nodes; // ziplist 节点的个数
	int compressDepth; // LZF 算法压缩深度
	...
}

上述代码简单地表示了 quicklist 的大致结构。为了进一步节约空间，Redis 还会对ziplist 进行压缩存储，使用 LZF 算法压缩，可以选择压缩深度。

ziplist 存多少元素?

quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起一个ziplist。

ziplist 的长度由配置参数 list-max-ziplist-size 决定。

压缩深度

quicklist 默认的压缩深度是 0，也就是不压缩。压缩的实际深度由配置参数 list-compress-depth 决定.

为了支持快速的 push/pop 操作，quicklist 的首尾两个 ziplist 不压缩，此时深度就是 1。

如果深度为 2，就表示 quicklist 的首尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。

延伸

参考：《Redis深度历险：核心原理和应用实践》

ziplist、linkedlist 和 quicklist 的性能对比

码农公寓

文章目录

队列 O(1)

栈 O(1)

查询 O(n)

快速列表 quicklist

ziplist 源码

entry

增加元素

ziplist 存多少元素?

压缩深度

相关文章