Redis支持多种数据类型的存储，其中一个是字符串。但是在C语言中，字符串只能使用char数组/指针表示，长度定长，且操作字符串的函数不丰富，效率也不高，不能满足Redis的需要。
因此Redis定义了SDS（Simple Dynamic String）来存储字符串，并提供丰富的函数处理SDS。
SDS定义和实现在文件sds.h和sds.c中。
1. SDS定义
SDS定义在sds.h中，不同于C语言，Redis有多种SDS的定义：
sdshdr5：长度用5位存的字符串sdshdr8：长度用8位存的字符串sdshdr16, sdshdr32, sdshdr64：意义同上
首先定义sds，就是char *：
typedef char *sds;
sdshdr5的定义如下：
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /*前5位存len，后三位存type,可用sds[-1]访问*/
char buf[]; /*字符串*/
};
其他四个定义类似，只是长度和占用的数据类型有变化，这里以sdshdr8为例：
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 字符串长度(不含0终止符) */
uint8_t alloc; /* 申请的字符串内存长度(不含header和0终止符) */
unsigned char flags; /*后三位存type,前5位未使用,可用sds[-1]访问*/
char buf[]; /*字符串*/
};
__attribute__ ((__packed__))：告诉编译器取消结构在编译过程中的优化对齐，按照实际占用字节数进行对齐。
2. SDS和C字符串的区别
2.1. 以$O(1)$获取字符串长度
对于C字符串，可调用strlen(char*)进行字符串长度获取，它需要扫描到\0才能得到结果，时间复杂度是$O(n)$。
而对于SDS，只需调用sdslen(const sds s)（将char*转成struct sdshdr##T*），读取字段len即可，时间复杂度是$O(1)$。
2.2. 防止溢出
C语言string.h中定义的字符串操作函数，往往都没有对数组界限进行检查，因此很容易造成溢出的问题。
以字符串拼接为例：
-
C语言使用
strcat(char *dst, const char *src)，若dst未分配足够空间，拼接src时容易造成越界，从而导致内存被非法修改，造成不可预计的后果 -
SDS使用
sdscat(sds s, const sds t)：它会分配足够的空间（如何分配之后回收），避免了内存溢出的危险sds sdscatsds(sds s, const sds t) { return sdscatlen(s, t, sdslen(t)); } sds sdscatlen(sds s, const void *t, size_t len) { size_t curlen = sdslen(s); // 分配足够空间 s = sdsMakeRoomFor(s,len); if (s == NULL) return NULL; // 拷贝/拼接 memcpy(s+curlen, t, len); // 重新设置长度 sdssetlen(s, curlen+len); s[curlen+len] = '\0'; return s; }
2.3. 减少修改字符串带来的内存重分配次数
C的字符串永远是$n+1$长度的数组，所以每次增长或缩短字符串的时候，都需要重分配内存，并执行拷贝，原串也得在不用的时候释放。
而在SDS中有多种优化方案减少内存分配的次数：
- 空间预分配
- 懒惰空间释放
a) 空间预分配
这里主要应用于增长字符串的操作，这里以sdscat(sds s, const char *t)为例，主要的预分配流程在函数sdsMakeRoomFor(sds s, size_t addlen)中：
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
// 1. 获取可用空间
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s;
// 2. 获取当前占用空间
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
// 3. 计算新空间
newlen = (len+addlen);
// 4. 计算新空间，即新的alloc值
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
// 这里忽略，就是扩容时检查sds的类型，若没变则realloc，否则alloc & copy & free
// 5. 设置alloc值
sdssetalloc(s, newlen);
return s;
}
可见，这里扩容的公式是：
- 当新串长度小于
SDS_MAX_PREALLOC（即1MB），则扩充到新串长度的2倍 - 否则在新串长度的基础上，再扩充
SDS_MAX_PREALLOC长度（即1MB）
这样，增长字符串$n$次，扩容的次数最多只有$n$次（而原来至少有$n$次）
b) 懒惰空间释放
这边以字符串缩短函数为例，即sdstrim(sds s, const char *cset)：
// 删除左右两边的字符，字符包含在cset中
sds sdstrim(sds s, const char *cset) {
char *start, *end, *sp, *ep;
size_t len;
sp = start = s;
ep = end = s+sdslen(s)-1;
while(sp <= end && strchr(cset, *sp)) sp++;
while(ep > sp && strchr(cset, *ep)) ep--;
len = (sp > ep) ? 0 : ((ep-sp)+1);
if (s != sp) memmove(s, sp, len);
s[len] = '\0';
sdssetlen(s,len);
return s;
}
可见，这里只对新串执行了移动操作，没有做任何的释放内存的操作。未来要添加内容时，可以减少扩容的概率。
当然SDS也提供了sdsRemoveFreeSpace(sds s) 函数，用于释放空闲空间（type不变时调用realloc，否则还是会有alloc + copy + free）
2.4. 二进制安全
C中的字符串必须以\0结尾，且符合一定的编码。
而SDS可以保存任何二进制数据。
SDS API以二进制方式保存数据，写进去的是什么，读出来的就是什么，因此可以存储特殊格式的数据。
2.5. 兼容C字符串函数
SDS中存储的buf字段存储的就是字符串（不考虑其他数据格式），因此可直接将它作为<string.h>定义的字符串函数的参数。
取这个字符串指针很简单：
- 若直接是
sds类型，直接传入即可（sds就是char*） - 若是
sdshdr##T，直接取buf字段即可
