Redis基本数据类型之List

2020-07-05

Redis List结构的数据存储是最常使用的一种之一,特别对于一些复杂的场景，如列表、队列、栈通过List结构都可以轻松去实现它。

1、简单介绍

Redis列表是简单的字符串列表，按照插入顺序排序。你可以添加一个元素导列表的头部（左边）或者尾部（右边）

一个列表最多可以包含 2^32 - 1 个元素 (4294967295, 每个列表超过40亿个元素)

2、常用命令

2.1、LPUSH-从列表头部（左边）设置值

LPUSH key value [value …]

将一个或多个值 value 插入到列表 key 的表头

如果有多个 value 值，那么各个 value 值按从左到右的顺序依次插入到表头

2.2、LPUSHX-存在Key时才从列表头部（左边）设置值

LPUSHX key value

将值 value 插入到列表 key 的表头，当且仅当 key存在并且是一个列表

2.3、RPUSH-从列表尾部（右边）设置值

RPUSH key value [value …]

将一个或多个值 value 插入到列表 key 的表尾(最右边)。

如果有多个 value 值，那么各个 value 值按从左到右的顺序依次插入到表尾

2.4、RPUSHX-存在Key时才从列表尾部（右边）设置值

RPUSHX key value

将值 value 插入到列表 key 的表尾，当且仅当 key存在并且是一个列表

2.5、LPOP-从头部弹出一个元素

LPOP key

移除并返回列表 key 的头元素，当 key 不存在时，返回 nil 。

2.6、RPOP-从尾部弹出一个元素

RPOP key

移除并返回列表 key 的尾部元素，当 key 不存在时，返回 nil 。

2.7、RPOPLPUSH-从源list的尾部弹出一个元素放入到目标list头部，并返回该元素

RPOPLPUSH source destination

命令 RPOPLPUSH 在一个原子时间内，执行以下两个动作：

将列表 source 中的最后一个元素(尾元素)弹出，并返回给客户端。
将 source 弹出的元素插入到列表 destination ，作为 destination 列表的的头元素

如果source不存在，nil则返回该值并且不执行任何操作。如果source和destination相同，该操作相当于从列表中删除最后一个元素，并将其作为列表的第一个元素推入，因此可以将其视为列表旋转命令。

2.8、LLEN-返回列表的长度

LLEN key

返回列表 key 的长度。

如果 key 不存在，则 key 被解释为一个空列表，返回 0 .如果 key 不是列表类型，返回一个错误。

2.9、LINDEX-获取列表指定下标的元素

LINDEX key index

返回列表 key 中，下标为 index 的元素。

下标(index)参数 start 和 stop 都以 0 为底，也就是说，以 0 表示列表的第一个元素，以 1 表示列表的第二个元素，以此类推。

你也可以使用负数下标，以 -1 表示列表的最后一个元素， -2 表示列表的倒数第二个元素，以此类推。

2.10、LRANGE-获取指定区间内的元素

LRANGE key start stop

返回列表 key 中指定区间内的元素，区间以偏移量 start 和 stop 指定。

下标(index)参数 start 和 stop 都以 0 为底，也就是说，以 0 表示列表的第一个元素，以 1 表示列表的第二个元素，以此类推。

你也可以使用负数下标，以 -1 表示列表的最后一个元素， -2 表示列表的倒数第二个元素，以此类推。

注意：这个区间是一个闭区间，两端的元素都会纳入其中

2.11、LSET设置指定下标的值

LSET key index value

将列表 key 下标为 index 的元素的值设置为 value 。

当 index 参数超出范围，或对一个空列表( key 不存在)进行 LSET 时，返回一个错误。

2.12、BLPOP-LPOP阻塞版本，list没有元素时，等待超时返回

BLPOP key [key …] timeout

它是 LPOP key 命令的阻塞版本，当给定列表内没有任何元素可供弹出的时候，连接将被 BLPOP命令阻塞，直到等待超时或发现可弹出元素为止。

当给定多个 key 参数时，按参数 key 的先后顺序依次检查各个列表，弹出第一个非空列表的头元素。

2.13、BRPOP-RPOP阻塞版本，list没有元素时，等待超时返回

BRPOP key [key …] timeout

它是 RPOP key 命令的阻塞版本，当给定列表内没有任何元素可供弹出的时候，连接将被 BRPOP命令阻塞，直到等待超时或发现可弹出元素为止。

当给定多个 key 参数时，按参数 key 的先后顺序依次检查各个列表，弹出第一个非空列表的尾部元素。

2.14、LTRIM-保留指定区间的元素

LTRIM key start stop

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

举个例子，执行命令 LTRIM list 0 2 ，表示只保留列表 list 的前三个元素，其余元素全部删除。

下标(index)参数 start 和 stop 都以 0 为底，也就是说，以 0 表示列表的第一个元素，以 1 表示列表的第二个元素，以此类推。

你也可以使用负数下标，以 -1 表示列表的最后一个元素， -2 表示列表的倒数第二个元素，以此类推。

3、内部实现

Redis中的列表对象在版本3.2之前，列表底层的编码是 ziplist 和 linkedlist 实现的，但是在版本3.2之后，重新引入了一个 quicklist 的数据结构，列表的底层都由quicklist实现

3.1、ziplist压缩列表

在mylist列表中添加三个元素

1	rpush mylist first second three

具体实现如图所示

关于ziplist结构及字段含义及内部实现请参照《Redis基本数据类型之Hash-压缩列表》

3.2、linkedlist 链表

在mylist列表中添加三个元素

1	rpush mylist first second three

具体实现如图所示

下面我们分析下linkedlist

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;

这就是linklist链表的定义，我们看到最关键的就是节点信息

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode;

由此我们发现每个节点中都会记录前后节点的指针信息，通过next和prev就会组成双端链表

完整的结构

3.3、quicklist快速列表

使用quicklist快速列表的原因：

双向链表在插入节点上复杂度很低，但它的内存开销很大，每个节点的地址不连续，容易产生内存碎片。

ziplist是存储在一段连续的内存上，存储效率高，但是它不利于修改操作，插入和删除数都很麻烦，复杂度高，而且其需要频繁的申请释放内存，特别是ziplist中数据较多的情况下，搬移内存数据太费时！

quicklist 是一个双向链表，并且是一个 ziplist 的双向链表，也就是说 quicklist 的每个节点都是一个 ziplist。

我们看下quicklist定义

typedef struct quicklist {
    // 表头节点
    quicklistNode *head;
    // 表尾节点
    quicklistNode *tail;
    // 所有ziplist中entry数量即列表中所有数据项的个数总和
    unsigned long count;        /* total count of all entries in all ziplists */
    // quicklist节点的个数 
    unsigned long len;          /* number of quicklistNodes */
    // ziplist大小限定，由list-max-ziplist-size给定
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    // 节点压缩深度设置，由list-compress-depth给定
    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;

重点字段说明：

fill ：ziplist 中 entry 能保存的数量,由 list-max-ziplist-size 配置项控制，表示了单个节点(quicklistNode)的负载比例(fill factor)，负数限制 quicklistNode 中的 ziplist 的字节长度, 正数限制 quicklistNode 中的 ziplist 的最大长度。

-5: 最大存储空间: 64 Kb <-- 通常情况下不要设置这个值
-4: 最大存储空间: 32 Kb <-- 非常不推荐
-3: 最大存储空间: 16 Kb <-- 不推荐
-2: 最大存储空间: 8 Kb <-- 推荐
-1: 最大存储空间: 4 Kb <-- 推荐
对于正整数则表示最多能存储到你设置的那个值, 当前的节点就装满了
通常在 -2 (8 Kb size) 或 -1 (4 Kb size) 时, 性能表现最好

compress ：一般收尾两端操作较频繁，中部操作相对较少，所以redis提供压缩深度配置，压缩深度,由 list-compress-depth 配置项控制，表示 quicklist 中的节点 quicklistNode, 除开最两端的 compress 个节点之后, 中间的节点都会被压缩（LZF压缩算法）。

0: 是个特殊值，表示都不压缩。这是Redis的默认值。
1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。
2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。
3: 表示quicklist两端各有3个节点不压缩，中间的节点压缩。
依此类推

看完整体我们看下具体节点的信息：

typedef struct quicklistNode {
    // 前置节点指针
    struct quicklistNode *prev;
    // 后置节点指针
    struct quicklistNode *next;
    // 数据指针，如果没有被压缩，就指向ziplist结构，反之指向quicklistLZF结构
    unsigned char *zl;
    // 表示指向ziplist结构的总长度(内存占用长度)
    unsigned int sz;             /* ziplist size in bytes */
    // ziplist里面包含的数据项个数
    unsigned int count : 16;     /* count of items in ziplist */
    // 编码方式，1--ziplist，2--quicklistLZF
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    // 预留字段，存放数据的方式，1--NONE，2--ziplist
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    // 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为1，之后再重新进行压缩
    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;

quicklistLZF

typedef struct quicklistLZF {
    // LZF压缩后占用的字节数
    unsigned int sz; /* LZF size in bytes*/
    // 柔性数组，指向数据部分
    char compressed[];
} quicklistLZF;

4、使用场景

lpush + lpop = stack(栈)

lpush + rpop = queue(队列)

lpush + ltrim = capped collection(有限集合)

lpush + brpop = message queue(消息队列)

本文作者： 顾明训
本文链接： https://www.itzones.cn/2020/07/05/Redis基本数据类型之List/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！