10. Redis 底层数据结构
理解 Redis 为何如此高效的关键，在于它精心设计的数据结构。本章深入剖析 SDS、IntSet、Dict、ZipList、Listpack、QuickList、SkipList 以及 RedisObject 的设计思路与实现细节。
1. 概述
1.1 Redis 为什么自己实现数据结构
C 标准库提供了基本的数据结构，但 Redis 没有直接使用它们，原因如下：
| C 标准库 | 问题 | Redis 方案 |
|---|---|---|
char* (C字符串) |
O(n) 获取长度、二进制不安全、缓冲区溢出 | SDS |
malloc/free |
频繁分配导致碎片、无引用计数 | RedisObject + jemalloc |
| 无内置 | 无哈希表、跳表、压缩列表 | Dict、SkipList、ZipList |
| 无内置 | 无内存友好的整数集合 | IntSet |
核心诉求：Redis 是一个内存数据库，内存效率与操作速度是生命线。 C 标准库的数据结构不够"贴身"，必须量身定做。
1.2 数据结构层次
Redis 的数据组织分为三个层次：
┌─────────────────────────────────────────────────────┐
│ 用户可见类型 │
│ String Hash List Set ZSet │
├─────────────────────────────────────────────────────┤
│ 底层实现结构 │
│ SDS IntSet Dict ZipList QuickList │
│ Listpack SkipList RedisObject │
├─────────────────────────────────────────────────────┤
│ 内存分配层 │
│ jemalloc (默认) / libc │
└─────────────────────────────────────────────────────┘1.3 类型映射关系
下面这张表展示了 5 种高级类型在不同场景下使用的底层数据结构，是理解 Redis 内存模型的核心：
┌─────────┐
│ STRING │
└────┬────┘
┌───────────────┼───────────────┐
▼ ▼ ▼
┌──────────┐ ┌───────────┐ ┌──────────┐
│ INT │ │ EMBSTR │ │ RAW │
│ (整数) │ │ (≤44字节) │ │ (>44字节)│
└──────────┘ └───────────┘ └──────────┘
│ │
▼ ▼
┌─────────────────────────┐
│ SDS │
└─────────────────────────┘
┌─────────┐
│ HASH │
└────┬────┘
┌───────────────┴───────────────┐
▼ ▼
┌──────────┐ ┌──────────┐
│ ZIPLIST │ (数据小) │ HT │ (数据大)
│/Listpack │ │ (Dict) │
└──────────┘ └──────────┘
┌─────────┐
│ LIST │
└────┬────┘
│
▼
┌────────────┐
│ QUICKLIST │ (Redis 3.2+)
└────────────┘
内部: ZipList/Listpack 节点组成的双向链表
┌─────────┐
│ SET │
└────┬────┘
┌───────────────┴───────────────┐
▼ ▼
┌──────────┐ ┌──────────┐
│ INTSET │ (全整数) │ HT │ (其他)
└──────────┘ │ (Dict) │
└──────────┘
┌─────────┐
│ ZSET │
└────┬────┘
┌───────────────┴───────────────┐
▼ ▼
┌──────────┐ ┌──────────────────┐
│ ZIPLIST │ (数据小) │ SKIPLIST + HT │ (数据大)
│/Listpack │ │ (跳表+字典双索引) │
└──────────┘ └──────────────────┘2. SDS（Simple Dynamic String）
SDS 是 Redis 中字符串的底层实现，几乎所有字符串操作都基于它。
2.1 C 语言字符串的问题
C 原生字符串 (char*) 有三个致命缺陷：
缺陷一：获取长度 O(n)
// C 字符串需要遍历到 \0
size_t len = 0;
while (s[len] != '\0') len++; // O(n)
Redis 的 STRLEN 命令必须 O(1)——如果一个 Key 存了几 MB 的字符串，每次 O(n) 遍历是不可接受的。
缺陷二：二进制不安全
C 字符串以 \0 作为结束标记，这意味着无法存储包含 \0 的二进制数据（如图片、序列化对象等）。Redis 作为通用存储，必须支持任意二进制数据。
缺陷三：缓冲区溢出风险
char dest[10];
strcat(dest, "this is a very long string"); // 溢出！
C 字符串不记录自身容量，拼接操作很容易越界。
2.2 🔬 SDS 结构设计
SDS 的设计用一个字可以概括：“带元数据的字符串”。
2.2.1 结构定义
以 sdshdr8 为例（最常见的中短字符串类型）：
sdshdr8 结构布局:
┌────────┬────────┬────────┬──────────────┬───┐
│ len │ alloc │ flags │ buf[...] │\0 │
│ 1字节 │ 1字节 │ 1字节 │ len+1字节 │ │
└────────┴────────┴────────┴──────────────┴───┘
← 3字节头部 → ← 数据区 →
len : 当前已使用的字节数（不含 \0）
alloc : 总容量（不含头部和 \0 终止符）
flags : 低 3 位标识 SDS 类型，高 5 位未使用
buf[] : 柔性数组，实际存储字符串数据C 伪代码结构定义：
// 注：以 sdshdr8 为例，实际 Redis 中有 5 种变体
struct sdshdr8 {
uint8_t len; // 已使用长度（最大 255）
uint8_t alloc; // 总分配容量（最大 255，不含头部与 \0）
unsigned char flags; // 低 3 位为类型标记 (SDS_TYPE_8 = 2)
char buf[]; // 柔性数组 (flexible array member)
};2.2.2 五种 SDS 类型
Redis 为了极致节省内存，按字符串长度设计了 5 种不同的 SDS 头部：
| 类型 | sdshdr5 | sdshdr8 | sdshdr16 | sdshdr32 | sdshdr64 |
|---|---|---|---|---|---|
| len 占用 | 5位(在flags中) | 1字节 | 2字节 | 4字节 | 8字节 |
| alloc占用 | 无 | 1字节 | 2字节 | 4字节 | 8字节 |
| 头部大小 | 1字节 | 3字节 | 5字节 | 9字节 | 17字节 |
| 最大容量 | 32字节 | 255字节 | 65535字节 | ~4GB | 极大 |
| 使用场景 | 极小字符串 | ≤255B短串 | ≤64KB | 中长串 | 巨型串 |
// sdshdr16 结构（字符串 ≤ 64KB 时使用）
struct sdshdr16 {
uint16_t len; // 2字节：已用长度
uint16_t alloc; // 2字节：总容量
unsigned char flags; // 1字节：低3位 = SDS_TYPE_16 (3)
char buf[];
};
// sdshdr32 结构（字符串 ≤ 4GB 时使用）
struct sdshdr32 {
uint32_t len; // 4字节
uint32_t alloc; // 4字节
unsigned char flags; // 1字节：低3位 = SDS_TYPE_32 (4)
char buf[];
};2.2.3 设计哲学：按需选型
字符串长度 → 自动选择的SDS类型
────────────────────────────────────────────
≤ 31 字节 → sdshdr5（头部仅1字节，len复用在flags中）
≤ 255 字节 → sdshdr8（头部3字节）
≤ 65535 字节 (64KB) → sdshdr16（头部5字节）
≤ 4GB → sdshdr32（头部9字节）
> 4GB → sdshdr64（头部17字节）💡 为什么这样设计？ 如果所有字符串都用 uint64_t 存长度，每个字符串浪费 7 字节。在有千万 Key 的 Redis 实例中，这意味着上百 MB 的浪费。“短字符串用小头” 是 Redis 内存效率的核心哲学。
2.2.4 SDS 指针技巧
// Redis 操作字符串时使用这个宏来获取 SDS 头部指针
// s 是用户可见的 buf 指针（指向实际字符串数据）
#define SDS_HDR(s, type) ((struct sdshdr##type *)((s) - sizeof(struct sdshdr##type)))
// 例如：从 buf 指针获取 sdshdr8 的 len
static inline size_t sdslen(const sds s) {
unsigned char flags = s[-1]; // flags 在 buf 前面紧邻
switch(flags & SDS_TYPE_MASK) {
case SDS_TYPE_8:
return SDS_HDR(8, s)->len; // 回退到头部读取 len
case SDS_TYPE_16:
return SDS_HDR(16, s)->len;
// ... 其他类型
}
}内存布局示意：
低地址 高地址
┌────────┬────────┬────────┬─────────────────────┐
│ len │ alloc │ flags │ buf (实际字符串) │
│ │ │ │ ▲ │
└────────┴────────┴────────┴──┼──────────────────┘
← 头部固定偏移 → sds 指针指向这里 (buf 起始)2.3 🔬 SDS 的优势
优势一：O(1) 获取长度
得益于 len 字段，sdslen(s) 直接读取，恒为 O(1)。对比 C 字符串需要遍历到 \0。
优势二：二进制安全
SDS 不依赖 \0 判断结尾，而是通过 len 字段明确记录字符串长度。可以存储任意二进制数据，包括图片、序列化的 Protobuf 等。
// SDS 可以存储含有 \0 的数据
sds bin_data = sdsnewlen("\x00\x01\x02\x00\x03", 5);
// sdslen(bin_data) == 5，不受中间 \0 影响
优势三：预分配空间（Pre-allocation）
减少内存重分配次数，具体策略如下：
新长度 newlen → 分配策略
──────────────────────────────────────────
newlen < 1MB → alloc = newlen * 2 + 1
(翻倍 + 1字节存\0)
newlen ≥ 1MB → alloc = newlen + 1MB + 1
(额外增加1MB)示例：
// 假设当前 SDS 是 "hello" (len=5, alloc=5)
// 追加 " world" (6字节), newlen = 11
// 11 < 1MB → alloc = 11 * 2 + 1 = 23
// 实际分配 23 字节，使用 11 字节，剩余 12 字节预留
⚡ 性能效果：连续追加 N 次小数据时，内存重分配次数从 O(N) 降至 O(log N)。
优势四：惰性空间释放（Lazy Free）
缩短字符串时不会立即 realloc 回收多余空间，而是只更新 len。预留空间可用于后续增长操作，避免频繁重分配。
// sds sdstrim(sds s, const char *cset) 裁剪后的行为
// s = "hello " len=8 alloc=16
// sdstrim(s, " ") → s = "hello" len=5 alloc=16
// alloc 不变！预留 11 字节待用
优势五：兼容 C 字符串函数
SDS 的 buf 末尾始终保留 \0（由 alloc + 1 保证），因此可以安全地传给 printf、strlen 等 C 标准库函数。
sds s = sdsnew("hello");
printf("%s\n", s); // ✅ 正常工作，因为 buf 末尾有 \0
// 同时也保留 len 字段，支持二进制安全操作
2.4 SDS 主要操作
| 操作 | 含义 | 时间复杂度 | 说明 |
|---|---|---|---|
sdsnew() |
创建 SDS | O(n) | 复制 C 字符串 |
sdsnewlen() |
创建指定长度 SDS | O(n) | 可含 \0，二进制安全 |
sdsempty() |
创建空 SDS | O(1) | len=0, alloc=0 |
sdsfree() |
释放 SDS | O(1) | |
sdslen() |
获取长度 | O(1) | 直接读 len 字段 |
sdsavail() |
获取可用空间 | O(1) | alloc - len |
sdscat() |
追加 C 字符串 | O(n) | 自动扩容 |
sdscatlen() |
追加指定长度数据 | O(n) | 二进制安全追加 |
sdscpy() |
复制覆盖 | O(n) | 尽可能复用已有空间 |
sdstrim() |
去除首尾字符 | O(n*m) | 惰性释放空间 |
sdsrange() |
截取子串 | O(n) | 惰性释放 |
sdscmp() |
比较两个 SDS | O(n) | |
sdssplitlen() |
分割 SDS | O(n*m) | 返回 SDS 数组 |
sdscatvprintf() |
格式化追加 | O(n) | 类似 vprintf |
sdsupdatelen() |
用 \0 更新 len |
O(n) | strlen 后更新 len |
sdsMakeRoomFor() |
确保容量 | O(1)或O(n) | 扩容核心逻辑 |
sdsMakeRoomFor —— 扩容核心逻辑
sds sdsMakeRoomFor(sds s, size_t addlen) {
size_t avail = sdsavail(s);
if (avail >= addlen) return s; // 空间足够，无需扩容
size_t len = sdslen(s);
size_t newlen = len + addlen;
// 🔑 预分配策略
if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC = 1MB
newlen *= 2; // 翻倍
else
newlen += SDS_MAX_PREALLOC; // 加 1MB
// 根据 newlen 选择合适类型的 SDS
int oldtype = sdsReqType(len);
int newtype = sdsReqType(newlen);
if (oldtype == newtype) {
// 类型没变，直接 realloc
s = sds_realloc(sh, sizeof(struct sdshdr##newtype) + newlen + 1);
} else {
// 类型升级（如 sdshdr8 → sdshdr16），重新分配并迁移
s = sds_malloc(sizeof(struct sdshdr##newtype) + newlen + 1);
memcpy(s, old_buf, len + 1);
sds_free(old_sh);
}
// ... 更新 alloc 等字段
}3. IntSet（整数集合）
IntSet 是 Redis 为 纯整数 Set 设计的高效紧凑存储结构。
3.1 🔬 结构定义
IntSet 内存布局:
┌──────────┬──────────┬──────────────────────────────────┐
│ encoding │ length │ contents[] │
│ 4字节 │ 4字节 │ (length * 编码宽度)字节 │
└──────────┴──────────┴──────────────────────────────────┘
↑ ↑
头部(8字节) 柔性数组(按encoding宽度解读)struct intset {
uint32_t encoding; // 编码类型
uint32_t length; // 元素个数
int8_t contents[]; // 实际数据（柔性数组，注意：声明为int8_t但实际按encoding解释）
};🚨
contents声明为int8_t[]只是为了占位，实际通过encoding字段按不同宽度访问，不是真的存int8_t。
3.2 编码类型
| 编码常量 | 值 | 元素范围 | 每元素宽度 |
|---|---|---|---|
INTSET_ENC_INT16 |
2 | [-32768, 32767] | 2 字节 |
INTSET_ENC_INT32 |
4 | [-2^31, 2^31 - 1] 即约±21亿 | 4 字节 |
INTSET_ENC_INT64 |
8 | [-2^63, 2^63 - 1] | 8 字节 |
// 获取 IntSet 中第 pos 个元素的值
// 关键是 (int64_t*) 强制转换：contents 按 encoding 指定的宽度解读
static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
if (enc == INTSET_ENC_INT64) {
return ((int64_t*)is->contents)[pos]; // 按 8 字节读
} else if (enc == INTSET_ENC_INT32) {
return ((int32_t*)is->contents)[pos]; // 按 4 字节读
} else {
return ((int16_t*)is->contents)[pos]; // 按 2 字节读
}
}3.3 🔬 编码升级（Upgrade）
3.3.1 何时触发
当插入的新元素超出当前编码范围时触发升级，不可逆。
当前 encoding = INTSET_ENC_INT16
当前元素：[10, 20, 30] 每个占 2 字节，共 6 字节
插入 100000（超出 [-32768, 32767]） → 触发升级到 INTSET_ENC_INT323.3.2 升级过程（分步详解）
假设 IntSet 当前状态：
encoding = INTSET_ENC_INT16
length = 3
contents: [10, 20, 30] (每个2字节)
插入元素 100000 (int32)
Step 1: 计算新编码所需空间
new_encoding = INTSET_ENC_INT32 (每元素4字节)
new_size = 8(头部) + (3+1)*4 = 24 字节
Step 2: 重新分配内存
┌──┬──┬──┬──┬──┬──┐ realloc后:
│10│20│30│ │ ──────────→ │10│20│30│ │ │ │ │
└──┴──┴──┴──┴──┴──┘ └──┴──┴──┴──┴──┴──┴──┘
旧空间(每个2B) 新空间(每个4B，有空洞)
Step 3: 从后向前移动元素（避免覆盖）
位置 pre_idx=2 (原值30):
_intsetSet(is, 2, 30) → contents[8..11] = 30 (int32格式)
位置 pre_idx=1 (原值20):
_intsetSet(is, 1, 20) → contents[4..7] = 20 (int32格式)
位置 pre_idx=0 (原值10):
_intsetSet(is, 0, 10) → contents[0..3] = 10 (int32格式)
Step 4: 插入新元素 100000
contents[12..15] = 100000
最终:
encoding = INTSET_ENC_INT32
length = 4
contents: [10, 20, 30, 100000] (每个4字节，总数据区16字节)从后向前移动 是升级算法的关键——如果从前向后，第二步写入就会覆盖掉未处理的原始数据。
3.3.3 为什么不可逆？
// 伪代码：为什么不降级
void intsetRemove(intset *is, int64_t value) {
// ... 删除元素后
// ❌ 缺失的逻辑：
// if (当前最大元素可以用 int16 表示) {
// 降级到 INTSET_ENC_INT16 // Redis 没有这个代码
// }
}降级不可逆的原因：
- 判断成本：每次删除都要检查当前最大元素是否适合更小编码 → 需要遍历整个集合
- 收益低：编码升级后元素数量通常已经较多，降级节省的空间有限
- 设计简单：避免"降级→再升级"的抖动
🚨 陷阱：假设 Set 中有 500 个 int16 范围的整数（每元素 2 字节），突然插入 1 个 int64 范围的大整数，所有 501 个元素全部变成 8 字节。内存从 500×2=1KB 暴涨到 501×8≈4KB，翻了 4 倍。
3.4 IntSet 特点总结
| 特性 | 说明 |
|---|---|
| 有序性 | 元素按升序排列，支持二分查找 O(log n) |
| 唯一性 | 保证不重复 |
| 内存布局 | 连续存储，无指针开销，缓存友好 |
| 查找 | 二分查找 O(log n) |
| 插入/删除 | O(n)（需要移动元素） |
| 适用条件 | Set 类型中元素全为整数，且数量 ≤ set-max-intset-entries(默认 512) |
4. Dict（字典 / 哈希表）
Dict 是 Redis 中使用最广泛的数据结构之一。全局键空间、过期键字典、Hash 类型的 HT 编码、Set 类型的 HT 编码都基于 Dict。
4.1 🔬 结构定义
三层结构：dict（顶层） → dictht（哈希表） → dictEntry（键值对节点）
dict
┌──────────────┐
│ type │──→ dictType (函数指针表)
│ privdata │ 特定类型的私有数据
│ ht[0] │──→ dictht (主哈希表)
│ ht[1] │──→ dictht (rehash 目标表，平时为空)
│ rehashidx │ -1: 未rehash; ≥0: rehash进行中
│ iterators │ 安全迭代器计数
└──────────────┘
dictht
┌──────────────┐
│ table │──→ [ * → * → * → * → ... ] (桶数组，每个桶是链表头)
│ size │ 桶数量 = 2^n
│ sizemask │ size - 1 (用于 & 取模)
│ used │ 已使用桶数量
└──────────────┘
dictEntry
┌───────────┬───────────┬──────────┐
│ key │ v{union} │ next │──→ 下一个 dictEntry (或 NULL)
└───────────┴───────────┴──────────┘C 伪代码：
// 顶层结构
struct dict {
dictType *type; // 类型特定函数（hash, keyCompare, keyDup, valDup, keyDestructor, valDestructor）
void *privdata; // 类型特定私有数据
dictht ht[2]; // 两个哈希表，ht[1] 仅在 rehash 时使用
long rehashidx; // rehash 进度，-1 表示不在 rehash
int16_t pauserehash; // 暂停 rehash 标志 (>0 时暂停)
};
// 哈希表
struct dictht {
dictEntry **table; // 桶数组指针 (数组元素是链表头指针)
unsigned long size; // 桶数量 (始终为 2^n)
unsigned long sizemask; // size - 1，用于计算桶索引: hash & sizemask
unsigned long used; // 已有节点数
};
// 键值对节点
struct dictEntry {
void *key; // 键
union { // 值（联合体减少内存）
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // 下一个节点 (链地址法解决冲突)
};可视化——一个 size=4 的哈希表：
table:
[0] ──→ ┌───────────┐ ┌───────────┐
│ key="foo" │───→│ key="bar" │───→ NULL
│ val=1 │ │ val=2 │
└───────────┘ └───────────┘
[1] ──→ NULL
[2] ──→ ┌───────────┐
│ key="baz" │───→ NULL
│ val=3 │
└───────────┘
[3] ──→ NULL
size=4, sizemask=3 (0b11), used=3
hash("foo") & 3 = 0
hash("bar") & 3 = 0 ← 冲突，头插到桶[0]链表
hash("baz") & 3 = 24.2 哈希算法
Redis 使用两种哈希算法：
| 算法 | 特点 | 使用版本 |
|---|---|---|
| MurmurHash2 | 速度快、分布均匀 | 早期默认 |
| SipHash | 安全性更好（防 HashDos 攻击） | Redis 5.0+ 默认 |
哈希种子：Redis 启动时随机生成一个哈希种子，每次计算哈希时混入种子值。这使得攻击者无法预测键的哈希分布，防止 HashDos（哈希碰撞拒绝服务攻击）。
// 简化的哈希计算逻辑
uint64_t dictGenHashFunction(const void *key, int len) {
// siphash(key, len, dict_hash_function_seed)
return siphash_nocase(key, len);
}
// 计算桶索引
idx = hash(key) & ht[0].sizemask; // sizemask = size-1 = 2^n-1
4.3 🔬 渐进式 Rehash（Progressive Rehash）
这是 Dict 设计中最精妙的部分，也是 Redis 能在重负载下保持低延迟的关键。
4.3.1 为什么需要渐进式
假设一个 1 亿 Key 的 Redis 实例。如果一次性 rehash，需要：
- 分配新哈希表 (~数 GB)
- 重新计算 1 亿次哈希
- 拷贝 1 亿个 dictEntry
这个过程可能耗时数秒，Redis 在这段时间内完全阻塞，所有客户端请求超时。
渐进式 rehash 的核心思想：把大象切成小块，一口一口吃。
4.3.2 过程详解
初始状态:
ht[0] ┌─────────────────────────────┐
│ size=4, used=3, sizemask=3 │
│ [0]→key_a→key_b→NULL │
│ [1]→NULL │
│ [2]→key_c→NULL │
│ [3]→NULL │
└─────────────────────────────┘
ht[1] NULL
rehashidx = -1
Step 1 — 分配 ht[1]:
计算 ht[1].size = 大于 ht[0].used 的最小 2^n
即：> 3 的最小 2^n = 4 (实际不会缩容，假设这是缩容场景)
正常扩容: > (3*2) 的最小 2^n = 8
ht[1] = ┌─────────────────────────────┐
│ size=8, used=0, sizemask=7 │
│ [0]→NULL [1]→NULL ... │
│ [7]→NULL │
└─────────────────────────────┘
rehashidx = 0
Step 2 — 渐进迁移:
每次对 dict 执行增/删/改/查时，额外迁移 rehashidx 指向的桶:
┌─────────────────────────────────────────────────────┐
│ rehashidx=0，迁移 ht[0].table[0] │
│ │
│ ht[0].table[0] 有 key_a, key_b │
│ 重新计算: hash(key_a) & 7 = 3 → ht[1].table[3] │
│ hash(key_b) & 7 = 5 → ht[1].table[5] │
│ │
│ 迁移后: ht[0].table[0] = NULL │
│ ht[0].used = 1 │
│ ht[1].used = 2 │
│ rehashidx = 1 │
└─────────────────────────────────────────────────────┘
下次操作时迁移 rehashidx=1 的桶，以此类推...
Step 3 — 定时器辅助迁移:
即使没有客户端操作，Redis 的 serverCron 也会每 1ms 执行一次 dictRehashMilliseconds(1)，
每次迁移最多 100 个桶。防止长期没有操作时 rehash 停滞。
Step 4 — 完成:
当 ht[0].used == 0 时，rehash 完成:
ht[1] → ht[0] (交换指针)
释放旧 ht[0] (原 ht[0] 的内存)
ht[1] = NULL
rehashidx = -14.3.3 Rehash 期间的操作规则
操作 期间行为
───────────────────────────────────────────
查找 先查 ht[0]，未命中再查 ht[1]
插入 只写入 ht[1]
删除 在两个表中都尝试删除
更新 先查 ht[0]，命中则更新；未命中查 ht[1] 并更新这样保证了新增数据逐渐流向新表，而旧表只减不增。
4.4 Rehash 触发条件
扩容条件
// 负载因子 = ht[0].used / ht[0].size
// 条件一：无后台进程时
if (load_factor >= dict_force_resize_ratio) { // dict_force_resize_ratio = 1
dictExpand(d, ht[0].used * 2);
}
// 条件二：有后台进程（BGSAVE / BGREWRITEAOF）时
if (load_factor >= dict_force_resize_ratio) { // = 5
dictExpand(d, ht[0].used * 2);
}💡 考点：为什么有 BGSAVE 时把阈值从 1 提高到 5？
BGSAVE 依赖 fork() 创建子进程。fork() 使用 Copy-On-Write (COW) 机制——父子进程共享同一块物理内存，直到某方修改时才复制。如果在 BGSAVE 期间 rehash，大量内存页被修改，触发大量 COW 复制，导致内存翻倍。阈值提高到 5 是为了延迟 rehash，减少 COW 开销。
缩容条件
// used / size < HASHTABLE_MIN_FILL = 0.1
// 即：大量桶是空的，负载极低
if (used * 100 / size < HASHTABLE_MIN_FILL) { // < 10%
dictResize(d); // size 缩小到大于 used 的最小 2^n
}4.5 特点总结
| 特性 | 说明 |
|---|---|
| 冲突解决 | 链地址法（Chaining） |
| 插入方式 | 头插法（O(1)，天然 LRU 语义） |
| 扩容 | 渐进式 rehash，不阻塞服务 |
| 缩容 | 条件触发，同样渐进式 |
| 查找 | 平均 O(1)，最坏 O(n)（极端冲突时） |
| 删除 | O(1)（已知桶索引和链表节点） |
5. ZipList（压缩列表）
ZipList 是 Redis 为小数据量场景设计的内存紧凑结构，Hash/List/ZSet 在小数据时都会使用它。
⚠️ Redis 7.0 起，ZipList 被 Listpack 全面替代。但理解 ZipList 是理解 Listpack 的前提，也是面试高频考点。
5.1 🔬 整体结构
ZipList 内存布局:
┌──────────┬──────────┬──────────┬───────┬───────┬───────┬──────────┐
│ zlbytes │ zltail │ zllen │entry1 │entry2 │entry3 │ zlend │
│ 4字节 │ 4字节 │ 2字节 │ │ │ │ 1字节 │
└──────────┴──────────┴──────────┴───────┴───────┴───────┴──────────┘
←────── 头部(10字节) ──────→ ↑ ↑
entries 0xFF 结束| 字段 | 大小 | 含义 |
|---|---|---|
zlbytes |
4 字节 | 整个 ZipList 占用的字节总数（含自身） |
zltail |
4 字节 | 最后一个 entry 的起始偏移量（支持快速尾部操作） |
zllen |
2 字节 | entry 数量（超过 65535 时需要遍历才能得到准确值） |
zlend |
1 字节 | 固定值 0xFF，标记结束 |
5.2 🔬 Entry 结构
每个 entry 由三部分组成：
Entry 结构:
┌──────────┬───────────┬─────────────────┐
│ prevlen │ encoding │ entry-data │
│ 1或5字节 │ 1/2/5字节 │ 变长 │
└──────────┴───────────┴─────────────────┘5.2.1 prevlen（前驱长度）
记录了前一个 entry 的总长度，用于从后向前遍历。
前驱长度 < 254 字节:
┌──────────┐
│ prevlen │ = 前驱长度值 (1字节, 0x00~0xFD)
└──────────┘
前驱长度 ≥ 254 字节:
┌──────┬─────────────────────────┐
│ 0xFE │ 4字节前驱长度 │
│1字节 │ (uint32_t, 小端) │
└──────┴─────────────────────────┘5.2.2 encoding（编码信息）
encoding 字段同时记录了数据类型和数据长度：
字符串编码:
00pp pppp 6位存长度, ≤63字节
01pp pppp qqqq qqqq 14位存长度, ≤16383字节
1000 0000 qqqq qqqq rrrr rrrr ... 大字符串, 后续4字节存长度
整数编码:
1100 0000 int16_t (2字节)
1101 0000 int32_t (4字节)
1110 0000 int64_t (8字节)
1111 0000 24位有符号整数 (3字节)
1111 1110 int8_t (1字节)
1111 1111 0000 xxxx 4位整数 (0~12), 编码中直接存储5.3 🔬 连锁更新（Chain Update）—— ZipList 的阿喀琉斯之踵
5.3.1 问题描述
连锁更新是 ZipList 最经典的缺陷案例，也是 Listpack 诞生的直接原因。
5.3.2 触发场景
初始状态：所有 entry 长度都是 253 字节
ZipList: [entry1(253B)] [entry2(253B)] [entry3(253B)] ...
prevlen=0 prevlen=1B prevlen=1B
(首节点) (存前驱长度 (存前驱长度
253, 1字节) 253, 1字节)
现在修改 entry1，使其长度变为 254 字节:
Step 1: entry1 长度从 253→254
现在 entry1 长度为 254
Step 2: entry2 的 prevlen 需要更新
原来 prevlen=1字节(存253)
现在 prevlen=5字节(0xFE+4字节存254)
但 prevlen 从 1 字节变 5 字节，entry2 总长度从 253→257！
Step 3: entry3 的 prevlen 需要更新
原来 prevlen=1字节(存253)
现在 prevlen=5字节(0xFE+4字节存257)
entry3 总长度也会变化... 连锁！
Step 4: 继续向后传播
entry4, entry5, entry6 ... 全部跟着变化图示：
更新前:
entry1(253B) entry2(253B) entry3(253B)
┌────────┐ ┌┬──┴────────┐ ┌┬──┴────────┐
│...data │ ││ p=1B│253B │ ││ p=1B│253B │ ...
└────────┘ │└───────────┘ │└───────────┘
长度=254(1B存) 长度=254(1B存)
更新后 (entry1 增长 1 字节):
entry1(254B) entry2(257B) entry3(257B) 全部连锁!
┌────────┐ ┌┬───┴──────────┐ ┌┬───┴──────────┐
│...data │ ││p=5B│253B │ ││p=5B│253B │ ...
└────────┘ │└──────────────┘ │└──────────────┘
长度=258(5B存) 长度=258(5B存)5.3.3 影响分析
- 时间复杂度：O(n^2) 最坏情况（每个 entry 更新都要重新分配整个 ZipList）
- 空间开销：每次 prevlen 从 1B 变 5B，每个后续 entry 增加 4 字节
- 实际风险：大量数据时会引起 Redis 明显卡顿
💡 缓解措施：通过配置限制 ZipList 的 entry 数量（hash-max-ziplist-entries 默认 512、zset-max-ziplist-entries 默认 128），让 ZipList 只在数据量小时存在，避免严重连锁更新。
5.4 ZipList 特点总结
| 特性 | 说明 |
|---|---|
| 优势 | 连续内存，无指针开销；缓存友好；适合小数据 |
| 劣势 | 操作 O(n)；连锁更新；中间插入需移动后续元素 |
| 适用 | Hash/List/ZSet 在小数据量时 |
| 致命缺陷 | 连锁更新 |
| 替代者 | Listpack (Redis 7.0+) |
6. Listpack（Redis 7.0+）
Listpack 是 ZipList 的继任者，设计目标只有一个：彻底消灭连锁更新。
6.1 核心改进思路
ZipList 的连锁更新源于一个设计缺陷：后继节点记录了前驱的长度。
Listpack 的修正：每个元素记录自己的长度，不再记录前驱长度。
ZipList 的遍历方式（导致连锁更新）:
从后向前: 读当前 entry 的 prevlen → 跳转到前一个 entry
问题: prevlen 可能 1B 变 5B → 连锁
Listpack 的遍历方式（无连锁更新）:
从后向前: 读当前 element 末尾的 element_len → 知道当前 element 总长 → 跳转
优势: element_len 只描述自己，修改不影响邻居6.2 🔬 结构设计
Listpack 整体布局:
┌──────────┬──────────┬───────────┬─────┬───────────┬──────────┐
│tot-bytes │num-elem │ element1 │ ... │ elementN │ end-byte │
│ 4字节 │ 2字节 │ │ │ │ 1字节 │
└──────────┴──────────┴───────────┴─────┴───────────┴──────────┘| 字段 | 大小 | 含义 |
|---|---|---|
tot-bytes |
4 字节 | 整个 Listpack 的总字节数 |
num-elem |
2 字节 | 元素数量（超过 65535 时需遍历） |
end-byte |
1 字节 | 固定值 0xFF，标记结束 |
每个 Element 的结构：
element 结构:
┌───────────┬──────────────┬──────────────┐
│ encoding │ data │ element-len │
│ 变长 │ 变长 │ 变长 │
└───────────┴──────────────┴──────────────┘
↑
从后向前遍历时先读这里- encoding：与 ZipList 类似，记录数据类型和数据长度
- data：实际数据
- element-len：当前这个 element 的总长度（encoding + data + element-len 的总字节数）
element-len 的编码：
element_len 值范围 编码方式
────────────────────────────────────────
1 ~ 127 1字节直接存
128 ~ 16383 2字节: 最高位=1, 低7位+下一字节
16384 ~ 2097151 3字节
2097152 ~ 268435455 4字节
268435456 ~ ... 5字节从后向前遍历的过程：
// 简化的反向遍历逻辑
unsigned char *lpPrev(unsigned char *lp, unsigned char *p) {
// p 指向当前 element 的 encoding 起始位置
// 需要跳到前一个 element 的 encoding 起始位置
if (p - lp == LP_HDR_SIZE) {
return NULL; // 已经是第一个元素
}
// 读取 p 前面紧挨着的 element-len 字段
// element-len 决定了前一个 element 的总大小
uint64_t prev_len = lpDecodeBacklen(p); // 从 p-1 开始向前解析
// 跳转到前一个 element 的起始位置
return p - prev_len;
}6.3 与 ZipList 的对比
| 特性 | ZipList | Listpack |
|---|---|---|
| 核心元数据 | 每个 entry 记录前驱长度 (prevlen) | 每个 element 记录自身长度 (element-len) |
| 连锁更新 | 存在——改一个 entry 可能触发全部后续更新 | 不存在——修改只影响自身 |
| 前向遍历 | O(1)（读 prevlen 跳转） | O(1)（读 element-len 跳转，但需要解析变长编码） |
| 后向遍历 | 无直接支持 | 无直接支持 |
| 内存紧凑度 | 类似 | 类似（element-len 可能多占 1~2 字节） |
| 复杂度 | 较复杂（prevlen 两种长度） | 略复杂（element-len 变长编码） |
| Redis 版本 | ≤ 6.x | ≥ 7.0 |
🔬 设计哲学对比：
ZipList:
Entry 知道 "我是谁" (encoding+data)
Entry 也知道 "我前面是谁" (prevlen)
→ 邻居耦合，修改会传播
Listpack:
Element 知道 "我是谁" (encoding+data)
Element 也知道 "我有多长" (element-len)
→ 自包含，修改不影响邻居6.4 适用场景
Listpack 在 Redis 7.0+ 中替代 ZipList 用于：
- Hash 小数据编码（替代
OBJ_ENCODING_ZIPLIST） - ZSet 小数据编码（替代
OBJ_ENCODING_ZIPLIST） - Stream 中的消费组等内部结构
7. QuickList（Redis 3.2+）
QuickList 是 Redis 3.2 引入的 List 类型默认编码，是一个精巧的混合结构。
7.1 设计动机：两个极端都不完美
方案 A: 纯双向链表 (LinkedList)
[node1] ⇄ [node2] ⇄ [node3] ⇄ [node4]
优势: 两端操作 O(1)，无连锁更新
劣势: 每个节点有 prev+next 指针 (16字节) + 内存分配器开销
对于小元素 (如 int)，指针开销远大于数据本身
方案 B: 纯 ZipList
[entry1|entry2|entry3|...|entry100000]
优势: 内存紧凑，无指针开销
劣势: 操作 O(n)，连锁更新风险，大列表操作极慢
方案 C: QuickList (折中)
[Ziplist1] ⇄ [Ziplist2] ⇄ [Ziplist3] ⇄ [Ziplist4]
优势: 结合两者优点——内存紧凑 + 分段降低连锁更新影响7.2 🔬 结构设计
QuickList 整体:
┌───────────────────────────────────────────────────────────┐
│ quicklist │
│ head────┐ ┌────tail │
│ count │ (总 entry 数) │ │
│ len=3 │ (节点数) │ │
│ fill │ (填充因子) │ │
│ compress│ (压缩深度) │ │
└──────────┼──────────────────────────────┼─────────────────┘
▼ ▼
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│quicklistNode │◄──►│quicklistNode │◄──►│quicklistNode │
│ prev=NULL │ │ prev ────────┼────│ prev ────────┼──...
│ next ────────┼────│ next ────────┼────│ next=NULL │
│ zl(ziplist) │ │ zl(ziplist) │ │ zl(ziplist) │
│ sz(字节数) │ │ sz │ │ sz │
│ count │ │ count │ │ count │
│ encoding │ │ encoding │ │ encoding │
│ container │ │ container │ │ container │
│ recompress │ │ recompress │ │ recompress │
└──────┬───────┘ └──────┬───────┘ └──────┬───────┘
▼ ▼ ▼
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ ZipList 或 │ │ ZipList 或 │ │ ZipList 或 │
│ Listpack │ │ Listpack │ │ Listpack │
│ (实际数据) │ │ (实际数据) │ │ (实际数据) │
└──────────────┘ └──────────────┘ └──────────────┘C 伪代码：
struct quicklist {
quicklistNode *head; // 头节点
quicklistNode *tail; // 尾节点
unsigned long count; // 所有 entry 总数
unsigned long len; // quicklistNode 节点数
int fill : 16; // 填充因子 (正数:最大entry数, 负数:最大字节)
unsigned int compress : 16; // 不压缩的端节点数 (LZF压缩深度)
// ... bookmarks 等辅助字段
};
struct quicklistNode {
quicklistNode *prev; // 前驱节点
quicklistNode *next; // 后继节点
unsigned char *zl; // 指向内部的 ZipList/Listpack
unsigned int sz; // zl 的字节数
unsigned int count : 16; // 本节点内的 entry 数量
unsigned int encoding : 2; // 1=RAW(未压缩), 2=LZF(已压缩)
unsigned int container : 2; // 1=NONE, 2=ZIPLIST
unsigned int recompress : 1; // 曾是压缩节点 (临时解压标记)
unsigned int attempted_compress : 1; // 测试用
unsigned int extra : 10; // 预留
};7.3 配置参数
# redis.conf
# 每个 quicklistNode 包含的 ZipList 最大大小
# 负值：按字节数限制
# -1 = 4KB, -2 = 8KB, -3 = 16KB, -4 = 32KB, -5 = 64KB
# 正值：按 entry 数量限制（最多该数量的 entry）
list-max-ziplist-size -2 # 默认: 每个节点最多 8KB
# 压缩深度
# 0 = 不压缩
# 1 = 两端各 1 个节点不压缩，中间节点压缩
# 2 = 两端各 2 个节点不压缩，中间节点压缩
# ...
list-compress-depth 0 # 默认: 不压缩fill 参数详解
fill = -1 → 每个节点最多 4KB (适合极小元素)
fill = -2 → 每个节点最多 8KB (默认，通用场景)
fill = -3 → 每个节点最多 16KB (适合偏大元素)
fill = -4 → 每个节点最多 32KB
fill = -5 → 每个节点最多 64KB (适合大元素，接近纯 ZipList)
fill = N → 每个节点最多 N 个entry (适合固定数量场景)7.4 LZF 压缩
当 list-compress-depth > 0 时，QuickList 使用 LZF 算法压缩中间的节点：
compress-depth = 2:
不压缩 压缩 不压缩
┌─────┐ ┌─────┐ ┌──────────┐ ┌──────────┐ ...
head ──────► │ N1 │ │ N2 │ │ N3(LZF) │ │ N4(LZF) │ ... ──► tail
└─────┘ └─────┘ └──────────┘ └──────────┘
↑ ↑ ↑
两端各2个不压缩 中间全部压缩设计思路：
- 两端不压缩：List 最频繁的操作是 LPUSH/RPOP 等两端操作，不压缩保证速度
- 中间压缩：中间节点访问频率低，牺牲一些 CPU 换取内存节省
- LZF 压缩率约 50%，对文本类数据效果好
7.5 QuickList 的设计优点
| 优点 | 说明 |
|---|---|
| 内存效率 | 链表节点内的 ZipList/Listpack 消除大量指针开销 |
| 操作效率 | 两端操作 O(1)，中间操作比纯 ZipList 快（分段后数据量小） |
| 无连锁更新风险 | 每个节点的 ZipList 较小，即使发生连锁更新影响也有限 |
| 可配置 | fill 和 compress-depth 允许按场景调优 |
| 中间压缩 | LZF 压缩减少内存，两端不压缩保证热点数据访问速度 |
8. SkipList（跳表）
SkipList（跳跃表）是 ZSet 的核心数据结构之一，也是算法面试中的经典考点。
8.1 🔬 结构定义
跳表整体结构:
header tail
┌───┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌────┐
│ │ │ │ │ │ │ │ │ │ │ │
│ L3│─►│ │─────►│ │─────►│ │─────►│ │ │NULL│
│ L2│─►│ │─────►│ │─────►│ │─────►│ │ │NULL│
│ L1│─►│ │──┐ │ │──┐ │ │──┐ │ │ │NULL│
│ L0│─►│Node1│──┼──►│Node2│──┼──►│Node3│──┼──►│Node4│ │NULL│
└───┘ │ │ │ │ │ │ │ │ │ │ │ └────┘
│ ◄───┼──┘ │ ◄───┼──┘ │ ◄───┼──┘ │ ◄───┘
│ bw │ │ bw │ │ bw │ │ bw │
└─────┘ └─────┘ └─────┘ └─────┘
score=1 score=3 score=5 score=7
ele="a" ele="b" ele="c" ele="d"C 伪代码：
// 跳表
struct zskiplist {
struct zskiplistNode *header; // 头节点 (不存储实际数据)
struct zskiplistNode *tail; // 尾节点
unsigned long length; // 节点总数 (不含 header)
int level; // 当前跳表的最大层数
};
// 跳表节点
struct zskiplistNode {
sds ele; // 成员 (member)，唯一
double score; // 分值，可重复
struct zskiplistNode *backward; // 后退指针 (仅第0层使用)
struct zskiplistLevel {
struct zskiplistNode *forward; // 前向指针
unsigned long span; // 跨度 (到 forward 节点跨越的节点数)
} level[]; // 柔性数组 (每个节点层数不同)
};关键字段解读：
score(double)：排序依据，可以相同（相同时按 ele 字典序排）ele(SDS)：成员，必须唯一backward：只在 L0 层使用，形成双向链表，支持逆序操作span：跨度 = 从当前节点到同层forward节点之间跨越的节点数（含forward自身），用于 O(log n) 排名计算level[]：柔性数组，不同节点的层数不同
8.2 为什么用跳表而不用红黑树
这是 Redis 面试的经典问题。答案涉及实现复杂度、功能需求和设计哲学三个层面：
| 维度 | SkipList | 红黑树 |
|---|---|---|
| 实现复杂度 | 简单 (~200行C代码) | 复杂 (旋转、变色、大量边界情况) |
| 范围查询 | 天然支持 O(log n + m) | 需要中序遍历，不如跳表直觉 |
| 排名查询 | span 字段 O(log n) | 需要维护子树大小（增加复杂度） |
| 并发友好 | 可分段加锁 | 旋转影响大范围节点 |
| 内存占用 | 平均 1.33 层/节点，每层 2 个指针 | 3 个指针 (left/right/parent) + color |
| 平衡性 | 概率平衡，期望 O(log n) | 严格平衡，保证 O(log n) |
💡 Redis 的选择逻辑：
“Keep It Simple” — Salvatore Sanfilippo (Redis 作者)
跳表在工程上足够好：概率平衡在实际负载下表现与红黑树相当，但代码量只有后者的 1/5，调试和维护成本极低。对于 Redis 这种追求极致稳定性的基础设施而言，简单 > 精妙。
8.3 🔬 层级生成算法
每个新节点的层数由随机算法生成，算法简单却精妙：
#define ZSKIPLIST_MAXLEVEL 32 // 最大 32 层
#define ZSKIPLIST_P 0.25 // 升级概率 1/4
int zslRandomLevel(void) {
int level = 1;
// 每次有 25% 的概率升级一层
while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}层级分布（概率）：
层级 概率 每多少个节点出现一次
─────────────────────────────────────────
L1 100% 1
L2 25% 4
L3 6.25% 16
L4 1.56% 64
L5 0.39% 256
...
L32 0.25^31 ≈ 2.3×10^-19 极其罕见期望层数 = 1/(1-0.25) = 1.33 层/节点
也就是说，每个节点平均只有 1.33 层指针，内存开销非常低。
8.4 核心操作
8.4.1 查找过程
查找 score=5 的节点:
┌───┐
header L3 ───► │ │──────────────────────────► NULL
└───┘
┌───┐ ┌─────┐
header L2 ───► │ │───────► │Node3│─────────► NULL
└───┘ │sc=5 │
└─────┘
┌───┐ ┌─────┐┌─────┐ ┌─────┐
header L1 ───► │ │─►│Node1││Node2│─►│Node3│─► ...
└───┘ │sc=1 ││sc=3 │ │sc=5 │
└─────┘└─────┘ └─────┘
步骤:
1. 从 header 的最高层 L3 开始
2. L3 forward 指向的目标 score=5 → 不大于 5 → 下降一层
3. L2 forward → Node3(score=5) → 不大于 5? 不小于也不大于 → 当前就是!
4. 如果跳到 score=7 说明走过了 → 下降一层重新找伪代码：
zskiplistNode *zslFind(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x = zsl->header;
for (int i = zsl->level - 1; i >= 0; i--) {
// 在本层向前移动，直到下一个节点的 score 大于目标
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele, ele) < 0)))
{
x = x->level[i].forward;
}
}
// x 现在指向目标节点的前驱（或就是目标）
x = x->level[0].forward;
if (x && x->score == score && sdscmp(x->ele, ele) == 0)
return x;
return NULL;
}8.4.2 插入过程
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
// 1. update[] 数组：记录每层需要更新的前驱节点
// 2. rank[] 数组：记录每层从头到 update[i] 的跨度
zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
unsigned long rank[ZSKIPLIST_MAXLEVEL];
// 3. 从高层向低层查找插入位置
x = zsl->header;
for (i = zsl->level - 1; i >= 0; i--) {
rank[i] = (i == zsl->level - 1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score || ...)) {
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x; // 记录第 i 层的前驱
}
// 4. 随机生成新节点的层数
level = zslRandomLevel();
if (level > zsl->level) {
// 新节点层数超过当前最大层 → 用 header 补齐
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
// 5. 创建新节点，逐层插入（类似链表插入）
x = zslCreateNode(level, score, ele);
for (i = 0; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
// 更新 span
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
// 6. 更新未涉及层的 span
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
// 7. 设置 backward 指针
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}8.4.3 删除过程
删除与插入对称：逐层更新 forward 指针，调整 span，更新 backward。
8.4.4 排名计算
// ZRANK 命令的实现核心
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x = zsl->header;
unsigned long rank = 0;
for (int i = zsl->level - 1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score || ...)) {
rank += x->level[i].span; // 累加跨度
x = x->level[i].forward;
}
}
if (x && x->score == score && sdscmp(x->ele, ele) == 0) {
return rank; // rank 就是从 header 到目标节点的跨度之和
}
return 0;
}8.5 Span（跨度）的作用
span 不是"层级"，而是跳跃的步数。
示例:
header ────────────────► Node3 (L2: span=3, 跳过 Node1, Node2)
header ──► Node1 ──────► Node3 (L1: span=1, span=2)
header ──► Node1 ──► Node2 ──► Node3 (L0: span=1, span=1, span=1)
计算 Node3 的排名:
从 header 的 L2 走到 Node3 → rank += 3 → 排名 = 3
ZRANK key member3 → O(log n) 而不是 O(n)!这就是 Redis 的 ZRANK / ZREVRANK 能 O(log n) 返回排名的原因。
9. RedisObject
RedisObject 是 Redis 所有数据类型的统一外壳，是理解 Key-Value 存储模型的基石。
9.1 🔬 结构定义
struct redisObject {
unsigned type:4; // 外部类型 (5种: string/list/hash/set/zset)
unsigned encoding:4; // 内部编码 (10+种: int/embstr/raw/ziplist/ht/...)
unsigned lru:24; // LRU 时钟 (24位可存约194天) 或 LFU 信息
int refcount; // 引用计数
void *ptr; // 指向实际数据结构的指针
};
// 总大小: 4bit+4bit+24bit=32bit=4字节 + 4字节(refcount) + 8字节(ptr) = 16字节
内存布局（x86-64）：
低位地址 高位地址
┌────────────────────────────────┬──────────┬────────────────┐
│ type:4 | encoding:4 | lru:24 │ refcount │ ptr (8字节) │
│ 4 字节 │ 4 字节 │ 8 字节 │
└────────────────────────────────┴──────────┴────────────────┘
←──── 共 16 字节 ────→9.2 Type 与 Encoding 对照表
用户类型 (type) |
内部编码 (encoding) |
使用的数据结构 | 触发条件 |
|---|---|---|---|
OBJ_STRING (0) |
OBJ_ENCODING_INT (1) |
直接存整数 (ptr 当整数用) | 整数值(long范围) |
OBJ_STRING (0) |
OBJ_ENCODING_EMBSTR (8) |
embstr编码SDS | 字符串 ≤ 44 字节 |
OBJ_STRING (0) |
OBJ_ENCODING_RAW (0) |
普通SDS | 字符串 > 44 字节 |
OBJ_LIST (1) |
OBJ_ENCODING_QUICKLIST (9) |
QuickList | 默认 (3.2+) |
OBJ_HASH (4) |
OBJ_ENCODING_LISTPACK (11) |
Listpack | field ≤ 512 且 value ≤ 64 |
OBJ_HASH (4) |
OBJ_ENCODING_HT (2) |
Dict | 超过阈值 |
OBJ_SET (2) |
OBJ_ENCODING_INTSET (6) |
IntSet | 全整数且数量 ≤ 512 |
OBJ_SET (2) |
OBJ_ENCODING_HT (2) |
Dict (value=NULL) | 非整数或超阈值 |
OBJ_ZSET (3) |
OBJ_ENCODING_LISTPACK (11) |
Listpack | 元素 ≤ 128 且 member ≤ 64 |
OBJ_ZSET (3) |
OBJ_ENCODING_SKIPLIST (7) |
SkipList + Dict | 超过阈值 |
注：Redis 7.0 之前，
OBJ_ENCODING_LISTPACK对应的是OBJ_ENCODING_ZIPLIST。
9.3 🔬 EMBSTR vs RAW
这是 String 类型的两种 SDS 编码，区别在于内存分配方式：
EMBSTR (embedded string):
┌────────────────────────────────────────────┐
│ 一次 malloc 分配 │
│ ┌──────────────┬──────────────────────┐ │
│ │ RedisObject │ SDS(sdshdr8 + buf) │ │
│ │ (16字节) │ (≤48字节) │ │
│ └──────────────┴──────────────────────┘ │
└────────────────────────────────────────────┘
总大小 = 16 + 3(sdshdr8头) + len + 1(\0) ≤ 64字节
len ≤ 44字节 (64 - 16 - 3 - 1 = 44)
RAW (raw string):
┌─────────────────┐ ┌──────────────────────┐
│ RedisObject │ │ SDS(sdshdr + buf) │
│ (16字节) │──→ │ (独立分配) │
│ malloc #1 │ │ malloc #2 │
└─────────────────┘ └──────────────────────┘
两次 malloc，内存不连续| 特性 | EMBSTR | RAW |
|---|---|---|
| 内存分配次数 | 1 次 | 2 次 |
| 内存释放次数 | 1 次 | 2 次 |
| 内存连续性 | RedisObject 和 SDS 连续 | 不连续 |
| 缓存友好性 | 好（一次缓存行加载） | 差（两次间接访问） |
| 可修改性 | 不可修改（只读） | 可修改 |
| 适用场景 | ≤44字节的短字符串 | >44字节或有修改需求 |
| 修改行为 | 任何修改自动转为 RAW | 直接在 SDS 上操作 |
⚡ EMBSTR 的限制：EMBSTR 的字符串不可变。任何修改操作（APPEND、SETRANGE 等）都会触发 EMBSTR → RAW 的转换，并重新分配内存。
// Redis 源码中的处理逻辑（简化）
void dbAdd(redisDb *db, robj *key, robj *val) {
// ...
}
// 当对 EMBSTR 执行修改操作时:
// 1. 创建新的 RAW 编码的 RedisObject
// 2. 复制原 EMBSTR 的数据
// 3. 执行修改
// 4. 释放原 EMBSTR 对象
9.4 引用计数与内存共享
// Redis 启动时创建 0~9999 的整数共享对象
// 这些对象在全局可复用，避免重复分配
for (int j = 0; j < 10000; j++) {
shared.integers[j] = createObject(OBJ_STRING, (void*)(long)j);
shared.integers[j]->encoding = OBJ_ENCODING_INT;
}🔬 为什么只共享 0~9999，不共享更大的范围或字符串？
共享对象的前提是：查找已有对象比创建新对象更快。对于整数，查找是 O(1)（直接数组索引）。对于字符串，需要在共享池中搜索匹配的字符串 → O(n) 在最坏情况下比直接分配还慢。Redis 选择了"简单 > 极致内存节省"。
9.5 🔬 编码转换规则详解
9.5.1 String 编码转换
INT ──────► RAW
触发: APPEND 非数字内容
INCRBYFLOAT
任何修改操作
EMBSTR ───► RAW
触发: APPEND, SETRANGE, SETBIT
任何修改操作
EMBSTR 是只读的，修改必须转 RAW
RAW ──/──► INT / EMBSTR
不会自动转回 (没有降级逻辑)9.5.2 Hash 编码转换
# 触发阈值 (redis.conf)
hash-max-listpack-entries 512 # field 数量 > 512 → 转 HT
hash-max-listpack-value 64 # 单个 value 长度 > 64 → 转 HTListpack ──────► Dict (HT)
触发: field数量 > 512 或 value > 64字节
方向: 单向，不可逆
🚨 陷阱: 先写入大量数据触发转HT → 再删除大部分数据
→ 仍然使用HT，浪费大量内存9.5.3 Set 编码转换
set-max-intset-entries 512 # 元素数量 > 512 → 转 HTIntSet ──────► Dict (HT)
触发: 元素数量 > 512 或 插入非整数元素
方向: 单向，不可逆
🚨 陷阱: SADD key "hello" # 一个字符串让整个IntSet转HT
内存: n*2字节 → n*24字节 (dictEntry) + RedisObject开销9.5.4 ZSet 编码转换
zset-max-listpack-entries 128 # 元素数量 > 128 → 转 Skiplist
zset-max-listpack-value 64 # 单个 member 长度 > 64 → 转 SkiplistListpack ──────► Skiplist + Dict
触发: 元素 > 128 或 member > 64字节
方向: 单向，不可逆9.6 🔬 为什么 ZSet 同时用 SkipList + Dict
这是 ZSet 的设计精髓：
查询类型 需要的结构
─────────────────────────────────────────
ZSCORE key member → Dict (O(1) 查找 member 的 score)
ZRANK key member → SkipList (O(log n) 排名)
ZRANGE key 0 10 → SkipList (范围遍历)
ZRANGEBYSCORE → SkipList (按 score 范围查找)
所以 ZSet 同时维护:
┌──────────┐ ┌──────────────┐
│ Dict │ │ SkipList │
│ │ │ │
│ member→score │ score,member → 排序链表
│ (哈希表) │ │ (跳表) │
└──────────┘ └──────────────┘
↑ ↑
└─── 同一份数据的两种索引 ───┘// ZSet 的结构
struct zset {
dict *dict; // member → score 的映射
zskiplist *zsl; // score → member 的有序集合
};- 两个结构指向同一批
zskiplistNode的内存（通过 dictEntry 的指针） - 插入/删除时同时更新两个结构（原子性由单线程保证）
- 额外开销：dict 的键指针 + dictEntry 开销（约 24 字节/元素）
- 收益：ZSCORE O(1)、ZRANK O(log n)、ZRANGE O(log n + m)
💡 为什么不只用跳表？ 只用跳表的话 ZSCORE 是 O(log n)。Redis 认为 ZSCORE 是高频操作，值得用额外内存换取 O(1)。
9.7 OBJECT 命令
OBJECT ENCODING key # 查看值的内部编码
# 返回: "int", "embstr", "raw", "listpack", "ht",
# "quicklist", "intset", "skiplist"
OBJECT REFCOUNT key # 查看引用计数 (通常为 1)
OBJECT IDLETIME key # 查看自上次访问以来的秒数 (LRU模式)
OBJECT FREQ key # 查看 LFU 访问频率计数示例：
> SET small "hello"
OK
> OBJECT ENCODING small
"embstr" # ≤44字节
> SET big "this is a very long string that exceeds forty-four bytes"
OK
> OBJECT ENCODING big
"raw" # >44字节
> SET num 100
OK
> OBJECT ENCODING num
"int" # 整数范围内
> APPEND num "abc"
(integer) 6
> OBJECT ENCODING num
"raw" # 修改后 INT → RAW (不可逆)10. 总结
10.1 五大类型对应的底层实现总表
| 用户类型 | 编码枚举 | 底层数据结构 | 触发条件 | 内存特征 |
|---|---|---|---|---|
| String | OBJ_ENCODING_INT (1) |
long long (ptr存值) | 整数值 | 无额外分配 |
| String | OBJ_ENCODING_EMBSTR (8) |
SDS (embstr) | ≤44字节字符串 | 一次分配，64B内 |
| String | OBJ_ENCODING_RAW (0) |
SDS (raw) | >44字节或修改后 | 两次分配 |
| Hash | OBJ_ENCODING_LISTPACK (11) |
Listpack | field≤512且val≤64B | 紧凑连续 |
| Hash | OBJ_ENCODING_HT (2) |
Dict | 超过阈值 | 指针多，开销大 |
| List | OBJ_ENCODING_QUICKLIST (9) |
QuickList (双向链表+Listpack) | 默认 | 分段紧凑 |
| Set | OBJ_ENCODING_INTSET (6) |
IntSet | 全整数且≤512 | 紧凑有序 |
| Set | OBJ_ENCODING_HT (2) |
Dict (val=NULL) | 非整数或>512 | 指针开销 |
| ZSet | OBJ_ENCODING_LISTPACK (11) |
Listpack | ≤128个且member≤64B | 紧凑连续 |
| ZSet | OBJ_ENCODING_SKIPLIST (7) |
SkipList + Dict | 超过阈值 | 双索引内存 |
10.2 数据结构选择决策树
需要快速 O(1) 查找? → Dict (哈希表)
需要有序 + 范围查询? → SkipList (跳表)
需要紧凑存储 + 数据量小? → Listpack / ZipList
需要两端快速操作? → QuickList (List类型)
纯整数集合 + 数量少? → IntSet
紧凑字符串 ≤ 44字节? → EMBSTR
大字符串 / 可修改? → RAW (SDS)10.3 🚨 编码相关陷阱速查表
| 陷阱 | 场景 | 后果 | 规避方法 |
|---|---|---|---|
| 编码不可逆 | Hash大量写入触转HT后删除 | 内存永久膨胀 | 使用 CONFIG SET 调大阈值 |
| IntSet升级 | set中500个int16，新增1个int64 | 内存×4 | 避免混用大小整数 |
| EMBSTR只读 | 对短字符串执行APPEND | 转RAW，多一次分配 | 一次性SET代替APPEND |
| ZipList连锁更新 | 修改临界值(253→254)的entry | O(n²)级卡顿 | 限制entry数量 |
| ZSet双索引 | 数据量大时 | 内存翻倍 | 评估是否需要ZSCORE O(1) |
| BGSAVE时rehash | fork后大量写入 | COW导致内存翻倍 | 阈值从1提到5 |
10.4 内存估算速查
用于评估内存占用 —— 尤其是大量小 Key 的场景：
| 组件 | 大小 (x86-64) | 说明 |
|---|---|---|
redisObject |
16 字节 | type(4b)+encoding(4b)+lru(24b)+refcount(4B)+ptr(8B) |
dictEntry |
24 字节 | key(8B)+val(8B)+next(8B) |
sdshdr8 |
3 字节 + data | len(1B)+alloc(1B)+flags(1B) |
sdshdr16 |
5 字节 + data | len(2B)+alloc(2B)+flags(1B) |
sdshdr32 |
9 字节 + data | len(4B)+alloc(4B)+flags(1B) |
sdshdr64 |
17 字节 + data | len(8B)+alloc(8B)+flags(1B) |
zskiplistNode |
~32B + level×16B | ele(8B)+score(8B)+backward(8B)+header开销 |
quicklistNode |
~48 字节 | 不含内部 zl 数据 |
intset 头 |
8 字节 | encoding(4B)+length(4B) |
listpack 头 |
6 字节 | tot-bytes(4B)+num-elem(2B) |
🔬 小 Key 内存估算示例：
一个简单的 SET key "hello":
dictEntry(key="key") = 24 字节
dictEntry(val) = 24 字节
redisObject(key) = 16 字节 (key 也是 redisObject)
redisObject(val) = 16 字节
SDS(EMBSTR "hello") = 16(redisObject)+3(sdshdr8)+5(data)+1(\0)=25 字节
但 embstr 是连续分配的: 总共 64 字节
(redisObject 16 + 剩余 48)
总计 ≈ 24 + 24 + 16 + 64 = 128 字节 (存一个 "hello")
实际数据 "hello" 只有 5 字节，但由于各种对象头和指针，
总占用达到了 ~128 字节，开销比 > 25:1
💡 这就是为什么 Redis 不适合存大量极小键值对——
元数据开销可能远超数据本身。10.5 设计哲学总结
Redis 底层数据结构的设计遵循几个核心原则：
- 内存至上：5 种 SDS 头部、IntSet 按需升级、EMBSTR 连续分配——每字节都精打细算
- 渐进式设计：rehash 不阻塞、SDS 预分配不频繁重分配——服务平稳优先
- Keep It Simple：跳表而不是红黑树、引用计数而不是 GC——实现简单才可靠
- 编码自适应：小数据用紧凑结构、大数据用高效结构——在时空之间动态平衡
- 不可逆设计：编码只升不降——复杂降级逻辑的风险 > 其内存收益
理解这些结构与原则，是真正掌握 Redis 性能调优与问题排查的基础。