一、基本概念
结构体
基本结构如下：
struct sdshdr {
//记录buf数组中已使用字节的数量
//等于SDS所保存字符串的长度
int len;
//记录buf数组中未使用字节的数量
int free;
//字节数组，用于保存字符串
char buf[];
};这种数据结构体的优势：
-
常数复杂度获取字符串长度：SDS 通过单独的 len 字段，将获取字符串内容长度的时间复杂度从 O(N) 降到了 O(1）
-
杜绝缓冲区溢出：原始的 C 语言中，如果出现对字符串进行拼接的操作（如常见的
char *strcat(char *dest,const char *src)），需要提前分配内存空间，否则拼接的内容可能会“溢出”覆盖到临近已经存放有其他内容的缓冲区。相对的，SDS API 如果需要增减字符串的长度，会自动按照特定策略进行内存分配，从根源上杜绝了缓冲区溢出的风险； -
避免了频繁分配（释放）内存操作：SDS 通过每次对内存空间“预分配”，避免了对字符串长度增减时候，每次都操作内存的问题（虽然内存操作理论上都是很快的，但 Redis 为了追求极致的速度和效率，尽量需要减少内存的分配次数）；
-
二进制安全：传统C字符串通过空字符串来识别字符串结尾，SDS 则通过 len 字段来识别，因此 SDS 理论上可以保存包含空字符串的二进制数据（图片、音视频等）；
-
兼容一些C字符串方法：虽然 SDS 对传统C字符串做了改进，但承载的字符串仍然是遵循C字符串以空字符结尾的惯例，这样就保证了 SDS 同样可以直接调用C底层库中的一些字符串操作函数；
空间预分配
对 SDS 字符串执行“增长” X 个字节的操作时候，如果检测到“剩余空间”不足，按照以下算法来分配新的内存空间：
-
如果“增长”后的 SDS 长度小于 1MB（即 SDS->len + X < 1MB），则直接对 SDS 分配和增长后的长度相等的内存空间，即：SDS->free += SDS->len + X
-
如果“增长”后的 SDS 长度大于或等于 1MB，则直接对 SDS 分配1MB的内存，即：SDS->free += 1MB
可以看出，按照这种分配策略，虽然 SDS 可能只需要 X 个字节的空间来存放新增的部分字符串，但 Redis 会直接分配超过需求长度的内存来提供给 SDS 使用，这样做的优点是避免了后续字符串“多次增长”后重复分配的情况，随之带来的缺点是，造成了内存空间的“浪费”（相信根据 Redis 在大规模实践场景的验证，这种算法带来的空间浪费应该足够抵消频繁分配内存导致的开销了）。
惰性释放内存
与字符串增长的情况相对应，如果 SDS 需要执行对字符串长度缩短的操作，SDS 并不会立即回收内存，而是将多出的空间记录到 free 字段。这样做的好处了，避免了字符串缩短后又增长时候再次重新分配内存。这种策略显然也会浪费一些内存空间，但 SDS 同样提供了可以直接释放内存的 API，这就给上层程序根据具体情况来决定是否立即释放内存空间的权利。
二、源码分析
结构体优化
SDS 源码定义在：https://github.com/redis/redis/blob/7.2.4/src/sds.h
可以看出，经过多年的优化迭代，作者对 SDS 的结构做了一些优化改动，SDS 的定义不再是统一通过一个结构体来实现，而是分成了五个结构类似的结构体：sdshdr5、sdshdr8、sdshdr16 和 sdshdr32：
struct __attribute__ ((__packed__)) sdshdr8 {
// 字符串长度，这里类型会根据不同的结构体，采用不同位数的整型
uint8_t len;
// 剩余空间，同样在不同SDS结构体中使用不同整型
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};作者在注释中提到，sdshr5 已经废弃不用，这里不再展开讨论：
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};分析其他几种 SDS 结构体之前，先来考虑这种情况：在64位操作系统中，按照旧的结构体定义，len 和 free 两个字段固定要占用4个字节的空间，最长可以记录的字符串长度为：2^32，在承载的字符串长度比较长的时候没有什么问题，但是如果承载的字符串数组 buf[] 的长度很短，例如只有一个字节长度的字符串，压根就不需要用4个字节来记录字符串长度！
正是基于优化上面这种情况的考虑，最新的 SDS 结构体引入了一个字节长度（8bit）的flags字段，flags 字段的前3个bit（最多可以记录2^3=8种 type）用来标识当前结构体具体是哪种 SDS，每种 Type 对应的 SDS 的 len 字段分别使用不一样长度的 int，上层可以根据需要承载的数据最大长度分情况使用各个SDS，目前使用的 SDS TYPE 有:
# 对应 sdshdr5，已废弃
#define SDS_TYPE_5 0
# 对应 sdshdr8，sds->len 类型为 uint8_t，允许最大承载长度：2^8
#define SDS_TYPE_8 1
# 对应 sdshdr16，sds->len 类型为 uint16_t，允许最大承载长度：2^16
#define SDS_TYPE_16 2
# 对应 sdshdr32，sds->len 类型为 uint32_t，允许最大承载长度：2^32
#define SDS_TYPE_32 3
# 对应 sdshdr64，sds->len 类型为 uint64_t，允许最大承载长度：2^64
#define SDS_TYPE_64 4内存预分配
SDS 内存分配使用方法_sdsMakeRoomFor，源码：https://github.com/redis/redis/blob/7.2.4/src/sds.c#L240
/*
* s 为原始SDS，addlen为需要扩容长度
* greedy参数表示是否使用贪婪算法，这个参数会影响需求长度大于1MB的情况
*/
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
void *sh, *newsh;
// sdsavail: s->alloc - s->len, 获取 SDS 的剩余长度
size_t avail = sdsavail(s);
size_t len, newlen, reqlen;
// 根据 flags 获取 SDS 的类型
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
// 空间足够则无需分配
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
//是否使用贪婪算法，获得实际扩容后的newlen
if (greedy == 1) {
// SDS_MAX_PREALLOC：1MB，新长度小于1MB则直接乘2，否则分配1MB
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
}
// 根据扩容后长度计算出新的 SDS TYPE
type = sdsReqType(newlen);
// TYPE5废弃后，计算出的TYPE5直接使用TYPE8
/* Don't use type 5: the user is appending to the string and type 5 is
* not able to remember empty space, so sdsMakeRoomFor() must be called
* at every appending operation. */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
//计算header部分（结构体中的len、alloc和flags）长度
hdrlen = sdsHdrSize(type);
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
//扩容后TYPE是否变化
if (oldtype==type) {
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
//获取buf总长，这里还不是最终长度，还要根据是否超出最大长度来执行截断操作
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
//最终可以用长度写入到结构体后返回
sdssetalloc(s, usable);
return s;
}其实 Redis 提供了两种不同的分配方法，可以根据上层程序具体需求单独调用：
- 贪婪分配（默认）：每次尽量分配多的内存，避免反复分配
/* Enlarge the free space at the end of the sds string more than needed,
* This is useful to avoid repeated re-allocations when repeatedly appending to the sds. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
return _sdsMakeRoomFor(s, addlen, 1);
}- 保守分配：每次需要多少就分配多少，会引起频繁分配内存的状况
/* Unlike sdsMakeRoomFor(), this one just grows to the necessary size. */
sds sdsMakeRoomForNonGreedy(sds s, size_t addlen) {
return _sdsMakeRoomFor(s, addlen, 0);
}内存惰性释放
以 sdstrim(sds s, const char *cset) 为例，这个函数会删除 SDS 承载字符串中所有出现 cset 指向字符串中的字符，参考源码：https://github.com/redis/redis/blob/7.2.4/src/sds.c#L735
/* Remove the part of the string from left and from right composed just of
* contiguous characters found in 'cset', that is a null terminated C string.
*
* After the call, the modified sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call.
*
* Example:
*
* s = sdsnew("AA...AA.a.aa.aHelloWorld :::");
* s = sdstrim(s,"Aa. :");
* printf("%s\n", s);
*
* Output will be just "HelloWorld".
*/
sds sdstrim(sds s, const char *cset) {
char *end, *sp, *ep;
size_t len;
sp = s;
ep = end = s+sdslen(s)-1;
while(sp <= end && strchr(cset, *sp)) sp++;
while(ep > sp && strchr(cset, *ep)) ep--;
len = (ep-sp)+1;
if (s != sp) memmove(s, sp, len);
s[len] = '\0';
sdssetlen(s,len);
return s;
}可以发现，这个函数在对 SDS 字符串进行裁剪之后，并没释放空出来的部分内存，只是通过 sdssetlen 函数更新了原始 SDS 里面的 len 字段，这样后续如果又出现对这个 SDS 扩容的操作，就可以直接利用这次空出来的空间，并不用再次分配内存了。