高级Redis：数据结构底层实现与优化技巧

2025-3-20

高级Redis：数据结构底层实现与优化技巧

Redis，全称 Remote Dictionary Server，是一个开源的、基于内存的、高性能的键值对（key-value）数据库。它以其卓越的性能、丰富的数据结构和强大的功能集，在各种应用场景中广受欢迎，例如缓存、会话管理、消息队列、实时排行榜、计数器等。

Redis 的成功很大程度上归功于其精心设计的数据结构以及这些数据结构底层的精妙实现。本文将深入探讨 Redis 常见数据结构的底层实现细节，并结合实际应用场景，分享一些优化技巧，帮助读者更好地理解和使用 Redis。

1. Redis 数据结构概览

Redis 提供了多种数据结构，每种数据结构都有其特定的用途和适用场景：

  • String（字符串）: 最基本的数据类型，可以存储字符串、整数或浮点数。
  • List（列表）: 按照插入顺序排序的字符串集合，支持两端插入和弹出操作。
  • Hash（哈希）: 键值对集合，类似于其他编程语言中的字典或映射。
  • Set（集合）: 无序、唯一的字符串集合，支持集合运算（交集、并集、差集）。
  • Sorted Set（有序集合）: 类似于 Set，但每个元素都关联一个分数（score），用于排序。

除了以上五种基本数据结构，Redis 还提供了一些高级数据结构，如：

  • Bitmap（位图）: 基于字符串实现的位数组，用于位操作。
  • HyperLogLog（基数统计）: 基于概率算法的基数估计算法，用于统计不重复元素的数量。
  • Geospatial（地理空间）: 用于存储地理位置信息，并进行位置查询和计算。

2. 数据结构底层实现详解

Redis 之所以能提供如此高的性能，与其底层数据结构的巧妙实现密不可分。接下来，我们将深入探讨每种数据结构的底层实现细节。

2.1 String（字符串）

Redis 的 String 并非直接使用 C 语言中的传统字符串（以空字符 \0 结尾的字符数组），而是基于其构建了一个名为 简单动态字符串（Simple Dynamic String，SDS） 的抽象类型。

SDS 的结构如下：

```c
struct sdshdr {
// 记录 buf 数组中已使用字节的数量
// 等于 SDS 所保存字符串的长度
int len;

// 记录 buf 数组中未使用字节的数量
int free;

// 字节数组，用于保存字符串
char buf[];

};
```

SDS 相比于 C 字符串，具有以下优势：

  • 常数时间复杂度获取字符串长度： SDS 结构中 len 字段直接存储了字符串长度，获取长度的时间复杂度为 O(1)，而 C 字符串需要遍历整个字符串才能获取长度，时间复杂度为 O(N)。
  • 杜绝缓冲区溢出： 当对 SDS 进行修改时，会先检查 free 字段是否有足够的空间，如果空间不足，则会先扩展空间，然后再进行修改，从而避免了缓冲区溢出的问题。
  • 减少内存重分配次数： SDS 采用了空间预分配和惰性空间释放两种优化策略。
    • 空间预分配： 当 SDS 进行扩展时，会预先分配一些额外的未使用空间（free），这样在下次进行修改时，如果空间足够，就不需要再次进行内存分配。
    • 惰性空间释放： 当 SDS 进行缩短时，并不会立即释放多余的空间，而是将这些空间保留在 free 字段中，以备将来使用。
  • 二进制安全： SDS 的 buf 数组可以存储任意二进制数据，而不仅仅是文本数据。因为 SDS 使用 len 字段而不是空字符 \0 来判断字符串的结束，所以可以安全地存储包含空字符的二进制数据。

2.2 List（列表）

Redis 的 List 底层实现为 双向链表（linkedlist） 或 压缩列表（ziplist）。具体使用哪种数据结构取决于列表的长度和元素的长度。

双向链表（linkedlist）

双向链表是经典的链表实现，每个节点都包含指向前一个节点和后一个节点的指针。

```c
typedef struct listNode {
// 前置节点
struct listNode *prev;

// 后置节点
struct listNode *next;

// 节点的值
void *value;

} listNode;

typedef struct list {
// 表头节点
listNode *head;

// 表尾节点
listNode *tail;

// 链表所包含的节点数量
unsigned long len;

// 节点值复制函数
void *(*dup)(void *ptr);

// 节点值释放函数
void (*free)(void *ptr);

// 节点值对比函数
int (*match)(void *ptr, void *key);

} list;
```

双向链表提供了快速的插入和删除操作（O(1) 时间复杂度），但随机访问元素的速度较慢（O(N) 时间复杂度）。

压缩列表（ziplist）

压缩列表是 Redis 为了节约内存而设计的一种特殊的编码方式。它是一个由一系列特殊编码的连续内存块组成的顺序型数据结构。

压缩列表的结构如下：

  • zlbytes： 记录整个压缩列表占用的内存字节数。
  • zltail： 记录压缩列表表尾节点距离起始地址的偏移量，用于快速定位到表尾节点。
  • zllen： 记录压缩列表包含的节点数量。
  • entryX： 压缩列表的各个节点，每个节点可以保存一个字节数组或一个整数值。
  • zlend： 特殊值 0xFF，用于标记压缩列表的末端。

每个 entryX 节点的结构如下：

  • previous_entry_length： 记录前一个节点的长度，用于从后向前遍历。
  • encoding： 记录当前节点的编码方式和长度。
  • content： 保存节点的值。

压缩列表的优点是内存紧凑，可以有效节省内存空间。但当列表长度较大或元素长度较长时，插入和删除操作可能会导致连锁更新，影响性能。

List 的底层实现选择

当列表对象可以同时满足以下两个条件时，列表对象使用 ziplist 编码：
1. 列表对象保存的所有字符串元素的长度都小于 64 字节.
2. 列表对象保存的元素数量小于 512 个.

不能满足这两个条件的列表对象需要使用 linkedlist 编码.

2.3 Hash（哈希）

Redis 的 Hash 底层实现为 字典（dict） 或 压缩列表（ziplist）。

字典（dict）

字典是 Redis 中最核心的数据结构之一，它用于实现键值对的存储和查找。字典的底层实现是一个哈希表，类似于其他编程语言中的 HashMap 或 Dictionary。

```c
typedef struct dict {
// 类型特定函数
dictType *type;

// 私有数据
void *privdata;

// 哈希表
dictht ht[2];

// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */

// 正在运行的安全迭代器的数量
  int iterators; /* number of iterators currently running */

} dict;

typedef struct dictht {
// 哈希表数组
dictEntry **table;

// 哈希表大小
unsigned long size;

// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;

// 该哈希表已有节点的数量
unsigned long used;

} dictht;

typedef struct dictEntry {
// 键
void *key;

// 值
union {
    void *val;
    uint64_t u64;
    int64_t s64;
} v;

// 指向下个哈希表节点，形成链表
struct dictEntry *next;

} dictEntry;
```

Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

  • ht[2]：包含两个哈希表，通常情况下只使用 ht[0]，ht[1] 用于 rehash。
  • rehashidx：记录 rehash 的进度，-1 表示没有进行 rehash。

Redis 使用 链地址法 解决哈希冲突，即当多个键的哈希值相同时，这些键值对会形成一个链表。

Rehashing（重新哈希）

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
扩展和收缩哈希表的工作可以通过执行 rehash （重新散列）操作来完成.
当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

  1. 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1 。
  2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5 。

当哈希表的负载因子小于 0.1 时，程序自动开始对哈希表执行收缩操作。
rehash 过程是渐进式的，并非一次性完成，这样可以避免在 rehash 期间阻塞服务器。

Hash 的底层实现选择

当哈希对象可以同时满足以下两个条件时，哈希对象使用 ziplist 编码：
1. 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节.
2. 哈希对象保存的键值对数量小于 512 个.

不能满足这两个条件的哈希对象需要使用 dict 编码.

2.4 Set（集合）

Redis 的 Set 底层实现为 字典（dict） 或 整数集合（intset）。

字典（dict）

当 Set 中的元素都是字符串时，使用字典作为底层实现。字典的键为集合中的元素，值为 NULL。

整数集合（intset）

当 Set 中的元素都是整数，且元素数量不超过一定限制时，使用整数集合作为底层实现。

```c
typedef struct intset {
// 编码方式
uint32_t encoding;

// 集合包含的元素数量
uint32_t length;

// 保存元素的数组
int8_t contents[];

} intset;
```

整数集合是一个有序、不重复的整数数组。encoding 字段决定了数组中整数的类型（int16_t、int32_t 或 int64_t）。

Set 的底层实现选择

当集合对象可以同时满足以下两个条件时，对象使用 intset 编码：
1. 集合对象保存的所有元素都是整数值.
2. 集合对象保存的元素数量不超过 512 个.

不能满足这两个条件的集合对象需要使用 dict 编码.

2.5 Sorted Set（有序集合）

Redis 的 Sorted Set 底层实现为 字典（dict） 和 跳跃表（skiplist）。

字典（dict）

字典的键为集合中的元素，值为元素的分数。字典用于快速查找元素的分数（O(1) 时间复杂度）。

跳跃表（skiplist）

跳跃表是一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

```c
typedef struct zskiplistNode {
// 成员对象
robj *obj;

// 分值
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;
```

  • level 数组：可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。
  • forward 指针：用于从表头向表尾方向访问节点。
  • span 属性：记录了两个节点之间的距离。
  • backward 指针：用于从表尾向表头方向访问节点。
  • score 属性：是一个 double 类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。
  • obj 属性：则是一个指针，它指向一个字符串对象，而字符串对象则保存着一个 SDS 值。

跳跃表通过多层级的指针，实现了快速的查找、插入和删除操作（平均时间复杂度为 O(log N)）。

Sorted Set 同时使用字典和跳跃表，保证了快速查找元素分数和按分数排序的功能。

3. 优化技巧

了解了 Redis 数据结构的底层实现后，我们可以根据其特性，结合实际应用场景，采取一些优化技巧，进一步提升 Redis 的性能和效率。

3.1 合理选择数据结构

根据实际需求选择合适的数据结构至关重要。例如：

  • 如果只需要存储键值对，且键和值都是字符串，则使用 String 类型。
  • 如果需要存储一个有序的列表，且需要频繁地在两端进行插入和弹出操作，则使用 List 类型。
  • 如果需要存储一个键值对集合，且需要快速查找键对应的值，则使用 Hash 类型。
  • 如果需要存储一个不重复的元素集合，且需要进行集合运算，则使用 Set 类型。
  • 如果需要存储一个有序的元素集合，且需要根据分数进行排序和范围查找，则使用 Sorted Set 类型。

3.2 控制键的长度

键的长度会影响内存占用和查找效率。应尽量使用短小精悍的键名，避免使用过长的键名。

3.3 使用合适的数据编码

Redis 会根据数据的大小和类型自动选择合适的底层编码。在某些情况下，我们可以通过调整配置参数来强制使用特定的编码，以达到优化目的。例如：

  • 对于 List、Hash 和 Set，可以通过调整 *-max-ziplist-entries 和 *-max-ziplist-value 参数来控制压缩列表的使用。
  • 对于 Set，可以通过调整 set-max-intset-entries 参数来控制整数集合的使用。

3.4 利用批量操作

Redis 提供了一些批量操作命令，如 MGET、MSET、HMSET、HMGET 等。使用批量操作可以减少网络往返次数，显著提高性能。

3.5 使用 Pipeline

Pipeline（流水线）可以将多个 Redis 命令打包发送给服务器，减少网络往返次数。与批量操作不同的是，Pipeline 不保证原子性。

3.6 避免使用耗时命令

一些 Redis 命令的时间复杂度较高，如 KEYS、SMEMBERS、HGETALL 等。在生产环境中应尽量避免使用这些命令，以免阻塞服务器。

3.7 使用 Lua 脚本

Lua 脚本可以将多个 Redis 命令组合成一个原子操作，减少网络开销，并保证操作的原子性。

3.8 设置过期时间

对于不需要永久存储的数据，应设置合理的过期时间，避免内存浪费。

3.9 内存优化

  • 使用 Redis 3.0 及以上版本： Redis 3.0 引入了新的内存分配器 jemalloc，相比于传统的 libc malloc，jemalloc 具有更低的内存碎片率和更高的性能。
  • 启用内存碎片整理： Redis 4.0 引入了主动内存碎片整理功能，可以通过配置 activedefrag yes 启用。
  • 避免使用过大的数据结构： 过大的数据结构会占用更多的内存，并可能导致性能下降。应尽量将大对象拆分成多个小对象存储。

3.10 持久化策略

Redis 提供了 RDB 和 AOF 两种持久化方式。应根据实际需求选择合适的持久化策略，并在性能和数据安全之间进行权衡。

  • RDB： 适合于数据备份和灾难恢复，但可能会丢失最后一次快照之后的数据。
  • AOF： 适合于对数据安全性要求较高的场景，但会降低写入性能。

4. 总结

Redis 之所以能够成为如此受欢迎的键值数据库，与其精心设计的数据结构和底层实现密不可分。本文深入探讨了 Redis 常见数据结构的底层实现细节，包括 String 的 SDS、List 的双向链表和压缩列表、Hash 的字典和压缩列表、Set 的字典和整数集合、Sorted Set 的字典和跳跃表。

通过了解这些底层实现，我们可以更好地理解 Redis 的性能特点，并根据实际应用场景，采取一些优化技巧，例如合理选择数据结构、控制键的长度、使用合适的数据编码、利用批量操作、使用 Pipeline、避免使用耗时命令、使用 Lua 脚本、设置过期时间、内存优化和持久化策略等。

希望本文能够帮助读者深入理解 Redis，并在实际工作中更好地应用 Redis，构建高性能、高可用的应用系统。

版权声明：
作者：admin
链接：https://hostlocvps.com/2025/03/20/%e9%ab%98%e7%ba%a7redis%ef%bc%9a%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%ba%95%e5%b1%82%e5%ae%9e%e7%8e%b0%e4%b8%8e%e4%bc%98%e5%8c%96%e6%8a%80%e5%b7%a7/
文章版权归作者所有，未经允许请勿转载。
THE END
Go Toolchain教程：构建高效Go应用的必备工具
<<上一篇
Web开发利器：在线HTML编辑器推荐与教程
下一篇>>
相关推荐
C++开发：VS Code最佳实践
cURL 代理: 提升网络稳定性
R CRAN: 常见问题解答
Git Reset：版本控制的基础知识
Y Combinator终极指南
Xbox Series S 最适合哪些玩家？
TortoiseSVN：图形化界面简化SVN操作
Pydantic 在实际项目中的应用案例
文学翻译服务
macOS 截图工具：完整指南