Redis 各种数据结构的内部原理

Redis 作为高性能的内存数据库，其优异的性能很大程度上得益于精心设计的底层数据结构。本文将深入剖析 Redis 各种数据结构的内部实现原理，解答关键设计决策背后的思考，并提供实际场景下的优化策略。

Redis 数据类型概览

Redis 支持多种数据类型，每种类型都有其特定的应用场景和底层实现：

redisObject 的精巧设计

统一对象模型

Redis 并不直接存储原始数据，而是将所有数据包装在 redisObject 结构中，这是 Redis 灵活性和高性能的基础：

redisObject 结构（16字节）

字段	位数	说明
type	4bit	数据类型
encoding	4bit	编码方式
LRU	24bit	LRU/LFU信息
refcount	32bit	引用计数
ptr	64bit	数据指针

type 字段取值

值	常量名	说明
0	`REDIS_STRING`	字符串类型
1	`REDIS_LIST`	列表类型
2	`REDIS_HASH`	哈希类型
3	`REDIS_SET`	集合类型
4	`REDIS_ZSET`	有序集合类型

encoding 字段取值

编码类型	说明
`REDIS_ENCODING_RAW`	原始字符串编码
`REDIS_ENCODING_INT`	整数编码
`REDIS_ENCODING_HT`	哈希表编码
`REDIS_ENCODING_ZIPMAP`	压缩映射编码
`REDIS_ENCODING_LINKEDLIST`	链表编码
`REDIS_ENCODING_ZIPLIST`	压缩列表编码
`REDIS_ENCODING_INTSET`	整数集合编码
`REDIS_ENCODING_SKIPLIST`	跳跃表编码

设计优势分析

为什么要这样设计？

类型安全：通过 type 字段，Redis 可以在运行时检查操作的合法性
编码透明：encoding 字段允许同一类型使用不同的底层实现，对用户透明
内存管理：refcount 支持对象共享，特别是小整数的共享
缓存友好：LRU 字段支持内存回收策略

自动编码选择机制

Redis 的智能之处在于能够根据数据特征自动选择最优编码：

SDS：超越 C 字符串的设计

SDS 结构设计

Simple Dynamic String (SDS) 是 Redis 字符串的底层实现，相比 C 字符串有显著优势：

C 字符串结构

SDS 结构组成

SDS vs C 字符串对比

三个维度的优势分析

内存安全角度：

缓冲区溢出防护：SDS 记录缓冲区大小，自动检查和扩容
内存泄漏预防：封装的内存管理，避免手动管理带来的错误

性能角度：

O(1) 长度获取：直接读取 len 字段，而非遍历计算
减少内存分配：空间预分配策略，减少频繁的内存分配
二进制安全：支持包含 \0 的二进制数据

功能角度：

兼容性好：保留 C 字符串的 \0 结尾，兼容 C 函数库
扩展性强：支持字符串的高效拼接、裁剪等操作

SDS 的空间分配策略

实际应用场景： 假设一个用户会话数据的频繁更新：

// 用户会话数据示例
session := "user:123:session_data_here"

// 多次追加操作
session += ",action_login_20240101"
session += ",action_view_page_home"
session += ",action_click_button_submit"
// ... 更多操作

// SDS 的预分配策略避免了每次追加都重新分配内存

List 的双重实现策略

ziplist vs linkedlist 选择逻辑

Redis List 根据数据特征自动选择底层实现：

1、Redis List 编码选择流程

2、ziplist 特性分析

3、linkedlist 特性分析

性能对比分析

操作类型	ziplist	linkedlist	说明
头部插入	O(n)	O(1)	ziplist 需要移动所有元素
尾部插入	O(1)	O(1)	两者都支持快速尾部插入
中间插入	O(n)	O(n)	都需要先定位位置
按索引访问	O(n)	O(n)	ziplist 缓存友好性稍好
内存占用	低	高	ziplist 无指针开销
缓存友好性	好	差	ziplist 连续内存布局

ziplist 内存布局设计

ziplist 通过精巧的内存布局实现空间效率最大化：

为什么能节省内存？

无指针开销：连续内存布局，无需存储指针
变长编码：根据实际需要使用最少的字节数
紧凑存储：所有数据紧密排列，无内存碎片
头信息优化：元数据信息最小化

Hash 的渐进式 Rehash

传统 Rehash 的问题

渐进式 Rehash 机制

Redis 通过渐进式 rehash 解决了传统 rehash 的阻塞问题：

解决的关键问题

阻塞问题：将大任务分解为小任务，避免长时间阻塞
内存峰值：虽然短期内存翻倍，但避免了更大的性能问题
一致性保证：通过巧妙的读写策略保证数据一致性

渐进式 rehash 的触发时机：

// 负载因子计算
loadFactor := used / size

// 触发扩容条件
if (loadFactor >= 1 && !backgroundSaving) || loadFactor >= 5 {
    // 开始渐进式 rehash
}

// 触发缩容条件  
if loadFactor < 0.1 {
    // 开始渐进式 rehash (缩容)
}

链表法 vs 开放寻址法

Redis 选择链表法的原因

Redis 选择链表法的核心原因：

删除操作频繁：Redis 需要支持大量的 DEL 操作，链表法删除简单
动态 rehash：链表法便于实现渐进式 rehash
实现复杂度：避免开放寻址法的边界情况处理
内存管理：避免开放寻址法的"删除标记"导致的内存浪费

ZSet：跳表 vs 红黑树

多维度对比分析

详细对比表

特性	跳表	红黑树	Redis 偏好
实现复杂度	简单	复杂	⭐ 跳表
范围查询	O(log n + k)	O(log n + k)	⭐ 跳表 (更自然)
插入删除	O(log n)	O(log n)	平手
内存开销	中等 (索引层)	低	红黑树
缓存友好性	好 (顺序访问)	中等	⭐ 跳表
并发支持	容易实现	困难	⭐ 跳表
调试难度	低	高	⭐ 跳表

实际业务场景优势

排行榜系统示例：

HyperLogLog：近似计数的艺术

什么是 HyperLogLog？

HyperLogLog 是一种概率数据结构，用于估算集合的基数（唯一元素个数），具有以下特点：

基数估算原理

为什么误差率是 0.81%？

HyperLogLog vs Set 选择指南

具体业务案例对比：

业务场景	数据规模	内存需求对比	推荐方案	理由
博客网站日活	10万用户	Set: 10MB vs HLL: 12KB	Set	数据量小，要求精确
电商平台日活	500万用户	Set: 500MB vs HLL: 12KB	HyperLogLog	内存节省显著
广告曝光统计	1亿次曝光	Set: 10GB vs HLL: 12KB	HyperLogLog	Set方案不可行
支付系统日活	100万用户	Set: 100MB vs HLL: 12KB	Set	金融数据要求精确

性能优化实战案例

Hash 对象内存过大的分析和优化

当发现 Redis 中某个 Hash 对象占用内存过大时，分析和优化流程：

大 List 平滑迁移方案

对于包含大量数据的 List，需要设计平滑迁移策略：

迁移策略设计要点：

批次大小：根据 List 大小和业务重要性调整
- 小于1万元素：批次1000，间隔10ms
- 1万-10万元素：批次500，间隔50ms
- 大于10万元素：批次100，间隔100ms
原子性保证：使用 Lua 脚本确保批次操作的原子性
监控指标：迁移进度、错误率、对业务的影响
回滚机制：迁移失败时的数据恢复策略

-- Lua 脚本示例：原子性批量迁移
local source = KEYS[1]
local target = KEYS[2] 
local count = tonumber(ARGV[1])

local elements = {}
for i = 1, count do
    local element = redis.call('LPOP', source)
    if element then
        table.insert(elements, element)
    else
        break
    end
end

if #elements > 0 then
    redis.call('RPUSH', target, unpack(elements))
end

return #elements

总结与最佳实践

数据结构选择指南

性能优化建议

合理设置配置参数：根据业务特点调整 ziplist 相关参数
监控内存使用：定期检查大对象，及时优化
选择合适的数据类型：避免用 String 存储结构化数据
利用渐进式操作：大数据量操作要考虑对性能的影响
理解编码转换：避免不必要的编码升级

Redis 的每个设计决策都体现了对性能、内存效率和使用便利性的精心平衡。深入理解这些内部原理，不仅能帮助我们更好地使用 Redis，也为系统设计提供了宝贵的参考。

Redis 数据类型概览​

redisObject 的精巧设计​

统一对象模型​

设计优势分析​

自动编码选择机制​

SDS：超越 C 字符串的设计​

SDS 结构设计​

三个维度的优势分析​

SDS 的空间分配策略​

List 的双重实现策略​

ziplist vs linkedlist 选择逻辑​

性能对比分析​

ziplist 内存布局设计​

Hash 的渐进式 Rehash​

传统 Rehash 的问题​

渐进式 Rehash 机制​

解决的关键问题​

链表法 vs 开放寻址法​

Redis 选择链表法的原因​

ZSet：跳表 vs 红黑树​

多维度对比分析​

详细对比表​

实际业务场景优势​

HyperLogLog：近似计数的艺术​

什么是 HyperLogLog？​

基数估算原理​

为什么误差率是 0.81%？​

HyperLogLog vs Set 选择指南​

性能优化实战案例​

Hash 对象内存过大的分析和优化​

大 List 平滑迁移方案​

总结与最佳实践​

数据结构选择指南​

性能优化建议​

Reference​