Redis 如何借助 SDS 实现高效内存管理
Redis 数据结构概述
在深入探讨 Redis 借助 SDS（Simple Dynamic String）实现高效内存管理之前，有必要先对 Redis 的数据结构体系有一个整体的认识。Redis 作为一个高性能的键值对存储系统，支持多种数据结构，如字符串（String）、哈希（Hash）、列表（List）、集合（Set）以及有序集合（Sorted Set）。这些数据结构的底层实现都围绕着高效的内存管理和快速的访问操作而设计。
Redis 的数据结构设计原则主要有两点：一是为了满足不同应用场景下对数据操作的需求，二是尽可能高效地利用内存资源。例如，在缓存场景中，经常需要对简单的字符串类型数据进行快速读写，这就要求字符串的存储和操作必须高效。而在社交网络应用中，可能会用到哈希结构来存储用户的各种属性，列表结构来记录用户的消息队列等。
SDS 结构剖析
SDS 结构定义
SDS 是 Redis 中用于表示字符串的一种数据结构。它的设计与传统 C 语言中的字符串有很大不同。在 C 语言中，字符串通常是以空字符（'\0'）结尾的字符数组。这种表示方法虽然简单，但在处理字符串长度、内存分配等方面存在诸多不便。
Redis 的 SDS 结构定义如下：
struct sdshdr {
// 记录 buf 数组中已使用字节的数量
// 等于 SDS 所保存字符串的长度
int len;
// 记录 buf 数组中未使用字节的数量
int free;
// 字节数组，用于保存字符串
char buf[];
};
这里需要注意的是，buf 数组的最后一个元素总是空字符 '\0'，这使得 SDS 可以兼容部分 C 语言字符串处理函数。
SDS 与传统 C 字符串对比
- 获取字符串长度：在 C 语言中，获取字符串长度需要遍历整个字符串直到遇到空字符
'\0'，时间复杂度为 O(n)。而 SDS 结构中通过len字段直接记录字符串长度，获取长度的时间复杂度为 O(1)。 - 内存分配：C 语言字符串在进行拼接等操作时，需要手动重新分配内存，并且容易出现缓冲区溢出的问题。SDS 则通过
free字段记录空闲空间，在进行修改操作时，如果空间不足，会自动进行内存重分配，并且会预分配一定的空间以减少频繁的内存分配操作。 - 二进制安全：C 语言字符串以空字符
'\0'作为结束标志，这意味着字符串中不能包含空字符，否则会被误认为是字符串的结束。而 SDS 以len字段判断字符串长度，对二进制数据是安全的，可以存储任意数据。
SDS 内存分配策略
空间预分配
当 SDS 进行修改操作（如追加字符串）时，如果所需空间超过当前 free 字段表示的空闲空间，Redis 会进行内存重分配。在重分配时，除了分配修改所需的空间外，还会进行空间预分配。
具体的预分配策略如下：
- 如果修改后 SDS 的长度（
len）小于 1MB，那么会分配和len相同大小的空闲空间，即free字段的值等于len。例如，当len为 10 字节时，重分配后free也为 10 字节，此时 SDS 实际分配的总空间为len + free + 1（最后一个字节用于存储空字符'\0'），即 21 字节。 - 如果修改后 SDS 的长度大于等于 1MB，那么会分配 1MB 的空闲空间。例如，当
len为 2MB 时，重分配后free为 1MB，SDS 实际分配的总空间为len + free + 1，即 3MB + 1 字节。
这种空间预分配策略减少了频繁的内存分配操作，提高了性能。例如，假设有一个 SDS 字符串，初始长度为 10 字节，当我们不断追加少量数据时，如果每次都只分配刚好够用的空间，那么每次追加都可能触发内存分配操作。而采用空间预分配策略，在第一次追加导致空间不足进行重分配时，会预分配一定空间，后续几次追加操作可能就不需要再次进行内存分配了。
惰性空间释放
当 SDS 进行缩短操作（如删除字符串的一部分）时，Redis 并不会立即释放多余的空间，而是将这些空间记录在 free 字段中，这就是惰性空间释放。
例如，有一个 SDS 字符串原本长度为 100 字节，当删除其中 20 字节的数据后，SDS 并不会立即将这 20 字节的空间归还给系统，而是将 free 字段增加 20，len 字段减少 20。这样，如果后续又需要对该字符串进行扩展操作，就可以直接使用这部分空闲空间，避免了再次向系统申请内存。
当然，如果确实需要释放这些多余的空间，Redis 也提供了相应的函数 sdstrim，可以手动释放 free 字段对应的空间。
SDS 在 Redis 中的应用场景
作为 Redis 键值对的键
在 Redis 中，键值对的键都是以 SDS 结构存储的。由于键通常需要快速查找和比较，SDS 的 O(1)时间复杂度获取长度以及二进制安全特性非常适合这种场景。例如，当使用 SET key value 命令设置一个键值对时，其中的 key 就是一个 SDS 字符串。
在 Redis 的字典（dict）结构中，键的比较是通过 dictCompareKeys 函数进行的，该函数会根据键的类型调用相应的比较函数。对于 SDS 类型的键，会直接使用 SDS 提供的比较函数，利用其高效的长度获取和二进制安全特性，快速判断两个键是否相等。
作为 Redis 字符串值的存储结构
Redis 的字符串值同样使用 SDS 来存储。无论是简单的字符串，还是可以进行数值操作的字符串（如 INCR 命令对存储数字的字符串进行自增操作），都基于 SDS 结构。
以 SET num 10 命令为例，这里的 num 键对应的值 10 就是以 SDS 形式存储的。当执行 INCR num 命令时，Redis 首先会检查值是否可以转换为数值类型，然后对 SDS 存储的字符串进行数值操作，操作完成后再将结果以 SDS 形式重新存储。
代码示例解析
创建和初始化 SDS
以下是创建和初始化一个 SDS 的示例代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 假设这是 Redis 中 SDS 结构定义
struct sdshdr {
int len;
int free;
char buf[];
};
// 创建一个初始内容为 "hello" 的 SDS
struct sdshdr* createSDS() {
// 计算所需的总空间，包括 len、free、字符串内容和结尾的 '\0'
int totalLen = sizeof(struct sdshdr) + 5 + 1;
struct sdshdr* sds = (struct sdshdr*)malloc(totalLen);
sds->len = 5;
sds->free = 0;
strcpy(sds->buf, "hello");
return sds;
}
int main() {
struct sdshdr* sds = createSDS();
printf("SDS 内容: %s, 长度: %d, 空闲空间: %d\n", sds->buf, sds->len, sds->free);
free(sds);
return 0;
}
在上述代码中，createSDS 函数创建了一个初始内容为 "hello" 的 SDS。首先计算所需的总空间，包括 sdshdr 结构体本身的大小、字符串 "hello" 的长度以及结尾的空字符 '\0'。然后通过 malloc 分配内存，设置 len 和 free 字段，并将字符串内容复制到 buf 数组中。
SDS 追加操作
下面是实现 SDS 追加操作的代码示例：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct sdshdr {
int len;
int free;
char buf[];
};
// 重新分配 SDS 空间
struct sdshdr* reallocSDS(struct sdshdr* sds, int newLen) {
int totalLen = sizeof(struct sdshdr) + newLen + 1;
struct sdshdr* newSds = (struct sdshdr*)realloc(sds, totalLen);
return newSds;
}
// 追加字符串到 SDS
struct sdshdr* appendSDS(struct sdshdr* sds, const char* appendStr) {
int appendLen = strlen(appendStr);
if (sds->free < appendLen) {
// 空间不足，重新分配空间
int newLen = sds->len + appendLen;
if (newLen < 1024 * 1024) {
newLen *= 2;
} else {
newLen += 1024 * 1024;
}
sds = reallocSDS(sds, newLen);
sds->free = newLen - sds->len;
}
strcat(sds->buf, appendStr);
sds->len += appendLen;
sds->free -= appendLen;
return sds;
}
int main() {
struct sdshdr* sds = createSDS();
sds = appendSDS(sds, ", world");
printf("追加后的 SDS 内容: %s, 长度: %d, 空闲空间: %d\n", sds->buf, sds->len, sds->free);
free(sds);
return 0;
}
在 appendSDS 函数中，首先计算要追加的字符串长度 appendLen。如果当前 SDS 的空闲空间 free 小于 appendLen，则根据空间预分配策略重新分配空间。这里简单模拟了 Redis 的空间预分配策略：如果新长度小于 1MB，则将新长度翻倍；如果新长度大于等于 1MB，则增加 1MB 空闲空间。然后使用 strcat 函数将追加的字符串连接到原字符串后面，并更新 len 和 free 字段。
SDS 缩短操作（惰性空间释放）
以下是实现 SDS 缩短操作并体现惰性空间释放的代码示例：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct sdshdr {
int len;
int free;
char buf[];
};
// 缩短 SDS 字符串
struct sdshdr* shortenSDS(struct sdshdr* sds, int newLen) {
if (newLen < sds->len) {
sds->buf[newLen] = '\0';
sds->free += sds->len - newLen;
sds->len = newLen;
}
return sds;
}
int main() {
struct sdshdr* sds = createSDS();
sds = appendSDS(sds, ", world");
sds = shortenSDS(sds, 5);
printf("缩短后的 SDS 内容: %s, 长度: %d, 空闲空间: %d\n", sds->buf, sds->len, sds->free);
free(sds);
return 0;
}
在 shortenSDS 函数中，如果新的长度 newLen 小于当前 SDS 的长度 len，则将 buf 数组的第 newLen 个位置设置为空字符 '\0'，表示字符串缩短到此位置。然后更新 free 字段，将减少的长度加到 free 中，同时更新 len 字段为新的长度。这样就实现了惰性空间释放，缩短后的空闲空间可以供后续操作使用。
SDS 内存管理对 Redis 性能的影响
减少内存碎片
由于 SDS 的空间预分配和惰性空间释放策略，Redis 在处理字符串操作时，内存分配和释放的频率相对较低。这有助于减少内存碎片的产生。
在传统的 C 语言字符串操作中，频繁的内存分配和释放容易导致内存碎片。例如，多次分配和释放不同大小的字符串，可能会使内存空间变得碎片化，后续申请较大内存块时可能无法找到连续的足够空间，即使总的空闲内存是足够的。
而 SDS 通过合理的空间预分配，在一定程度上减少了内存分配的次数，使得内存使用更加紧凑。惰性空间释放则避免了不必要的内存释放操作，进一步减少了内存碎片的产生。这对于 Redis 这样需要频繁处理字符串数据的系统来说，大大提高了内存利用率和性能。
提高操作效率
SDS 的 O(1)时间复杂度获取长度以及高效的内存分配策略，使得 Redis 在处理字符串相关操作时具有很高的效率。
以 GET 和 SET 命令为例，由于键和值都以 SDS 形式存储，在查找键和设置值时，可以快速获取字符串长度进行比较和操作。在进行字符串拼接、截取等操作时，SDS 的空间预分配和惰性空间释放策略减少了额外的内存分配和释放开销，使得这些操作能够快速完成。
在 Redis 的性能测试中，使用 SDS 结构存储字符串相比传统 C 语言字符串实现，在高并发读写以及频繁字符串操作场景下，性能提升显著。这也是 Redis 能够成为高性能键值对存储系统的重要原因之一。
SDS 内存管理的优化方向探讨
更细粒度的空间预分配策略
虽然当前的空间预分配策略已经在很大程度上提高了性能，但对于一些特定场景，可能需要更细粒度的策略。例如，对于一些经常进行小幅度增长的字符串，可以根据增长的频率和幅度来调整预分配的空间大小。如果增长频率较高且幅度较小，可以适当增加预分配的比例，以进一步减少内存分配次数。
可以通过记录字符串增长的历史数据，动态调整预分配策略。例如，统计最近几次增长操作的平均增长幅度，根据这个平均值来确定预分配空间的大小。这样可以在不同的应用场景下，更加灵活地优化内存使用和性能。
结合内存池技术
内存池技术可以预先分配一块较大的内存空间，然后在需要时从这个内存池中分配小块内存。当不再使用这些小块内存时，将其归还到内存池而不是归还给系统。
对于 Redis 的 SDS 内存管理，可以结合内存池技术。在初始化阶段，分配一个较大的内存池，当创建或扩展 SDS 时，优先从内存池中分配内存。当 SDS 释放空间时，将空间归还到内存池。这样可以进一步减少系统调用的开销，提高内存分配和释放的效率。
不过，实现内存池技术需要注意内存池的大小管理、内存碎片整理等问题。如果内存池大小设置不合理，可能会导致内存浪费或者内存不足的情况。同时，需要设计合理的算法来管理内存池中的空闲块，以提高内存分配的效率。
综上所述，Redis 的 SDS 结构通过独特的内存分配策略，在高效内存管理方面发挥了重要作用。通过深入理解 SDS 的原理和应用，可以更好地优化 Redis 的性能，并且为进一步的优化提供思路。同时，在实际应用中，根据不同的业务场景，可以对 SDS 的内存管理策略进行适当的调整和扩展，以满足更高的性能需求。