已经有了char为何Redis还要重新设计个SDS?
前言
字符串在我们日常开发中十分常见，比如用户的登录账号，姓名，手机号等等都会使用字符串来表示。 而Redis中保存的key都是字符串，value有时也是字符串，可见字符串是Redis中使用最为广泛的一种数据结构。
为什么Redis不用char？
在Java中我们要想定义一个字符串直接new一个String对象就行了，比如下面就定义了一个字符串s1：
String s1 = new String("Hello World");
如果你看过java.lang.String的源码就能知道，String底层是基于char数组来实现的，而C语言中是没有String这种类的，C语言中就是直接使用char[]数组来声明字符串的。
char s[] = "redis"
除了我们看到的redis字符串之外，C语言的编译器还会自动在末尾加入一个字符\0，代表这字符串的结束，如下图所示：
可以看到如果直接使用C语言的char去保存字符串，会存在很多问题，例如：
- 获取字符串的长度需要通过遍历整个字符数组，直到
\0结束，时间复杂度是O(N)，字符串越长，性能就会越差 - 非二进制安全，因为C语言是通过
\0来判断字符串是否结束，那当我们存储的内容中如果本身就包含\0，那么数据就会在\0处被截断，这也就不能满足Redis能保存任意二进制数据的要求了 - 无法动态扩缩容，char数组在创建之初长度就确定下来了，如果需要追加内容就需要重新申请内存空间，并将追加之后的字符串copy到新创建的数组中去，然后释放老的数组空间，这样会带来额外的资源消耗
什么是SDS？
综合以上C语言char实现字符串的不足之处后，Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String） ，简称SDS
例如我们执行命令：
127.0.0.1:6370> set k1 v1
OK
那么Redis会在底层创建两个SDS，一个是包含“k1”的SDS，一个是包含“v1”的SDS。
SDS里面拥有一个字符数组buf[]，用来保存实际数据，同时SDS结构里还包含了三个元数据属性，分别是保存buf数组已保存的字符串的字节数len，保存buf申请的总的字节数alloc，以及SDS类型标识flags，如下图所示：
例如一个包含数据的SDS内存结构如下：
为什么有5种SDS？
在前面我们有提到过，SDS结构中有一个flags属性，占1个字节，用低三位来保存SDS的类型。通过阅读Redis源码，在sds.h文件里可以看到定义了五种sds结构体，分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64，如下图所示：
通过对比，可以看出，除了sdshdr5没有len和alloc属性，其余4种都拥有相同的属性，只是len和alloc的类型不一样，由此可以得到一个结论：五种SDS分别用来存储不同长度的字符串。
sdshdr8里的len和alloc都是uint8_t类型的，在C语言里有多种长度的int类型，uint8_t是8位无符号整形，会占用1字节的内存空间，能表示的最大长度就是2^8-1（255字节）。
而对于 sdshdr16、sdshdr32、sdshdr64 三种类型来说，它们的 len 和 alloc 数据类型分别是 uint16_t、uint32_t、uint64_t，即它们能表示的字符数组长度，分别不超过 2 的 16 次方、32 次方和 64 次方。这两个元数据各自占用的内存空间在 sdshdr16、sdshdr32、sdshdr64 类型中，则分别是2字节、4字节和8字节
之所以设计不同的类型，是为了能灵活保存不同大小的字符串，从而有效节省内存空间。因为在保存不同大小的字符串时，结构头的内存空间也不一样，这样一来，在保存小字符串时，结构头占用空间也比较少。否则，假设 SDS 都设计一样大小的结构头，比如都使用 uint64_t 类型表示 len 和 alloc，那么假设要保存的字符串是 10 个字节，而此时结构头中 len 和 alloc 本身就占用了16个字节了，比保存的数据都多了。所以这样的设计对内存并不友好，也不满足 Redis 节省内存的需求。
内存预分配
在前面说到，C语言的char是无法动态扩缩容的，那么SDS是如何实现动态扩缩容的呢？我们一起从源码中来寻找答案。
扩容
SDS的扩容逻辑实现在_sdsMakeRoomFor()函数中，源代码如下：
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
void *sh, *newsh;
// 计算剩余空间，点进去看看，就是alloc-len
size_t avail = sdsavail(s);
size_t len, newlen, reqlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
/* Return ASAP if there is enough space left. */
// 分支一：检查sds剩余可用空间要是足够的话，就不用扩容了
if (avail >= addlen) return s;
// 获取长度
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
// 原有长度+所需长度=所需空间
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
// greedy为1时会额外分配冗余空间，如果greedy参数为0的话, 则每次空间分配都只能分配到刚好够用的空
if (greedy == 1) {
// 新空间需求在1M以下, 则直接分配所需的2倍空间
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
// 新空间需求在1M以上, 则在满足需求后额外分配1M空间.
newlen += SDS_MAX_PREALLOC;
}
// 下面的逻辑其实和初始化字符串的逻辑类似了，根据扩容之后的长度，确认sds类型
type = sdsReqType(newlen);
/* 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. */
// sdshdr5没有属性记录总空间, 也就无法计算出剩余的可使用空间, 不能支持扩容. 因此扩容返回的sds至少也是type8.
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
if (oldtype==type) {
// sds类型没变的话，sds里面原有的字符串是不用进行拷贝的，这里直接走realloc，扩大buf的长度就行了
// 这个newsh返回的还是sds的首地址，其实和sh是一样的
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
// s指向buf的首地址
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
// 要是sds的类型发生了变化，那len、alloc的长度就变了，这个时候buf里面的数据就需要迁移
// 这里就要走malloc分配一个新的sds实例，然后把原来buf里面的数据拷贝过去
newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
// 拷贝数据buf里面原有的数据
memcpy((char*)newsh+hdrlen, s, len+1);
// 释放原sds实例
s_free(sh);
// s指向了新sds实例的buf
s = (char*)newsh+hdrlen;
s[-1] = type; // 设置新sds实例的flags字段
sdssetlen(s, len); // 设置新sds实例的len字段
}
// 设置新sds实例的alloc或者是扩大后sds的alloc字段
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
sdssetalloc(s, usable);
return s;
}
重点就是， 扩容的时候会多申请一些内存，小于1M翻倍扩容，大于1M按1M扩容
缩容
SDS的缩容逻辑实现在sdsResize()函数中，源代码如下：
sds sdsResize(sds s, size_t size, int would_regrow) {
void *sh, *newsh;
// 计算当前sds类型
char type, oldtype = s[-1] & SDS_TYPE_MASK;
// 获取当前sds长度
int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
// 再算一下当前的len
size_t len = sdslen(s);
// 前移指针，拿到当前sdshdr首地址
sh = (char*)s-oldhdrlen;
/* Return ASAP if the size is already good. */
// 要是没有剩余空间，就不用缩容buf了
if (sdsalloc(s) == size) return s;
/* Truncate len if needed. */
if (size < len) len = size;
/* Check what would be the minimum SDS header that is just good enough to
* fit this string. */
// 算算要是存储当前len长度的字符串，需要用什么类型的sdshdr
type = sdsReqType(size);
if (would_regrow) {
/* Don't use type 5, it is not good for strings that are expected to grow back. */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
}
hdrlen = sdsHdrSize(type);
/* If the type is the same, or can hold the size in it with low overhead
* (larger than SDS_TYPE_8), we just realloc(), letting the allocator
* to do the copy only if really needed. Otherwise if the change is
* huge, we manually reallocate the string to use the different header
* type. */
// 要是sdshdr类型没发生变化，或者是大sdshdr之间变来变去，就没必要更新sdshdr，
// 毕竟有效负载全在buf那里，更新sdshdr节省的那几个字节带来收益微乎其微，
// 但是付出的代价是要拷贝一边巨大的buf，所以这里使用realloc，缩容buf就行了
int use_realloc = (oldtype==type || (type < oldtype && type > SDS_TYPE_8));
size_t newlen = use_realloc ? oldhdrlen+size+1 : hdrlen+size+1;
if (use_realloc) {
int alloc_already_optimal = 0;
#if defined(USE_JEMALLOC)
/* je_nallocx returns the expected allocation size for the newlen.
* We aim to avoid calling realloc() when using Jemalloc if there is no
* change in the allocation size, as it incurs a cost even if the
* allocation size stays the same. */
alloc_already_optimal = (je_nallocx(newlen, 0) == zmalloc_size(sh));
#endif
if (!alloc_already_optimal) {
newsh = s_realloc(sh, newlen);
if (newsh == NULL) return NULL;
s = (char*)newsh+oldhdrlen;
}
} else {
// 如果是sdshdr缩到的比较厉害，比如缩到了sdshdr8，这个时候就需要通过malloc
// 新申请一块内存区域，然后拷贝buf，这个时候buf比较小，拷贝的代价不大，
// 而且sdshdr缩小的那几个字节，可以提高整个sdshdr的有效负载
newsh = s_malloc(newlen);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len);
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
}
s[len] = 0;
sdssetlen(s, len);
sdssetalloc(s, size);
return s;
}
从源码中可以看到，当缩容后的类型还大于sdshrd8的时候，不会做类型上的变更，而是直接缩容buf。此时可能就会产生疑问，有更小的SDS为何不用？
这主要是因为sdshdr8以上的字符串，有效负载几乎全在buf上。比如说，从sdshdr64缩小成sdshdr16，len、alloc总共节省了12字节，但是重新申请空间要拷贝的数据量是多少？至少是 2^8 吧，256 个字节，这是sdshdr16的存储下限，字节数再少，就要用sdshdr8存储了。而且一般sdshdr16的字符串长度不会恰好卡在下限，都要比 256 字节多。这样的话，节省空间带来的收益微乎其微，但是付出的代价是要拷贝一遍大 buf，所以这里对于sdshdr8以上的缩容，不做SDS类型上面的变更。
如果是字符串长度缩得比较厉害，比如缩到了sdshdr8，这个时候就需要重新申请一块内存区域，然后拷贝buf里面的数据，这个时候buf比较小，拷贝的代价不大，而且sdshdr类型的变化，会缩小几个字节，可以提高整个 sdshdr 的有效负载。
紧凑的编程技巧
除了设计不同SDS的结构体来满足存储不同大小的字符串，Redis还在编程上使用了专门的编译优化来节省内存空间，我们可以看到每个SDS结构体的定义中都使用了__attribute__ ((__packed__))，以sdshdr8为例：
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
};
__attribute__ ((__packed__))的作用就是告诉编译器，在编译sdshdr8结构体的时候，不要使用内存对齐的方式，而是采用紧凑的方式分配内存。在默认情况下，编译器会按照8字节对齐的方式，给变量分配内存。也就是说，即使一个变量的大小不到8个字节，编译器也会给它分配8个字节。
比如下方示例代码，分别定义了s1和s2，s2采用紧凑的方式分配内存，都拥有char a和int b属性，char占1字节，int占4字节，虽然char类型占用1个字节，int类型占用4个字节，但是如果你运行这段代码，就会发现打印出来的结果是8。这就是因为在默认情况下，编译器会给 s1 结构体分配8个字节的空间，而这样其中就有3个字节被浪费掉了。
#include <stdio.h>
int main() {
struct s1 {
char a;
int b;
} ts1;
struct __attribute__ ((__packed__)) s2 {
char a;
int b;
} ts2;
printf("s1 size=%lu\n", sizeof(ts1));
printf("s2 size=%lu\n", sizeof(ts2));
return 0;
}
运行代码可以看到s1 size=8，s2 size=5。
总结
- 通过本文的讲解，我们能够知道Redis之所以重新设计个SDS，是因为C语言的字符串是使用
\0来表示字符串结束的，获取字符串长度还需要遍历整个字符串，效率不高，并且无法完整的表示包含\0的字符串数据，因为无法满足Redis的需求。 - SDS的数据结构，在字符数组的基础上额外增加了len、alloc、flags等属性，可以直接读取，无需遍历整个字符串，大大提高了操作效率，而且不再依赖
\0作为字符串结束符，可以存储任意二进制数据，并且设计不同大小的sds结构体，来满足不同长度的字符串存储，大大提交内存利用率。 - 使用
__attribute__ ((__packed__))编程技巧，让编译器使用紧凑的方式分配内存，达到节省内存的目的。
转载自:https://juejin.cn/post/7381999273355165746