演进历程
时间线对比
版本 | 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)实现,没有压缩存储的概念
特点
- 简单直接:每个List就是一个adlist
- 内存开销大:每个节点24字节 + 数据大小
- 无压缩:没有内存优化
- 通用性强:支持任意数据类型
// 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 /* 默认紧凑存储格式 */
关键变化总结
- Redis 2.6以前:List只有一种实现(adlist)
- Redis 2.6:引入ziplist,小列表使用压缩存储
- Redis 3.2:引入quicklist,统一使用quicklist实现
- Redis 5.0:引入listpack,作为ziplist的替代
- 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) |
压缩支持 | 无 | 无 | 无 | 有 |
关于压缩
- listpack本身没有压缩:它设计为紧凑的连续内存布局
- quicklist有压缩:可以对包含listpack的节点进行LZF压缩
- 压缩是分层的:listpack提供紧凑存储,quicklist提供压缩存储
内存开销对比
adlist节点
listNode: 24字节 + 数据大小
ziplist(已废弃)
连续内存块,无指针开销
listpack
紧凑存储,最小化元数据开销
quicklist节点
quicklistNode: 32字节 + listpack数据