简单动态字符串(simple dynamic string,SDS)

1. 简单动态字符串

Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串）。

Redis 构建了一种名为简单动态字符串（simple dynamic string,SDS）的抽象类型，并将其作为Redis的默认字符串表示。

SDS定义:

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

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

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

SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性中，空字符额外占1字节空间，添加空字符到字符串末尾等操作，都是由SDS函数自动完成。

2. SDS 与 C 字符串区别

2.1 获取字符串长度的复杂度

在C语言中，其字符串并不记录自身的长度信息，获取一个C字符串长度需要遍历整串，复杂度为O(N) 。

SDS的len属性中直接就记录了其本身的长度，故获取其长度的复杂度为O(1)。

在Redis中，通过使用SDS将获取字符串长度的复杂度从O(N)降到O(1)，这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。例如，Redis 的字符串键在底层上也是通过SDS实现的，即使对一个非常长的字符串键反复执行STRLEN命令，也不会影响 Redis 性能。

2.2 杜绝缓冲区溢出

因为C字符串不记录自身长度，当一个字符串str2拼接到字符串str1时，很可能因为str1自身空间分配不足造成缓冲区溢出。

SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS的API需要对其进行修改时，API会先检查其空间是否满足修改需求，若不满足，则API会自动将SDS的空间扩展到执行修改所需的大小，然后采取执行真正的修改操作。

举个例子，<string.h>/strcat 是一个具有拼接字符串功能的函数，现有字符串str1保存了一个字符串"Redis"，字符串str2保存了"SpringBoot"，且它俩在内存中的位置是相邻的。

当执行 strcat(str1," Mysql"); 操作时，str1并没有足够的空间，那么 strcat 函数执行后，str1的数据将会溢出到str2所在空间，str2之前所保存的内容会被修改。

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

C字符串并不记录自身长度，其每次增长或缩短，程序都总要对保存这个C字符串的数组进行一次内存重新分配操作，而这通常是耗时操作。

SDS通过未使用空间(free)解除了字符串长度和底层数组长度之间的关联，且通过未使用空间，实现了空间预分配和惰性空间释放两种优化策略。

空间预分配： 空间预分配用于优化SDS的字符串增长操作，当SDS进行空间扩展时，程序不仅会为其分配修改所必须的空间，还会为其分配额外未使用的空间。

• • 如果对SDS进行修改后，SDS的长度（也即是len属性的值）将小于1MB，那么程序将分配和len 属性同样大小的未使用空间。

• • 如果对SDS进行修改后，SDS的长度将大于等于1MB，那么程序将分配1MB的未使用空间。

惰性空间释放： 惰性空间释放用于优化SDS的字符串缩短操作：当SDS进行空间收缩时，程序不会立即使用空间分配来回收缩短后多出来的字节，而是使用free属性将这些字节数量记录起来，并等待将来使用

SDS也提供了相应的API，在有需要时可以真正的释放SDS未使用的空间，所以不用担心惰性空间释放策略会造成内存浪费。

2.4 二进制安全

C字符串中不能包含空格，否则最先被程序读入的空字符将被误认为是字符串结尾，使得C字符串只能保存文本数据，而不能保存如图片、音频、视频等二进制数据。

SDS的API会以处理二进制的方式处理存放在buf数组中的数据，程序不会对其中的数据做任何的限制、过滤，数据在写入时是什么样的，它被读取时就是什么样。

2.5 对比总结

参考：[1]黄健宏. Redis设计与实现[M]. 机械工业出版社, 2014.