简单动态字符串

Redis 中使用 SDS (Simple Dynamic String, 简单动态字符串) 作为 Redis 的默认字符串表示。

Redis 中 ，C 字符串只会作为 字符串字面量 (string literal) 用在无须对字符串进行修改的地方，如打印日志。

而 SDS 将会用作：

• 字符串值
• 缓冲区 (buffer):
  • AOF 缓冲区
  • 客户端状态中的输入缓冲区

1.1 SDS 的定义

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

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

SDS 遵循 C 字符串以空字符结尾的惯例，保存空字符的 1 字节空间不计算在 SDS 的 len 属性中，且为其分配额外的 1 字节空间。这样的好处是可以直接复用一些 C 的库函数。

1.2 SDS 与 C 字符串的区别

C 使用长度为 N+1 的字符数组表示长度为 N 的字符串，其最后一个元素总是空字符 \0。

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

因为 C 字符串并不记录自身的长度信息，所以获取 C 字符串长度必须遍历整个字符串，这个操作的时间复杂度为 O(N)。

在 SDS 中以 len 属性记录了 SDS 本身的长度，所以获取 SDS 长度的时间复杂度为 O(1)。

通过使用 SDS 而不是 C 字符串，Redis 将获取字符串长度的时间复杂度从 O(N) 降低到了 O(1)，确保了获取字符串长度不会称为 Redis 的性能瓶颈。例如：反复执行 STRLEN 指令不会对系统性能造成影响。

1.2.2 杜绝缓冲区溢出

C 字符串不记录本身长度带来的另一个问题就是容易造成 缓冲区溢出 (buffer overflow)。

例如 <string.h>/strcat函数可以将字符串的内容拼接到 dest 字符串的末尾：

char *strcat(char *dest, const char *src);

函数 strcat 假定用户执行函数时，已经为 dest 分配了足够的内存用于容纳 src 的所有内容，一旦假设不成立将会造成缓冲区溢出，

比如，假设存在两个内存中相邻的字符串 s1 和 s2 ，s1 中保存 “Redis”，s2 保存 “MongoDB” 。

若欲执行

strcat(s1, " Cluster");

而忘记了为 s1 分配足够的空间，则在函数执行之后，s1 的数据将会溢出到 s2 的内存空间中，导致其数据被意外修改。

与 C 字符串不同，SDS 空间分配策略完全杜绝了缓冲区溢出：

1. 当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改需求
2. 若不满足，API 会自动将 SDS 的空间扩展至执行修改所需的大小。再执行实际的修改操作

故使用 SDS 无需手动修改 SDS 的空间大小，也不会出现缓存溢出的问题。

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

因为 C 字符串不记录自身的长度，所以每次增长或缩短一个 C 字符串，都要其进行一次内存重分配操作：

• 若执行增长字符串的操作，比如拼接 (append)，执行操作之前需要先通过内存分配来扩展底层数组的空间大小 (忘记此操作将会导致缓冲区溢出) 。
• 若执行缩短字符串的操作，比如截断 (trim),执行操作之后需要内存重分配来释放不再使用的内存空间 (忘记此操作将会导致内存泄漏^[1])。

因为内存重新分配涉及复杂算法和系统调用，所以通常是比较耗时的操作：

• 一般程序中，若修改字符串长度的情况不经常出现，那么每次修改都进行内存的重新分配是可以接受的。
• Redis 作为数据库，经常用于速度要求严苛、数据频繁修改的场合。若每次修改都进行内存的重新分配，则会对性能造成影响。

为了避免这些缺陷，SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联：buf 数组的长度不一定为 len + 1，数组中可以包含未使用的字节，其数量存储在 free 属性中。

通过未使用空间，SDS 实现了空间预分配和惰性空间释放两种优化策略。

1. 空间预分配

空间预分配用于优化 SDS 的字符串增长操作：当 SDS API 对 SDS 进行修改并需要对其空间进行扩展时，不仅会分配修改所需的空间，还会分配额外的未使用空间。

额外空间数量由一下公式决定：

• 修改后，SDS.buf < 1MB，则分配和 len 同样大小的未使用空间，此时 free 和 len 相同（例如：SDS 修改后为 len 为13，则 free 也为 13， buf 实际长度为 27 = 13 + 13 + 1）。
• 修改后，SDS.buf >= 1MB，则会额外分配 1MB 的空间（例如：buf 修改后为 30MB，则实际长度为 30MB + 1MB + 1Byte)。

通过这种预分配策略，SDS 将连续增长 N 此字符串所需次数从必定 N 次降低为最多 N 次。

2. 惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作：当SDS API 需要缩短 SDS 保存的字符串时，不立即进行内存重分配来回收不再使用的字节，而是使用 free 属性记录下来等待下次使用。

通过惰性空间释放策略，SDS 避免了缩短字符串时所需的内存重分配操作，并未将来可能的增长操作提供了优化。

1.2.4 二进制安全

C 字符串中不能包含空字符（会被认为是字符串结尾），故 C 字符串只能保存文本数据，而不能保存二进制数据。

SDS API 都是二进制安全的 (binary-safe^[2])，数据将会被当做二进制来处理，而不是字符。

1.2.5 兼容部分 C 字符串函数

虽然 SDS API 都是二进制安全的，但其也遵守了 C 字符串中以空字符结尾的惯例，这样是为了让那些保存文本数据的 SDS 可以重用 C 字符串函数。

1.3 总结

1.3.1 C 字符串和 SDS 的区别

描述	C 字符串	SDS
获取字符串长度的时间复杂度	O(N)	O(1)
API 安全	API 不安全，可能会导致缓冲区溢出	API 安全，不会导致缓冲区溢出
内存分配	修改字符串长度 N 次必定进行 N 次内存重分配	修改字符串长度 N 次至多进行 N 次内存分配
保存内容	只能保存文本数据	可以保存文本数据或二进制数据
使用 <string.h> 库函数	可以使用所有	可以使用一部分

1.3.2 小结

• Redis 只会使用 C 字符串作为字面量 (stringn literal)，大多数情况下使用 SDS 来表示字符串
• 相较于 C 字符串，SDS 有以下优点：
  1. 常数复杂度 (O(1)) 获取字符串长度
  2. 杜绝缓冲区溢出
  3. 减少修改字符串长度时所需的内存重分配次数
  4. 二进制安全
  5. 兼容部分 C 字符串函数

Reference

1. Redis设计与实现

---

1. 内存泄漏（英语：memory leak）是一种资源泄漏，主因是计算机程序对存储器配置管理失当，失去对一段已分配内存空间的控制，造成程序继续占用已经不再使用的内存空间，或是存储器所存储之对象无法透过执行代码而访问，令内存资源空耗 ↩︎

2. A binary-safe function is one that treats its input as a raw stream of bytes and ignores every textual aspect it may have ↩︎