Redis为什么要自己实现SDS

Redis 为什么要自己实现一个 SDS？

原因一：SDS 获取字符串长度的时间复杂度比用 C 语言的字符数组实现的字符串要快

用 C 的字符数组实现的字符串在获取字符串长度时需要遍历整个字符数组，然后把每个字符进行计数，直到遇到空字符（'\0' ） 才停止计数得出字符串的长度，这样的时间复杂度为 O(N)

而 SDS 在 len 属性中记录了字符串的长度，所以获取字符串的长度就相当于获取 len 的值，时间复杂度为 O(1)

原因二：用 C 语言字符数组实现的字符串容易造成缓冲区溢出

string.h 库的 strcat 函数将 src 字符串中的类容拼接到 dest 字符串的末尾

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

因为用 C 语言的字符数组实现的字符串不记录自身的长度，所以假定用户在执行 strcat 函数时，已经为 dest 分配足够多的内存空间，则可以容纳 src 字符串的所有内容，而一旦这个假设不成立，就会产生内存溢出

举个例子， 假设程序里有两个在内存中紧邻着的 C 字符串 s1 和 s2 ， 其中 s1 保存了字符串 "Redis" ， 而 s2 则保存了字符串 "MongoDB" ， 如下图

在这种情况下如果执行如下代码

strcat(s1," Cluster");

在 s1 后面追加 " Cluster" ，但是s1的原有的空间不足，也未为 s1 重新分配足够的空间导致在执行 strcat 函数后 s1 的数据直接溢出到 s2 所在的内存空间中，最终导致 s2 的内容意外地被篡改，结果如下图

而 SDS 和 C 语言实现的字符串不同，SDS API 对 SDS 进行修改时 API 会先检查 SDS 的空间是不是满足修改所需的要求，如果不满足，API 会自动将 SDS 的空间扩展到执行修改所需要的空间大小，然后再执行修改操作，所以使用 SDS 不需要手动修改 SDS 的空间大小也不会出现和 C 语言字符串那样的缓冲区溢出的问题

举个例子， SDS 的 API 里面也有一个用于执行拼接操作的 sdscat 函数， 它可以将一个 C 字符串拼接到给定 SDS 所保存的字符串的后面， 但是在执行拼接操作之前， sdscat 会先检查给定 SDS 的空间是否足够， 如果不够的话， sdscat 就会先扩展 SDS 的空间， 然后才执行拼接操作

比如说， 如果我们执行

sdscat(s, " Cluster");

SDS 的 s 的结构如下图

sdscat在执行拼接操作前会检查 s 的内存空间长度是否足够拼接 " Cluster" ，在发现 s 的空间长度不足够拼接 " Cluster" 后，会先扩展 s 的内存空间，然后再执行拼接操作，拼接后的 s 如下图

并且 sdscat 这个函数不仅对这个 SDS 进行了拼接操作，还对 SDS 分配了 13 字节的未使用空间，并且拼接之后的字符串也正好是 13 个字节，这种现象和 SDS 的空间分配策略有关

原因三：减少修改字符串时带来的内存重新分配次数

因为用 C 语言实现的字符串不记录自身的长度，所以对于一个包含 N 个字符的 C 语言字符串来说，这个 C 语言字符串的底层实现总是一个 N+1 长度的字符数组 （额外的一个字符用于保存空字符 '\0')，因为 C 字符串和底层字符数组的这种关联性，所以每次缩短和增加字符串 C 语言实现的字符串时需要对实现 C 语言字符串的底层字符数组重新进行一次内存分配

• 如果程序执行的是增长字符串的操作，那么在执行该操作之前需要先重新进行一次内存分配来扩展底层的字符数组，如果忘了会导致缓冲区溢出

• 如果程序执行的是缩短字符串的操作，那么在执行该操作之后需要重新进行一次内存分配释放那些不再使用的那部分空间，如果忘了会导致内存泄漏

举个例子，如果要将一个值为 "Redis" 的 C 字符串 s 改为 "Redis Cluster"，在执行

strcat(s," Cluster");

之前，我们需要先使用内存分配操作，扩展 s 空间

因为内存重新分配算法涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作，在一般程序中，如果修改字符串长度的情况不太常出现，那么每次修改都执行一次内存重新分配是可以接受的，但是 Redis 作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串的长度都需要执行一次内存重新分配的话，那么光是执行的内存重新分配的时间就占去修改字符串所有时间的一部分，如果这种修改频繁的发生的话，可能会影响性能，所以 Redis 为了避免 C 字符串的这种缺陷，SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联，在 SDS 中，buf 数组的长度不一定是字符数量加一，数组中包含了未使用的字节，而这些未使用字节的数量就由 SDS 的 free 属性记录

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

空间预分配

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

分配额外空间会根 z 据不同的的情况选择不同的策略，分配策略如下：

• 如果对 SDS 进行修改之后，SDS 中 len 属性的值小于 1 MB，这时程序会为 SDS 分配和 len 属性值一样大小的未使用空间，这时 len 的值和 free 的值是一样的，举个例子，SDS 进行扩展后， SDS 的 len 属性值为 13 ，那么程序会为 SDS 分配和 len 属性值一样大小的 13 个字节的未使用空间 ，最终 free 的值为 13 ，SDS 的 buf 数组的长度大小变为 27 byte(13+13+1=27,额外的自字节用于保存空字符)

• 如果对 SDS 进行修改之后，SDS 的 len 属性的值大于等于 1 MB，这是程序会为 SDS 分配 1 MB 的未使用空间，举个例子，SDS 进行修改后，SDS 的 len 的值为30MB，那么程序会为 SDS 分配1 MB 的未使用空间，最终 free 的值为 1 MB ，SDS 的 buf 数组的长度大小变为 30MB + 1 MB + 1 byte

sdscat(s," Cluster");

在执行 sdscat 进行拼接之前需要检查 s 的长度是否足够，发现 s 的长度不够拼接 " Cluster"，sdscat 就会先扩展 s 的空间，然后才执行拼接 " Cluster"的操作

拼接前的 SDS 结构如下图

拼接后的 SDS 的结构如下

如果这时在对 s 进行如下操作

sdscat(s," Tutorial");

那么这次 sdscat 执行的时候 就不需要重新分配内存，因为未使用空间里面的 13 个字节可以保存 9 个字节的 " Tutorial" ,函数执行完后的 SDS 的结构图如下

在扩展 SDS 前会先检查 SDS 的 未使用空间是否已经足够扩展所需要的空间，如果未使用空间足够就直接使用未使用空间，而无需执行内存重新分配的操作，通过这种分配策略，SDS 将连续增长 N 次字符串所需的内存重新分配次数必定为 N 次减低为最多为 N 次

惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作，当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重新分配来回收缩减多出来字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用

举个例子，sdstrim 函数接受一个 SDS 和一个 C 字符串作为参数，从 SDS 左右两端分别移除所有在 C 字符串中出现过的字符串

如下面对 SDS 值 s 执行 sdstrim

sdstrim(s,"XY"); // 移除 SDS 字符串中的所有 'X' 和 'Y'

执行字符串缩减前的 SDS 如下

执行 sdstrim 对 SDS 值 s 进行缩减后的结构图如下

注意执行 sdstrim 之后的 SDS 并没有释放多出来的 8 个字节的空间，而是将这 8 个字节空间作为未使用的空间保留在 SDS 中，如果将要对 SDS 进行增长操作的话，这些未使用空间就可能派上用场

举个例子，对上面执行完 sdstrim 操作后的 s 执行 sdscat 操作增长操作

sdscat(s," Redis");

那么完成这次 sdscat 操作将不需要执行内存分配因为 SDS 里面预留的 8 个字节的空间已经足以拼接 6 个字节的 " Redis" ，拼接后的结构图如下

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

与此同时，SDS 也提供了相应的 API ,让我们可以在需要的时候，真正的释放 SDS 里面的未使用空间，所以不需要担心惰性空间策略造成的内存浪费

原因四：二进制安全

C 语言字符串中的字符必须符合某种编码（比如 ASCII）,并且出了字符串的末尾之外，字符串的其他地方不能包含空字符（'\0' ），否者最先被程序读入的空字符串会被误认为字符串的结尾，这样导致了 C 语言字符串自能保存文本，不能保存图片、音频、视频、压缩文件这样的二进制数据

举个例子，如果有一个使用空字符分割多个单词的特殊数据格式，结构如下图，那么这种格式就不适合用 C 字符串保存，因为 C 字符串的函数只能识别出空字符（'\0' ）前面的 Redis 而它后面的 "Cluster"

虽然数据库一般保存的是文本数据，但是使用数据库保存二进制数据的场景也不少见，因此，为了确保 Redis 可以适用于各种不同的使用场景，SDS 的 API 都是二进制安全的：所有的 SDS API 都会处理二进制的方式处理 SDS 存在 buf 数组中的数据，数据写入的时候是上面样的，它读出来就是上面样的

这就是我们为什么将 SDS 的 buf 属性称为字节数组的原因，因为 Redis 不用这个数组保存字符，而是用来保存一系列的二进制数据

所以使用 SDS 保存上面提到的特殊格式的字符串是没有任何问题，因为 SDS 时使用 len 属性来判断字符串是否结束的，如下图

通过使用二进制安全的 SDS ，而不是 C 字符串，使得 SDS 不仅可以保存文本数据，还可以保存任意格式的二进制数据

原因五：兼容部分 C 语言字符串函数

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

举个例子，如上图所示，如果我们有一个保存文本数据的 SDS 值的 sds，那么我们有可以重用 <string.h>/strcasecmp 函数，使用它来对比 SDS 保存字符串和另一个 C 字符串

strcasecmp(sds->buf,"Hello World");

这样 Redis 就是不用专门编写一个用来对比 SDS 值和 C 字符串值的函数

类似的我们可以将一个保存了数据的 SDS 作为 strcat 函数的第二个参数，将 SDS 保存的字符串追加到一个 C 字符串的后面

strcat(c_string,sds->buf);

这样 Redis 就不用专门去写一个函数来将 SDS 保存的字符串追加到 C 字符串后面

通过遵循 C 字符串以空字符结尾的惯例， SDS 可以在有需要时重用 `` 函数库， 从而避免了不必要的代码重复

总结

C 语言字符串	SDS
获取字符串长度的时间复杂度为 O(N)	获取字符串长度的复杂度为O(1)
API 是不安全的，可能会造成缓冲区溢出	API 是安全的，不会造成缓冲区溢出
修改字符串长度 N 次必然需要执行 N 次内存重新分配	修改字符串 N 次最多需要执行 N 次内存重新分配
只能保存文本数据	可以保存文本或者二进制数据
可以使用所有 <string.h> 库中的函数	可使用部分 <stringh 库中的部分函数