2 简单动态字符串

概述

 Redis 没有直接使用 C 语言传统的字符串表示(以空字符结尾的字符数组，以下简称 C 字符串)，而是自己构建了一种名为简单动态字符串(simple dynamic string，SDS)的抽象类型，并将 SDS 用作 Redis 的默认字符串表示。
 举个例子：如果客户端执行命令：$ redis > set msg "hello world"
 那么 Redis 将在数据库中创建一个新的键值对，其中：

• 键值对的键是一个字符串对象，对象的底层实现是一个保存着字符串 "msg" 的 SDS。
• 键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串 "hello world" 的 SDS。

 除了用来保存数据库中的字符串值之外，SDS 还被用作缓冲区(buffer)：AOF 模块中的 AOF 缓冲区，以及客户端状态中的输入缓冲区，都是由 SDS 实现的。

SDS 的定义

 每个 sds.h/sdshdr 结构表示一个 SDS 值：

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

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

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

 如下图是一个示例： java -jar plantuml.jar -charset UTF-8 sds_example.txt

• free 属性的值为 0，表示这个 SDS 没有分配任何未使用空间。
• len 属性的值为 5，表示这个 SDS 保存了一个五字节长的字符串。
• buf 属性是一个 char 类型的数组，数组的前 5 个字节分别保存了'R'、'e'、'd'、'i'、's'五个字符，而最后一个字节则保存了空字符'\0'。

 SDS 遵循 C 字符串以空字符结尾的惯例，保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面，并且为空字符分配额外的 1 字节空间，以及添加空字符到字符串末尾等操作，都是由 SDS 函数自动完成的，所以这个空字符对于 SDS 的使用者来说是完全透明的。这么用的好处是，SDS 可以直接重用一部分 C 字符串函数库里面的函数(比如 printf 函数)。

SDS 与 C 字符串的区别

常数复杂度获取字符串长度

 C 字符串并不记录自身的长度信息，所以需要遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为 O(N)。
 和 C 字符串不同，因为 SDS 在 len 属性中记录了 SDS 本身的长度，所以获取一个 SDS 长度的复杂度仅为 O(1)。

杜绝缓存区溢出

 除了获取字符串长度的复杂度高之外，C 字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出。缓冲区溢出示例如下：

            s1                          s2
            |                           |
...'R' | 'e' | 'd' | 'i' | 's' | '\0' | 'M' | 'o' | 'n'  | 'g' | 'o' | 'D' | 'B' | '\0'| ...

 如上，因为 C 字符串本身不记录长度，s1 的内容如果改为"Redis Cluster"，但 s1 的空间不足了，那么 s1 的数据将溢出到 s2 所在的空间中，导致 s2 保存的内容被意外地修改。

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

减少修改字符串时带来的内存重分配次数

 C 字符串每次增长或者缩短，程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作。
 因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作。为了避免 C 字符串的这种缺陷，SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联：在 SDS 中，buf 数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由 SDS 的 free 属性记录。
 通过未使用空间，SDS 实现了空间预分配和惰性空间释放两种优化策略。

1. 空间预分配
    通过空间预分配策略，Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。其中，额外分配的未使用空间数量由以下公式决定：

• 对于空间小于 1M 来说,分配空间为原有总长度+同样长度+ 1byte(B,字节)。比如原长度为 8 的字符串,新增 5 个长度后,总共为 13 长度,则预分配 13 + 13 + 1= 27 字节(额外一字节用于保存空字符串)。
• 对于大于 1M 来说,分配空间为原有总长度 + 1MB + 1byte。比如增加完字符串后长度为 15MB,则为 15MB + 1MB + 1byte。  在扩展 SDS 空间之前，SDS API 会先检查未使用空间是否足够，如果足够的话，API 就会直接使用未使用空间，而无需执行内存重分配。

2. 惰性空间释放
    惰性空间释放用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。
    通过惰性空间释放策略，SDS 避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。
    与此同时，SDS 也提供了相应的 API，让我们可以再有需要时，真正地释放 SDS 的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

二进制安全

 C 字符串中的字符必须符合某种编码（比如 ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得 C 字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
 虽然数据库一般用于保存文本数据，但使用数据库来保存二进制数据的场景也不少见，因此，为了确保 Redis 可以适用于各种不同的使用场景，SDS 的 API 都是二进制安全的（binary-safe），所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时时什么样的，它被读取时就是什么样。这是由于 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束。

兼容部分 C 字符串函数

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

总结

 下表对 C 字符串和 SDS 之间的区别进行了总结：

SDS API

 参考 SDS 主要操作 APIopen in new window。

参考文献

• Redis 设计与实现-第 2 版open in new window