Redis 系列 16. 底层数据结构：redisObject、SDS、QuickList、ListPack 与跳表

1. 为什么要看底层结构

Redis 对外暴露的是 String、Hash、List、Set、ZSet 这些数据类型，但底层编码会根据数据规模和内容变化。

比如同样是 String，底层可能是 int、embstr、raw。同样是 Hash，小数据量时可能是 listpack，大了以后会转 hashtable。

这会直接影响内存、性能和 BigKey 风险。

查看编码：

object encoding user:1001
debug object user:1001

DEBUG OBJECT 生产环境慎用，一般只在测试环境验证。很多生产环境会禁用 DEBUG 类命令，排查时优先使用 OBJECT ENCODING、MEMORY USAGE 和业务侧采样。

2. redisObject 是入口

Redis 每个 key 对应的 value 都会通过对象结构管理。可以从核心字段理解 redisObject：

字段	说明
type	对外数据类型，比如 string、list、hash
encoding	底层编码，比如 raw、int、listpack、hashtable
ptr	指向真实数据结构
lru/lfu	用于淘汰策略相关信息
refcount	引用计数

redisObject 结构图如下：

这里要注意版本差异。Redis 早期文档里常见 ziplist，Redis 7 已经大量使用 listpack 替代 ziplist。学习时要以当前 Redis 版本的 OBJECT ENCODING 和源码为准。

encoding 不是写入时永远固定的静态标签，而是运行时动态行为。同一个对外类型会随着元素数量、元素大小和内容变化发生编码转换，并且很多转换是 upgrade-only：从紧凑编码升级到 hashtable 或 skiplist 后，通常不会因为元素变少自动降回紧凑编码。

lru/lfu 字段服务于淘汰策略。LFU 不是简单递增计数，还包含随时间衰减的 aging / decay 机制，用来避免很久以前的热点 key 永远占据高频位置。refcount 则用于引用计数和共享对象优化，例如小整数共享对象这类 OBJ_SHARED 场景。

3. String：SDS、int、embstr、raw

Redis String 不是 C 语言原生字符串，而是 SDS。

SDS 的好处：

1. O(1) 获取长度，因为长度缓存在 len 字段里。
2. 二进制安全，可以存 \0。
3. 扩容时有空间预分配，减少频繁 realloc。
4. 记录已用长度和剩余空间。

SDS 扩容会做空间预分配。较小时通常按倍增方式预留空间；达到一定阈值后，预分配增量会变得更保守，避免大字符串每次扩容都造成过大的内存浪费。

常见编码：

编码	场景
int	可以用 64-bit signed integer 表示的字符串
embstr	较短字符串，对象头和 SDS 连续分配
raw	较长字符串，单独分配 SDS

验证：

set age 18
object encoding age

set name zhangsan
object encoding name

set bigstr "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
object encoding bigstr

embstr 的优势是对象头和 SDS 内存更连续，分配和释放成本更低；字符串变大后会转成 raw。不要把 String 当成无限大的 JSON 容器。大 JSON String 会导致 JSON 解析成本、网络传输、序列化、删除和复制都变重，也会放大客户端和服务端的延迟。

4. Hash：listpack 和 hashtable

Hash 适合存对象字段：

hset user:1001 name zhangsan age 18 city shenzhen
hget user:1001 name
hgetall user:1001

小 Hash 通常使用紧凑编码 listpack，大到一定程度会转成 hashtable。阈值受配置影响，不同版本配置项名称可能不同，Redis 7 常见配置是：

hash-max-listpack-entries 512
hash-max-listpack-value 64

含义是：元素个数和单个 value 大小都较小时，尽量使用紧凑编码；超过阈值后转 hashtable，以换取更好的查询和更新性能。

hashtable 背后依赖 Redis 字典结构。字典扩容或收缩时会使用渐进式 rehash，把迁移成本分摊到后续多次操作中，避免一次性搬迁整个哈希表造成长时间阻塞。

5. List：quicklist

Redis List 的常见底层结构是 quicklist。Redis 早期 List 会在 ziplist 和双向链表之间切换；后来 quicklist 替代了这种组合。放到 Redis 7 的语境里，可以把它理解成“链表 + listpack”的组合：

1. 外层是双向链表，便于两端 push/pop。
2. 每个节点内部是紧凑列表，节省内存。

常用命令：

lpush queue:task t1 t2 t3
rpop queue:task
lrange queue:task 0 9

List 常见问题是把它当消息队列无限堆积。LLEN 持续增长时，要关注消费者是否正常、是否需要拆队列、是否要迁移到 Stream 或专业 MQ。

quicklist 适合两端 push / pop，但中间位置的大范围访问仍然不适合高频使用。Redis 7 语境下要注意 listpack 取代 ziplist 的迁移，不要再按旧版本 ziplist 配置项理解 List 的内存行为。

6. Set：intset 和 hashtable

Set 用于去重：

sadd tag:java user:1 user:2 user:3
sismember tag:java user:1
scard tag:java

底层编码常见两种：

编码	场景
intset	元素都是整数且数量较少，内部按整数有序存储
hashtable	普通集合或元素较多

配置项示例：

set-max-intset-entries 512

Set 的危险命令是 SMEMBERS，大集合一次性返回会阻塞主线程并占满网络。大集合遍历应该使用 SSCAN。

7. ZSet：listpack、skiplist 和 dict

ZSet 是有序集合，典型场景是排行榜：

zadd rank:daily 100 user:1 90 user:2
zrevrange rank:daily 0 9 withscores
zrank rank:daily user:1

小 ZSet 可以使用 listpack。数据量大以后，通常使用 skiplist + dict：

结构	用途
dict	按 member 快速查 score
skiplist	按 score 排序和范围查询

Redis 7 常见配置项是：

127.0.0.1:6379> config get zset-max-listpack-*
1) "zset-max-listpack-entries"
2) "128"
3) "zset-max-listpack-value"
4) "64"

也就是说，元素数量较少并且 member 较短时，ZSet 可以使用 listpack；超过阈值后会转成 skiplist + dict。

如果为了观察编码转换，可以在测试环境临时调小阈值：

127.0.0.1:6379> config set zset-max-listpack-entries 3
OK

127.0.0.1:6379> config set zset-max-listpack-value 6
OK

这里表示：

当 zset 元素数量超过 3 个时，改用跳跃表。
当 zset 中 member 长度超过 6 字节时，改用跳跃表。

再次查看配置：

127.0.0.1:6379> config get zset-max-listpack-*
1) "zset-max-listpack-entries"
2) "3"
3) "zset-max-listpack-value"
4) "6"

简单总结：

元素数量较少，并且 member 较短：使用 listpack
元素数量较多，或者 member 较长：使用跳跃表

这种组合让 ZSet 既能快速按成员查分数，又能按分数范围排序。

dict 用于 O(1) 级别的 member lookup，skiplist 用于按 score 排序。score 相同的情况下，Redis 会按 member 字典序作为 tie-breaker，这也是 ZSet 排名结果稳定性的来源之一。

8. 跳表为什么适合范围查询

普通链表查找只能从头走，复杂度 O(N)。跳表通过多级索引，把查找过程变成类似二分的逐层下降。

跳表的平均查找、插入、删除复杂度是 O(logN)，范围查询也很自然：先定位起点，再沿着底层链表向后遍历。因此范围查询复杂度通常可以理解为 O(logN + M)，其中 M 是返回元素数量。

跳表查询的时间复杂度分析

跳表是在原始有序链表的基础上，增加多级索引来提升查询效率的数据结构。

假设原始链表中有 n 个节点，跳表会按照一定规则从下层节点中抽取部分节点，作为上一层索引。

一种常见理解方式是：每两个节点向上抽取一个节点，也就是“两两取首”。这是为了帮助理解复杂度，Redis 跳表实际使用 random level generator 生成层高，不是严格按固定间隔抽取。因此实际层高是概率模型，不是严格的 log₂n。

这样可以估算出每一级索引的节点数量：

第 1 级索引节点数量大约是：n / 2
第 2 级索引节点数量大约是：n / 4
第 3 级索引节点数量大约是：n / 8

依次类推，第 k 级索引的节点数量就是：

n / (2^k)

也就是说，每向上一层，索引节点数量大约减少一半。

假设跳表索引一共有 h 级，并且最高级索引只剩下大约 2 个节点。

根据公式可以得到：

n / (2^h) = 2

进一步推导：

h = log₂n - 1

如果把原始链表这一层也计算在内，那么整个跳表的高度大约就是：

log₂n

所以跳表的查询时间复杂度可以近似认为是：

O(log n)

公式推导

n / (2^k)
=> n / (2^h) = 2
=> h = log₂n - 1
=> O(log n)

简单总结

跳表通过给有序链表增加多级索引，把原来需要从头到尾遍历的查询方式，变成了类似二分查找的分层查找。

因此，跳表的查询效率比普通链表高很多。

普通链表查询的时间复杂度是：

O(n)

跳表查询的时间复杂度是：

O(log n)

一句话总结：

跳表用空间换时间，通过多级索引提高查询效率。

$$
\frac{n}{2^k}
\Rightarrow
\frac{n}{2^h}=2
\Rightarrow
h=\log_2 n - 1
\Rightarrow
O(\log n)
$$

Redis 没有用平衡树实现 ZSet 排序结构，跳表实现相对简单，范围遍历也方便。本节推导只是帮助理解跳表为什么接近 O(logN)，不要把它理解成 Redis 跳表每一层都严格减半。

9. 编码转换带来的启发

底层编码告诉我们几个工程结论：

结论	说明
小对象更省内存	Redis 会用紧凑编码优化小集合
大对象会转换编码	转换后查询可能更快，但内存会变大
BigKey 风险真实存在	大 Hash、大 List、大 ZSet 都会拖慢命令并放大延迟
命令复杂度要看规模	HGET 和 HGETALL 不是一个量级

所以 Redis 使用建议仍然回到那几条：key 要拆得合理，value 不能无限大，集合要控制长度，批量读取要分页或游标化。

encoding conversion 的触发通常是 threshold-based：元素个数、元素长度、是否全为整数等条件变化后触发升级。同一种 Redis 数据类型在不同规模下可能有完全不同的底层编码，所以不要假设 “Hash 就一定是 hashtable” 或 “ZSet 就一定是 skiplist”。

BigKey 的风险也不只是内存占用。大对象会造成 latency amplification：命令执行时间、网络返回、复制、AOF、删除释放都会被放大。

10. 常用验证命令

type key
object encoding key
memory usage key
strlen key
hlen key
llen key
scard key
zcard key

这些命令能帮我们从“感觉这个 key 可能大”变成“知道它是什么类型、什么编码、占多少内存、多少元素”。

MEMORY USAGE 看到的不只是逻辑 value 大小，还会包含对象头、编码结构和 allocator overhead。Redis 常用 jemalloc，内存碎片会让 RSS 和逻辑数据大小出现差距。

看源码是为了更准确地写业务代码。Redis 的性能不是凭空来的，底层结构的优化也有边界。