【Redis】list 类型

一. list 类型介绍

• 列表 (list) 相当于数组或者顺序表，但是 list 内部的结果 (编码方式)，并非是一个简单的数组，而是更接近于 “双端队列”。
• 列表类型是用来存储多个有序的字符串，列表中的每个字符串称为元素，一个列表最多可以存储 2^32 - 1 个元素。
• 在 Redis 中，可以对列表两端插入和弹出，还可以获取指定范围的元素列表、获取指定索引下标的元素等。
• 列表是一种比较灵活的数据结构，头部和尾部都能高效的插入和删除元素，它可以充当栈和队列的角色，在实际开发上有很多应用场景。
  • Redis 有一个典型的场景，就是作为消息队列，最早的时候，就是通过 list，但是功能有限，后来 Redis 又提供了一个 stream 类型。

列表两端插入和弹出操作：

列表的获取、删除等操作：

列表类型的特点：

• 约定列表最左侧元素的下标是 0，且 Redis 的下标支持负数下标，最右侧元素的下标是 -1
• 列表中的元素是有序的，这意味着可以通过索引下标获取某个元素或者某个范围的元素列表。
  • 例如：要获取第5个元素，可以执行 lindex user:1:messages 4，或者倒数第 1 个元素，lindex user:1:messages -1 就可以得到元素 e
• 区分获取和删除的区别。
  • 例如：lrem 1 b 是从列表中把从左数遇到的前 1 个 b 元素删除，这个操作会导致列表的长度从 5 变成 4。
  • 例如：lindex 4 只会获取元素，但列表长度是不会变化的。
• 列表中的元素是允许重复的。
  • 例如：上图中列表包含了两个 a 元素的。
  • 像 hash 这样的类型，field 是不能重复的。

列表中的元素是有序的。

• 有序的含义，要根据上下文进行区分。
  • 有的时候，谈到有序，指的是 “升序”、“降序”。
  • 有的时候，谈到有序，指的是 顺序很关键。
    • 如果把元素的位置颠倒，顺序调换，此时得到的新的列表和之前的列表是不等价的。
• 同一个词，怎么理解，务必要结合上下文，结合具体的场景。
  • 例如：栈和堆指的是什么？
    • 数据结构的栈和堆？操作系统的栈和堆？JVM的栈和堆？
  • 再例如：同步是什么？
    • 同步和互斥中的同步：多线程/进程按照一定的顺序访问共享资源。
      • 目的：防止竞态条件 (多个线程同时访问共享数据导致数据不一致)
    • 同步和异步中的同步：调用方在调用一个函数后，会等待该函数执行完成并返回结果，才继续执行后续代码。
      • 结果：调用方的执行流是阻塞的，直到被调用方完成。

二. list 命令

lpush、lpushx、rpush、rpushx

• lpush：将一个或者多个元素从左侧插入，也就是头插到 list 中。
  • 若 key 不存在，则先创建 list，再插入数据。
• 语法：lpush key element [element ...]
• 时间复杂度：只插入一个元素为 O(1)，插入多个元素为 O(N)，N 为插入元素个数。
• 返回值：插入后 list 的长度。

如果 key 已经存在，并且 key 对应的 value 类型不是 list，此时 lpush 命令就会报错，Redis 中所有的这些各种数据类型的操作，都是类似的效果。

• lpushx：将一个或者多个元素从左侧插入，也就是头插到 list 中。
  • 若 key 不存在，创建 list 失败，也就是插入数据失败。
• 语法：lpushx key element [element ...]
• 时间复杂度：只插入一个元素为 O(1)，插入多个元素为 O(N)，N 为插入元素个数。
• 返回值：插入后 list 的长度。

• rpush：将一个或者多个元素从右侧插入，也就是尾插到 list 中。
  • 若 key 不存在，则先创建 list，再插入数据。
• 语法：rpush key element [element ...]
• 时间复杂度：只插入一个元素为 O(1)，插入多个元素为 O(N)，N 为插入元素个数。
• 返回值：插入后 list 的长度。

• rpushx：将一个或者多个元素从右侧插入，也就是尾插到 list 中。
  • 若 key 不存在，创建 list 失败，也就是插入数据失败。
• 语法：rpushx key element [element ...]
• 时间复杂度：只插入一个元素为 O(1)，插入多个元素为 O(N)，N 为插入元素个数。
• 返回值：插入后 list 的长度。

注意：

• lpushx 和 rpushx 中，结尾的 x，表示的是 exists
• lrange 中起始的 l，表示的是 list，而并非 left，所以不存在 rlange

lpop、rpop

• lpop：从 list 左侧取出元素，也就是头删。
• 语法：lpop key
• 时间复杂度：O(1)
• 返回值：取出的元素或者 nil

• rpop：从 list 右侧取出元素，也就是尾删。
• 语法：rpop key
• 时间复杂度：O(1)
• 返回值：取出的元素或者 nil

注意：

• 再当前 Redis 5 版本中，lpop 和 rpop 都是没有 count 参数的。
• 从 Redis 6.2 版本，新增了一个 count 参数，描述这次要删几个元素。
  • lpop key count、rpop key count
• Redis 中的 list 是一个双端队列，从两头插入/删除元素的效率非常高效 O(1)
  • 搭配 rpush 和 rpop，也就是尾插和尾删，就相当于 “栈”。
  • 搭配 rpush 和 lpop，也就是尾插和头删，就相当于 “队列”。

lindex、lrange

• lindex：给定下标，获取对应的元素。
• 语法：lindex key index
• 时间复杂度：O(N)，N 指的是 list 中元素的个数。
• 返回值：取出的元素或者 nil

• lrange：获取 list 中，从 start 到 end 区间的所有元素，左闭右闭。
• 语法：lrange key start stop
• 时间复杂度：O(N)
• 返回值：指定区间的元素。

注意：此处的序号，是专门给结果集使用的序号，与下标无关。

如下图，hash 操作有可能会得到这种带有序号的结果，此处的序号仅仅是标识返回元素的顺序，和下标无关，hash 类型就没有下标的概念。

谈到下标，往往会关注到超出范围的情况。

• C++ 中，下标超出范围，一般会认为这是一个 “未定义行为”
  • 可能会导致程序崩溃、可能会得到一个不合法的数据、可能会得到一个看起来合法，但是错误的数据、可能恰好得到一个符合要求的数据。
  • 优点：效率是最高的。
  • 缺点：程序员不一定能第一时间发现问题。
• Java 中，下标超出范围，一般会抛异常。
  • 优点：出现问题即使发现。
  • 缺点：多出一步下标合法的验证，速度比上面慢。
• 在 Redis 中并没有采取上述的两种设定，Redis 的做法，是直接尽可能的获取到给点区间的元素。
  • 如果给定区间非法，比如超出下标，就会尽可能的获取对应的内容。
  • 此处对于越界下标的处理方式，更接近与 python 的处理方式 (切片)
  • 特点：鲁棒性，程序的容错能力更强 (你对我越粗鲁，我表现的较棒)

linsert、lrem、ltrim

• linsert：在特定位置插⼊元素。
• 语法：linsert key BEFORE|AFTER pivot element
• 时间复杂度：O(N)，N 指的是 list 中元素的个数。
• 返回值：插入后的 list 长度。

万一要插入的列表中，基准值存在多个，怎么办？

linsert 进行插入的时候，要根据基准值，找到对应的位置，从左往右找，第一个符合基准值的位置即可。

• lrem：删除 list 中的元素，具体删除的方法如下。
• 语法：lrem key count element
  • 当 count > 0 时：从前往后，删除 |count| 个值为 element 的元素。
  • 当 count < 0 时：从后往前，删除 |count| 个值为 element 的元素。
  • 当 count = 0 时：删除所有值为 element 的元素。
• 时间复杂度：O(N + M)，N 是 list 的长度，M 是要删除的元素个数。
• 返回值：返回成功删除的元素个数。

• ltrim：保留区间内的元素，删除区间外的元素。
• 语法：ltrim key start stop
• 时间复杂度：O(N)，N 是要删除的区间内元素个数。
• 返回值：返回 OK

lset、llen

• lset：根据下标，修改元素。
• 语法：lset key index element
• 时间复杂度：O(N)，N 指的是 list 中元素的个数。
• 返回值：下标未越界时，返回OK，下标越界时，报错。

• llen：获取 list 长度。
• 语法：llen key
• 时间复杂度：O(1)
• 返回值：list 的长度。

阻塞版本命令：blpop、brpop

• 阻塞：当前的线程不走了，代码不继续执行了，会满足一定的条件之后，被唤醒。
• 阻塞队列：多线程的时候，讲了一个基于 “阻塞队列” 的 “生产者消费者模型”，使用队列作为中间的 “交易场所”，期望这个队列有两个特性：
  • 是线程安全的。
  • 在某些情况下，产生阻塞。
    • 如果队列为空，尝试出队列时，就会产生阻塞，直到队列不为空时，阻塞解除。
    • 如果队列为满，尝试入队列时，就会产生阻塞，直到队列不为满时，阻塞解除。
• Redis 中的 list 也相当于 “阻塞队列” 一样。
  • 线程安全，是通过单线程模型支持的。
  • 阻塞，则只支持 “队列为空” 的情况，不考虑 “队列为满” 的情况。

lpop、rpop 是非阻塞版本，而 blpop 和 brpop 是阻塞版本，区别如下：

• 在列表中有元素的情况下，阻塞和非阻塞表现是一致的。
• 但如果列表中没有元素，非阻塞版本会直接返回 nil，但阻塞版本会根据 timeout 阻塞一段时间，阻塞期间 Redis 可以执行其他命令，但要求执行该命令的客户端会表现为阻塞状态。
  • 此处的 blpop 和 brpop 看起来好像消耗很久，但实际上并不会对 Redis 服务器产生负面影响，类似 IO多路转接。
• 命令中如果设置了多个 key，那么会从左向右进行遍历 key，一旦有一个 key 对应的列表中可以弹出元素，命令立即返回。
  • blpop 和 brpop 都是可以同时去尝试获取多个 key 的列表元素，多个 key 对应多个 list，这多个 list 中，哪个有元素了，就会返回哪个元素，类似 IO多路转接。
• 如果多个客户端同时多个 key 执行 pop，则最先执行命令的客户端会得到弹出的元素。

阻塞版本的 blpop 和 非阻塞版本 lpop 的区别：

• blpop：头删的阻塞版本。
• 语法：blpop key [key ...] timeout
  • 此处可以指定一个 key 或者 多个key，每个 key 的对应一个 list
  • 如果这些 list 有任何一个非空，blpop 都能够把这里的元素给获取到，立即返回。
  • 如果这些 list 都为空，此时就需要阻塞等待，等待其他客户端王这些 list 中插入元素。
  • 此处还可以指定超时时间 timeout，单位是秒 (Redis 6 中允许设定为小数，Redis 5 中必须是整数)
• 时间复杂度：O(1)
• 返回值：取出的元素或者 nil

针对一个非空的列表进行操作：

返回的结果相当于一个二元组 (类似 pair)，一方是告诉我们当前的水来自于哪个 list，另一方面告诉我们获取到的数据是什么。

针对一个空的列表进行操作：

先打开一个客户端1，先对多个列表进行 blpop 操作，此时由于列表中没有数据，这是就会阻塞。再打开另一个客户端2，往列表中插入数据后，客户端1 解决阻塞，头删数据并返回。

针对多个 key 进行操作：

先打开一个客户端1，先进行 blpop 操作，此时由于这些列表中都没有数据，这是就会阻塞。再打开另一个客户端2，往其中一个列表中插入数据后，客户端1 解决阻塞，存在数据的列表头删数据并返回。

针对多个客户端 blpop 进行操作：

开启连个客户端都进行 blpop 操作，另一个客户端往列表中插入数据，此时第一个执行 blpop 的客户端，返回数据。

• brpop 的效果和 blpop 完全一样，就不演示了。
• 此处的 blpop 和 brpop 这两命令，虽然可以一定程度上满足 “消息队列” 这样的需求，但是整体来说还是比较有限的。

三. list 命令小结

命令	执行效果	时间复杂度
lpush key element [element …]	头插数据，list 不存在时，创建 list，插入数据	O(1)
lpushx key element [element …]	头插数据，list 不存在时，不会创建 list，插入数据失败	O(1)
rpush key element [element …]	尾插数据，list 不存在时，创建 list，插入数据	O(1)
rpushx key element [element …]	尾插数据，list 不存在时，不会创建 list，插入数据失败	O(1)
lpop key	头删数据	O(1)
rpop key	尾删数据	O(1)
blpop key [key …] timeout	阻塞头删数据	O(1)
brpop key [key …] timeout	阻塞尾删数据	O(1)
lindex key index	查找下标的数据	O(N)
lrange key start stop	查找区间内的数据	O(N)
linsert key BEFORE	AFTER pivot element	插入数据
lrem key count element	移除数据	O(N)
ltrim key start stop	保留区间内的数据	O(N)
lset key index element	修改下标的数据	O(N)
llen key	获取 list 的长度	O(1)

四. list 内部编码方式

• ziplist (压缩列表)：当列表的元素个数小于 list-max-ziplist-entries 配置 (默认 512个)，同时列表中每个元素的长度都小于 list-max-ziplist-value 配置 (默认 64 字节) 时，Redis 会选用 ziplist 来作为列表的内部编码实现来减少内存消耗。
  • 当元素的个数多了，操作起来效率会降低。
• linkedlist (链表)：当列表类型无法满足 ziplist 的条件时，Redis 会使用 linkedlist 作为列表的内部实现。
• quicklist：相当于链表和压缩列表的结合，整体还是一个链表，链表的每个节点是一个压缩列表，每个压缩列表都不让它太大，同时再把多个压缩列表通过链式结构连起来。
  • 优点：可以节约空间，同时效率也不会降低太多。

注意：现在的 list 内部的编码使用的是 quicklist，而不在使用 ziplist 和 linkedlist 了。

五. list 使用场景

缓存功能

微博 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:<uid>:mblogs 作为微博的键：

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

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

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

此方案在实际中可能存在两个问题：

• 如果每次分页获取的微博个数较多，需要执行多次 hgetall 操作，此时可以考虑使用 pipeline (流水线) 模式批量提交命令，或者微博不采用哈希类型，而是使用序列化的字符串类型，使用 mget 获取。
  • 当前一页中有多少数据不确定，可能会导致下面的循环比较大，从而执行多次 hgetall，也就是很多的网络请求。
  • 流水线：虽然我们是多个 Redis 命令，但是把这些命令合并成一个网络请求进行通信，可以大大降低客户端和服务器之间的交互次数。
• 分裂获取文章时，lrange 在列表两端表现较好，获取列表中间的元素表现较差，此时可以考虑将列表做拆分。
  • 假设摸个用户发了 1w 哥微博，list 的长度就是 1w，就可以把这 1w 哥微博拆分成 10 份，每个就是 1k，如果是想获取到 5k 个左右的微博，就可以先找到哪个列表，再进行某个方向的遍历操作，找到微博，提高效率。

消息队列

Redis：阻塞消息队列模型

Redis 可以使用 lpush + brpop 命令组合实现经典的阻塞式生产者-消费者模型队列，生产者客户端使用 lpush 从列表左侧插入元素，多个消费者客户端使用 brpop 命令阻塞式地从队列中 “争抢” 队首元素。通过多个客户端来保证消费的负载均衡和高可用性。

• Redis 是基于 多路转接 的单线程模型，所有命令的执行是串行的，是线程安全的。
• brpop 这个操作是阻塞操作，当列表为空的时候，brpop 就会阻塞等待，一直等到其它客户端 push 元素，谁先执行 brpop 操作，谁就可以拿到这个新来的元素。像这样的设定，就能构成一个 “轮询” 式的效果。
• 假设消费者执行的顺序是 1、2、3，当新元素到达之后，首先是消费者 1 拿到元素 (按照执行 brpop 命令的先后顺序来决定谁获取到的)，消费者 1 拿到元素之后，也就从 brpop 中返回了 (相当于这个命令执行完了)，如果消费者 1 还想继续消费，就需要重新执行 brpop，此时再来一个新的元素过来，就是消费者 2 拿到该元素，也从 brpop 中返回，如果消费者 2 还想继续消费，也需要重新执行 brpop，再来一个新元素，就是消费者 3 拿到这个元素。

Redis：分频道阻塞消息队列模型

Redis 同样使用 lpush + brpop 命令，但通过不同的键模拟频道的概念，不同的消费者可以通过 brpop 不同的键值，实现订阅不同频道的理念。

多个频道/列表，这种场景是非常常见的，例如：日常使用的一些程序，抖音。

• 有一个频道，来传输 短视频 数据。
• 有一个频道，来传输 弹幕 数据。
• 有一个频道，来传输 点赞、转发、收藏 数据。
• 有一个频道，来传输 评论 数据。
• 搞成多个频道，就可以在某种数据发生问题的时候，不会造成其它数据的影响，做到解耦合。