开场白
作为redis的使用者，我们最常用的操作可能就是set了，而最常用的数据结构则是string了，我们常常会使用命令:
127.0.0.1:6379> set key value
这个命令中，key和value都被保存到一个字符串中。需要注意的是，这个字符串并非C语言的字符串结构，而是redis自己实现的一个名为sds的数据结构
SDS的定义
我们翻到redis3.0的源码，找到src/sds.h,先看看这个sds的结构体定义：
/*
* 保存字符串对象的结构
*/
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
- 字段
free：表示可分配的空间的字节长度 - 字段
len：表示已占用空间的字节长度 - 字段
buf：表示装载实际字符串的字符数组
举一个最简单的例子，比如Redis这个字符串，在sds的保存则是这样的：
image.png
为什么要在后面加上这个\0呢？这么设计的目标是为了遵循C语言字符结尾的惯例，同时能够兼容一部分C语言字符串操作库函数，比如strlen。同时这个\0是不会记录进去len字段的。
使用SDS的好处
1.有效提升处理长字符串的性能
C语言的字符串类型，计算长度是必须要遍历字符的，也就是如果长度为5的字符串，那么计算长度必须要遍历五次才能得出结果，计算复杂度是O(N)。如果使用了sds的话，可以在分配字符串的时候就直接把长度记录在len字段，那么这个计算复杂度将会是O(1)，这么做能够解决redis处理大型字符串长度的性能瓶颈问题。
2.防止缓冲区溢出，优化内存分配
普通的C语言字符串会存在缓冲区溢出的问题，举个最简单的例子，如字符串s1是redis，字符串s2是mongodb，并假设他们在内存中是紧紧相邻的。假如一个粗心的程序员没有为s1去分配更多空间的前提下就调用了strcat进行了字符串拼接，如strcat(s1, "cluster")，那么这个s1就会溢出并且可能擦写s2的内存，就会出现一些很坑爹但又难以发现的bug了。但是使用sds就能规避这个问题，比如src/sds.c文件中有一个函数叫sdscat,我们看一下代码
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
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;
}
// 着重看这个函数
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;
}
我们着重看看sdsMakeRoomFor函数，它展示了redis的sds是如何分配内存的，还是举个栗子：我们有字符串s1="redis"，我们调用sdscat(s1, "cluster")，那么s1会变为redis cluster，因为原来的s1的len字段只有5字节，因此连接cluster需要进行内存扩展操作，可以从代码看到，如果s1的free的长度大于等于cluster的长度，那么会把free这部分让出来进行分配给cluster字符串，但如果不够长又会产生两种分配策略：
- 如果连接后新的字符串的长度尚未超过宏定义
SDS_MAX_PREALLOC(默认是1MB)，那么会分配两倍于新字符串的长度。比如连接后的字符串s1是redis cluster，长度即是13，那么会多分配出13个字节，并把长度保存在free字段，那么最终扩容后buf的空间就是13 + 13 + 1 = 27个字节。 - 如果连接后的字符串长度超过宏定义
SDS_MAX_PREALLOC（默认是1MB），那么会比新字符串长度分配多SDS_MAX_PREALLOC（默认是1MB）的内存。比如连接后的字符串s1长度是10MB，那么buf扩容分配后的空间就是30MB + 1MB + 1Byte。
除此之外，redis的sds api也有惰性释放的机制。假如一个字符串需要被裁减，比如redis cluster变为redis，sds的api不会马上把cluster这7个字节空间马上释放掉，而是会继续保留，并记录在free字段中，也就是free=7，这么做是为了日后如果redis这个字符串要增长的时候就不用去重新分配内存了。当然，如果你真的觉得这部分空间用不着了，也可以通过sdsRemoveFreeSpace这个函数去释放掉这部分free的空间。
3.保证二进制安全
C语言字符串必须符合某种编码，并且除了字符串末尾之外，字符串里面不能包含空字符串，否则会认为是结尾了，因此也导致C语言字符串没办法保存、图片、视频、压缩文件等二进制数据。
redis的sds使用了字符数组作为字符串的保存结构的好处就显现出来了，正因为是字符数组，那么可以用来保存任何的二进制数据，并且保证读入数据是什么，读出的数据就是什么。
以上就是redis简单动态字符串的特点和优势的总结，后面会继续redis的其他数据结构，敬请期待！
文章参考自：<<Redis设计与实现>> 第二版
网友评论