Redis（六）：list/lpush/lrange/lpop 命令源码解析

上一篇讲了hash数据类型的相关实现方法，没有茅塞顿开也至少知道redis如何搞事情的了吧。

本篇咱们继续来看redis中的数据类型的实现: list 相关操作实现。

同样，我们以使用者的角度，开始理解list提供的功能，相应的数据结构承载，再到具体实现，以这样一个思路来理解redis之list。

零、redis list相关操作方法

从官方的手册中可以查到相关的使用方法。

1> BLPOP key1 [key2] timeout

功能: 移出并获取列表的第一个元素， 如果列表没有元素会阻塞列表直到等待超时或发现可弹出元素为止。（LPOP的阻塞版本）

返回值: 获取到元素的key和被弹出的元素值

2>BRPOP key1 [key2 ] timeout

功能: 移出并获取列表的最后一个元素， 如果列表没有元素会阻塞列表直到等待超时或发现可弹出元素为止。（RPOP 的阻塞版本）

返回值: 获取到元素的key和被弹出的元素值

3>BRPOPLPUSH source destination timeout

功能: 从列表中弹出一个值，将弹出的元素插入到另外一个列表中并返回它；如果列表没有元素会阻塞列表直到等待超时或发现可弹出元素为止。（RPOPLPUSH 的阻塞版本）

返回值: 被转移的元素值或者为nil

4>LINDEX key index

功能: 通过索引获取列表中的元素

返回值: 查找到的元素值,超出范围时返回nil

5>LINSERT key BEFORE|AFTER pivot value

功能: 在列表的元素前或者后插入元素

返回值: 插入后的list长度

6>LLEN key

功能: 获取列表长度

返回值: 列表长度

7>LPOP key

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

返回值: 第一个元素或者nil

8>LPUSH key value1 [value2]

功能: 将一个或多个值插入到列表头部

返回值: 插入后的list长度

9>LPUSHX key value

将一个值插入到已存在的列表头部，如果key不存在则不做任何操作

返回值: 插入后的list长度

10>LRANGE key start stop

功能: 获取列表指定范围内的元素 （包含起止边界）

返回值: 值列表

11>LREM key count value

功能: 移除列表元素, count>0:移除正向匹配的count个元素,count

返回值: 移除的元素个数

12>LSET key index value

功能: 通过索引设置列表元素的值

返回值: OK or err

13>LTRIM key start stop

功能: 对一个列表进行修剪(trim)，就是说，让列表只保留指定区间内的元素，不在指定区间之内的元素都将被删除。

返回值: OK

14>RPOP key

功能: 移除列表的最后一个元素，返回值为移除的元素。

返回值: 最后一个元素值或者nil

15>RPOPLPUSH source destination

功能: 移除列表的最后一个元素，并将该元素添加到另一个列表并返回

返回值: 被转移的元素

16>RPUSH key value1 [value2]

功能: 在列表中添加一个或多个值

返回值: 插入后的list长度

17>RPUSHX key value

功能: 为已存在的列表添加值

返回值: 插入后的list长度

redis中的实现方法定义如下:

一、list相关数据结构

说到list或者说链表，我们能想到什么数据结构呢？单向链表、双向链表、循环链表... 好像都挺简单的，还有啥？？我们来看下redis 的实现:

二、rpush/lpush 新增元素操作实现

rpush是所尾部添加元素，lpush是从头部添加元素，本质上都是一样的，redis实际上也是完全复用一套代码。

总体来说，redis的list实现不是纯粹的单双向链表，而是 使用双向链表+ziplist 的方式实现链表功能，既节省了内存空间，对于查找来说时间复杂度也相对小。我们用一个时序图来重新审视下：

三、lindex/lrange/rrange 查找操作

读数据是数据库的一个另一个重要功能。一般来说，有单个查询，批量查询，范围查询之类的功能，咱们就分头说说。

对于范围查找来说，按照redis之前的套路，有可能是在单个查找的上面再进行循环查找就可以了，是否是这样呢？我们来看看：

看起来并没有利用单个查找的代码，而是使用迭代器进行操作。看起来不难，但是有点绕，我们就用一个时序图来重新表达下：

四、lrem 删除操作

增删改查，还是要凑够的。删除的操作，自然是要配置数据结构来做了，比如: 如何定位要删除的元素，删除后链表是否需要重排？

delete 操作总体来说就是一个迭代，比对，删除的操作，细节还是有点多的，只是都是些我们前面说过的技术，也就无所谓了。

五、lpop 弹出队列

这个功能大概和删除的意思差不多，就是删除最后一元素即可。事实上，我们也更喜欢使用redis这种功能。简单看看。

弹出一个元素，大概分三步：

1. 获取头节点或尾节点;

2. 从ziplist中获取第一个元素或最后一个元素;

3. 删除头节点或尾节点;

六、blpop 阻塞式弹出元素

算是阻塞队列吧。我们只想看一下，像本地语言实现的阻塞，我们知道用锁+wait/notify机制。redis是如何进行阻塞的呢？

redis阻塞功能的实现: 使用一个 db->blocking_keys 的列表来保存需要阻塞的请求，在下一次循环时，进行扫描这些队列的条件是否满足，从而决定是否继续阻塞或者取出。

思考：从上面实现中，有个疑问：如何保证最多等待 timeout 时间或者最多循环多少次呢？你觉得应该如何处理呢？

OK, 至此，整个list数据结构的解析算是完整了。