Redis 的 String 数据结构，居然这么厉害

1. 动态字符串

Redis 有 5 种基础数据结构，它们分别是：string(字符串)、list(列表)、hash(字典)、set(集合) 和 zset(有序集合)。

Redis中的字符串并不是传统的C语言字符串（即字符数组，以下简称C字符串），而是自己构建了一种简单动态字符串（simple dynamic string，SDS），并将 SDS 作为 Redis 的默认字符串表示。

Redis 相关的前置知识建议阅读作者的文章：Java工程师的进阶之路 Redis篇

在 Redis 中，C 字符串一般只用在无需对字符串值进行修改的地方，比如 Redis 的启动时的日志。Redis 需要的字符串是一个可修改字符长度的字符串，就会用到 SDS 来表示一个字符串。比如下面这个例子：

127.0.0.1:6379> set msg "hello world"
OK

这是一条很简单的命令，将 “hello world” 这个字符串与 msg 这个键建立映射关系。而 “hello world” 在Redis 中的表示，就是一个 SDS。说了那么久的 SDS，那这个 SDS 到底长什么样呢？我们来看看：

sds.h：

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

下图展示了一个 SDS 的示例：

1. free 属性的值为 0，表示这个 SDS 没有任何剩余的可使用字节数；
2. len 为 5，表示这个 SDS 保存了一个长度为 5 的字符串；
3. buf 属性是一个 char 类型的数组，数组的前五个字节分别保存了 ‘R’、’e’、’d’、’i’、’s’ 五个字符，而 最后一个字节则保存空字符 ‘’，代表字符串结束；

2. SDS 的优势

看到这里，可能还有人不明白使用 SDS 的好处。没关系，我们接下来再看看另一个示例。我们看下图，这个  SDS 和上图的 SDS 不一样，虽然都保存字符串 “Redis”。但下图中 SDS 的 buf 字符数组长度以及 free 所保存的值都与上图的 SDS 不一样：

我们都知道，Redis 作为一款非关系型的内存数据库，它的值很容易变动。同时我们也知道，C 语言中字符数组的长度是无法变动的。如果 Redis 中使用的字符串是 C 字符串，而不是 SDS，当我们变动一个键所对应的字符串，如果新字符串的长度小于等于原先字符串的长度，那么我们只要替换字符数组上的内容，再把代表字符串结尾的提前（如果新旧字符串长度相等，则空字符串还留在原先的位置）。但 如果新字符串的长度大于原先旧字符串的长度，那么很不幸，我们只能重新申请一个能容纳新字符串长度的数组，用于保存新字符串，这对Redis无疑是不利的。

Redis 在为一个字符串创建一个 SDS 对象时，通常会申请比字符串长度更长的字节数组（buf），Redis 将字符串保存进这个数组，同时在 len 这个变量保存字符串的长度，再用 free 这个变量保存 buf 尚未使用的字节数量。

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

当客户端要求变动一个键所对应的字符串时，如果 buf 的长度大于新字符串的长度，那么就无需再声明一个新的数组来容纳新字符串了。

我们再来看 sdshdr 这个结构体，这里面有 free、len 和 buf 这三个域。那么这个 len 会不会有些多余？因为 free 已经记录尚未使用的字节数量了，同时 len 我们也可以通过： 的方式来计算字符串长度，那么这个 len 真的是多余的吗？其实不是，如果有使用过 Java、Python 等这些高级语言的人都有经验，在这些高级语言中，我们可以轻而易举的调用一个函数来获取字符串的长度，而这些高级语言的字符串内部实现，同样也记录了字符串的长度。

假设我们要计算一个字符串长度，每次都要调用 ，这个操作的时间复杂度为 ，下图展示了 C 程序中计算字符串长度的过程：

从上图我们可以知道，当通过 计算一个 C 字符串的长度，游标会遍历到空字符处才停止，而大家在编程中，多多少少在一些业务场景会重复用到某个字符串长度。于是，SDS 中，len 域的作用就在于此，我们只需要计算一次字符串的长度，当需要用到时直接从 len 中取，这时的时间复杂度为 。

除了获取字符串长度的时间复杂度高之外，C 字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出。C 语言中的 strcat 函数可以拼接两个字符串，具体定义如下：

#include <string.h>
char *strcat(char *dest, const char *src);

strcat 函数可以将 src 字符串中的内容拼接到 dest 字符串之后，但因为 C 本身不记录字符串长度，默认认为 dest 已经分配了足够的内存空间。举个例子，假设程序中有紧邻的两个字符串 S1 和 S2，其中 S1 保存了字符串 “Redis”，而 S2 保存了字符串 “MongoDB”，如图所示：

如果程序员没有注意 S1 的长度，直接执行 ，那么势必会覆盖到 S2 的内存，换言之 S2 所对应的字符数组的内容会被修改，如图所示：

与 C 字符串不同，SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性，当 SDS API 需要对 SDS 进行修改时，API 会检查 SDS 的空间是否满足修改的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行所需的大小，然后才执行修改操作。

SDS 的 API 里面有一个用于执行拼接操作的 sdscat 函数，它可以将一个 C 字符串拼接到给定的 SDS 所保存的字符串后面，但是 在执行拼接操作之前，sdscat 会检查给定的SDS的空间是否足够，如果不够的话，sdscat 就会扩展 SDS 的空间，然后才执行拼接操作。例如，我们执行 ，其中 SDS 值 s 如图所示：

那么 sdscat 检查后发现，目前 s 的空间并不足以拼接 ” Cluster”，之后，sdscat 就会扩展 s 空间，然后执行拼接 ” Cluster” 操作，拼接完之后的 SDS 如图所示：

Redis 作为内存数据库，经常被用于速度要求严苛，数据被频繁修改的场合，如果每次修改字符串长度都需要执行一次内存重分配的话，那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分，如果这种修改频繁发生的话，可能还会对性能造成影响。

3. 空间优化策略

为了避免 C 字符串的缺陷，SDS 通过未使用空间解除字符串长度和底层数组长度之间的关联。在 SDS 中，buf 数组的长度不一定是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由 SDS 的 free 属性记录。通过未使用空间，SDS 实现了空间预分配和惰性空间释放两种优化策略。

3.1. 空间预分配

空间预分配用于优化 SDS 的字符串增长操作，我们都知道当 SDS 的 API 对一个 SDS 进行修改时，除了分配给本身所需的字节空间，还会再额外分配一些备用空间。那么，这个备用空间是多大呢？备用空间由以下公式决定：

• 如果对 SDS 进行修改后，SDS 的长度（即 len 属性的值）小于 1MB，那么程序分配和 len 属性同样大小的未使用空间，这时 SDS 的 free 属性的值将于 len 属性的值相同。比如经过修改之后，SDS 的 len 将变为 13 个字节，那么程序也会分配 13 个字节的备用空间，外加一个字节用于存储空字符串标识字符串结束，所以 SDS 的 buf 数组实际长度为 字节;
• 如果对 SDS 进行修改之后，SDS 的长度大于等于 1MB，那么程序会多分配 1MB 的未使用时间。比如经修改后，SDS 的 len 为 30MB，那么程序会多分配 1MB 的未使用空间，SDS 的 buf 数组的实际长度为 字节;

3.2. 惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作，当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序其实并不立即使用内存重分配回收缩短后多出来的字节，而是将修改后尚未被使用的字节数存放在 free 中，用于以后使用。

4. 二进制安全

C 字符串的必须必须符合某种编码（比如 ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符串将被误认到达字符串末尾，这限制了 C 字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

虽然数据库一般用于保存文本数据，但使用数据库来保存二进制数据的场景也不少见。因此，为了确保 Redis 可以适用于各种不同的场景，SDS 的 API 都是二进制安全的，所有 SDS API 都会以处理二进制的方式来处理存放在 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤、或假设，数据在写入时是什么样的，它被读取时就是什么样的。

这也是我们将 SDS 的 buf 属性称为字节数组的原因，因为 Redis不是用这个数组来保存字符，而是用它来保存一系列的二进制数据。且在 SDS 中，并非以一个空字符来判断是否到达字符数组的末尾，而是通过 len 属性的值，如图：

兼容部分C字符串函数

虽然 SDS 的 API 都是二进制安全的，但它们一样遵循 C 字符串以空字符结尾的惯例：这些 API 总会将 SDS 保存的数据的末尾设置为空字符，并且总会在为 buf 数组分配空间时多分配一个字节的空间来容纳空字符，这是为了让保存了文本数据的 SDS 可以重用一部分 <string.h> 库定义的函数。比如：strcasecmp 是用于忽略大小写比较两个字符串的函数，使用它来对比 SDS 保存的字符串和另一个 C 字符串。

strcasecmp(sds->buf, "hello world");

又或者，我们可以将 sds 中的 buf 所保存的内容，追加到另一个 C 字符串上。这样，就无需再去编写另外一套与<string.h> 中功能类似的函数了。

strcat(c_string, sds->buf);

5. C 字符串和 SDS 之间的区别