【Redis#6】Redis 数据结构 -- List 类型

一、前言

Redis 的 List 是通过 链表 实现的，因此：

• 在头尾插入和删除元素的时间复杂度都是 O(1) 。
• 而访问中间元素的复杂度是 O(N) ，不建议频繁操作中间元素。

列表类型用于 存储多个有序的字符串，如 a、b、c、d、e 五个元素从左到右组成一个有序列表，每个字符串称为 元素，最多可存储

个元素。

• 列表支持 两端插入（push）、弹出（pop）、获取指定范围或索引的元素等操作
• 列表可充当栈和队列的角色，在实际开发中应用广泛

img

特点

• 有序性：通过 索引 下标 可获取特定或范围内的元素。比如要获取第五个元素，则可以执行：lindexuser:1:messsage 或者 lindexuser1:message-1
• 支持 前后 插入删除 的设计
• 获取与删除 区别：如 lrem 1 b 删除列表中第一个 b 元素，而 lindex 4 仅获取元素，不影响列表长度。
• 元素可重复：列表允许包含重复元素

如图所示：

img

二、list 命令🧱

1. PUSH & PUSHX

区别如下：

语法如下：

L/R PUSH/PUSHX key element [element ...]

① LPUSH：从左侧插入元素，时间复杂度 O(N)（取决于插入元素个数）

• 注意：是按照键入在命令中的顺序，从左向右将命令中的元素插入到list中的
• 例如：LPUSH key 1 2 3 4，那么最后list呈现的结果为：4 3 2 1，采取的为头插

② LPUSHX：在key存在时，将⼀个或者多个元素从左侧放⼊（头插）到list中。不存在，直接返回

③ RPUSH：从右侧插入元素，时间复杂度 O(N)（取决于插入元素个数）

④ RPUSHX：若键存在，则从右侧插入元素，否则返回

案例如下：

127.0.0.1:6379> lpushx mylist "hello"
(integer) 0
127.0.0.1:6379> lpush mylist "hello"
(integer) 1
127.0.0.1:6379> rpush mylist "world"
(integer) 2
127.0.0.1:6379> LRANGE mylist 0 1
1) "hello"
2) "world"

2. LPOP & RPOP

LPOP：从左侧弹出元素，时间复杂度 (O(1))

RPOP：从右侧弹出元素，时间复杂度 (O(1))

注意：可一次删除多个

案例如下：

127.0.0.1:6379> lpop mylist 
"hello"
127.0.0.1:6379> LRANGE mylist 0 -1
1) "world"

3. LRANGE & LINDEX & LINSERT

① LRANHGE：获取指定范围的元素，时间复杂度 (O(N))。

• 注意：Redis会尽可能地获取到给定区间的元素，如果给定区间非法，比如超出下标，就会尽可能地获取到对应的内容
• Redis对于下标越界地处理方式类似于Python的切片操作

LRANGE key start stop

注意：stop 为 -1时，相当于是 len - 1 查询从 start 开始的所有元素

127.0.0.1:6379> LRANGE mylist 0 1
1) "hello"
2) "world"
127.0.0.1:6379> LRANGE mylist 0 -1
1) "hello"
2) "world"

② LINDEX：获取从左数第index位置的元素。时间复杂度：O(N)，返回取出的元素或者nil

 LINDEX key index

③ LINSERT：从左侧开始的特定位置插入元素（如果有多个 pivot 元素，只在第一个 pivot 的位置插入）。时间复杂度：O(N)，返回插入后的 List 长度

LINSERT key <BEFORE | AFTER> pivot element

案例如下：

127.0.0.1:6379> linsert mylist AFTER "world" a
(integer) 2
127.0.0.1:6379> LINSERT mylist BEFORE "world" "hi"
(integer) 3

127.0.0.1:6379> LRANGE mylist 0 -1
1) "hi"
2) "world"
3) "a"

127.0.0.1:6379> lindex mylist 1
"world"

4. LLEN & LREM & LSET & LTRIM

① LLEN：获取 list 长度，时间复杂度：O(1)，返回 list 长度。

LLEM key

② LREM：rem 的意思是 remove，所以意思很明显，就是要移出某个元素

lrem key count element

其中 count 表示的是要删除多少个元素，其中返回值表示的是删除成功的个数

• count > 0：删除元素从头到尾
• count < 0：删除元素从尾到头
• count = 0：不删除

案例如下：

127.0.0.1:6379> rpush list 1 2 3 hi 1 2 3 ho 1 2 3 hi
(integer) 12
127.0.0.1:6379> lrem list 2 hi
(integer) 2
127.0.0.1:6379> lrange list 0 -1
 1) "1"
 2) "2"
 3) "3"
 4) "1"
 5) "2"
 6) "3"
 7) "ho"
 8) "1"
 9) "2"
10) "3"

③ LSET：根据下标修改元素（支持负数下标，如果下标越界，会返回一个报错）

lset key index element

④ LTRIM：保留 [start, stop] 闭区间的元素，其他元素全部删除

ltrim key start stop

案例如下：

127.0.0.1:6379> rpush list 1 2 3 4 5 
(integer) 5
127.0.0.1:6379> ltrim list 1 3
OK
127.0.0.1:6379> lrange list 0 -1
1) "2"
2) "3"
3) "4"

127.0.0.1:6379> lset list 1 666
OK
127.0.0.1:6379> lrange list 0 -1
1) "2"
2) "666"
3) "4"

5. 补充 – 阻塞版本命令

• 先前的所有命令均为非阻塞命令，可以直接操作并立即得到结果。
• 然而，Redis 的列表类型还提供了一些具有 阻塞性质 的命令

比如：在多线程中，有一个生产消费模型，其可以基于阻塞队列实现，主要满足以下两个性质：

• 如果阻塞队列满了，那么生产者阻塞
• 如果阻塞队列空了，那么消费者阻塞

在Redis中，list只考虑队列为空的情况，也就是消费者。用户读取数据时，队列为空，那么用户陷入阻塞，直到队列有数据。

阻塞 vs 非阻塞：

• 在列表中有元素的情况下，阻塞和非阻塞表现是一致的。但如果列表中没有元素，非阻塞版本会理解返回nil，但阻塞版本会根据timeout，阻塞一段时间，期间Redis可以执行其他命令，但要求执行该命令的客户端会表现为阻塞状态
• 命令中如果设置了多个键，那么会从左向右进行遍历键，一旦有一个键对应的列表中可以弹出元素，命令立即返回。
• 如果多个客戶端同时多一个键执行pop，则最先执行命令的客戶端会得到弹出的元素

现有下面三种情况，图示如下：

情况一：列表不为空

image-20250628114619435

情况二：列表为空，且 5s 内没有新元素加入

image-20250628114817569

情况三：列表为空，但 5s 内有新元素加入

• lpop user:1:messages 立即得到 nil
• blpop user:1:messages 执行命令，若 timeout 结束前，有新元素加入，则直接得到新元素

命令使用，语法如下：

BLPOP/BRPOP key [key ...] timeout

说明：

• 可以同时指定多个 key，即多个列表，只要任意一个列表有数据，就返回结果。
• 设置超时时间 timeout，以秒为单位，超过时间则返回 nil。
• 超时时间设为 0，则一直阻塞，不会超时。
• 阻塞发生在客户端，Redis 会将指令放入后台等待，继续处理其他请求

① BLPOP：读取并删除列表头部元素，如果列表为空则用户陷入阻塞，案例如下：

127.0.0.1:6379> lpush list1 1 2 3
(integer) 3
127.0.0.1:6379> blpop list1 list2 5
1) "list1"
2) "3"
127.0.0.1:6379> llen list2
(integer) 0
127.0.0.1:6379> blpop list2 10
(nil)
(10.02s)

此处启用了两个客户端，左侧客户端blpop一个空列表，等待 10s，随后陷入阻塞。接着右侧客户端插入一个元素到list2，随后左侧客户端立刻拿到数据并进行头删

127.0.0.1:6379> lpush list2 1 # 启用第二个客户端
(integer) 1

127.0.0.1:6379> blpop list2 10
1) "list2"
2) "1"
(1.91s)

② BRPOP：读取并删除列表尾部元素，如果列表为空则用户陷入阻塞（具体使用和上面类似，不过多讲解）

三、内部编码

ziplist（压缩列表）：一种内存紧凑的存储方式，适合存储数量较少且元素较小的列表。当列表的元素个数小于 list-max-ziplist-entries 配置（默认512个），同时列表中每个元素的长度都小于 list-max-ziplist-value 配置（默认64字节）时，Redis会选用 ziplist 来作为列表的内部编码实现来减少内存消耗。

• 优点：
  • 内存节省：使用连续的内存块存储数据，减少内存碎片和开销。
  • 结构简单：适合小规模数据，尤其在内存资源有限的情况下。
• 缺点：
  • 操作效率：数据量增加时，读写效率下降，线性查找特性导致操作复杂度较高。
  • 扩展性差：不适合大规模数据存储。

linkedlist（链表）：当列表类型无法满足 ziplist 条件时，使用 linkedlist 作为内部实现。

• 优点：头尾的插入删除非常高效。
• 缺点：中间部分的插入删除时间复杂度较高。

img

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

✔️quicklist(快速链表)

结构：quicklist 实际上是 zipList 和 linkedList 的混合体，它将 linkedList 按段切分（外层列表仍然是 linkedlist 双链表结构），每个链表节点都是一个 ziplist，对中间部分的节点进行一定程度的压缩，提高效率，多个 zipList 之间使用双向指针串接起来

img

源码如下：

typedef struct quicklistNode {
    struct quicklistNode *prev; 			//上一个node节点
    struct quicklistNode *next; 			//下一个node
    unsigned char *zl;            			//保存的数据 压缩前ziplist 压缩后压缩的数据
    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;

参数分析：

• prev：指向链表前一个节点的指针。
• next：指向链表后一个节点的指针。
• zl：数据指针。如果当前节点的数据没有压缩，那么它指向一个ziplist结构；否则，它指向一个quicklistLZF结构。
• sz：表示zl指向的ziplist的总大小（包括zlbytes, zltail, zllen, zlend和各个数据项）。需要注意的是：如果ziplist被压缩了，那么这个sz的值仍然是压缩前的ziplist大小。
• count：表示ziplist里面包含的数据项个数。这个字段只有16bit。稍后我们会一起计算一下这16bit是否够用。
• encoding：表示ziplist是否压缩了（以及用了哪个压缩算法）。目前只有两种取值：2表示被压缩了（而且用的是LZF压缩算法），1表示没有压缩。
• container：是一个预留字段。本来设计是用来表明一个quicklist节点下面是直接存数据，还是使用ziplist存数据，或者用其它的结构来存数据（用作一个数据容器，所以叫container）。但是，在目前的实现中，这个值是一个固定的值2，表示使用ziplist作为数据容器。
• recompress：当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=1做一个标记，等有机会再把数据重新压缩。
• attempted_compress：这个值只对Redis的自动化测试程序有用。我们不用管它。
• extra：其它扩展字段。目前Redis的实现里也没用上。

typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

quicklistLZF结构表示一个被压缩过的ziplist。其中：

• sz: 表示压缩后的ziplist大小。
• compressed: 是个柔性数组（flexible array member），存放压缩后的ziplist字节数组。

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;

• head：指向头节点（左侧第一个节点）的指针。
• tail：指向尾节点（右侧第一个节点）的指针。
• count：所有ziplist数据项的个数总和。
• len：quicklist节点的个数。
• fill：16bit，ziplist大小设置，存放list-max-ziplist-size参数的值。
• compress：16bit，节点压缩深度设置，存放list-compress-depth参数的值。

四、使用场景

Ⅰ消息队列

实现：Redis 可以使用 **lpush ** + brpop 命令组合实现经典的 阻塞式生产者-消费者模型队列。

流程：

• 生产者：客户端使用 lpush 从列表左侧插入元素。
• 消费者：多个消费者客户端使用 brpop 命令阻塞式地从队列中“争抢”队首元素

img

特点：通过多个客户端来保证消费的负载均衡和高可用性，保证只有一个消费者能“抢到”元素

Ⅱ 分频道的消息队列

实现：Redis 同样使用 lpush + brpop 命令，但通过不同的键模拟频道的概念

流程：

• 生产者：将消息推送到不同的键值（频道）
• 消费者：通过 brpop 不同的键值，实现订阅不同频道的理念

img

特点：每个频道只有一个消费者能“抢到”元素，不同的消费者可以订阅不同的频道，确保某个主题的数据出现问题时不会影响其他频道

思考：如何确定是哪个消费者“抢到”了元素？

1. 阻塞命令机制

• brpop 命令：当消费者调用 brpop 命令时，如果指定的列表为空，消费者将进入阻塞状态，等待列表中有元素可用。
• 多个消费者竞争：如果有多个消费者同时调用 brpop 命令，Redis 会确保只有一个消费者能够成功获取到元素。这个消费者 是第一个被唤醒并成功执行 brpop 命令的 消费者。

1. 客户端处理逻辑

• 唯一标识：每个消费者在执行 brpop 命令时，可以记录自己的唯一标识（如消费者ID）。
• 日志记录：当消费者成功获取到元素后，可以在日志中记录这次操作，包括消费者ID、获取的元素内容和时间戳等信息。
• 回调函数：在消费者应用中，可以设置回调函数来处理 brpop 命令的结果。回调函数中可以包含记录日志、更新状态等操作。

示例：假设我们有两个消费者（Consumer A 和 Consumer B）订阅同一个频道 key-1，生产者将消息推送到 key-1。

生产者

lpush key-1 message1

消费者 A/B

import redis
 
client = redis.StrictRedis()
 
def handle_message(message):
    print(f"Consumer A got message: {message}")
    # 记录日志
    with open('consumer_a_log.txt', 'a') as log_file:
        log_file.write(f"Consumer A got message: {message}\n")
 
while True:
    message = client.brpop('key-1')
    if message:
        handle_message(message[1].decode('utf-8'))

日志记录

Consumer A 的日志文件 consumer_a_log.txt：

Consumer A got message: message1

Consumer B 的日志文件 consumer_b_log.txt，同上

总结如下，可以通过上述方法明确知道是哪个消费者 “抢到了" 元素

• 唯一标识：每个消费者有自己的唯一标识。
• 日志记录：成功获取到元素后，记录日志。
• 回调函数：设置回调函数处理 brpop 命令的结果。

Ⅲ 微博 Timeline

需求：每个用户都有属于自己的 Timeline（微博列表），需要分页展示文章列表。

实现：

① 每篇微博使用哈希结构存储，例如微博中3个属性：title、timestamp、content

hmset mblog:1 title xx timestamp 1476536196 content xxxxx
...
hmset mblog:n title xx timestamp 1476536196 content xxxxx

② 向用户Timeline添加微博，user::mblogs 作为微博的键

lpush user:1:mblogs mblog:1 mblog:3
...
lpush user:k:mblogs mblog:9

image-20250629125011388

此时博客目录 通过 list 将每篇博客数据（hash） 组织起来了

③ 分页获取：分页获取用户的 Timeline，例如获取用户 1 的前 10 篇微博

keylist = lrange user:1:mblogs 0 9
for key in keylist {
    hgetall key
}

1 + n 问题（关于 pipeline 流水线）

题意：如果每次分页获取的微博个数较多，需要执行多次 hgetall 操作，此时可以考虑使用 pipeline（流水线）模式批量提交命令或者微博不采用哈希类型，而是使用序列化的 字符串类型，使用 mget 获取。

• 中间元素获取性能：lrange 在列表两端表现较好，获取列表中间的元素表现较差，此时可以考虑将列表做拆分。

拆分的实现：

• 假设某个用户发了 1w 个微博，list 长度就是 1w。
• 就可以把这 1w 个微博拆成 10 份，每份就是 1k。
• 如果是想获取到 5k 个左右的微博，只用读取 5 份

Pipeline (流水线)：虽然咱们是多个 Redis 命令，但是把这些 命令合并成一个网络请求进行通信，大大降低客户端和服务端之间的交互次数了。

思考：

• Quicklist：Quicklist 的外层是一个双向链表（linkedlist），每个节点是一个 （局部数据合并为）ziplist存储，是一种高效的列表内部编码方式。
• Pipeline：是一种客户端技术，用于将多个命令合并成一个网络请求发送给服务器，从而减少网络往返时间，提高命令执行效率。

区别：Quicklist 是一种数据结构优化，而 Pipeline 是一种网络通信优化。

补充：用 list 实现栈和队列

• 同侧存取：lpush + lpop 或者 rpush + rpop 为栈。
• 异侧存取：lpush + rpop 或者 rpush + lpop 为队列。