Redis源码阅读笔记之字符串
在redis中，字符串（String）是由一个结构体SDS（Simple Dynamic String）组成，不仅字符串使用SDS，它也可以用于缓冲区：AOF模块中的AOF缓冲区以及客户端状态中的输入缓冲区都是由SDS组成的。其结构图如下：
其源码如下所示：
/*
* 类型别名，用于指向 sdshdr 的 buf 属性
*/
typedef char *sds;
/*
* 保存字符串对象的结构
*/
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
/*
* 返回 sds 实际保存的字符串的长度
*
* T = O(1)
*/
static inline size_t sdslen(const sds s) {
//sdshdr的大小等于len+free+buf=4+4+buf,而buf=len+free+1('\0'C语言字符串结束符)
//一个SDS结构体的大小等于SDS=buf+size(free)+size(len)=buf+8=len+free+9（刚开始没有创建字符串时len=0,free=0）
//减去结构体本身的大小剩下的为实际保存的字符串的长度
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->len;
}
/*
* 返回 sds 可用空间的长度
*
* T = O(1)
*/
static inline size_t sdsavail(const sds s) {
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->free;
}
C语言获取字符串长度的时间复杂度为O(N)，SDS获取字符串长度的时间复杂度为O(1)。
C语言在字符串拼接的时候有可能会缓冲区溢出，而SDS API会在拼接字符串时先检查是否有可用空间，如果没有会进行分配然后拼接，因此防止了缓冲区溢出。
C语言如果一个字符串要追加内容就需要扩容，重新分配足够的空间，否则会缓冲区溢出；如果要缩短一个字符串，必须释放空闲的空间，即也要进行空间重新分配，否则就会内存泄漏。
而空间内存的重新分配涉及到复杂的内存处理算法，如果这样频繁的进行操作对于性能的影响十分大，况且redis进行高效的读写，修改频繁，因此，redis防止重新内存频繁分配，使用了空间预分配和惰性分配策略。
空间预分配
对于频繁的字符串追加内容的操作，redis使用空间预分配策略，有以下两种情况：
1.如果修改后的字符串小于SDS_MAX_PREALLOC（1MB），则将分配len（使用空间的大小）大小的空间给free作为未使用的空间进行预分配。最终的SDS的大小为2*len+1（字符串以'\0'结尾）。
// 根据新长度，为 s 分配新空间所需的大小
if (newlen < SDS_MAX_PREALLOC)
// 如果新长度小于 SDS_MAX_PREALLOC
// 那么为它分配两倍于所需长度的空间
newlen *= 2;
2.如果修改后的字符串大小大于SDS_MAX_PREALLOC（1MB），则分配1MB的空间给free进行预分配，即最终返回的SDS大小为len+1MB+1。
else
// 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
newlen += SDS_MAX_PREALLOC;
惰性分配
对于字符串缩减的操作，为了避免重复的回收空间，redis在对字符串进行缩减操作之后会利用free来保存释放的空间大小，而不是去回收它，为下一次字符串追加操作做空间的预分配。SDS API也提供了相应的API在我们真正需要回收内存时对内存进行释放，因此不必担心会空间浪费。
源码如下所示：
/*
* 对 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;
}
/*
* 将长度为 len 的字符串 t 追加到 sds 的字符串末尾
*
* 返回值
* sds ：追加成功返回新 sds ，失败返回 NULL
*
* 复杂度
* T = O(N)
*/
/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
* end of the specified sds string 's'.
*
* After the call, the passed sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
struct sdshdr *sh;
// 原有字符串长度
size_t curlen = sdslen(s);
// 扩展 sds 空间
// T = O(N)
s = sdsMakeRoomFor(s,len);
// 内存不足？直接返回
if (s == NULL) return NULL;
// 复制 t 中的内容到字符串后部
// T = O(N)
sh = (void*) (s-(sizeof(struct sdshdr)));
memcpy(s+curlen, t, len);
// 更新属性
sh->len = curlen+len;
sh->free = sh->free-len;
// 添加新结尾符号
s[curlen+len] = '\0';
// 返回新 sds
return s;
}
在C语言字符串中，遵循ASCII编码格式，即除了末尾的'\0'外，在其他任何地方出现'\0'都会被误认为是字符串的结束符，因此C语言字符串只能存储一些文件数据，对于一些图片，音频等二进制数据不能存储，为了避免这一缺点，redis使用SDS API来保证二进制数据的安全，不会去改变字符串的内容。
可以使用<string.h>库中的部分函数来对字符串进行比较，拼接等操作。
在这些API中，需要注意：
sdsclear函数清空字符串内容时使用的是惰性删除。源码如下：
void sdsclear(sds s) {
// 取出 sdshdr
struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
// 重新计算属性
sh->free += sh->len;
sh->len = 0;
// 将结束符放到最前面（相当于惰性地删除 buf 中的内容）
sh->buf[0] = '\0';
}
sdstrim函数对SDS两端的内容进行修剪
/*
* 对 sds 左右两端进行修剪，清除其中 cset 指定的所有字符
*
* 比如 sdsstrim(xxyyabcyyxy, "xy") 将返回 "abc"
*
* 复杂性：
* T = O(M*N)，M 为 SDS 长度， N 为 cset 长度。
*/
/* Remove the part of the string from left and from right composed just of
* contiguous characters found in 'cset', that is a null terminted 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,"A. :");
* printf("%s\n", s);
*
* Output will be just "Hello World".
*/
sds sdstrim(sds s, const char *cset) {
struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
char *start, *end, *sp, *ep;
size_t len;
// 设置和记录指针
sp = start = s;
ep = end = s+sdslen(s)-1;
// 修剪, T = O(N^2)
//strchr函数用来查找某字符在字符串中首次出现的位置
while(sp <= end && strchr(cset, *sp)) sp++;
while(ep > start && strchr(cset, *ep)) ep--;
// 计算 trim 完毕之后剩余的字符串长度
len = (sp > ep) ? 0 : ((ep-sp)+1);
// 如果有需要，前移字符串内容
// T = O(N)
if (sh->buf != sp) memmove(sh->buf, sp, len);
// 添加终结符
sh->buf[len] = '\0';
// 更新属性
sh->free = sh->free+(sh->len-len);
sh->len = len;
// 返回修剪后的 sds
return s;
}
