深入理解 Redis 数据结构：底层实现与性能优化实践

引言

Redis 作为高性能的内存数据库，其卓越的性能表现离不开精心设计的数据结构。本文将深入剖析 Redis 核心数据结构的底层实现机制，包括简单动态字符串(SDS)、字典(Dict)、跳跃表(SkipList)、快速列表(QuickList)和整数集合(IntSet)，并探讨其在实际场景中的性能优化策略。

1. 简单动态字符串 (SDS)

Redis 没有直接使用 C 语言的传统字符串，而是构建了自己的简单动态字符串(Simple Dynamic String, SDS)抽象类型。SDS 在 C 字符串之上增加了长度信息，带来了显著的优势。

1.1 SDS 结构定义

SDS 的结构包含三个关键属性：len 记录已使用字节长度，free 记录剩余可用字节数，buf 是实际存储数据的字节数组。这种设计使得获取字符串长度的时间复杂度从 O(N) 降至 O(1)。

struct sdshdr {
    int len;    // 已使用长度
    int free;   // 剩余可用长度
    char buf[]; // 字节数组
};

1.2 SDS 的优势

O(1) 时间复杂度获取长度：通过 len 属性直接获取，无需遍历。

杜绝缓冲区溢出：在修改 SDS 前，API 会先检查空间是否满足，不满足时自动扩容。

减少内存重分配次数：采用空间预分配和惰性空间释放策略。空间预分配时，若修改后 len 小于 1MB，则分配与 len 相等的 free 空间；若大于 1MB，则额外分配 1MB 空间。

二进制安全：buf 可以存储任意二进制数据，中间允许包含空字符。

2. 字典 (Dict)

字典是 Redis 数据库的底层实现方式之一，也是哈希键的底层实现之一。Redis 的字典使用哈希表作为底层实现，每个字典包含两个哈希表，用于实现渐进式 rehash。

2.1 哈希表实现

哈希表节点存储键值对，包含 key、v(value 指针) 和 next 指针(解决哈希冲突的链地址法)。字典结构则包含两个哈希表数组、当前正在渐进式 rehash 的索引位置以及 rehash 状态标识。

2.2 渐进式 Rehash

随着操作逐步执行，rehash 过程不会一次性完成。当负载因子满足条件时(定时任务触发或操作时检测到)，系统启动 rehash。每次对字典执行添加、删除、查找操作时，除了执行指定操作外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对迁移到 ht[1]，完成后递增 rehashidx。

3. 跳跃表 (SkipList)

跳跃表是 Redis 有序集合(ZSet)的底层实现之一。平均查找复杂度为 O(log N)，最坏 O(N)，但可通过概率平衡实现接近二分查找的效率。

3.1 跳跃表结构

跳跃表节点包含后退指针、分值(score)、成员对象(obj)和多层 level 数组。每层包含前进指针和跨度(span)。通过幂次定律随机生成层数——层数越高的节点越少，类似金字塔结构。

4. 快速列表 (QuickList)

Redis 3.2 引入 QuickList 作为列表键的底层实现。它是双向链表与压缩列表(zipList)的结合体——每个链表节点都是一个 zipList。这样既保持了链表的灵活性，又利用了 zipList 的内存紧凑优势。

5. 整数集合 (IntSet)

整数集合是集合键的底层实现之一，当集合只包含整数元素且数量较少时使用。支持 16 位、32 位和 64 位整数存储，并在添加更大整数时执行升级(upgrade)操作。

6. 编码转换机制

Redis 会根据数据特征自动选择最合适的底层编码，实现内存效率与操作效率的平衡：

• 字符串对象：int、embstr、raw 三种编码
• 列表对象：linkedlist(默认)、quicklist(Redis 3.2+)
• 哈希对象：hashtable、ziplist
• 集合对象：hashtable、intset
• 有序集合：skiplist+dict、ziplist

7. 性能实践建议

根据业务场景选择合适的数据类型：计数器用 String 的 INCR；消息队列用 List 或 Stream；排行榜用 ZSet；社交关系用 Set；对象存储用 Hash。

结语

深入理解 Redis 的底层数据结构，有助于我们更好地利用其特性进行系统设计。每种数据结构都有其设计哲学和适用场景，合理选择可以显著提升系统性能。