演进历程

时间线对比

版本 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数据