对于许多开发者而言，Redis 源码像一座高山，仰望之余却不知从何攀爬。常常有朋友询问：“Redis 的核心数据结构怎么学才能真正掌握？”今天，我们将聚焦于其中的两大基石：SDS 动态字符串与 Adlist 双向链表。通过“拆解-实现-优化”的路径，带你从零开始，手写这两个核心模块，真正理解 Redis 速度背后的设计精髓。
一、Redis 高性能的秘密：极致优化的数据结构
你是否思考过，同样是存储键值对，为何 Redis 能达到每秒 10 万以上的请求处理能力，而许多自研的系统却望尘莫及？
核心答案，往往在于底层数据结构的差距。Redis 并非依赖某种“黑科技”，而是对每一个基础组件都进行了极致的工程优化。这些优化共同构筑了其高性能的基石，想要深入理解系统设计，这些组件的源码是绝佳的学习范本。你可以在 云栈社区 找到更多关于系统设计与性能优化的深度讨论。
下面列举的几个核心数据结构，每一个都是经过千锤百炼的工程杰作：
- SDS（Simple Dynamic String）：相比 C 原生字符串，避免了缓冲区溢出，并大幅减少了内存重分配次数。
- Adlist（双向链表）：通过函数指针实现泛型，支持任意数据类型存储，其迭代器设计提升了遍历效率。
- Dict（哈希表）：渐进式 rehash 机制使得扩容过程平滑，避免了服务卡顿。
- Skiplist（跳表）：有序集合的核心实现，查询效率逼近红黑树，但实现更为简洁。
- 等等……
然而，看懂源码和能够自己实现，是完全不同的两回事。很多人翻开 sds.c 文件，感觉已经理解，但一旦要求从零实现，立刻无从下手。这中间的鸿沟，在于对设计思想、实现步骤和工程权衡的缺乏实践。
二、学习方法论：拆解 → 实现 → 优化
为了跨越“看懂”到“会写”的鸿沟，我们采用一种渐进式的、可反馈的学习路径：
第一步：拆解设计目标
- SDS 为何设计 5 种不同的头部结构？
- Adlist 中的函数指针究竟承担什么角色？
- 这些设计背后的取舍（Trade-off）是什么？
第二步：从简到繁实现
- 第1天：完成一个最基础、能跑通的版本。
- 第2-N天：逐步添加功能和优化，每天都有可运行的代码和可见的进步。
第三步：逼近生产级优化
- 实现内存预分配策略。
- 优化热点代码路径。
- 完善泛型机制。
这种方法有效降低了学习门槛，通过持续的成就感建立信心，最终让你对数据结构的理解远超泛泛阅读。
三、SDS 实战：5 天实现高性能动态字符串
让我们先一览 SDS 模块五天的学习路线图。
5 天学习计划
Day 1：基础版 SDS - 掌握核心内存布局
今日目标是实现最简单的 SDS，理解其 header + buf 的连续内存设计。
今日目标：实现最简单的SDS，掌握header+buf的内存布局
┌─────────────────────────────────────┐
│ sdshdr8 (header) │
├──────────┬─────────┬────────┬───────┤
│ len (1B) │ alloc(1B)│ flags │ buf[] │
└──────────┴─────────┴────────┴───────┘
↑
SDS指针指向这里（buf的起始位置）
核心API：
✓ sdsNew() - 创建字符串
✓ sdsCat() - 字符串拼接
✓ sdsFree() - 释放内存
✓ sdsLen() - 获取长度
通过第一天，你将理解：为何 SDS 要将头部与数据放在连续内存、为何返回指针指向 buf 而非头部、以及 C 字符串的固有缺陷与 SDS 的解决方案。
Day 2：多类型支持 - 深入内存优化
Redis 设计了 5 种 SDS 头部类型以适应不同长度的字符串，核心目的是节省内存。
Redis的5种header类型：
sdshdr5 - 最多32字节（几乎不用）
sdshdr8 - 最多255字节
sdshdr16 - 最多64KB
sdshdr32 - 最多4GB
sdshdr64 - 理论无限大
类型选择逻辑：
长度 < 255 → sdshdr8
长度 < 64KB → sdshdr16
长度 < 4GB → sdshdr32
其他 → sdshdr64
这一天，你将掌握通过 flags 字段快速识别类型的技巧，以及类型升降级的策略。
Day 3：性能优化 - 预分配策略
减少内存重分配次数是提升性能的关键。Redis 采用了一种智能的预分配策略。
// Redis的预分配策略
if (len < SDS_MAX_PREALLOC) {
newlen = len * 2; // 小字符串：翻倍分配
} else {
newlen = len + SDS_MAX_PREALLOC; // 大字符串：增加1MB
}
你会理解预分配的意义，并学会如何进行性能对比测试。
Day 4：完善 API - 构建丰富功能集
实现完整的字符串操作工具箱：
✓ sdstrim() - 去除首尾空白
✓ sdsrange() - 截取子串
✓ sdssplitlen() - 分割字符串
✓ sdscatprintf() - 格式化输出
✓ sdstolower() - 大小写转换
✓ sdscmp() - 字符串比较
Day 5：测试与总结 - 达到生产级质量
进行全面的验证，确保代码的健壮性和高性能。
测试覆盖：
✓ 功能测试（100+用例）
✓ 性能测试（对比标准库）
✓ 内存测试（valgrind检测）
✓ 边界测试（空字符串、超大字符串）
性能数据：
- 拼接操作：比C字符串快5-10倍
- 内存重分配：减少90%以上
- 内存占用：节省30-50%（相比固定大小buffer）
学完 SDS 模块，你将获得：
✅ 深刻理解：从“知道”变为“能实现”。
✅ 面试利器：能透彻阐述 SDS 的每一个设计细节。
✅ 可用代码：一个可直接使用的高性能字符串库。
✅ 工程思维：掌握性能优化与工程权衡的方法。
四、Adlist 实战：4 天实现泛型双向链表
Adlist 是 Redis 列表类型的底层实现之一，其设计体现了泛型和灵活性。
4 天学习计划
Day 1：基础框架 - 搭建三大核心结构
实现 listNode（节点）、list（链表头）和 listIter（迭代器）。
双向链表的三大核心结构：
listNode (节点)
┌────────┐ ┌────────┐ ┌────────┐
│ prev │ ←── │ prev │ ←── │ prev │
├────────┤ ├────────┤ ├────────┤
│ value │ │ value │ │ value │
├────────┤ ├────────┤ ├────────┤
│ next │ ──→ │ next │ ──→ │ next │
└────────┘ └────────┘ └────────┘
list (链表)
┌──────────────────┐
│ head ──→ 首节点 │
│ tail ──→ 尾节点 │
│ len = 节点数量 │
│ dup (函数指针) │
│ free (函数指针) │
│ match (函数指针)│
└──────────────────┘
listIter (迭代器)
┌──────────────────┐
│ next ──→ 当前节点│
│ direction (方向) │
└──────────────────┘
Day 2：插入操作与迭代器
实现 O(1) 复杂度的头部/尾部插入，并完成正向、反向迭代器。
核心操作：
✓ listAddNodeHead() - O(1) 头部插入
✓ listAddNodeTail() - O(1) 尾部插入
✓ listInsertNode() - 任意位置插入
迭代器遍历：
listIter *iter = listGetIterator(list, AL_START_HEAD);
while ((node = listNext(iter)) != NULL) {
// 正向遍历
}
Day 3：删除与查找操作
实现节点的删除、解链，以及按值和索引的查找功能。
删除操作：
✓ listDelNode() - 删除指定节点
✓ listUnlinkNode() - 解除节点链接（不释放内存）
✓ listEmpty() - 清空链表
查找操作：
✓ listSearchKey() - 按值查找（O(n)）
✓ listIndex() - 按索引查找（O(n)）
Day 4：高级操作 - 理解泛型设计精髓
这是 Adlist 最精妙的部分，通过函数指针实现泛型，赋予链表处理任意数据类型的能力。
函数指针的妙用：
typedef void (*listFreeCallback)(void *value);
typedef void *(*listDupCallback)(void *value);
typedef int (*listMatchCallback)(void *value, void *key);
list->free = myFreeFunction; // 自定义释放逻辑
list->dup = myDupFunction; // 自定义复制逻辑
list->match = myMatchFunction; // 自定义比较逻辑
高级操作：
✓ listDup() - 深拷贝整个链表
✓ listJoin() - 合并两个链表
✓ listRotate() - 旋转操作（尾节点移到头部）
Adlist 的设计精髓
通过四天的实践，你会深刻领悟：
- 为何 Redis 不使用
std::list？ 为了 C 语言的极致灵活性与更小的内存开销，并通过函数指针实现跨类型的泛型。
- 操作分离哲学：
Link/Unlink（链接操作）与 Add/Del（内存管理）分离，给予调用者更大的控制权。
- 迭代器模式的优势： 提供统一、安全且支持双向的遍历接口。
五、真实代码示例与设计思考
以下是 SDS 中根据长度选择头部类型的核心逻辑，看似简单，却蕴含细节：
// 根据字符串长度选择最优的header类型
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5) // 32字节
return SDS_TYPE_5;
if (string_size < 1<<8) // 256字节
return SDS_TYPE_8;
if (string_size < 1<<16) // 64KB
return SDS_TYPE_16;
if (string_size < 1ll<<32) // 4GB
return SDS_TYPE_32;
return SDS_TYPE_64;
}
这短短几行代码背后，我们需要思考：临界点为何如此设定？如何高效判断现有 SDS 的类型？类型升级时如何保证数据无缝迁移？这些正是深入源码解析时需要攻克的难点。
六、课程特色与收获
本学习路径旨在提供一套可交付、可理解、可深化的实践方案：
- 每日清晰目标： 每天结束都能获得一个可运行、可测试的版本。
- 图解辅助理论： 结合内存布局图与流程图，理解设计而非死记代码。
- 完整构建系统： 提供 CMake 项目，避免环境问题，聚焦于C/C++ 代码本身。
- 渐进式路径： 从基础版到优化版，再到生产级，每一步都扎实稳固。
学习 Redis 数据结构，最终目的是吸收其优秀的设计思想。SDS 教会你在内存与性能间权衡；Adlist 展示了泛型设计的灵活性；后续的 Dict 则诠释了如何实现平滑的无阻塞扩容。这些思想，是超越特定工具、提升系统设计能力的宝贵财富。
从看懂到会写，关键在于迈出实践的第一步。希望这份对 SDS 与 Adlist 的实战解析，能成为你深入 Redis 世界乃至更广阔的系统编程领域的一块坚实基石。
发表于 2026-2-15 08:09:05
|
查看: 30|
回复: 0
