简策小栈

Appearance

List（列表） ​

1. 概述 ​

List是简单的字符串列表，按插入顺序排序。

常用命令：LPUSH、RPUSH、LPOP、RPOP、LRANGE、LINDEX、LSET

2. 底层数据结构 ​

2.1 三种编码 ​

编码说明适用场景
ziplist压缩列表，小列表少量元素
quicklist快速列表（Redis 3.2+）大列表
linkedlist双端链表，旧版本历史兼容

2.2 quicklist ​

Redis 3.2+使用quicklist作为List的底层实现：

quicklist = [quicklistNode1] → [quicklistNode2] → [quicklistNode3]
                ↓                    ↓                    ↓
            [ziplist]            [ziplist]            [ziplist]

设计思想：结合ziplist和linkedlist的优点

  • ziplist：内存紧凑，缓存局部性好
  • linkedlist：O(1)头尾操作

2.3 quicklistNode结构 ​

c
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;    // 1=原生,2=lzf压缩
    unsigned int container: 2;  // 1=ziplist,2=quicklistNode
    unsigned int recompress: 1; // 是否需要解压
    unsigned int attempted_compress: 1;
    unsigned int extra: 10;
} quicklistNode;

2.4 配置参数 ​

bash
# 压缩深度（两端各多少个节点不压缩）
list-compress-depth 0

# 单节点ziplist最大大小（字节）
list-max-ziplist-size -2

# 元素数量限制
list-max-ziplist-entries 512

3. 编码转换 ​

ziplist → quicklist → quicklist（压缩）

转换条件：

  • list-max-ziplist-size > 0：ziplist字节大小限制
  • list-max-ziplist-entries > 0：元素数量限制

4. 面试考点 ​

Q1: Redis List的底层实现？ ​

答案： Redis 3.2+使用quicklist作为List的底层实现，由多个ziplist节点组成双向链表。每个quicklistNode包含一个ziplist，平衡了内存紧凑性和头尾操作的O(1)复杂度。

Q2: 为什么用quicklist而不是linkedlist？ ​

答案： linkedlist每个节点独立分配内存，内存碎片化且缓存局部性差。quicklist将多个元素存储在一个ziplist中，减少内存分配，提高缓存命中率。综合了ziplist紧凑和linkedlist灵活的优点。

Q3: LPUSH和RPUSH的时间复杂度？ ​

答案： 都是O(1)。quicklist在头尾操作时直接操作对应的ziplist，无需遍历。

5. 应用场景 ​

5.1 消息队列 ​

bash
LPUSH queue:msg "msg1"
LPUSH queue:msg "msg2"
RPOP queue:msg    # "msg1"
RPOP queue:msg    # "msg2"

注意：Redis的list做消息队列有风险，缺少消息确认机制，建议使用Stream。

5.2 排行榜 ​

bash
LPUSH rank:user:1001 100    # 用户得分
LRANGE rank:user:1001 0 -1 # 获取排名列表

5.3 最新消息列表 ​

bash
LPUSH latest:news "news1"
LPUSH latest:news "news2"
LPUSH latest:news "news3"
LTRIM latest:news 0 99   # 只保留前100条
LRANGE latest:news 0 -1 # 获取最新100条

6. 实践问题 ​

Q: List如何实现异步队列？ ​

答案： 使用RPOPLPUSH或BLPOP/BRPOP实现可靠队列：

bash
# 生产者
RPUSH queue:task "task1"

# 消费者
BRPOP queue:task 0   # 阻塞获取
RPUSH queue:processed "task1"  # 处理完移到已处理队列

Q: 如何控制List内存占用？ ​

答案： 通过配置参数控制：

  • list-max-ziplist-size：单个ziplist最大字节
  • list-max-ziplist-entries：单个ziplist最大元素数
  • list-compress-depth：两端不压缩的节点数

最后更新: