Redis 数据结构之简单动态字符串（SDS）

Redis 没有直接使用 C 字符串（以 '\0' 结尾的字符数组），而是将简单动态字符串（simple dynamic string，SDS）作为 Redis 的默认字符串表示

在 Redis 中，C 字符串只会作为字符串字面量用在一些无须对字符串值进行修改的地方，比如日志

当 Redis 需要的不仅是一个字符串字面量，而是一个可被修改的字符串值时，Redis 就会使用 SDS 来表示字符串值。比如 Redis 数据库中的字符串键值对、缓冲区（AOF 模块的 AOF 缓冲区以及客户端状态中的输入缓冲区）

SDS 定义

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

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

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

SDS 示例

SDS 遵循 C 字符串以空字符结尾的惯例，保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面，并为空字符分配额外 1 字节空间。遵循这一惯例的好处是，SDS 可以直接重用一部分 C 函数

SDS 相比 C 字符串的好处

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

2、杜绝缓冲区溢出

C 字符串不记录自身的长度，所以 C 字符串函数假定用户执行时已经分配了足够多的内存。而这一旦不成立，就会产生缓冲区溢出，导致后续内存空间保存的内容被意外修改

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

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

C 字符串不记录自身长度，所以对于一个包含 N 个字符串的 C 字符串来说，这个 C 字符串底层实现总是一个 N+1 个字符长的数组。所以每次增长或缩短一个 C 字符长，程序都要进行一次内存重分配操作：

• 增长字符串时，需要通过内存重分配来扩展底层数组的空间大小，否则会产生缓冲区溢出
• 缩短字符串时，需要通过内存重分配来释放空间，否则会产生内存泄漏

内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以通常是一个比较耗时的操作。Redis 作为数据库，经常用于速度要求严苛、数据被频繁修改的场合，不能允许内存重分配频繁发生

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

• 空间预分配
  用于优化 SDS 的字符串增长操作：当需要对 SDS 进行空间扩展时，不仅会为 SDS 分配所需空间，还会为 SDS 分配额外的未使用空间
• 惰性空间释放
  用于优化 SDS 的字符串缩短操作：当需要缩短 SDS 所保存的字符串时，程序不使用内存重分配来回收缩短后多出来的字节，而是用 free 属性将这些字节的数量记录起来
  于此同时，SDS 也提供了相应 API，可以在有需要时，真正释放 SDS 的未使用空间，所以该策略不会造成内存浪费

4、二进制安全

C 字符串中的字符必须符合某种编码，并且除了字符串末尾外，字符串内不能包含空字符，否则最先被程序读入的空字符将被误认为时字符串末尾。这些限制使得 C 字符串只能保存文本数据，而不能保存图片、音频这样的二进制数据

SDS API 都是二进制安全的，所有 SDS API 都会以处理二进制的方式来处理 buf 数组中的数据，程序不会对其中的数据做任何限制、过滤，数据在写入时时什么样的，被读取时就是什么样的。这也是将 SDS 的 buf 属性称为字节数组的原因