Redis核心数据结构底层编码原理深度解析：SDS、跳表、压缩列表与哈希表实现

Redis以其极高的性能和丰富的数据结构闻名于世，但你真的了解String、List、Hash、Set、ZSet这五种核心数据结构在底层是如何实现的吗？本文将从Redis 7.0源码出发，深入剖析每种数据结构背后的编码方式与实现原理，帮助读者真正理解Redis的设计哲学和性能奥秘。全文将涵盖SDS动态字符串、quicklist与listpack、dict哈希表、intset整数集合以及skiplist跳表五大核心数据结构，并结合实际生产场景给出最佳实践建议。

Redis之所以能实现微秒级的数据操作，很大程度上得益于其对底层数据结构的精心设计和灵活选择。Redis会根据存储数据的特点（如数据大小、元素数量、内容类型等）动态选择最合适的底层编码方式，在内存占用和CPU性能之间取得最佳平衡。理解这些底层原理，对于写出高效的Redis代码、解决线上性能问题、以及设计分布式缓存方案都至关重要。

在Redis中，每种数据类型的键都可以通过

1	OBJECT ENCODING

命令查看其当前使用的底层编码。例如，一个只包含整数的Set可能使用intset编码，而一旦加入了非整数元素，就会自动升级为hashtable编码。这种自动化的编码选择机制是Redis精妙设计的核心之一。本文将一一拆解每种编码的实现细节，并结合实际案例说明不同场景下的最佳实践。

Redis服务器架构示意图

一、String底层：SDS动态字符串

Redis中的String类型并非直接使用C语言的字符串，而是自己封装了一个名为SDS（Simple Dynamic String）的数据结构。C语言字符串存在三个明显的缺陷：第一，获取字符串长度需要O(n)遍历整个字符数组直到遇到’\0’；第二，二进制不安全，字符串中不能包含’\0’字符，否则会被截断；第三，字符串拼接操作容易导致缓冲区溢出。SDS完美解决了这些问题，成为Redis字符串操作的基础。

SDS数据结构定义


1
2
3
4
5
struct sdshdr {

    int len;    // 已使用的字节数

    int free;   // 未使用的字节数

    char buf[]; // 字节数组，存放实际数据

};

在Redis 7.0中，SDS根据存储数据的大小，使用了五种不同的头部结构：sdshdr5（未使用）、sdshdr8、sdshdr16、sdshdr32、sdshdr64。这种精细化设计可以根据字符串长度选择最合适的头部大小，从而节省每一个字节的内存。当字符串长度小于256字节时，使用sdshdr8仅需额外3字节的头部开销；而对于超大字符串（超过4GB），则使用sdshdr64。

结构体	len/free类型	适用长度范围	头部内存开销
sdshdr5	未使用	–	–
sdshdr8	uint8_t	≤255字节	3字节
sdshdr16	uint16_t	≤65535字节	5字节
sdshdr32	uint32_t	≤4GB	9字节
sdshdr64	uint64_t	>4GB	17字节

SDS的四大核心优势

1. O(1)获取字符串长度：SDShdr中直接记录了len字段，获取字符串长度不需要像C字符串那样遍历计算，时间复杂度从O(n)降为O(1)。这对于频繁调用STRLEN命令的场景来说，性能提升是巨大的。

2. 二进制安全：SDS不依赖’\0’作为字符串结束标志，而是以len字段为准来判断字符串的结束位置。因此SDS可以存储任何二进制数据，包括图片文件、序列化对象、压缩后的数据等。这也是Redis可以存储二进制安全数据的关键原因。

3. 空间预分配机制减少内存分配：当对SDS进行修改（如APPEND、SETRANGE操作）时，Redis会采用空间预分配策略来减少内存重新分配的次数。具体策略是：如果修改后的SDS长度小于1MB，则分配与len同样大小的free空间；如果修改后的SDS长度大于等于1MB，则额外分配1MB的free空间。这意味着对一个正在增长的字符串执行APPEND操作，平摊到每次追加的时间复杂度接近O(1)。

4. 惰性空间释放：当字符串缩短时，SDS不会立即释放多余的内存，而是用free字段记录这些空闲空间，方便后续可能的追加操作。如果确实需要释放内存，可以调用sdsclear等API手动触发。

String的三种编码方式


1
2
3
4
5
6
7
8
9
10
11
# int编码：当value是整数时，直接用long类型存储

SET counter 100

OBJECT ENCODING counter  # 返回 "int"



# embstr编码：当字符串长度≤44字节时，SDS和String对象一次性分配

SET greeting "hello"

OBJECT ENCODING greeting  # 返回 "embstr"



# raw编码：当字符串长度>44字节时，分两次分配

SET long_text "$(python -c 'print("A"*100)')"

OBJECT ENCODING long_text  # 返回 "raw"

embstr编码的特别之处在于，SDS头部和RedisObject对象是在同一块连续内存中分配的，只需要一次malloc操作。而raw编码需要两次分配：一次分配RedisObject，一次分配SDS。embstr编码不仅减少了内存分配次数，还提高了缓存局部性。值得注意的是，embstr是只读的，如果对embstr字符串执行任何修改操作（如APPEND），它会自动转换为raw编码。

内存数据结构示意图

二、List底层：quicklist与listpack

Redis的List类型在早期版本中使用ziplist（压缩列表）和linkedlist（双向链表）两种编码。从Redis 3.2开始引入了quicklist代替它们，结合了两种编码的优点。到了Redis 7.0，进一步引入了listpack来替代ziplist，彻底解决了ziplist的连锁更新问题。

Quicklist：双向链表+压缩列表的混合体

Quicklist本质上是一个双向链表，但每个节点不是一个单独的元素，而是一个连续的listpack（早期版本为ziplist）块。这种设计巧妙地将双向链表插入和删除方便的优点，与listpack内存紧凑、缓存友好的优点结合起来。每个listpack块的大小可以通过

1	list-max-ziplist-size

参数配置，默认每个节点最多8KB。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// quicklist结构示意

typedef struct quicklist {

    quicklistNode *head; // 头节点

    quicklistNode *tail; // 尾节点

    unsigned long count; // 所有listpack中的元素总数

    unsigned long len;   // quicklistNode节点数

    int fill: 16;        // 每个listpack的填充因子

    unsigned int compress: 16; // LZF压缩深度

} quicklist;



typedef struct quicklistNode {

    struct quicklistNode *prev;

    struct quicklistNode *next;

    unsigned char *entry; // 指向listpack的指针

    unsigned int sz;       // listpack字节数

    unsigned int count;    // listpack中元素数

    unsigned int encoding: 2; // RAW=1, LZF=2

    // ... 其他字段

} quicklistNode;

Listpack：连锁更新问题的终结者

Listpack是Redis 7.0中替代ziplist的新实现。ziplist存在一个根本性问题——连锁更新（cascading update）。当在ziplist中间插入或删除元素时，可能导致后面所有元素的prevlen字段（记录前一个元素长度）需要更新，最坏情况下所有后续元素都需要重新分配内存，时间复杂度达到O(n²)。在大数据量下，这会导致严重的性能抖动。


1
2
3
4
5
6
7
8
9
10
11
// listpack每个元素的编码格式

+----------+----------+----------+

| encoding | data     | backlen  |

+----------+----------+----------+



// encoding: 编码类型和数据长度

// data: 实际数据

// backlen: 记录当前元素自身总长度，用于从后向前遍历



// 关键改进：backlen只依赖自身，不依赖相邻元素

// 因此插入或删除一个元素不会影响其他元素的内存布局

Listpack通过backlen字段记录每个元素自身的长度，彻底解决了连锁更新问题。每个元素的内存布局是独立的，当前元素的修改不会影响其他元素。这使得Listpack在插入和删除操作上具有稳定的性能表现，不再有ziplink那种极端情况下的性能退化问题。

List的典型应用场景

应用场景	推荐命令组合	详细说明
轻量级消息队列	LPUSH + BRPOP	左进右出实现FIFO队列，BRPOP支持阻塞等待
最新N条动态	LPUSH + LTRIM	每次推送后修剪，保持列表固定长度
时间线/Feed流	LPUSH + LRANGE	分页获取最新内容，适合用户时间线
可靠工作队列	RPOPLPUSH	消费同时备份到另一个队列，支持重试
栈结构	LPUSH + LPOP	后进先出，适合撤销操作历史


1
2
3
4
5
6
7
8
9
# 最新N条消息，始终保持列表不超过1000个元素

LPUSH recent:news "article-1001"

LTRIM recent:news 0 999



# 分页获取（第1页，每页10条）

LRANGE recent:news 0 9



# 分页获取（第2页）

LRANGE recent:news 10 19

三、Hash底层：dict哈希表与listpack

Redis的Hash类型可以采用两种底层编码方式：当所有字段和值的长度都小于

1	hash-max-listpack-value

（默认64字节），且字段数量小于

1	hash-max-listpack-entries

（默认512）时，使用listpack编码；否则自动升级为dict（哈希表）编码。这种自动升降级机制保证了小Hash的高效存储和大Hash的高性能访问。

Dict哈希表：渐进式Rehash机制

Redis的dict哈希表使用链地址法（separate chaining）解决哈希冲突，采用MurmurHash2算法计算哈希值，并实现了特有的渐进式rehash机制来避免一次性扩容带来的服务暂停。


1
2
3
4
5
6
7
8
typedef struct dict {

    dictType *type;

    dictEntry **ht_table[2]; // 两张哈希表

    unsigned long ht_used[2];

    long rehashidx; // rehash进度，-1表示未进行

    int16_t pauserehash;

    unsigned long iterators;

} dict;

渐进式Rehash的关键设计要点：

双表机制：dict内部维护ht_table[0]和ht_table[1]两张哈希表。rehash时，ht_table[1]扩容为ht_table[0]的2倍大小，然后将数据从ht_table[0]逐步迁移到ht_table[1]。
分批迁移：rehashidx初始为0，每次对dict执行增、删、改、查操作时，会顺便将ht_table[0]中rehashidx桶上的所有元素迁移到ht_table[1]，然后rehashidx加1。这样就把一次性的O(n)扩容操作分摊到了后续的每一次操作中。
操作兼容：rehash期间，查询和更新操作会同时检查两张表；新增操作只写入ht_table[1]；删除操作需要检查两张表。
触发条件精确控制：负载因子（ht_used / ht_size）大于1时触发扩容；大于5时强制扩容（即使有BGSAVE子进程在运行）；小于0.1时触发收缩。

Hash使用误区与最佳实践

很多开发者将Hash简单视为字符串到字符串的映射，但实际上Hash在Redis中有着非常高效的内存利用方式。当使用listpack编码时，小Hash的内存效率极高，甚至比使用多个独立的String键还要节省内存，因为listpack中的字符串共享了元数据。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 小Hash使用listpack编码（推荐，省内存）

HSET user:1001 name "Alice" age "28" city "Beijing" email "alice@example.com"

OBJECT ENCODING user:1001  # 返回 "listpack"



# 大Hash自动升级为dict

HSET user:1 field_100 "long_value_xxx..."

OBJECT ENCODING user:1  # 返回 "hashtable"



# 使用Hash存储对象 vs 使用String存储JSON

# ✅ 推荐：使用Hash存储，支持单独修改字段

HSET product:2001 price 299 stock 1000 name "无线耳机"

HINCRBY product:2001 stock -1        # 原子减库存

HGET product:2001 price              # 仅获取价格



# ❌ 不推荐：用String存JSON，无法单独修改字段

SET product:2001 '{"price":299,"stock":999,"name":"无线耳机"}'

# 修改库存需要先GET整个JSON，反序列化，修改，再SET

经验建议：使用Hash存储对象比直接使用String键存储JSON更灵活、更节省内存。但需要注意，单个Hash不要超过10000个字段，否则可能导致Redis阻塞（特别是使用HGETALL时）。如果数据量极大，建议使用多个Hash键进行分片，例如按用户ID的哈希值取模。

哈希表数据结构示意图

四、Set底层：整数集合intset与哈希表

Redis的Set类型根据存储的元素特性选择底层编码：当所有元素都是整型值且元素数量小于

1	set-max-intset-entries

（默认512）时，使用intset（整数集合）编码；否则自动升级为dict哈希表编码。intset编码是Redis中最紧凑的内存结构之一。

Intset：有序的紧凑整型数组


1
2
3
4
5
typedef struct intset {

    uint32_t encoding; // 编码方式：INTSET_ENC_INT16/INT32/INT64

    uint32_t length;   // 元素个数

    int8_t contents[]; // 柔性数组，实际存储元素

} intset;

Intset内部使用有序数组存储元素，所有元素按从小到大排列，通过二分查找判断元素是否存在，时间复杂度为O(log n)。当插入新元素时，如果新元素的取值范围超出了当前encoding的上下界，intset会触发升级操作，将整个数组转换为更高位数的编码，并重新排列所有元素。

升级机制示例：


1
2
3
4
5
6
SADD small_set 1 2 3     # 初始为int16编码，每个元素占2字节

# 内存布局: |encoding=int16|length=3|1|2|3| (共14字节)



SADD small_set 70000     # 70000超出int16范围(-32768~32767)，触发升级为int32

# 升级后，所有元素重新编码为4字节

# 内存布局: |encoding=int32|length=4|1|2|3|70000| (共28字节)

intset的升级操作是不可逆的——即使删除了导致升级的元素，intset也不会自动降级。这是Redis在性能和内存之间做出的权衡，因为降级操作的代价同样不低。

Set的经典应用场景

应用场景	Redis命令	说明
标签系统	SADD + SISMEMBER	为文章/用户打标签，快速判断是否存在
独立访客统计	SADD + SCARD	记录当天访问用户ID，SCARD获取UV
社交关系计算	SINTER / SUNION / SDIFF	共同好友、推荐好友、好友差集
在线用户列表	SADD + SREM	心跳机制维护在线状态
随机抽奖	SRANDMEMBER / SPOP	随机抽取中奖用户，SPOP可移除


1
2
3
4
5
6
7
# 共同好友示例

SADD user:1:friends "user_a" "user_b" "user_c" "user_d"

SADD user:2:friends "user_b" "user_d" "user_e"

SINTER user:1:friends user:2:friends  # 共同好友: user_b, user_d



# 推荐好友（user2的好友 - user1的好友）

SDIFF user:2:friends user:1:friends  # 推荐: user_e

五、ZSet底层：跳表skiplist与listpack

ZSet（有序集合）是Redis中最复杂也最强大的数据结构。当元素数量小于

1	zset-max-listpack-entries

（默认128）且每个元素长度小于

1	zset-max-listpack-value

（默认64）时使用listpack编码；否则使用跳表+哈希表的组合编码。ZSet之所以强大，是因为它同时支持按分数的范围查询和按成员的精确查找。

跳表（Skip List）的完整实现

跳表是一种可以在有序序列中实现快速查找的概率性数据结构，其平均查找时间复杂度为O(log n)，最坏情况为O(n)。Redis的跳表实现参考了William Pugh的论文，但做了以下重要改进：

允许重复分数：当多个成员具有相同分数时，按成员字典序排列
引入span字段：每个前进指针记录了跨越的节点数，使得按排名查询（ZRANK）时间复杂度为O(log n)
双向遍历：每个节点有backward指针，支持从后向前遍历


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// ZSet跳表节点结构

typedef struct zskiplistNode {

    sds ele;                    // 成员对象（SDS字符串）

    double score;               // 分值

    struct zskiplistNode *backward; // 后退指针

    struct zskiplistLevel {

        struct zskiplistNode *forward; // 前进指针

        unsigned int span;      // 到下一个节点的跨度

    } level[];                  // 层级数组（柔性数组）

} zskiplistNode;



typedef struct zskiplist {

    struct zskiplistNode *header, *tail;

    unsigned long length;      // 节点数量

    int level;                 // 当前最大层数

} zskiplist;



// ZSet整体结构：dict + skiplist 组合

typedef struct zset {

    dict *dict;     // 成员->分值映射，提供O(1)的ZSCORE查询

    zskiplist *zsl; // 跳表，按分值排序，支持范围查询

} zset;

为什么Redis选择跳表而非红黑树

这是一个经典的面试题。Redis的作者antirez在源码注释中给出了解释：

实现简单：跳表的核心代码只有几百行，而平衡树的插入和删除涉及复杂的旋转操作，代码量翻倍
范围查询更高效：跳表在ZRANGEBYSCORE这种区间扫描场景下，只需要找到起始节点然后沿着forward指针遍历即可，不需要像平衡树那样进行中序遍历
易于调试：跳表的结构直观，打印出所有层级即可看到完整结构，而平衡树的结构难以直观理解
灵活的调优：通过调整概率因子p（Redis中p=1/4）和最大层数（Redis中最大32层），可以灵活平衡时间和空间

ZSet实战：排行榜与延迟队列


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 场景1：游戏实时排行榜

ZADD leaderboard:game001 15000 "player_888"

ZADD leaderboard:game001 12000 "player_666"

ZADD leaderboard:game001 18000 "player_999"

ZADD leaderboard:game001 13500 "player_777"



# 获取Top 10（按分值从高到低）

ZREVRANGE leaderboard:game001 0 9 WITHSCORES

# 1) "player_999"  2) "18000"  3) "player_888"  4) "15000"



# 获取玩家排名（从0开始）

ZREVRANK leaderboard:game001 "player_666"

# 返回 2（排名第3）



# 获取某个分数段的玩家

ZRANGEBYSCORE leaderboard:game001 13000 17000 WITHSCORES



# 原子更新玩家分数

ZINCRBY leaderboard:game001 500 "player_666"



# 场景2：延迟队列实现

# score = 任务执行时间戳

ZADD delay:queue 1730707200 "task:send_email:user123"

ZADD delay:queue 1730793600 "task:cleanup:temp_files"



# 轮询获取到期任务（使用当前时间戳）

ZRANGEBYSCORE delay:queue 0 $(date +%s) WITHSCORES

# 执行后移除

ZREM delay:queue "task:send_email:user123"

六、五种编码方式对比总结

数据类型	可用编码方式	编码转换条件	查询时间复杂度
String	int / embstr / raw	整数用int，≤44字节用embstr，否则raw	O(1)
List	quicklist + listpack	始终使用（无转换）	头尾O(1)，中间O(n)
Hash	listpack / hashtable	小数据（<512字段，<64字节）用listpack	O(1)平均
Set	intset / hashtable	小整数集（<512个）用intset	O(1)平均
ZSet	listpack / skiplist+dict	小数据（<128个，<64字节）用listpack	O(log n)

七、生产环境诊断工具

Redis提供了非常实用的OBJECT命令和MEMORY命令，可以在生产环境中查看键的底层编码方式，帮助诊断内存使用情况和优化数据结构：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 查看内部编码

OBJECT ENCODING mykey

# 可能返回值: int, embstr, raw, listpack, quicklist, hashtable, intset, skiplist



# 查看空闲时间（多久没被访问，用于淘汰策略）

OBJECT IDLETIME mykey



# 查看引用计数（调试共享对象）

OBJECT REFCOUNT mykey



# 查看内存使用（精确到字节）

MEMORY USAGE mykey



# 诊断示例

> SET num 42

> OBJECT ENCODING num

"int"  # 数字直接用int编码，仅8字节



> SET greeting "hello"

> OBJECT ENCODING greeting

"embstr"  # 短字符串，一次malloc分配



> SET long_text "$(python -c 'print("A"*45)')"

> OBJECT ENCODING long_text

"raw"  # 超过44字节，两次malloc分配



> SADD small_set 100 200 300

> OBJECT ENCODING small_set

"intset"  # 整数集合，紧凑存储



> ZADD rank 1 "a" 2 "b"

> OBJECT ENCODING rank

"listpack"  # 小有序集合

八、总结与最佳实践

Redis的核心性能优势根植于其对底层数据结构的精湛设计和灵活选择。通过本文的深入分析，我们得到以下关键结论：

SDS替代C原生字符串，提供O(1)长度获取、二进制安全、预分配减少内存碎片三大核心优势
Quicklist+Listpack组合了链表和连续数组的双重优点，listpack彻底解决了ziplist的连锁更新问题
渐进式Rehash让哈希表扩容不阻塞服务，是Redis保持高可用的关键设计之一
Intset为小整数集合提供极致的内存效率，升级机制保证了数据范围的灵活性
跳表+Dict的组合为ZSet同时提供了O(log n)的范围查询和O(1)的精确查找

在实际生产环境中，建议开发者从以下几个方面优化Redis的使用：

使用小数据结构：尽量让Hash、ZSet、Set保持在listpack/intset编码范围内，可以大幅节省内存
避免大Key：单个键不要存储超过10000个元素，否则可能导致Redis阻塞
定期诊断：使用
1
MEMORY USAGE

和

1
OBJECT ENCODING

定期检查键的编码方式和内存占用
关注版本更新：Redis 7.0的listpack替代ziplist是一个重要的性能改进，建议升级到最新稳定版
合理配置参数：根据业务数据特征调整
1
hash-max-listpack-entries

、

1
zset-max-listpack-entries

等参数

理解这些底层实现不仅有助于面试和源码阅读，更重要的是可以在日常开发中做出更好的Redis使用决策——知道何时用listpack编码省内存、知道为什么大Key会导致阻塞、知道如何根据数据特点选择合适的数据类型和配置参数。希望本文能帮助读者建立起从底层数据结构到上层应用的完整知识体系，在实际工作中更加得心应手地使用Redis。