祥哥的技术博客

主题

📅 2026年7月20日 🏷️ Redis ⏱️ 14 分钟阅读 Redis数据结构SDSSkipList

Redis 5 种基本数据结构及其底层实现 ​

提出问题 ​

Redis 之所以快，除了单线程模型，数据结构设计是另一个核心原因。面试常问：Redis 有哪几种基本数据类型？各自的底层编码是什么？String 底层为什么用 SDS（Simple Dynamic String）而不是 C 语言的 char*？ZSet 为什么用跳跃表而不用红黑树？这些问题的答案，直接决定了你是不是真的理解 Redis 的性能哲学。

对 Java 后端的特殊意义：你在 Java 里用 HashMap、ArrayList、TreeSet，但 Redis 的数据结构不是在 JVM 堆里跑，而是在一个共享内存的进程里。数据结构的编码方式直接决定了内存消耗和网络开销。做 Agent 工程时，缓存 Agent 的 session state、tool 调用结果、LLM 的中间推理——每一个选择背后都是数据结构。

分析问题 ​

Redis 对外暴露 5 种基本类型，但每种类型背后有 2-3 种底层编码，并且会根据数据量和元素大小自动切换。这种"内部编码 + 自适应切换"的设计，是 Redis 在内存效率和操作性能之间精心打造的平衡。

String — SDS 与三种编码切换 ​

C 语言的 char* 有两大问题：获取长度要遍历整条字符串 O(N)，拼接字符串时没有长度保护容易缓冲区溢出。Redis 的 SDS 结构里直接存了 len（当前长度）和 free（剩余空间），获取长度 O(1)。

c
struct sdshdr {
    int len;    // 已用长度
    int free;   // 剩余空间
    char buf[]; // 字符数组
};

SDS 的预分配策略也很聪明：小于 1MB 时翻倍扩容，大于 1MB 时每次只加 1MB，避免内存浪费。这跟 Java 的 ArrayList 扩容策略（1.5 倍）本质一致，但 SDS 的翻倍策略在小数据时更激进，因为 Redis 的内存是它自己管理的，不像 JVM 有 GC 兜底。

但大多数人不知道：String 底层有三种编码，不是只有 SDS。

编码触发条件存储方式类比 Java
int值可解析为整数（如 "12345"）直接存 long 型，8 字节Long.valueOf() 缓存 -128~127 类似
embstr长度 ≤ 44 字节一次性分配内存，SDS 和 redisObject 连续String.intern() 的紧凑化，但更底层
raw长度 > 44 字节分两次分配，redisObject 和 SDS 分开普通 new String()

踩坑案例：某次线上 Redis 内存暴涨，排查发现是一个缓存 key 的 value 从 43 字节涨到 45 字节，编码从 embstr 跳到 raw，内存碎片率从 1.01 飙升到 1.8。因为 embstr 是只读的，一旦修改就退化为 raw，所以对 String 做 append 操作，即使结果很短也不会保持在 embstr。

python
# 模拟编码切换
import redis

r = redis.Redis()
r.set("key1", "a" * 43)
print(r.object("encoding", "key1"))  # embstr
r.set("key2", "a" * 45)
print(r.object("encoding", "key2"))  # raw
r.append("key1", "b")
print(r.object("encoding", "key1"))  # raw，append 后永不回退 embstr

这个 44 字节的临界值来自：redisObject（16 字节）+ SDS 头（3 字节）+ 终止符（1 字节）= 20，64 字节缓存行减去 20 = 44。所以 embstr 的 44 字节不是拍脑袋定的，是 CPU 缓存行对齐的结果。

Java 视角：你在 Java 里用 StringBuilder 拼接字符串时，JVM 内部也是类似的预分配策略（char[] 扩容）。但 SDS 的 free 字段让你能直接读出来，而 Java 的 StringBuilder 容量得猜 capacity()。做 Agent 的 tool call 结果缓存时，如果缓存的值刚好 43 字节以内，用 SET 不要用 APPEND，否则 raw 编码多一倍内存。

List — QuickList 与 Listpack 的演进 ​

Redis 3.2 之前，List 底层是 ZipList（压缩列表，连续内存）或 LinkedList（双向链表），取长补短。3.2 之后统一为 QuickList：一个双向链表，每个节点里挂一个 ZipList 片段。

c
// 伪代码：QuickList 的一个节点
struct QuickListNode {
    QuickListNode *prev;
    QuickListNode *next;
    ZipList *zl;         // 压缩列表片段
    int sz;              // 压缩列表的字节数
    int count;           // 该片段中的元素数量
};

这样设计的好处是：既有链表的快速插入删除，又有紧凑内存减少碎片和指针开销。你还可以通过 list-max-ziplist-size 调整每个片段的大小，在内存和性能之间做取舍。

ZipList 的坑：连锁更新（Cascade Update）

ZipList 的每个 entry 都存了 prevlen（前一个 entry 的长度）。如果前一个 entry 从 ≤254 字节变成 ≥255 字节，prevlen 字段就需要从 1 字节扩展为 5 字节，从而引发当前 entry 的长度变化，再触发下一个 entry 的连锁更新——最坏情况 O(N²)。

text
时序：ZipList 连锁更新

正常状态：
entry1 (250B) → entry2 (prevlen=1, data=100B) → entry3 (prevlen=1, data=200B)

插入一个 300B 的 entry1 之后：
entry1 (300B) → entry2 (prevlen=1→5, data=100B) → entry3 (prevlen 需要从 1→5, data=200B)
                 ↑ entry2 长度从 101 变成 105，触发了 entry3 的 prevlen 更新

所以 Redis 7.0 用 Listpack 替代了 ZipList。Listpack 的 entry 只存自己的长度，不存前一个 entry 的长度，彻底消除了连锁更新问题。生产环境升级到 7.0+ 后，如果 List/Hash/ZSet 中有大量小 entry，内存碎片率会明显下降。

Agent 场景实战：用 List 做 LLM 对话历史队列时，LPUSH + LTRIM 是经典操作。但注意：如果每轮对话的 message 是 200 字节（大于 64 字节的 ZipList 阈值），QuickList 里的每个节点头部开销会累积。实测 1000 轮对话，使用 List 存 message 比用 String 拼接存 JSON 多消耗 40% 内存。建议：合并相邻的 10 条 message 为一个 JSON 字符串存一条 List 元素。

java
// Java 端：LLM 对话历史存 Redis List
// 错误做法：每轮一个 List entry
// redisTemplate.opsForList().leftPush("chat:session:123", messageJson);

// 正确做法：每 10 轮合并一次
List<String> batch = new ArrayList<>(10);
batch.add(messageJson);
if (batch.size() >= 10) {
    String merged = String.join("|||", batch);  // 自定义分隔符
    redisTemplate.opsForList().leftPush("chat:session:123", merged);
    batch.clear();
}

Hash — ZipList → Dict 的不可逆转换 ​

Hash 在元素少、值短的时候用 ZipList 存储（内存紧凑），超过阈值后转为 Dict（哈希表）。但重点来了：这个转换是不可逆的。一旦一个 Hash 从 ZipList 升到 Dict，即使你把元素删光了，它也不会退回去。线上如果预估一个 Hash 的 field 数量会超过 512 个，就提前调大 hash-max-ziplist-entries，否则内存翻倍影响整体。

踩坑案例：一个业务用 Hash 存储用户画像，每个用户有 200 个 field，但有一个热点用户有 3000 个 field。那个命中的用户让整个 Hash 升到 Dict，其他 999 个用户的 field 也跟着变成了 Dict 存储。内存从 3GB 飙升到 12GB。这就是 ZipList 转 Dict 的一粒老鼠屎效应。

解决方案：要么把热点用户单独拆 key（user:hot:123 单独一个 Hash），要么调大 hash-max-ziplist-entries 到 3000+，但要注意 ZipList 的查询性能跟 entry 数量相关（O(N)），调大了查询会变慢。

Agent 场景实战：用 Hash 存 Agent 的 tool call 结果缓存是最常见的场景。每个 tool 的 cache key 作为 field，序列化结果作为 value。如果 Agent 有 50 个 tool，每个 tool 的缓存 field 不超过 10 个，那么一个 Hash 总共 500 个 field，刚好在 ZipList 阈值（512）以内。但如果某个多轮对话让缓存的 field 数超过 512，整个 Hash 升到 Dict，所有 field 都翻倍。

java
// Spring Boot 中控制 Hash 的编码
// 用 HashOperations 存 Agent Tool 缓存
HashOperations<String, String, String> ops = redisTemplate.opsForHash();

// 预估每个 Agent session 最多 400 个 tool 缓存 field
// 手动调大阈值，避免不可逆升级
// 在 Redis 配置中设置：hash-max-ziplist-entries 1024
// 或者用 CONFIG SET 动态调整：
// redisTemplate.opsForRedis().execute((RedisCallback<Void>) conn -> {
//     conn.setConfig("hash-max-ziplist-entries", "1024");
//     return null;
// });

// 然后放心存
ops.put("agent:cache:session_001", "tool:search", "{\"result\":\"...\"}");

Set — IntSet 升级为 Dict 不可逆 ​

Set 如果所有元素都是整数且数量少，Redis 用 IntSet 存储（有序数组，二分查找）。一旦插入非整数或元素数超过 set-max-intset-entries（默认 512），就转为 Dict。

IntSet 的升级也是不可逆的，但跟 Hash 的 ZipList 不同，IntSet 升 Dict 的代价相对可控，因为 Set 本身没有 field-value 的概念，Dict 的 key 就是 Set 的元素。

对比 IntSet vs Dict 的 Set 操作性能：

操作IntSet (有序数组)Dict (哈希表)
SISMEMBERO(log N) 二分查找O(1) 哈希
SADDO(N) 插入后移位O(1)
SMEMBERSO(N) 顺序遍历O(N) 遍历，顺序随机
内存效率极高，int 直接存 4/8 字节低，每个 key 有 dictEntry 开销约 32 字节

Agent 场景实战：Set 在 Agent 工程中最适合做去重和权限判断。比如 Agent 执行过程中的已处理实体 ID 集合，如果全是整数（long 类型的 ID），Set 自动用 IntSet，内存效率极高。但一旦混入字符串（如 "user_123"），就升到 Dict了。

java
// 错误：混入字符串导致 IntSet 升级
// redisTemplate.opsForSet().add("agent:processed:ids", "123", "456", "user_789");
// 第 3 个元素 "user_789" 让整个 Set 从 IntSet 升到 Dict

// 正确：统一用整数 ID
redisTemplate.opsForSet().add("agent:processed:ids", "123", "456", "789");
// 三个都是整数，IntSet 愉快地工作

ZSet — 跳跃表 + 字典的双结构 ​

ZSet 是五个类型里最"重"的。它同时维护一个 SkipList（按 score 排序）和一个 Dict（按 member 查分），两点牺牲内存换 O(log N) 范围查询 + O(1) 单点查询。

c
typedef struct zset {
    dict *dict;      // member → score 映射
    zskiplist *zsl;  // 按 score 排序的跳跃表
} zset;

跳跃表层数服从几何分布，每层概率 1/4，平均每个节点只有 1.33 层指针。相比平衡树（红黑树），跳跃表省去了旋转操作，实现简单，并发友好，这就是 Redis 选它的原因。

python
# 模拟跳跃表插入
import random
class SkipNode:
    def __init__(self, score, member, level):
        self.score = score
        self.member = member
        self.forward = [None] * (level + 1)

def random_level():
    level = 0
    while random.random() < 0.25:  # p=1/4
        level += 1
    return level  # 期望约 1.33 层

为什么不用红黑树？ 面试高频题。三个原因：

  1. 实现复杂度：跳跃表约 200 行 C 代码 vs 红黑树约 500 行，Redis 的 C 代码没有标准库的红黑树实现，自己写一个太容易出 bug
  2. 范围查询：跳跃表的 forward 指针可以直接遍历，红黑树的中序遍历需要递归/栈，跳跃表区间锁粒度更细
  3. 并发修改：红黑树旋转时可能涉及多个节点，跳跃表插入只影响相邻节点的 forward 指针，多线程下更容易局部锁定

ZSet 的 ZipList 编码：小数据时 ZSet 也用 ZipList，按 (member, score) 交替存储。zset-max-ziplist-entries 默认 128 个 entry，zset-max-ziplist-value 默认 64 字节。超过任一阈值就升到 SkipList+Dict，也是不可逆的。

踩坑案例：实时排行榜场景，往 ZSet 里批量加 1000 个成员，每个成员名约 10 字节，值约 8 字节。突然插入第 129 个时，ZSet 从 ZipList 升到 SkipList+Dict，内存从 3KB 涨到 30KB。如果业务知道数据量会超过 128，直接 ZADD 之前先插入一个 dummy 成员触发升级，提前消耗掉那一次转换的开销就行。

java
// Java 端：ZSet 做 Agent 的优先级队列
// 场景：多个 Agent 任务需要按优先级调度

// 批量插入前先触发升级
ZSetOperations<String, String> zset = redisTemplate.opsForZSet();
// 插入一个 dummy 成员触发升级，后面再删掉
zset.add("agent:task:queue", "__dummy__", 0);
zset.remove("agent:task:queue", "__dummy__");
// 此时 ZSet 已经是 SkipList+Dict 编码，后续插入稳定

// 然后正常插入任务
for (Task task : taskList) {
    zset.add("agent:task:queue", task.getId(), task.getPriority());
}

// 轮询最高优先级任务
Set<String> top = zset.reverseRange("agent:task:queue", 0, 0);

数据结构选择实战指南 ​

把 5 种数据结构的编码切换规则总结成一张决策图：

text
String → 值是什么类型？
  ├─ 整数且 ≤ 2^63-1 → int 编码 (8B)
  ├─ 字符串 ≤ 44B  → embstr (1 次 malloc)
  └─ 字符串 > 44B  → raw (2 次 malloc)

List → 数据规模？
  ├─ 小（各 entry ≤ 64B，总数 ≤ 512）→ QuickList-ZipList 片段小
  └─ 大 → QuickList-ZipList 片段大（调 list-max-ziplist-size）

Hash → 数据规模？
  ├─ 小（field ≤ 512，value ≤ 64B）→ ZipList
  └─ 大 → Dict（注意不可逆！）

Set → 元素类型？
  ├─ 全是整数且 ≤ 512 个 → IntSet
  └─ 其他 → Dict

ZSet → 数据规模？
  ├─ 小（member ≤ 128，value ≤ 64B）→ ZipList
  └─ 大 → SkipList + Dict（注意不可逆！）

总结 ​

Redis 的数据结构设计遵循一个核心原则：小数据用紧凑编码省内存，大数据用高效结构保性能。记住这个原则，面试时就不会只背"五种类型"的八股，而是能顺着"为什么选这个结构"、"阈值怎么调"、"转换有什么代价"一路深挖下去——这才是 P7 该有的水平。

类型小数据编码大数据编码核心阈值升级可逆？7.0 变化
Stringint/embstrraw44 字节（embstr 上限）不可逆—
ListQuickListQuickListlist-max-ziplist-size—Listpack 替代 ZipList
HashZipListDicthash-max-ziplist-entries 512不可逆Listpack 替代 ZipList
SetIntSetDictset-max-intset-entries 512不可逆—
ZSetZipListSkipList+Dictzset-max-ziplist-entries 128不可逆Listpack 替代 ZipList

面试追问：如果 ZooKeeper 的 ZNode 也要做排序集合，为什么不用 Redis 的 ZSet？—— 因为 ZK 的 ZNode 是树形路径，不是扁平集合，路径查询需要前缀匹配，ZSet 的 SkipList 按 score 排序，无法做路径前缀扫描。所以 Redis 和 ZK 的 ZSet 名字一样，底层数据结构完全不同。

面试追问二：一个 Java 进程和一个 Redis 进程都存了 100 万个 String key，谁的物理内存更大？—— Redis 的 SDS 结构紧凑，没有 Java String 的 char[] 对象头（12 字节）+ 对齐 padding，同样 100 万条 10 字节字符串，Redis 约 80MB，Java 约 200MB（含对象头）。但 Java 的 String 在 JVM 堆里，GC 可以回收；Redis 的 string 是永久的，不主动删除就一直在。所以 Agent 场景下缓存 LLM 输出时，用 Redis 存千万级单条不如用本地 Caffeine 缓存，后者可以按 LRU 自动淘汰。

参考：Redis 源码 src/quicklist.h、src/ziplist.c、src/t_zset.c、src/listpack.c、Redis 官方文档

手撕 → 框架 → 生产化，一步步把 AI Agent 工程化搞透。

Copyright © 2026 祥哥