SDS原理
总体概述：是Redis中可变字符串的数据结构，所有可变的字符串都使用此数据结构。除了被用作字符串，还被用作缓冲区。
数据结构
len标记已占用长度，free标记剩余长度，buf[]是char数组。
‘\0'不算在长度中，遵循’\0'结尾的好处是可以重用C函数库的函数。如printf等。
SDS记录长度的好处
- SDS获得字符长度的时间是O(1)
- SDS可以防止字符串溢出，意外修改其它区域的数据。
- 使用len记录长度，不用依靠’\0'判断结尾，所以可以保存二进制数据
SDS内存分配策略
对SDS中的字符串进行修改导致字符串长度改变的时候，需要进行内存重分配。
由于内存分配耗时，很可能成为高频修改时的一个性能瓶颈。所以会进行空间预分配和惰性空间释放。
空间预分配公式
- 如果len在修改后小于1MB，分配和len一样多的free空间。
- 如果大于1MB，分配1MB的未使用空间。
惰性空间释放
在长度缩短的时候SDS不会主动释放free的空间，在有必要的时候才真正释放。
二进制安全
C字符串处理二进制数据可能会因为’\0'的原因提前结束。SDS以处理二进制的方式来处理buf数组的数据，不会作任何过滤。
所以SDS本质上是保存一系列二进制数据，因此SDS也能作为缓冲区的实现。保存字符只是通过保存二进制实现的功能。
代码解读
Redis中SDS的创建：
/*
* 根据给定的初始化字符串 init 和字符串长度 initlen
* 创建一个新的 sds
*
* 参数
* init ：初始化字符串指针
* initlen ：初始化字符串的长度
*
* 返回值
* sds ：创建成功返回 sdshdr 相对应的 sds
* 创建失败返回 NULL
*
* 复杂度
* T = O(N)
*/
/* Create a new sds string with the content specified by the 'init' pointer
* and 'initlen'.
* If NULL is used for 'init' the string is initialized with zero bytes.
*
* The string is always null-termined (all the sds strings are, always) so
* even if you create an sds string with:
*
* mystring = sdsnewlen("abc",3");
*
* You can print the string with printf() as there is an implicit \0 at the
* end of the string. However the string is binary safe and can contain
* \0 characters in the middle, as the length is stored in the sds header. */
sds sdsnewlen(const void *init, size_t initlen) {
struct sdshdr *sh;
// 根据是否有初始化内容，选择适当的内存分配方式
// T = O(N)
if (init) {
// zmalloc 不初始化所分配的内存
sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
} else {
// zcalloc 将分配的内存全部初始化为 0
sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
}
// 内存分配失败，返回
if (sh == NULL) return NULL;
// 设置初始化长度
sh->len = initlen;
// 新 sds 不预留任何空间
sh->free = 0;
// 如果有指定初始化内容，将它们复制到 sdshdr 的 buf 中
// T = O(N)
if (initlen && init)
memcpy(sh->buf, init, initlen);
// 以 \0 结尾
sh->buf[initlen] = '\0';
// 返回 buf 部分，而不是整个 sdshdr
return (char*)sh->buf;
}
其他诸如创建空SDS都是使用这个接口进行的封装，而其中sdsMakeRoomFor方法则体现了Redis对free空间分配的逻辑：
/* 对 sds 中 buf 的长度进行扩展，确保在函数执行之后，
* buf 至少会有 addlen + 1 长度的空余空间
* （额外的 1 字节是为 \0 准备的）
*
* 返回值
* sds ：扩展成功返回扩展后的 sds
* 扩展失败返回 NULL
*
* 复杂度
* T = O(N)
*/
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
// 获取 s 目前的空余空间长度
size_t free = sdsavail(s);
size_t len, newlen;
// s 目前的空余空间已经足够，无须再进行扩展，直接返回
if (free >= addlen) return s;
// 获取 s 目前已占用空间的长度
len = sdslen(s);
sh = (void*) (s-(sizeof(struct sdshdr)));
// s 最少需要的长度
newlen = (len+addlen);
// 根据新长度，为 s 分配新空间所需的大小
if (newlen < SDS_MAX_PREALLOC)
// 如果新长度小于 SDS_MAX_PREALLOC
// 那么为它分配两倍于所需长度的空间
newlen *= 2;
else
// 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
newlen += SDS_MAX_PREALLOC;
// T = O(N)
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
// 内存不足，分配失败，返回
if (newsh == NULL) return NULL;
// 更新 sds 的空余长度
newsh->free = newlen - len;
// 返回 sds
return newsh->buf;
}
