动态字符串 SDS

一、C 语言 char* 字符串的不足

C 语言的 char* 会在 \0 处表示字符串结束，如果数据在本身就有 \0，那么数据会被截断。不符合 redis 保存任意二进制数据的需求。
使用 \0 作为字符串的结束字符。也会操作字符串的函数的复杂度增加。比如 strcat 字符串追加函数，需要遍历源字符串才能完成追加。操作函数的复杂度一旦增加，就会影响字符串的操作效率。

二、SDS 结构设计

struct __attribute__ ((__packed__)) sdshdr64 {
		// 字符数组现有长度
    uint64_t len;
    // 字符数组的分配空间长度
    uint64_t alloc;
    // SDS 类型
    unsigned char flags;
    // 字符数组
    char buf[];
};

因为 SDS 结构中记录了字符数组已占用的空间和被分配的空间，这就可以带来效率上提升。

SDS 通过记录字符数组的使用长度和分配空间大小，避免了对字符串的遍历操作，降低了操作开销，比如在创建、追加、复制、比较等场景

三、紧凑型字符串结构设计

SDS 结构中有一个元数据 flags，表示的是 SDS 类型。一共有 5 种类型，分别是：sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64 。如上 sdshdr64 结构，len 和 alloc 都是 uint64_t 类型，可以保存的字符数组长度为 (2^64 - 1)。

这样的设计可以节省内存，可以灵活的保存不同大小的字符串。举个反例：假如我们要保存的字符串是 10 字节，此时 len 和 alloc 如果使用 uint64_t 类型，占用 16 字节，比保存的数据都多，那就得不偿失了。

而且结构体使用 __attribute__ ((__packed__)) 修饰，就是告诉编译器，不要进行字节对齐，采用紧凑的方式分配内存。

四、SDS 的空间分配算法

当 SDS 需要进行空间扩展时，不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使用空间。

空间预分配：SDS 扩容，会多申请一些内存（小于 1MB 翻倍扩容，大于 1MB 按 1MB 扩容）。可以减少执行字符串增长操作所需的内存重分配次数
多余内存不释放：SDS 缩容，不会立即释放多余的内存，这样，SDS 避免了缩短字符串时所需的内存重分配操作，并未将来可能有的增长操作提供了优化。

四、SDS 的优势

操作效率高，获取长度无需遍历，时间复杂度为 O(1)
二进制安全，因为单独记录字符串长度，所以可以存储 \0 的数据
兼容一部分 C 字符串函数
杜绝了缓冲区溢出。当 SDS API 需要对 SDS 进行修改时，内部会检查 SDS 的空间是否满足修改所需的要求，如果不满足，SDS 会自动扩容。而 C 字符串操作函数 strcat 可能会由于空间不足而造成缓冲区溢出。
减少修改字符串时所带来的内存重分配次数，提高了效率