《Redis 设计与实现》笔记之简单动态字符串

一、SDS 的定义

Redis 不使用 C 语言的字符数组来表示字符串，而是重写了一个 SDS 结构体来表示字符串。

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

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

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

二、SDS 与字符串区别

2.1 常数空间获取字符串长度

C 字符串需要遍历才可以获取字符串长度，因此时间复杂度是 $O(n)$

由于 SDS 中增加了一个成员变量 len，因此获取一个 SDS 长度的复杂度仅为 $O(1)$。

2.2 避免缓冲区溢出

C 语言的库函数 **char *strcat(char *dest, const char *src)** 可以将 src所指向的字符串追加到 dest 所指向的字符串的结尾。

C 字符串是不记录自身长度的，strcat函数默认 dest 有足够多的内存空间，但是一旦内存空间不满足就会发生缓冲区溢出。

比如程序中有两个字符串 s1 = "Hello", s2 = "world"，假设它们的内存空间是连在一块的，这时候我执行 strcat(s1, "yunhu")，那么 s2 原本的值就被覆盖了，这就是缓冲区溢出。

而 SDS 在修改时会检查 SDS 的空间是否满足，如果不满足就扩容，之后才执行实际修改操作，因此没有缓冲区溢出问题。

2.3 减少内存分配

如果字符串增长，比如 append，C 字符串需要内存重分配扩展底层数组大小，否则就会出现缓冲区溢出。

如果字符串缩短，那么需要重分配来释放那些没用使用的内存空间，如果忘记则会出现内存泄漏。

Redis 经常被用来频繁修改数据，这样每一次修改字符串长度都会进行一次内存重分配，对性能造成影响。

因此 Redis 在 SDS 中添加了一个成员变量 free，表示未使用的字节数量。

通过这个未使用的空间，SDS 就进行了优化。

2.3.1 空间预分配优化

在对 SDS 进行空间扩展的时候，不仅本身的 len 会分配所需要的空间，free 也会有分配。

• 如果 len < 1 MB，free = len，len 增加到 10，那么 free 等于 10。
• 如果 len >= 1 MB, free = 1 MB。

第二次扩展时，当 free 的空间大于 0 的时候，会先使用 free 的空间，如果 free 的空间够，就无须进行内存的重分配了，性能得到优化。

2.3.2 惰性空间释放优化

当缩短字符串的时候，Redis 不直接进行内存的重分配，而是将 free 也就是未使用的空间大小增加。

之后如果有增加字符串的行为，如果 free 的空间够，那么只需将 free 中的空间用来使用，不必内存重分配。

2.4 二进制安全

C 字符串中不能包含空字符，因此它只能保存文本数据，无法保存图片、音视频等二进制数据。

因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束，因此数据在写入与读取时完全相同。

2.5 兼容部分 C 字符串函数

SDS 也是空字符串结尾，因此也可以使用<string.h>函数库，从而避免了不必要的代码重复。