列表

列表操作

alt text

注意：list内部的编码方式，并非是一个简单的数组，而是更接近于双端队列。

alt text

列表特点

  1. 列表中的元素是有序的，这意味着可以通过索引下标获取某个元素或者某个范围的元素列表。
  2. 区分获取和删除的区别。lindex能获取到元素的值，lrem也能返回被删除元素的值。
  3. 列表的元素是可以重复的。hash类型，field是不能重复的。

因为当前的List，头和尾都可以高效的插入和删除元素，就可以把这个list当做一个栈/队列来使用了。

相关指令

非阻塞版本命令

LPUSH

  • 功能：将一个或者多个元素从头插到list中。
  • 时间复杂度：$O(1)$。
  • 返回值：插入list1之后的长度。
  • 注意：如果key已经存在，并且key对应的value类型，不是list，此时lpush就要报错。
1
2
3
4
5
6
LPUSH key element [element...]

127.0.0.1:6379> lpush key 1 2 3 4
(integer) 4
127.0.0.1:6379> lpush key 5 6 7 8
(integer) 8

LRANGE

  • 功能：查看list中start到end区间的元素。
  • 注意：redis打印出的序号是结果集专用的序号。
1
2
3
4
5
6
7
8
9
10
11
LRANGE key start stop

27.0.0.1:6379> lrange key 0 -1
1) "8"
2) "7"
3) "6"
4) "5"
5) "4"
6) "3"
7) "2"
8) "1"

在Redis中如果出现越界访问的情况，是直接尽可能的获取到给定区间的元素，如果给定区间的元素，如果给定区间非法，比如超出下标，就会尽可能的获取对应的内容。此处越界下标的处理方式，更接近于python的处理方式。

缺点：程序员不一定能在第一时间发现问题。
优点：效率是最高的。

1
2
3
4
5
6
7
8
9
127.0.0.1:6379> lrange key 0 100
1) "8"
2) "7"
3) "6"
4) "5"
5) "4"
6) "3"
7) "2"
8) "1"

LPUSHX

功能：在key存在时，将一个或者多个元素头插到list中，不存在，直接返回。
时间复杂度：$O(1)$。
返回值：插入后list的长度。

1
2
3
4
5
6
LPUSHX key element [element ...]

127.0.0.1:6379> lpushx key1 1 2 3 4
(integer) 0
127.0.0.1:6379> lrange key1 0 -1
(empty list or set)

RPUSH

功能：将一个或者多个元素尾插到list中
时间复杂度：$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
RPUSH key element [element ...]

127.0.0.1:6379> rpush key 1 2 3 4
(integer) 4
127.0.0.1:6379> rpush key 5 6 7 8
(integer) 8
127.0.0.1:6379> lrange key 0 -1
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"
7) "7"
8) "8"

RPUSHX

功能：将一个或者多个元素尾插到list中，不存在，直接返回。
时间复杂度：$O(1)$

1
2
3
4
5
6
127.0.0.1:6379> keys *
1) "key"
127.0.0.1:6379> rpushx key 9 10 11 12
(integer) 12
127.0.0.1:6379> rpushx key1 9 10 11 12
(integer) 0

LPOP

功能：list头删
时间复杂度：O(1)
返回值：取出的元素或者nil

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LPOP key

127.0.0.1:6379> lpop key
"1"
127.0.0.1:6379> lpop key
"2"
127.0.0.1:6379> lrange key 0 -1
 1) "3"
 2) "4"
 3) "5"
 4) "6"
 5) "7"
 6) "8"
 7) "9"
 8) "10"
 9) "11"
10) "12"

RPOP

功能：list尾删
时间复杂度：O(1)
返回值：取出的元素或者nil

1
2
3
4
5
6
7
8
9
10
11
12
13
RPOP key [count]

127.0.0.1:6379> rpop key
"12"
127.0.0.1:6379> rpop key
"11"
127.0.0.1:6379> lrange key 0 -1
1) "5"
2) "6"
3) "7"
4) "8"
5) "9"
6) "10"

LINDEX

功能：获取从左数第index个位置的元素，如果下标非法，返回的是空值

1
2
3
4
5
6
LINDEX key index

127.0.0.1:6379> lindex key 1
"6"
127.0.0.1:6379> lindex key -1
"10"

LINSERT

功能：在第一个特定元素的位置插入元素
返回值：返回插入之后链表的长度，选择插入的位置不存在时，返回-1。
时间复杂度：$O(N)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LINSERT key <BEFORE | AFTER> pivot element

127.0.0.1:6379> linsert key before 4 100
(integer) -1
127.0.0.1:6379> lrange key 0 -1
1) "5"
2) "6"
3) "7"
4) "8"
5) "9"
6) "10"
127.0.0.1:6379> linsert key before 5 100
(integer) 7
127.0.0.1:6379> lrange key 0 -1
1) "100"
2) "5"
3) "6"
4) "7"
5) "8"
6) "9"

LLEN

功能：返回list长度。
时间复杂度：$O(N)$

1
2
3
4
5
6
7
8
9
10
127.0.0.1:6379> lrange key 0 -1
1) "100"
2) "5"
3) "6"
4) "7"
5) "8"
6) "9"
7) "10"
127.0.0.1:6379> llen key
(integer) 7

LREM

功能：删除list中的key
时间复杂度：$O(N + M)$

1
2
3
4
5
LREM key count element

count > 0：从左往右删除2个
count < 0：从右往左删除2个
count = 0：全部删除

LRTIM

功能：保留start和stop之间区间内的元素（区间外面两边的元素就直接被删除了）
时间复杂度：$O(N)$

1
2
3
4
5
6
7
8
9
10
11
LTRIM key start stop

127.0.0.1:6379> rpush key 1 2 3 4 5 6 7 8
(integer) 8
127.0.0.1:6379> ltrim key 2 5
OK
127.0.0.1:6379> lrange key 0 -1
1) "3"
2) "4"
3) "5"
4) "6"

LSET

功能：根据下标修改元素。注意，LSET越界会报错。
时间复杂度：$O(N)$

1
2
3
4
5
6
7
8
9
10
11
LSET key index element

127.0.0.1:6379> lset key 2 100
OK
127.0.0.1:6379> lrange key 0 -1
1) "3"
2) "4"
3) "100"
4) "6" 
127.0.0.1:6379> lset key 10 100
(error) ERR index out of range

阻塞版本命令

blpop和brpop是lpop和rpop的阻塞版本，和对应非阻塞版本的作用基本一致。

  • 列表中有元素的情况下，阻塞和非阻塞表现是一致的。如果列表中没有元素，非阻塞版本就会理解返回nil，但阻塞版本会根据timeout，阻塞一段时间，期间redis可以执行其他命令，但要求执行该命令的客户端会表现为阻塞态。
  • 命令中如果设置了多个键，那么会从左往右进行遍历键，一旦有一个键对应的列表中可以弹出元素，命令立即返回。
  • 如果对个客户端同时多一个键执行pop，则最先执行命令的客户端会弹出的元素。
  1. 如果list中存在元素，blpop和brpop就和lpop以及rpop作用完全相同。
  2. 如果list中不存在元素，blpop和brpop就会产生阻塞，一直阻塞到队列不空为止。

BLPOP

此处可以指定一个或者多个key，每个key都对应一个list。

  • 如果这些list中有任何一个非空，blpop都能够把这里的元素立刻获取到，立刻返回。
  • 如果这些list1都为空，此时就需要阻塞等待，等待其他客户端往这些list中插入元素了。
1
BLPOP key [key....] timeout
  1. 针对一个非空的列表进行操作：

返回的结果相当于一个pair(二元组)

  • 一方面告诉我们当前的数据来自哪个key
  • 一方面告诉我们取到的数据是什么。
1
2
3
127.0.0.1:6379> blpop key 0
1) "key"
2) "3"
  1. 针对一个空的列表进行操作：
1
2
3
4
5
6
127.0.0.1:6379> blpop key 100
1) "key"
2) "1"
(10.06s)
127.0.0.1:6379> rpush key 1 2 3 4
(integer) 4

命令总结

操作类型 命令 时间复杂度
添加 rpush key value [value...] O(k)，k元素个数
lpush key value [value...] O(k)，k元素个数
linsert key before | after pivot value O(n)，n是pivot距离头尾的距离
查找 lrange key start end O(s + n)，s是偏移量，n是start到end
lindex key index O(n)，n是元素的偏移量
llen key O(1)
删除 lpop key O(1)
rpop key O(1)
lremkey count value O(k)，k是元素个数
lremkey key start end O(k)，k是元素个数
修改 lset key index value O(n)，n是索引偏移量
阻塞操作 lset key index value O(1)

内部编码

对于redis以前版本：

  • ziplist（压缩列表）：当列表的元素个数小于list-max-ziplist-entries配置（默认512字节），同时每个列表的长度都小于list-max-ziplist-entries配置（默认64字节）时，Redis会选用ziplist来作为列表的内部编码来减少内存消耗。
  • linkedlist（链表）：当列表类型无法满足ziplist条件时，Redis会选用linkedlist作为列表的内部实现。

对于Redis现在的版本：

  • quicklist：quicklist相对于是链表和压缩列表的结合。整体还是一个链表，链表的节点，是一个压缩列表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.   
# For a fixed maximum size, use -5 through -1, meaning:      
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2

应用场景

用list作为数组这样的结构，来存储多个元素。

消息队列

alt text

消费者通过brpop从队列中取任务。当list为空时，brpop就会阻塞等待，一直等到其他客户端想list中push了元素。

假设消费者执行顺序是：1 2 3

  1. 当新元素到达之后，首先是消费者1拿到元素。
  2. 消费之1拿到元素之后，也就从brpop返回了。如果消费者1还想继续消费，就需要重新执行brpop。
  3. 此时再来一个新元素过来，就是消费者2拿到该元素也从brpop中返回。如果消费者2还想继续消费，也需要重新执行brpop。

分频道的消息队列

对于抖音来说：有一个通道来传输短视频数据，还可以有一个通道来传输弹幕，还可以有一个通道来传输点赞，转发，收藏数据。还可以有通道来传输评论数据。

alt text

微博Timeline

每个用户都有属于自己的Timeline（微博列表），现在需要分页展示文章列表。此时可以考虑使用列表，因为列表不但是有序的，同时支持按照索引范围获取元素。

  1. 每篇微博使用哈希存储，例如微博中3个属性：title、timestamp、content
1
2
3
hmset mblog:1 title xx timestamp ... content xxx
...
hmset mblog:n title xx timestamp ... content xxx
  1. 向用户timeline1添加微博，user::mblogs作为微博的jian键
1
2
3
lpush user:1:mblogs mblogs:1 mblog:3
...
lpush user:k:mblogs mblog:9
  1. 分页获取用户的Timeline，例如用户的前10篇微博
1
2
3
keylist = lrange user:1:mblogs 0 9
for key in keylist
    hgetallkey

此方案在实际中存在问题：

  1. 1 + n问题。即如果每次分页获取的微博个数较多，需要执行多次hgetall操作，此时可以考虑使用pipline流水线（将多个命令合并成一个网络请求进行通信）模式批量提交命令。或者微博不采用哈希类型，而是使用序列化的字符串类型，使用mget获取。
  2. 分裂获取文章时，lrange在列表两端表现较好，获取列表中间的元素表现较差，此时可以考虑将列表做拆分。