Redis，List篇 - PorcoBlog

本文最后更新于 17 天前，其中的信息可能已经过时，如有错误请留言

Redis 是一组连接起来的字符串集合。

旧版本的 List 最大元素数量是 2^32 – 1 个，新版本的最大元素数量是 2^64 – 1。

用于存储一批任务、或一批消息等。

一、List 的语法

1、LPUSH

语法：LPUSH key value [value …]

功能：从头部增加元素，返回值为 List 中元素的总数。

 127.0.0.1:6379> LPUSH list s1 s2 s3
(integer) 3
 
127.0.0.1:6379> LPUSH list s4
(integer) 4

s4 是第二个命令插入的，插入之后它就在 List 头部，此时 List 结构如下：

2、RPUSH

语法：RPUSH key value [value …]

功能：从尾部增加元素，返回值为 List 中元素的总数。

 127.0.0.1:6379> RPUSH list s5
(integer) 5

s5 是用 RPUSH 命令插入的，插入之后它就在 List 尾部，此时 List 结构如下：

3、LPOP

语法：LPOP key

功能：移出并获取列表的第一个元素。

 127.0.0.1:6379> LPOP list
"s4"

s4 从 List 中移除，此时 List 结构如下：

4、RPOP

语法：RPOP key

功能：移出并获取列表的最后一个元素。

 127.0.0.1:6379> RPOP list
"s5"

s5 从 List 中移除，此时 List 结构如下：

5、LREM

语法：LREM key count value

功能：移除值等于 value 的元素。当 count=0，则移除所有等于 value 的元素。当 count>0，则从左到右开始移除 count 个。当 count<0 则从右到左移除 count 个。返回值为被移除元素的数量。

 127.0.0.1:6379> LREM list 0 s2
(integer) 1

6、DEL

语法：DEL key [key …]

功能：删除对象，返回值为删除成功了几个键。

 127.0.0.1:6379> DEL list
(integer) 1

7、UNLINK

语法：UNLINK key [key …]

功能：删除对象，返回值为删除成功了几个键。和 DEL 主要有如下不同：

del 命令同步删除命令，会阻塞客户端，直到删除完成。 unlink 命令是异步删除命令，只是取消 Key 在键空间的关联，让其不再能查到，删除是异步进行，所以不会阻塞客户端。

构造 list 如下，用于以下读操作

8、LLEN

查看元素个数

 127.0.0.1:6379> LLEN list
(integer) 3

9、LRANGE

语法：LRANGE key start stop

功能：查看 start 到 stop 为角标的元素。

 127.0.0.1:6379> LRANGE list 0 1
1) "s3"
2) "s2"

start、stop 如果为负数，表示倒数第几个元素：

 127.0.0.1:6379> LRANGE list -2 -1
1) "s2"
2) "s1"

二、List 的底层实现

List 在旧版本底层实现有两种：ZIPLIST 和 LINKEDLIST

ZIPLIST 对内存友好，因为元素节凑排列，省去了指针的内存空间，适合元素比较小，且数量少的场景，因为内存紧凑排列，所以元素修改的时候，可能会发生复制，性能会差一些，所以不适合元素多的场景。

LINKEDLIST 相当于是链表，需要指针来将元素相连，所以适合元素多，或者占用空间大的场景，因为增删改元素，不用大面积复制。

新版本用 QUICKLIST，相当于是 ZIPLIST 的链表，所以有结合两者的优点。面试常问的仍然是 ZIPLIST。

ZIPLIST：

ZIPLIST 中有下面几个字段需要留意：

1、zlbytes：记录 ziplist 占用的空间大小

2、zltail：记录最后一个元素偏移的字节数，用于快速定位到最后一个元素（最后一个 entry，不存在定位到 zlend）

3、zllen：记录有多少个数据节点，但是 zllen 只有两个字节，所以当元素数量大于 65535 的时候，就存不下了，必须要遍历所有节点，才能得到节点数量，但 ziplist 本身设计就是适用于节点数量少的场景。

4、中间是元素 entry

5、zlend：特殊节点，标记 ziplist 结束。

entry 的结构：

1、prevlen：上一个节点的数据长度，通过这个可以定位到上一个节点的起始地址，从而实现倒序遍历。但也是因为这个字段，会引起连锁更新反应。连锁更新反应是这样的，后面一个节点，记录了前面一个节点的大小，但是如果前面一个节点的大小变化很大，导致后一个节点的 prevlen 原本 1 个字节不够用，需要扩容，那么后一个节点的下一个节点的 prevlen 也要更新，触发连锁更新。

2、encoding：

encoding 一般分为两个部分，前面几个 bit 用来记录是什么类型的数据，后面几个 bit 用来记录数据的长度。

3、entrydata：真实数据

ZIPLIST 查询数据

通常是 O (1)，可能是 O (n)，因为 zllen 只有 2 个字节

查询一个指定的数据是 O (n)，因为要遍历数据

ZIPLIST 更新数据

更新数据的复杂度是 O (n)，因为在头部插入节点，所有节点都要往后移动

包括前面提到，会触发连锁更新问题

LISTPACK

LISTPACK 通过 element-tot-len 字段来解决连锁更新的问题。连锁更新问题的根源在于 prevlen，LISTPACK 用 element-tot-len 来代替 prevlen，用来记录前一个 entry 节点的长度。

记录前一个节点的长度，是为了从后向前遍历。于是 element-tot-len 里面每一个字节用第一个 bit 来标记 element-tot-len 是否结束，1 代表继续，0 代表结束。每个字节后面的 7 个 bit 用来记录真实的长度数据。

这样前一个 entry 节点的长度就不用记录在后一个节点中，从而也就不会触发连锁更新。

三、List 面试题

1、List 是完全先入先出吗？

List 是双端操作对象，可以先进先出，也可以先进后出

2、List 如何获取指定范围内的数据

用 LRANGE，可以指定 start end

3、List 如何移除特定值的数据？时间复杂度是多少

LREM key count value，移除这个 key 对应的 List 里面值为 value 的数据，移除 count 个，count>0 时，从左往右数 count 个，count<0 时，从右往左数 count 个。由于需要遍历整个 List，所以复杂度是 O (n)

4、List 对象底层编码方式是什么？

我用的是 5.0.5 版本，List 对象的编码全部由 QUICKLIST 实现。QUICKLIST 是一个由 ZIPLIST 和 LINKEDLIST 组成的双向链表，结合了 ZIPLIST 和 LINKEDLIST 两者的优点。

旧的版本里面，对于数据少的时候，用的 ZIPLIST，元素紧凑排列，节约内存（节省链表指针的内存）。数据多的时候，用的 LINKEDLIST，性能更好一些。QUICKLIST 结合了这两者的优点，它是由 ZIPLIST 组成的 LINKEDLIST，兼顾了性能和内存。

5、LINKEDLIST 编码下，查询节点个数的复杂度是多少？

LINKEDLIST 的表头结构里面，有个 len 字段，代表链表的节点个数，所以查询节点个数的复杂度是 O (1)。

 // from Redis 5.0.5
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;