从 C 字符串到 SDS 看 Redis 的性能优化之路

Redis 底层数据结构：从 C 字符串说起

在深入探讨 Redis 的简单动态字符串（Simple Dynamic String, SDS）之前，先来回顾一下 C 语言中的字符串。C 语言作为一种高效且底层的编程语言，其字符串的设计理念深深影响了后续许多系统和应用的开发。

C 字符串的结构与特性

C 语言中的字符串实际上是一个以空字符 '\0' 结尾的字符数组。例如，定义一个简单的字符串：

char str[] = "Hello, Redis!";

这里，str 是一个字符数组，数组的最后一个元素是 '\0'，用于标识字符串的结束。这种设计简洁而直观，符合 C 语言追求高效、贴近硬件的特点。

从内存布局来看，假设 str 数组存储在内存地址 0x1000 处，其内存布局大致如下：

内存地址	存储内容
0x1000	'H'
0x1001	'e'
0x1002	'l'
0x1003	'l'
0x1004	'o'
0x1005	','
0x1006	' '
0x1007	'R'
0x1008	'e'
0x1009	'd'
0x100A	'i'
0x100B	's'
0x100C	'!'
0x100D	'\0'

C 字符串在实际应用中的问题

1. 获取字符串长度的时间复杂度：在 C 语言中，要获取一个字符串的长度，通常会使用 strlen 函数。例如：

#include <stdio.h>
#include <string.h>

int main() {
    char str[] = "Hello, Redis!";
    size_t len = strlen(str);
    printf("The length of the string is: %zu\n", len);
    return 0;
}

strlen 函数的实现是通过遍历字符串，直到遇到 '\0' 字符为止。这意味着其时间复杂度为 O(n)，其中 n 是字符串的长度。在处理大量字符串操作或者长字符串时，这种线性时间复杂度的操作可能会成为性能瓶颈。

2. 内存分配与释放的问题：C 语言中字符串的内存分配需要手动管理。例如，动态分配一个字符串的内存：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    char *dynamicStr = (char *)malloc(100 * sizeof(char));
    if (dynamicStr == NULL) {
        perror("malloc");
        return 1;
    }
    strcpy(dynamicStr, "This is a dynamic string");
    printf("Dynamic string: %s\n", dynamicStr);
    free(dynamicStr);
    return 0;
}

在这个例子中，通过 malloc 分配了 100 个字符的内存空间，使用完后需要通过 free 释放。如果忘记释放内存，就会导致内存泄漏。而且，在进行字符串拼接等操作时，如果预先分配的内存不足，还需要重新分配内存并复制原字符串内容，这不仅繁琐，而且性能开销较大。

3. 二进制安全问题：C 字符串以 '\0' 作为结束标志，这就限制了字符串中不能包含 '\0' 字符。例如，如果要存储一个二进制文件的内容，其中可能包含 '\0'，使用 C 字符串就无法准确存储。这在处理一些非文本数据，如图片、音频等二进制数据时，会带来很大的不便。

Redis 的 SDS 设计理念

为了解决 C 字符串在实际应用中存在的问题，Redis 设计了自己的字符串结构——简单动态字符串（SDS）。SDS 的设计理念围绕着高效、安全和灵活这几个核心目标。

SDS 的数据结构

Redis 的 SDS 数据结构定义在 sds.h 头文件中，其主要结构如下：

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

从这个结构可以看出，SDS 与 C 字符串最大的区别在于，它通过 len 字段记录了字符串的长度，通过 free 字段记录了剩余可用的空间。这样的设计使得很多操作可以在常数时间内完成，同时也解决了内存管理和二进制安全的问题。

SDS 如何解决 C 字符串的问题

1. 获取字符串长度的优化：由于 SDS 结构中直接记录了字符串的长度 len，获取字符串长度的操作时间复杂度变为 O(1)。例如，假设有一个 SDS 实例 s，要获取其长度，直接访问 s->len 即可，无需像 C 字符串那样遍历整个字符串。

// 假设 s 是一个指向 sdshdr 结构的指针
int length = s->len;

这种优化在频繁需要获取字符串长度的场景下，能显著提升性能。

2. 内存分配与释放的优化：SDS 在进行字符串修改操作时，会根据需要自动调整内存空间。例如，当进行字符串拼接时，如果当前剩余空间 free 不足以容纳新的内容，SDS 会自动重新分配内存，并且在重新分配内存时，会采用一种预分配策略。具体来说，当 SDS 需要扩展内存时，它不仅会分配刚好满足需求的内存，还会额外分配一些空间（如果扩展后长度小于 1MB，额外分配与当前长度相同的空间；如果扩展后长度大于等于 1MB，额外分配 1MB 的空间）。这样可以减少频繁的内存分配操作，提高性能。同时，SDS 也提供了相应的释放内存的函数，简化了内存管理。

3. 二进制安全：SDS 不再以 '\0' 作为字符串结束的唯一标识，而是通过 len 字段来确定字符串的长度。这意味着 SDS 可以存储任意二进制数据，包括包含 '\0' 字符的数据。例如，可以直接将一个二进制文件的内容存储在 SDS 中，而不用担心数据被截断。

SDS 的性能优化分析

常数时间获取字符串长度的优势

在 Redis 中，很多操作都需要获取字符串的长度。以 SET 和 GET 命令为例，当执行 SET key value 命令时，Redis 需要记录 value 的长度，以便后续存储和管理。如果使用 C 字符串，每次都需要通过 strlen 函数以 O(n) 的时间复杂度获取长度；而使用 SDS，直接通过 len 字段以 O(1) 的时间复杂度获取长度。

假设 Redis 每秒处理 10000 个 SET 命令，每个 value 的平均长度为 100 个字符。使用 C 字符串时，每次获取长度需要遍历 100 个字符，那么每秒获取长度的总时间开销为： [10000 \times 100 \times t] 其中 (t) 是遍历一个字符的时间。

而使用 SDS，每次获取长度只需访问一次内存，时间开销可近似为常数 (C)，每秒获取长度的总时间开销为： [10000 \times C] 显然，在这种高并发且频繁获取字符串长度的场景下，SDS 的性能优势非常明显。

预分配策略的性能提升

SDS 的预分配策略在减少内存分配次数方面起到了关键作用。以字符串拼接操作为例，假设我们要通过多次拼接操作构建一个长字符串。

如果使用 C 字符串，每次拼接时如果发现空间不足，都需要重新分配内存并复制原字符串内容。例如，初始分配了 100 字节的空间，当拼接的内容超过 100 字节时，需要重新分配 200 字节的空间，复制原 100 字节内容，再拼接新的内容。如果不断进行这样的操作，内存分配和复制的开销会非常大。

而对于 SDS，假设初始分配了 100 字节的空间（len = 0, free = 100），当第一次拼接 50 字节的内容时，len 变为 50，free 变为 50。此时如果再次拼接 70 字节的内容，由于当前 free 不足，SDS 会重新分配内存。根据预分配策略，如果拼接后长度小于 1MB，会额外分配与当前长度相同的空间，即总共分配 (50 + 70) * 2 = 240 字节的空间（len = 120, free = 120）。这样，后续的拼接操作如果总长度不超过 240 字节，就无需再次分配内存，大大减少了内存分配的次数，提高了性能。

二进制安全带来的灵活性与性能影响

虽然二进制安全本身并不直接提升性能，但它使得 Redis 可以处理更广泛的数据类型，包括二进制数据。这在一些场景下间接提高了 Redis 的性能。例如，在缓存图片数据时，如果使用 C 字符串，由于无法存储包含 '\0' 的数据，可能需要对图片数据进行特殊处理，如编码转换等，这无疑增加了额外的性能开销。而使用 SDS，图片数据可以直接存储，避免了这些额外的处理，提高了整体性能。

SDS 代码示例分析

创建和初始化 SDS

在 Redis 的源码中，提供了一系列操作 SDS 的函数。首先来看创建和初始化 SDS 的函数 sdsnew：

sds sdsnew(const char *init) {
    size_t initlen = (init == NULL)? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

sds sdsnewlen(const char *init, size_t initlen) {
    struct sdshdr *sh;
    if (init) {
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
    } else {
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
    }
    if (sh == NULL) return NULL;
    sh->len = initlen;
    sh->free = 0;
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;
}

在 sdsnew 函数中，首先通过 strlen 获取初始字符串的长度（如果 init 不为空），然后调用 sdsnewlen 函数。sdsnewlen 函数中，根据 init 是否为空，使用 zmalloc 或 zcalloc 分配内存。这里分配的内存大小为 sizeof(struct sdshdr) + initlen + 1，其中 sizeof(struct sdshdr) 是 SDS 头部的大小，initlen 是字符串内容的长度，+1 是为了存储 '\0' 字符。然后设置 len 和 free 字段，并将初始内容复制到 buf 数组中，最后返回 buf 数组的指针。

字符串拼接操作

Redis 中实现字符串拼接的函数是 sdscatlen：

sds sdscatlen(sds s, const char *t, size_t len) {
    struct sdshdr *sh, *newsh;
    size_t curlen = sdslen(s);

    sh = (void*) (s-(sizeof(struct sdshdr)));
    if (len + curlen > sh->free) {
        newsh = sdsMakeRoomFor(s, len);
        if (newsh == NULL) return NULL;
        sh = newsh;
        s = (char*)newsh->buf;
    }
    memcpy(s+curlen, t, len);
    sh->free -= len;
    sh->len += len;
    s[curlen+len] = '\0';
    return s;
}

在 sdscatlen 函数中，首先获取当前 SDS 的长度 curlen，然后检查剩余空间 free 是否足够容纳新的内容 len。如果空间不足，调用 sdsMakeRoomFor 函数重新分配内存。sdsMakeRoomFor 函数会根据预分配策略分配足够的内存。分配好内存后，通过 memcpy 将新的内容 t 复制到 s 字符串的末尾，更新 free 和 len 字段，并在末尾添加 '\0' 字符。

释放 SDS 内存

释放 SDS 内存的函数是 sdsfree：

void sdsfree(sds s) {
    if (s == NULL) return;
    sdsHdrSize(zmalloc_size(s));
    zfree(s-sizeof(struct sdshdr));
}

在 sdsfree 函数中，首先检查 s 是否为空，如果不为空，通过 zmalloc_size 获取当前分配的内存大小，然后通过 zfree 释放内存，释放的内存地址为 s - sizeof(struct sdshdr)，即 SDS 头部的起始地址。

SDS 在 Redis 中的实际应用场景

键值对中的值存储

在 Redis 中，键值对是最基本的数据存储形式。其中，值可以是字符串、哈希、列表等多种数据类型。而字符串类型的值，底层就是通过 SDS 来存储的。例如，当执行 SET mykey "Hello, Redis!" 命令时，"Hello, Redis!" 这个字符串就会以 SDS 的形式存储在 Redis 中。这种存储方式不仅保证了高效的字符串操作，还使得 Redis 可以处理任意二进制数据作为值，满足了各种应用场景的需求。

作为其他数据结构的基础

SDS 不仅用于存储字符串值，还作为 Redis 其他数据结构的基础。例如，哈希表中的字段名和字段值，列表中的元素等，在底层很多时候都是以 SDS 的形式存在。以哈希表为例，当执行 HSET myhash field1 "value1" 命令时，field1 和 value1 都是以 SDS 形式存储。这种统一的数据结构基础，使得 Redis 的实现更加简洁高效，同时也便于进行各种数据操作和优化。

网络通信中的数据传输

Redis 作为一个网络服务器，需要通过网络接收和发送数据。在网络通信过程中，接收到的请求数据和要发送的响应数据，很多时候也是以 SDS 的形式进行处理。例如，当客户端发送一个 GET mykey 请求时，Redis 接收到的请求字符串会被解析并以 SDS 形式存储，处理完请求后，返回的响应数据（如果是字符串类型）同样以 SDS 形式发送回客户端。这种使用 SDS 的方式，保证了数据在网络传输过程中的高效处理和二进制安全。

对比其他数据库字符串存储方式

与 MySQL 字符串存储的对比

1. 存储结构：MySQL 中字符串类型有多种，如 CHAR 和 VARCHAR。CHAR 类型是固定长度的，它在存储时会按照定义的长度分配固定大小的空间，即使实际存储的字符串长度小于定义长度，也会占用固定大小的空间。例如，定义 CHAR(10)，无论存储的字符串是 'abc' 还是 'abcdefghij'，都会占用 10 个字符的存储空间。而 VARCHAR 类型是可变长度的，它会在存储字符串内容的基础上，额外使用 1 - 2 个字节来记录字符串的长度（长度小于 255 字节时用 1 个字节，大于等于 255 字节时用 2 个字节）。相比之下，Redis 的 SDS 不仅记录了字符串的长度，还记录了剩余可用空间，在内存管理上更加灵活。
2. 性能特点：在查询操作中，如果是固定长度的 CHAR 类型，MySQL 可以快速定位到数据位置，因为其存储位置是固定的。但对于 VARCHAR 类型，由于需要先读取长度信息再定位数据，可能会有一些额外的开销。而 Redis 的 SDS 由于采用了预分配策略和 O(1) 获取长度的特性，在频繁进行字符串操作（如拼接、获取长度等）时，性能优势明显。在存储大字符串时，MySQL 的 VARCHAR 可能需要额外的空间管理操作，而 Redis 的 SDS 可以更好地适应动态增长的需求。

与 MongoDB 字符串存储的对比

1. 存储结构：MongoDB 中的文档是以 BSON（Binary JSON）格式存储的，字符串在 BSON 中以 UTF - 8 编码存储，并且会记录字符串的长度。虽然也记录长度，但与 Redis 的 SDS 不同，MongoDB 没有像 SDS 那样的预分配策略和对剩余空间的管理。而且，BSON 格式主要是为了在网络传输和存储中更高效地表示数据，其结构相对复杂。
2. 性能特点：MongoDB 更侧重于文档存储和分布式处理，在处理大量文档中的字符串时，其性能更多地受到整个文档结构和分布式存储的影响。而 Redis 的 SDS 设计初衷就是为了高效的字符串操作，在单机环境下，对于简单的字符串操作（如计数、拼接等），Redis 的性能会更优。但在处理复杂的文档结构和分布式存储方面，MongoDB 具有更大的优势。

总结 SDS 对 Redis 性能优化的关键作用

通过对 C 字符串和 Redis 的 SDS 的深入分析，可以清晰地看到 SDS 在解决 C 字符串固有问题的同时，为 Redis 的高性能提供了坚实的基础。从常数时间获取字符串长度，到高效的内存预分配策略，再到二进制安全特性，SDS 的每一个设计细节都紧密围绕着提升性能和灵活性展开。

在实际应用中，无论是作为键值对中的值存储，还是作为其他数据结构的基础，亦或是在网络通信中的数据传输，SDS 都发挥着不可或缺的作用。与其他数据库的字符串存储方式相比，SDS 展现出了独特的优势，使其成为 Redis 在高性能字符串处理方面的核心竞争力之一。理解和掌握 SDS 的设计与实现，对于深入理解 Redis 的性能优化机制以及在实际应用中更好地使用 Redis 具有重要意义。