演进历程

时间线对比

版本 List实现 特点
Redis 1.0-2.5 纯adlist 简单，内存开销大
Redis 2.6 adlist + ziplist 引入压缩存储
Redis 3.2 quicklist 结合链表和ziplist
Redis 5.0 quicklist + listpack 引入listpack
Redis 7.0 quicklist + listpack listpack成为默认

Redis版本演进

typedef struct redisObject {
    unsigned type:4;      // OBJ_LIST
    unsigned encoding:4;  // OBJ_ENCODING_XX
    // ...
    void *ptr;         
} robj;

redisObject结构本身没有变化，变化的是encoding字段的值和ptr指向的数据结构类型

2.6前

List类型完全使用adlist双向链表（OBJ_ENCODING_LINKEDLIST）实现，没有压缩存储的概念

特点

  1. 简单直接：每个List就是一个adlist
  2. 内存开销大：每个节点24字节 + 数据大小
  3. 无压缩：没有内存优化
  4. 通用性强：支持任意数据类型
// Redis 2.6以前的List类型的实现
// encoding = OBJ_ENCODING_LINKEDLIST
// ptr 指向 adlist (list *)

// List就是adlist
list *myList = listCreate();
#define OBJ_ENCODING_LINKEDLIST 4 /* List使用adlist实现 */

2.6

引入ziplist(OBJ_ENCODING_ZIPLIST)作为小列表的压缩存储

// List类型的实现
// 小列表：encoding = OBJ_ENCODING_ZIPLIST, ptr 指向 ziplist (unsigned char *)
// 大列表：encoding = OBJ_ENCODING_LINKEDLIST, ptr 指向 adlist (list *)

#define OBJ_ENCODING_LINKEDLIST 4 /* 大列表使用adlist */
#define OBJ_ENCODING_ZIPLIST 5    /* 小列表使用ziplist压缩 */

3.2

引入quicklist(OBJ_ENCODING_QUICKLIST)，结合了链表和ziplist的优点

链表 prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率

性能对比

特性 Redis 2.6以前 Redis 2.6+ Redis 3.2+
内存效率 低 中等 高
插入性能 O(1) O(1) O(1)
内存开销 24字节/节点 压缩存储 混合优化
压缩支持 无 有 有 
// List类型的实现
// encoding = OBJ_ENCODING_QUICKLIST
// ptr 指向 quicklist (quicklist *)
// quicklist内部使用ziplist作为节点存储

#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding */
#define OBJ_ENCODING_ZIPLIST 5    /* 用于quicklist节点 */
#define OBJ_ENCODING_QUICKLIST 9  /* List使用quicklist实现 */

5.0

引入listpack(OBJ_ENCODING_LISTPACK)，替代ziplist

// List类型的实现
// encoding = OBJ_ENCODING_QUICKLIST
// ptr 指向 quicklist (quicklist *)
// quicklist内部可以选择使用ziplist或listpack作为节点存储

#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding */
#define OBJ_ENCODING_ZIPLIST 5    /* 用于quicklist节点 */
#define OBJ_ENCODING_QUICKLIST 9  /* List使用quicklist实现 */
#define OBJ_ENCODING_LISTPACK 11  /* 新的紧凑存储格式 */

7.0

listpack成为默认紧凑存储格式，quicklist使用listpack节点

// List类型的实现
// encoding = OBJ_ENCODING_QUICKLIST
// ptr 指向 quicklist (quicklist *)
// quicklist内部默认使用listpack作为节点存储，ziplist被废弃

#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding */
#define OBJ_ENCODING_ZIPLIST 5    /* No longer used: old list/hash/zset encoding */
#define OBJ_ENCODING_QUICKLIST 9  /* List使用quicklist实现 */
#define OBJ_ENCODING_LISTPACK 11  /* 默认紧凑存储格式 */

关键变化总结

  1. Redis 2.6以前：List只有一种实现（adlist）
  2. Redis 2.6：引入ziplist，小列表使用压缩存储
  3. Redis 3.2：引入quicklist，统一使用quicklist实现
  4. Redis 5.0：引入listpack，作为ziplist的替代
  5. Redis 7.0：listpack成为默认，ziplist被废弃

使用场景分工

adlist

  • Redis内部管理（客户端、模块、事务）

  • 需要通用性和灵活性的场景

  • 频繁的插入/删除操作

ziplist

  • 已废弃，不再使用

listpack

  • Set/Hash/ZSet的小数据紧凑存储

  • quicklist的节点存储

  • 需要内存效率的场景

quicklist

  • List类型的用户数据存储

  • 大列表的高效操作

  • 需要平衡内存和性能的场景

链表相关数据结构比较

adlist（双向链表）

特点

  • 通用双向链表：每个节点都有前驱和后继指针

  • 通用性：使用void*存储任意数据类型

  • 灵活性：支持自定义复制、释放、匹配函数

  • 内存开销：每个节点需要额外的指针空间

使用场景

  • Redis内部管理：客户端列表、模块系统、事务处理

  • 非用户数据：服务器内部的数据结构管理

性能特点

// 内存开销
typedef struct listNode {
    struct listNode *prev;  // 8字节
    struct listNode *next;  // 8字节  
    void *value;           // 8字节
} listNode; // 总计24字节 + 数据大小

ziplist（压缩列表）- 已废弃

特点

  • 紧凑存储：连续内存块，无指针开销

  • 小数据优化：适合少量元素的存储

  • 插入/删除开销：需要重新分配内存

  • Redis 7.0中被listpack替代

使用场景

  • 历史版本：Redis 3.2-6.x中的小列表存储

  • 已废弃：不再用于新的数据存储

quicklist（快速列表）- List类型当前实现

特点

  • 混合结构：双向链表 + listpack节点

  • 平衡设计：结合链表和紧凑存储的优点

  • 压缩支持：节点可压缩（LZF）

  • 性能优化：适合大列表的高效操作

使用场景

  • List类型：Redis List类型的当前实现

  • 大列表：处理大量元素的列表操作

listpack（紧凑列表）- 新标准

特点

  • 改进的紧凑存储：比ziplist更高效的内存布局

  • 更好的操作性能：插入/删除操作优化

  • 支持更大数据量：比ziplist能处理更多元素

  • Redis 7.0+默认：替代ziplist成为紧凑存储标准

使用场景

  • Set类型：小集合的紧凑存储

  • Hash类型：小哈希表的紧凑存储

  • ZSet类型：小有序集合的紧凑存储

  • quicklist节点：作为quicklist的节点存储

对比表

性能对比

特性 adlist ziplist listpack quicklist
内存效率 低 高 高 中等
插入性能 O(1) O(n) O(n) O(1)
删除性能 O(1) O(n) O(n) O(1)
遍历性能 O(n) O(n) O(n) O(n)
随机访问 O(n) O(n) O(n) O(n)
压缩支持 无 无 无 有

关于压缩

  1. listpack本身没有压缩：它设计为紧凑的连续内存布局
  2. quicklist有压缩：可以对包含listpack的节点进行LZF压缩
  3. 压缩是分层的：listpack提供紧凑存储，quicklist提供压缩存储

内存开销对比

adlist节点

listNode: 24字节 + 数据大小

ziplist（已废弃）

连续内存块，无指针开销

listpack

紧凑存储，最小化元数据开销

quicklist节点

quicklistNode: 32字节 + listpack数据