List详解

要理解Redis的List类型，我们需要从基本特性、底层实现原理（重点是quicklist）、操作逻辑和应用场景四个维度展开。

一、List类型的基本特性

Redis的List是有序、可重复的字符串列表，支持两端高效操作（头部/尾部插入、删除），是Redis中最常用的数据结构之一。

1. 核心特性

• 有序性：元素按插入顺序排列，可通过索引（lindex）访问指定位置的元素。
• 可重复性：允许存储相同的字符串元素（如lpush list1 a a，列表会有两个a）。
• 二进制安全：元素可以是任意二进制数据（如图片、序列化对象），包括空字符串（""）。
• 两端操作高效：头部（lpush/lpop）和尾部（rpush/rpop）的插入/删除操作时间复杂度为O(1)（忽略极端情况，如ziplist扩容）。

2. 常用命令示例

命令	功能说明	示例	结果（列表状态）
lpush key value	向列表头部插入元素	lpush list1 a b c	[c, b, a]
rpush key value	向列表尾部插入元素	rpush list1 d e	[c, b, a, d, e]
lpop key	从列表头部弹出元素（删除并返回）	lpop list1	返回c，列表变为[b, a, d, e]
rpop key	从列表尾部弹出元素	rpop list1	返回e，列表变为[b, a, d]
lrange key start end	获取列表指定范围的元素（0开始，-1表示末尾）	lrange list1 0 -1	返回["b", "a", "d"]
llen key	获取列表长度	llen list1	返回3
lindex key index	获取指定索引的元素	lindex list1 1	返回a

二、底层实现原理：从ziplist到quicklist

Redis的List类型没有直接使用传统的双向链表（linkedlist），而是通过组合数据结构优化内存和性能。演变过程如下：

• Redis 3.2之前：使用ziplist（压缩列表）和linkedlist（双向链表）的组合（小列表用ziplist，大列表用linkedlist）。
• Redis 3.2及之后：默认使用quicklist（快速列表），彻底替代了上述组合，成为List的唯一实现。

1. 为什么需要quicklist？

传统linkedlist的问题：

• 每个节点需要存储prev/next指针（共16字节，64位系统），内存开销大（例如，存储100万个元素需要额外16MB指针空间）。
• 节点分散在内存中，无法利用CPU缓存（缓存命中率低）。

传统ziplist的问题：

• ziplist是连续内存块，插入/删除元素时需要移动后续元素（时间复杂度O(n)），当列表过大时，性能急剧下降。

quicklist的设计目标：结合ziplist的内存高效和linkedlist的插入/删除高效，解决两者的痛点。

2. quicklist的结构

quicklist是双向链表，每个节点（称为quicklistNode）是一个**ziplist**（压缩列表）。简单来说，quicklist = 双向链表 + 多个ziplist节点。

（1）quicklist的整体结构

typedef struct quicklist {
    quicklistNode *head;  // 指向第一个节点
    quicklistNode *tail;  // 指向最后一个节点
    unsigned long count;  // 列表总元素个数
    unsigned int len;     // 节点个数（即ziplist的数量）
    int fill : 16;        // 每个ziplist的最大大小（由list-max-ziplist-size配置）
    unsigned int compress : 16;  // 压缩深度（由list-compress-depth配置）
} quicklist;

（2）quicklistNode的结构（每个节点是一个ziplist）

typedef struct quicklistNode {
    struct quicklistNode *prev;  // 前一个节点指针
    struct quicklistNode *next;  // 后一个节点指针
    unsigned char *zl;           // 指向ziplist的指针（如果节点未压缩）
    unsigned int sz;             // ziplist的总字节数（包括表头和表尾）
    unsigned int count : 16;     // ziplist中的元素个数
    unsigned int encoding : 2;   // 编码方式（0=RAW，1=LZF压缩）
    unsigned int container : 2;  // 容器类型（0=ziplist，1=其他）
    unsigned int recompress : 1; // 是否需要重新压缩（用于临时解压操作）
    unsigned int attempted_compress : 1; // 是否尝试过压缩（用于统计）
    unsigned int extra : 10;     // 预留字段
} quicklistNode;

3. ziplist的结构（quicklist节点的内部实现）

ziplist是quicklist的核心内存优化组件，它将多个元素紧凑存储在连续内存块中，避免了指针开销。其结构如下：

+--------+--------+--------+--------+--------+--------+--------+
| zlbytes | zltail | zllen  | entry1 | entry2 | ...    | zlend  |
+--------+--------+--------+--------+--------+--------+--------+

• zlbytes：ziplist的总字节数（4字节），用于快速计算内存大小。
• zltail：最后一个元素的偏移量（4字节），用于快速定位尾部元素（反向遍历）。
• zllen：元素个数（2字节），如果超过65535，则需要遍历整个列表计算。
• entry：元素节点（多个），每个元素由prevlen（前一个元素长度）、encoding（编码方式）、data（数据）组成。
• zlend：结束标记（1字节，固定为0xFF）。

（1）元素节点（entry）的结构

每个元素节点的结构取决于前一个元素的长度和当前元素的数据类型：

+----------+----------+----------+
| prevlen  | encoding | data     |
+----------+----------+----------+

• prevlen：前一个元素的长度（1或5字节）：
  • 若前一个元素长度 < 254，则用1字节存储（值为前一个元素的长度）。
  • 若前一个元素长度 ≥ 254，则用5字节存储（第一个字节为0xFE，后面4字节为前一个元素的长度）。
• encoding：数据类型和长度（1-5字节）：
  • 字符串类型：高两位为00，后面几位表示字符串长度（如00xxxxxx表示长度为xxxxxx的短字符串，01xxxxxx xxxxxxxx表示长度为xxxxxx xxxxxxxx的中长字符串）。
  • 整数类型：高两位为10，后面几位表示整数类型（如10000000表示8位整数，10000001表示16位整数，10000010表示24位整数，10000011表示32位整数，10000100表示64位整数）。
• data：实际数据（根据encoding的类型存储，如字符串的字节流或整数的二进制表示）。

4. quicklist的关键配置（优化内存和性能）

Redis通过以下配置调整quicklist的行为，平衡内存占用和操作效率：

• list-max-ziplist-size：控制每个ziplist节点的最大大小（默认值为-2）：
  • 正数：表示每个ziplist最多存储N个元素（如5表示每个节点最多5个元素）。
  • 负数：表示每个ziplist的最大字节数（如-2表示最多8192字节，-1表示最多4096字节）。
• list-compress-depth：控制quicklist的压缩深度（默认值为0）：
  • 0：不压缩任何节点（默认）。
  • 1：压缩head和tail节点之外的所有节点（即中间节点）。
  • 2：压缩head和tail节点之外的两层节点（依此类推）。
  • 压缩算法使用LZF（轻量级、快速），用于减少中间节点的内存占用（中间节点访问频率低）。

三、quicklist的操作逻辑

quicklist的操作（如lpush/rpush/lpop/rpop）会根据节点的ziplist是否有剩余空间决定是直接插入还是创建新节点。

1. 头部插入（lpush）

• 步骤1：检查quicklist的head节点（第一个ziplist）是否有剩余空间（根据list-max-ziplist-size判断）。
• 步骤2：若有空间，则直接将元素插入到head节点的ziplist头部（ziplist的头部插入需要移动后续元素，但ziplist很小，开销可接受）。
• 步骤3：若无空间，则创建一个新的quicklistNode（包含新的ziplist），将元素插入到新节点的ziplist头部，然后将新节点添加到quicklist的头部（head指针指向新节点）。

2. 尾部插入（rpush）

• 逻辑与lpush类似，但检查的是tail节点（最后一个ziplist）的剩余空间，插入到ziplist的尾部（ziplist的尾部插入不需要移动元素，效率更高）。

3. 头部弹出（lpop）

• 步骤1：从head节点的ziplist头部弹出元素（删除并返回）。
• 步骤2：若弹出后ziplist为空，则删除该head节点（head指针指向原head的next节点）。
• 步骤3：若head节点的ziplist非空，则更新quicklist的count（总元素个数）。

4. 范围查询（lrange）

• 步骤1：遍历quicklist的节点，找到包含起始索引和结束索引的ziplist节点。
• 步骤2：对于每个目标ziplist节点，遍历其内部元素，取出指定范围的元素。
• 注意：lrange的时间复杂度为O(k)（k为返回的元素个数），但遍历quicklist节点的开销很小（节点数量少）。

四、quicklist的优势

• 内存高效：每个ziplist节点紧凑存储元素，避免了linkedlist的指针开销（例如，存储100万个元素，quicklist的内存占用约为linkedlist的1/3）。
• 插入/删除高效：节点之间用双向链表连接，插入/删除节点的时间复杂度为O(1)（只需调整指针）；ziplist内部的插入/删除开销很小（因为ziplist的大小被list-max-ziplist-size限制，最多几千字节）。
• 支持压缩：中间节点可以压缩（list-compress-depth），进一步减少内存占用（例如，压缩后的ziplist大小可减少50%以上）。
• 兼容旧版本：quicklist的操作逻辑与旧版本的ziplist/linkedlist组合完全一致，无需修改应用代码。

五、List类型的应用场景

List的有序性和两端操作高效使其适合以下场景：

• 消息队列：用lpush向队列头部添加消息，用rpop（或brpop阻塞弹出）从队列尾部获取消息（例如，异步任务队列）。
• 最新消息列表：用lpush向列表头部添加最新消息，用lrange 0 9获取前10条最新消息（例如，朋友圈的“最新动态”）。
• 栈：用lpush入栈，用lpop出栈（后进先出）。
• 队列：用lpush入队，用rpop出队（先进先出）。
• 历史记录：用lpush添加历史记录，用ltrim限制列表长度（例如，用户的“最近浏览记录”，保留前100条）。

六、注意事项

• 避免大列表：List的长度过大（如超过100万个元素）会导致内存占用过高，且lrange等遍历操作会阻塞Redis进程（Redis是单线程）。
• 合理配置quicklist参数：
  • list-max-ziplist-size：设置过大（如-1=4096字节）会导致ziplist插入/删除效率下降；设置过小（如1）会导致quicklist节点过多，指针开销增加。建议根据元素大小调整（例如，元素是短字符串，可设置为-2=8192字节）。
  • list-compress-depth：设置为1或2即可（压缩中间节点），设置过大（如10）会导致压缩和解压缩的时间增加，影响性能。
• 使用brpop替代rpop：brpop是阻塞式弹出，当列表为空时，会等待直到有元素插入（避免轮询导致的CPU浪费）。

总结

Redis的List类型是有序、可重复的字符串列表，底层通过quicklist（双向链表+ziplist节点）实现，兼顾了内存效率和插入/删除性能。其核心优势是两端操作高效，适合需要有序存储、频繁插入/删除的场景（如消息队列、最新消息列表）。合理配置quicklist的参数（list-max-ziplist-size、list-compress-depth）可以进一步优化内存占用和性能。