Redis 5分钟掌握简单动态字符串SDS（一）

Redis 没有直接使用 C 语言传统的字符串表示（而是以空字符结尾的字符数组，以下简称 C 字符串），自己构建了一种名为简单动态字符串（simple dynamic string，SDS） 的抽象类型，并将 SDS 用作 Redis 的默认字符串表示。

在 Redis 里面，C 字符串只会作为字符串字面量（string literal），用在一些无须对字符串值进行修改的地方，比如打印日志： redisLog(REDIS_WARNING,"Redis is now ready to exit, bye bye...");

当 Redis 需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis 就会使用 SDS 来表示字符串值：比如在 Redis 的数据库里面，包含字符串的键值对在底层都是由 SDS 实现的。

举个例子，如果客户端执行命令：

redis> SET msg "hello world"
OK

那么 Redis 将在数据库中创建了一个新的键值对，其中：

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

又比如说，如果客户端执行命令：

redis> RPUSH fruits "apple" "banana" "cherry"
(integer) 3

那么 Redis 将在数据库中创建一个新的键值对，其中：

• 键值对的键是一个字符串对象，对象的底层实现是一个保存了字符串 "fruits" 的 SDS 。
• 键值对的值是一个列表对象，列表对象包含了三个字符串对象，这三个字符串对象分别由三个 SDS 实现：第一个 SDS 保存着字符串 "apple" ，第二个 SDS 保存着字符串 "banana" ，第三个 SDS 保存着字符串 "cherry" 。

除了用来保存数据库中的字符串值之外，SDS 还被用作缓冲区（buffer）：AOF 模块中的 AOF 缓冲区，以及客户端状态中的输入缓冲区，都是由 SDS 实现的，在之后介绍 AOF 持久化和客户端状态的时候，我们会看到 SDS 在这两个模块中的应用。

AOF中记录的是每一个命令的详细信息，包括完整的命令类型、参数等。只要产生写命令，就会实时写入到AOF文件中

SDS的定义

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

与C字符串的区别

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

获取字符串长度

因为 C 字符串并不记录自身的长度信息，所以为了获取一个 C 字符串的长度，程序必须遍历整个字符串
$O(N)$ 。和 C 字符串不同，因为 SDS 在 len 属性中记录了 SDS 本身的长度，所以获取一个 SDS 长度的复杂度仅为
$O(1)$ 。

杜绝缓冲区溢出

C 字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow）。
假设程序里有两个在内存中紧邻着的 C 字符串 s1 和 s2 ，其中 s1 保存了字符串 “Redis” ，而 s2 则保存了字符串 “MongoDB” . 如果一个程序员决定通过执行：strcat(s1, "Cluster")将 s1 的内容修改为 “Redis Cluster” ，但粗心的他却忘了在执行 strcat 之前为 s1 分配足够的空间，那么在 strcat 函数执行之后，s1 的数据将溢出到 s2 所在的空间中，导致 s2 保存的内容被意外地修改。 SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出问题。

减少内存分配次数

因为 C 字符串的长度和底层数组的长度之间存在着这种关联性，所以每次增长或者缩短一个 C 字符串，程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作，在 SDS 中，数组里面可以包含未使用的字节，而这些字节的数量就由 SDS 的 free 属性记录。并实现了两种优化策略：

1. 空间预分配，当进行字符串增长操作时，程序会额外分配空间，并记录的free字段
   

   比如原长度为8的字符串,新增5个长度后,总共为13长度,则预分配13+13+1=27字节(额外一字节用于保存空字符串)
   对于大于1M来说,分配空间为原有总长度+1MB+1byte
   比如增加完字符串后长度为15MB,则为15MB+1MB+1byte

2. 惰性空间释放，当进行字符串缩短操作时，程序不立即重新分配内存，而是用free属性将这些字节的数量记录起来。

二进制安全

C字符串中不能包含空字符串，否则会被误认为是字符串结尾。所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设 ——数据在写入时是什么样的，它被读取时就是什么样。