Redis 数据结构 · 底层源码解析

基于 Redis 7.0 官方源码，深度剖析五大数据类型的底层实现

SDS · String QuickList · List Dict · Hash IntSet · Set SkipList · ZSet
🔤
SDS (Simple Dynamic String)
Redis 自研动态字符串，比 C 字符串更安全高效

💡 核心设计思想

  • len 字段：记录已用长度，O(1) 获取字符串长度
  • alloc 字段：记录已分配空间，支持惰性释放
  • flags 字段：低 3 位标识类型，高位存储短长度
  • 二进制安全：不依赖 \0 结尾，可存储任意字节
  • 空间预分配：小于 1MB 时翻倍扩容，大于 1MB 时每次 +1MB
📄 src/sds.hC Header
/* SDS 5 种头部结构，通过 flags 区分类型 */ /* sdshdr5: 低3位=类型, 高5位=长度(≤31)，未实际使用 */ struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; char buf[]; }; /* sdshdr8: 1字节存储len和alloc */ struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* 已使用的字节数 */ uint8_t alloc; /* 已分配的字节数(不含头部和\0) */ unsigned char flags; /* 低3位=SDS_TYPE_8 */ char buf[]; }; /* sdshdr16: 2字节存储len和alloc */ struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; uint16_t alloc; unsigned char flags; char buf[]; }; /* sdshdr32: 4字节存储len和alloc */ struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; uint32_t alloc; unsigned char flags; char buf[]; }; /* sdshdr64: 8字节存储len和alloc (超长字符串) */ struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; uint64_t alloc; unsigned char flags; char buf[]; }; /* 类型枚举常量 */ #define SDS_TYPE_5 0 #define SDS_TYPE_8 1 #define SDS_TYPE_16 2 #define SDS_TYPE_32 3 #define SDS_TYPE_64 4 #define SDS_TYPE_MASK 7 /* flags & 7 获取类型 */ #define SDS_MAX_PREALLOC (1024*1024) /* 1MB */
📄 src/sds.hInline Functions
/* 通过 s[-1] 获取 flags，再根据类型获取头部 */ #define SDS_HDR(T, s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) /* 获取字符串长度 - O(1) */ static inline size_t sdslen(const sds s) { unsigned char flags = s[-1]; switch(flags & SDS_TYPE_MASK) { case SDS_TYPE_5: return SDS_TYPE_5_LEN(flags); case SDS_TYPE_8: return SDS_HDR(8,s)->len; case SDS_TYPE_16: return SDS_HDR(16,s)->len; case SDS_TYPE_32: return SDS_HDR(32,s)->len; case SDS_TYPE_64: return SDS_HDR(64,s)->len; } return 0; } /* 获取可用空间 = alloc - len */ static inline size_t sdsavail(const sds s) { unsigned char flags = s[-1]; switch(flags & SDS_TYPE_MASK) { case SDS_TYPE_8: { SDS_HDR_VAR(8,s); return sh->alloc - sh->len; } /* ... 其他类型类似 ... */ } return 0; }
📐 sdshdr8 内存布局示例（"Hello"）
len
5
alloc
8
flags
00000001
buf[]
'H' 'e' 'l' 'l' 'o' '\0'
内存地址: ... | 05 | 08 | 01 | 48 | 65 | 6c | 6c | 6f | 00 | .. | ..

类型选择策略

  • • len ≤ 31 → sdshdr5 (未使用)
  • • len ≤ 255 → sdshdr8
  • • len ≤ 65535 → sdshdr16
  • • len ≤ 2³² → sdshdr32
  • • len > 2³² → sdshdr64

空间预分配规则

  • • alloc-len < 1MB: 新空间 = len * 2
  • • alloc-len ≥ 1MB: 新空间 = len + 1MB
  • • 最大预分配: 1MB
  • • 惰性释放: 缩短时不立即回收
📋
QuickList (List 列表)
双向链表 + 压缩列表的完美结合，Redis 7.0 起使用 Listpack

💡 核心设计思想

  • QuickList = 双向链表：每个节点是一个压缩列表（或 Listpack）
  • 结合两者优点：双端 O(1) 操作 + 内存紧凑存储
  • Redis 7.0+：用 Listpack 替代 ziplist（消除级联更新问题）
  • 节点压缩：LZF 压缩算法进一步节省内存
📄 src/quicklist.hC Header
/* QuickList 节点结构 - 每个节点是一个压缩列表 */ typedef struct quicklistNode { quicklistNode *prev; /* 前驱节点指针 */ quicklistNode *next; /* 后继节点指针 */ unsigned char *entry; /* 指向压缩列表/listpack 的指针 */ size_t sz; /* 当前节点的字节数 */ unsigned int count : 16; /* 元素个数 (最多 65535) */ unsigned int encoding : 2; /* RAW=1, LZF=2 */ unsigned int container : 2; /* PLAIN=1, PACKED=2 (Redis7用PACKED) */ unsigned int recompress : 1; /* 是否需要重新解压 */ unsigned int attempted_compress : 1; /* 是否尝试压缩 */ unsigned int extra : 10; /* 预留字段 */ } quicklistNode; /* 位字段详解: count(16) + encoding(2) + container(2) + recompress(1) + attempted(1) + extra(10) = 32bits */ /* QuickList 主结构 - 整个链表的元信息 */ typedef struct quicklist { quicklistNode *head; /* 链表头节点 */ quicklistNode *tail; /* 链表尾节点 */ unsigned long count; /* 链表总元素个数 */ unsigned long len; /* 链表节点个数 */ int fill : 16; /* 每个节点的容量因子 (-1,-2,-4,-5 或 1-48) */ unsigned int bookmark_count : 4; /* 书签数量 */ quicklistBookmark bookmarks[]; } quicklist;
📄 src/listpack.hC Header
/* Listpack (LP) 结构 - Redis 7.0 替代 ziplist */ /* * +----------+----------+--------+--------+--------+---------+--------+ * |total_bytes| | entry1 | entry2 | ... | entryN | end | * | (4B) | (可变长) |(可变) |(可变) | | (可变) | (1B) | * +----------+----------+--------+--------+-------+---------+--------+ */ /* entry 编码格式 (每个元素): */ /* +----------+-------------+----------------+ */ /* | encoding | length | content | */ /* | (1-3B) | (可变长) | (字节数组) | */ /* +----------+-------------+----------------+ */ /* * encoding 规则: * |00xxxxxx| -> 长度 ≤ 63 的小整数 * |01xxxxxx|xxxxxxxx| -> 长度 ≤ 16383 的短字符串 * |10000000|xxxxxxxx|... -> 14位以上长度的字符串 * |11000000| -> int16 * |11010000| -> int32 * |11100000| -> int64 * |11110000| -> 24位有符号整数 * |11111110| -> int8 * |11111111| -> end of listpack (LP_END) */ /* fill 参数说明: */ /* -1: 每个节点最大 4KB */ /* -2: 每个节点最大 8KB (默认) */ /* -4: 每个节点最大 16KB */ /* -5: 每个节点最大 32KB */ /* 正数: 最多存储的元素个数 (1-48) */
📐 QuickList 内存结构图
head
0x1000
tail
0x2000
count
1000
len
10
Node 1
prev: NULL
next: →
count: 127
sz: 4096
⇆
Node 2
count: 100
encoding: LZF
⇆
... more nodes ...
⇆
Node N
next: NULL
count: 50

ziplist vs listpack

  • • ziplist: 存在级联更新问题
  • • listpack: 消除 backrawl 指针
  • • 每个 entry 只记录自己的长度
  • • 尾部有一个 end 标记 (0xFF)

QuickList 优势

  • • 两端操作 O(1): LPUSH/RPOP
  • • 中间存储紧凑省内存
  • • 可配置 fill 参数平衡取舍
  • • LZF 压缩进一步省空间
🗂️
Dict (Hash 哈希)
渐进式 rehash 的哈希表实现，支持 O(1) 查找

💡 核心设计思想

  • 两个哈希表：ht[0] 正常用，ht[1] 用于 rehash
  • 渐进式 rehash：分批迁移，避免一次性扩容卡顿
  • 链地址法：解决哈希冲突，插入表头
  • 负载因子：扩容 > 0.75，缩容 < 0.1
📄 src/dict.hC Header
/* 哈希表节点 - 键值对 */ typedef struct dictEntry { void *key; /* 键 (void* 支持任意类型) */ union { void *val; /* 值 (void*) */ uint64_t u64; /* 或 64 位无符号整数 */ int64_t s64; • 或 64 位有符号整数 */ double d; /* 或 double */ } v; struct dictEntry *next; /* 下一个节点 (链地址法) */ void *metadata[]; /* 外部字典使用的元数据 */ } dictEntry; /* 哈希表结构 - 桶数组 */ typedef struct dictht { dictEntry **table; /* 哈希桶数组 (二级指针) */ unsigned long size; /* 桶的数量 (必须是 2^n) */ unsigned long sizemask; /* size - 1, 用于 & 运算取模 */ unsigned long used; /* 已使用的节点数 */ } dictht;
📄 src/dict.hC Header
/* 字典主结构 - 包含两个哈希表实现渐进式 rehash */ typedef struct dict { dictType *type; /* 类型特定函数 (hash/cmp/dup/free) */ void *privdata; /* 私有数据 (传给 type 的函数) */ dictht ht[2]; /* 两个哈希表: ht[0]=主表, ht[1]=rehash表 */ long rehashidx; /* rehash 进度: -1=未开始, >=0=正在迁移的桶索引 */ int16_t pauserehash; /* rehash 暂停标志: >0 暂停 */ long size; /* 哈希表总大小 */ long used; /* 已使用的节点总数 */ } dict; /* 类型特定操作 - 可自定义 hash 函数等 */ typedef struct dictType { uint64_t (*hashFunction)(const void *key); /* 哈希函数 */ void *(*keyDup)(void *privdata, const void *key); /* 键复制 */ void *(*valDup)(void *privdata, const void *obj); /* 值复制 */ int (*keyCompare)(void *privdata, const void *key1, const void *key2); /* 键比较 */ void (*keyDestructor)(void *privdata, void *key); /* 键析构 */ void (*valDestructor)(void *privdata, void *obj); /* 值析构 */ } dictType;
📐 Dict 渐进式 Rehash 内存结构图
rehashidx
3
pauserehash
0
→ 正在迁移第 3 个桶
ht[0] (主表)
[0] ✓ 已迁移
[1] ✓ 已迁移
[2] ✓ 已迁移
[3] 迁移中...
[4] 未迁移
ht[1] (rehash表)
[0] 空
[1] 空
[2] 空
[3] 接收中
[4] new capacity

扩容与缩容

  • • 扩容因子: used/size > 0.75
  • • 缩容因子: used/size < 0.1
  • • 新容量: 第一个 ≥ used*2 的 2^n
  • • 缩容: 第一个 ≥ used 的 2^n

Rehash 过程

  • 1. rehashidx = 0 开始
  • 2. 每次操作迁移一个桶
  • 3. rehashidx++
  • 4. 完成时 ht[0] = ht[1]，重置
🎯
IntSet (Set 集合)
整数集合优化，小规模纯整数场景的内存高效存储

💡 核心设计思想

  • 纯整数优化：只存储整数时使用紧凑二进制表示
  • 升级机制：当需要更大的整数编码时，自动升级
  • 降级不支持：一旦升级，只能升级，不会降级
  • 二分查找：内容有序，支持 O(log N) 查找
📄 src/intset.hC Header
/* 整数集合结构 */ typedef struct intset { uint32_t encoding; /* INTSET_ENC_INT16/INT32/INT64 */ uint32_t length; /* 元素个数 */ int8_t contents[]; /* 实际存储柔性数组, 类型由 encoding 决定 */ } intset; /* 编码方式 */ #define INTSET_ENC_INT16 (sizeof(int16_t)) /* 2 字节, 范围: -32768~32767 */ #define INTSET_ENC_INT32 (sizeof(int32_t)) /* 4 字节, 范围: -2^31~2^31-1 */ #define INTSET_ENC_INT64 (sizeof(int64_t)) /* 8 字节, 范围: -2^63~2^63-1 */ /* contents 实际类型由 encoding 决定, 不是 int8_t! */ /* 这只是内存对齐的占位符, 实际存储可能为 int16_t/int32_t/int64_t */
📐 IntSet 内存布局（[1, 256, 65535]）
encoding
4 (INT32)
length
3
[0]
1
[1]
256
[2]
65535
十六进制视图:
04 00 00 00 03 00 00 00 01 00 00 00 00 01 00 00 FF FF 00 00

🔄 升级过程示例

初始: [1, 200] → encoding=INT16 (2字节/元素)
↓ 添加 50000
↑ 50000 > 32767, 需要升级到 INT32!
步骤: 分配新内存 → 重新编码所有元素 → 插入新元素
结果: [1, 200, 50000] → encoding=INT32 (4字节/元素)

编码升级条件

  • • 当前编码无法容纳新元素
  • • 新元素超出当前编码范围
  • • 只在添加元素时触发
  • • 删除元素不会触发降级

IntSet vs Hashtable

  • • IntSet: 全整数, ≤512 个
  • • Hashtable: 超出阈值时转换
  • • IntSet 更节省内存
  • • Hashtable 查找 O(1)
🏆
SkipList + Dict (ZSet 有序集合)
Redis 最精妙的数据结构，同时实现高效排序和 O(1) 查找

💡 核心设计思想

  • 双重索引：SkipList 保证排序，Dict 保证 O(1) 查找
  • 跳表层数：每层元素以 p=0.25 概率晋升，默认最大 32 层
  • score 是 double：64 位浮点数，支持相等时的字典序比较
  • Dict 和 SkipList 共享节点：不浪费内存
📄 src/server.hC Header
/* 跳表节点结构 */ typedef struct zskiplistNode { sds ele; /* 成员 (SDS 字符串) */ double score; /* 分值 (用于排序) */ struct zskiplistNode *backward; /* 反向指针, 只有 L1 有 */ struct zskiplistLevel { zskiplistNode *forward; /* 前向指针 */ uint32_t span; /* 到下一个节点的跨度 (用于 ZRANK) */ } level[]; /* 柔性数组, 层信息 (动态长度) */ } zskiplistNode; /* 跳表最大层数: 32 (足够索引 2^32 个元素) */ #define ZSKIPLIST_MAXLEVEL 32 /* 晋升概率: 1/4, 即每 4 个元素有 1 个晋升到上一层 */ #define ZSKIPLIST_P 0.25
📄 src/server.hC Header
/* 跳表主结构 */ typedef struct zskiplist { zskiplistNode *header; /* 头节点 (不存储数据, 所有层从头开始) */ zskiplistNode *tail; /* 尾节点 */ unsigned long length; /* 节点个数 (不含头节点) */ int level; /* 当前最大层数 (不含头节点) */ } zskiplist; /* ZSet 主结构 - 同时维护跳表和字典 */ typedef struct zset { dict *dict; /* 字典: member → score, O(1) 查找 */ zskiplist *zsl; /* 跳表: 按 score 排序, 范围查询 */ } zset;
📐 SkipList 结构图
层
HEAD
→
L4
→
L3
→
...
→
NIL
L3
HEAD
→
score=100
→
nil
L2
HEAD
→
score=50
→
score=100
→
nil
L1
HEAD
→
score=10
→
score=50
→
score=80
→
nil
查找 score=80: L3 HEAD → 跳过 → L3 nil → L2 HEAD → 跳过50 → L2 100 → L1 HEAD → 10 → 50 → 找到80!
期望复杂度 O(log N)

为什么用跳表？

  • • 比平衡树实现简单
  • • 范围查询更高效 (ZRANGEBYSCORE)
  • • 插入/删除只需修改局部指针
  • • 内存占用可接受 (约 1.33 层/节点)

Dict + SkipList 双索引

  • • Dict: ZSCORE 查找 O(1)
  • • SkipList: 排序/范围 O(log N)
  • • 共享 member 指针，节省内存
  • • score 只在 SkipList 中