本文作者： Pushy
本文链接： http://pushy.site/2019/12/21/redis-sds/
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！
1. 什么是 SDS
众所周知，在 Redis 的五种数据解构中，最简单的就是字符串：
redis> set msg "Hello World"
而 Redis 并没有直接使用 C 语言传统的字符串表示，而是自己构建了一个名为简单动态字符串（Simple dynamic string，即 SDS）的抽象数据结构。
执行上面的 Redis 命令，在 Server 的数据库中将创建一个键值对，即：
- 键为 “msg” 的 SDS；
- 值为 “Hello World” 的 SDS。
我们再来看下 SDS 的定义，在 Redis 的源码目录 sds.h 头文件中，定义了 SDS 的结构体：
struct sdshdr {
// 记录 buf 数组中当前已使用的字节数量
unsigned int len;
// 记录 buf 数组中空闲空间长度
unsigned int free;
// 字节数组
char buf[];
};
可以看到，SDS 通过 len 和 free 属性值来描述字节数组 buf 当前的存储状况，这样在之后的扩展和其他操作中有很大的作用，还能以 O(1) 的复杂度获取到字符串的长度（我们知道，C 自带的字符串本身并不记录长度信息，只能遍历整个字符串统计）。
那么为什么 Redis 要自己实现一套字符串数据解构呢？下面慢慢来研究！
2. SDS 的优势
杜绝缓冲区溢出
除了获取字符串长度的复杂度为较高之外，C 字符串不记录自身长度信息带来的另一个问题就是容易造成内存溢出。举个例子，通过 C 内置的 strcat 方法将字符串 motto 追加到 s1 字符串后边：
void wrong_strcat() {
char *s1, *s2;
s1 = malloc(5 * sizeof(char));
strcpy(s1, "Hello");
s2 = malloc(5 * sizeof(char));
strcpy(s2, "World");
char *motto = " To be or not to be, this is a question.";
s1 = strcat(s1, motto);
printf("s1 = %s \n", s1);
printf("s2 = %s \n", s2);
}
// s1 = Hello To be or not to be, this is a question.
// s2 = s a question.
但是输出却出乎意料，我们只想修改 s1 字符串的值，而 s2 字符串也被修改了。这是因为 strcat 方法假定用户在执行前已经为 s1 分配了足够的内存，可以容纳 motto 字符串中的内容。而一旦这个假设不成立，就会产生缓冲区溢出。
通过 Debug 我们看到，s1 变量内存的初始位置为 94458843619936 （10进制）， s2 初始位置为 94458843619968，是一段相邻的内存块：
[图片上传失败...(image-b46e0c-1577019474368)]
所以一旦通过 strcat 追加到 s1 的字符串 motto 的长度大于 s1 到 s2 的内存地址间隔时，将会修改到 s2 变量的值。而正确的做法应该是在 strcat 之前为 s1 重新调整内存大小，这样就不会修改 s2 变量的值了：
void correct_strcat() {
char *s1, *s2;
s1 = malloc(5 * sizeof(char));
strcpy(s1, "Hello");
s2 = malloc(5 * sizeof(char));
strcpy(s2, "World");
char *motto = " To be or not to be, this is a question.";
// 为 s1 变量扩展内存，扩展的内存大小为 motto * sizeof(char) + 空字符结尾(1)
s1 = realloc(s1, (strlen(motto) * sizeof(char)) + 1);
s1 = strcat(s1, motto);
printf("s1 = %s \n", s1);
printf("s2 = %s \n", s2);
}
// s1 = Hello To be or not to be, this is a question.
// s2 = World
可以看到，扩容后的 s1 变量内存地址起始位置变为了 94806242149024（十进制），s2 起始地址为 94806242148992。这时候 s1 与 s2 内存地址的间隔大小已经足够 motto 字符串的存放了：
[图片上传失败...(image-eca5dd-1577019474368)]
而与 C 字符串不同， SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性，具体的实现在 sds.c 中。通过阅读源码，我们可以明白之所以 SDS 能杜绝缓冲区溢出是因为再调用 sdsMakeRoomFor 时，会检查 SDS 的空间是否满足修改所需的要求（即 free >= addlen 条件），如果满足 Redis 将会将 SDS 的空间扩展至执行所需的大小，在执行实际的 concat 操作，这样就避免了溢出发生：
// 与 C 语言 string.h/strcat 功能类似，其将一个 C 字符串追加到 sds
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
sds sdscatlen(sds s, const char *t, size_t len) {
struct sdshdr *sh;
size_t curlen = sdslen(s); // 获取 sds 的 len 属性值
s = sdsMakeRoomFor(s, len);
if (s == NULL) return NULL;
// 将 sds 转换为 sdshdr，下边会介绍
sh = (void *) (s - sizeof(struct sdshdr));
// 将字符串 t 复制到以 s+curlen 开始的内存地址空间
memcpy(s + curlen, t, len);
sh->len = curlen + len; // concat后的长度 = 原先的长度 + len
sh->free = sh->free - len; // concat后的free = 原来 free 空间大小 - len
s[curlen + len] = '\0'; // 与 C 字符串一样，都是以空字符 \0 结尾
return s;
}
// 确保有足够的空间容纳加入的 C 字符串, 并且还会分配额外的未使用空间
// 这样就杜绝了发生缓冲区溢出的可能性
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
size_t free = sdsavail(s); // 当前 free 空间大小
size_t len, newlen;
if (free >= addlen) {
/* 如果空余空间足够容纳加入的 C 字符串大小, 则直接返回, 否则将执行下边的代码进行扩展 buf 字节数组 */
return s;
}
len = sdslen(s); // 当前已使用的字节数量
sh = (void *) (s - (sizeof(struct sdshdr)));
newlen = (len + addlen); // 拼接后新的字节长度
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
newsh = realloc(sh, sizeof(struct sdshdr) + newlen + 1);
if (newsh == NULL) return NULL; // 申请内存失败
/* 新的 sds 的空余空间 = 新的大小 - 拼接的 C 字符串大小 */
newsh->free = newlen - len;
return newsh->buf;
}
另外，在看源码时我对 sh = (void *) (s - sizeof(struct sdshdr)); 一脸懵逼，如果不懂可以看：Redis（一）之 struct sdshdr sh = (void) (s-(sizeof(struct sdshdr)))讲解
减少修改字符带来的内存重分配次数
对于包含 N 个字符的 C 字符串来说，底层总是由 N+1 个连续内存的数组来实现。由于存在这种关系，因此每次修改时，程序都需要对这个 C 字符串数组进行一次内存重分配操作：
- 如果是拼接操作：扩展底层数组的大小，防止出现缓冲区溢出（前面提到的）；
- 如果是截断操作：需要释放不使用的内存空间，防止出现内存泄漏。
Redis 作为频繁被访问修改的数据库，为了减少修改字符带来的内存重分配的性能影响，SDS 也变得非常需要。因为在 SDS 中，buf 数组的长度不一定就是字符串数量 + 1，可以包含未使用的字符，通过 free 属性值记录。通过未使用空间，SDS 实现了以下两种优化策略：
Ⅰ、空间预分配
空间预分配用于优化 SDS 增长的操作：当对 SDS 进行修改时，并且需要对 SDS 进行空间扩展时，Redis 不仅会为 SDS 分配修改所必须的空间，还会对 SDS 分配额外的未使用空间。
在前面的 sdsMakeRoomFor 方法可以看到，额外分配的未使用空间数量存在两种策略：
- SDS 小于
SDS_MAX_PREALLOC：这时 len 属性值将会和 free 属性相等； - SDS 大于等于
SDS_MAX_PREALLOC：直接分配SDS_MAX_PREALLOC大小。
sds sdsMakeRoomFor(sds s, const char *t, size_t len) {
...
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
newsh = realloc(sh, sizeof(struct sdshdr) + newlen + 1);
if (newsh == NULL) return NULL;
newsh->free = newlen - len;
return newsh->buf;
}
通过空间预分配策略，Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。
Ⅱ、惰性空间释放
惰性空间释放用于优化 SDS 字符串缩短操作，当需要缩短 SDS 保存的字符串时，Redis 并不立即使用内存重分配来回收缩短多出来的字节，而是使用 free 属性将这些字节记录起来，并等待来使用。
举个例子，可以看到执行完 sdstrim 并没有立即回收释放多出来的 22 字节的空间，而是通过 free 变量值保存起来。当执行 sdscat 时，先前所释放的 22 字节的空间足够容纳追加的 C 字符串 11 字节的大小，也就不需要再进行内存空间扩展重分配了。
#include "src/sds.h"
int main() {
// sds{len = 32, free = 0, buf = "AA...AA.a.aa.aHelloWorld :::"}
s = sdsnew("AA...AA.a.aa.aHelloWorld :::");
// sds{len = 10, free = 22, buf = "HelloWorld"}
s = sdstrim(s, "Aa. :");
// sds{len = 21, free = 11, buf = "HelloWorld! I'm Redis"}
s = sdscat(s, "! I'm Redis");
return 0;
}
通过惰性空间释放策略，SDS 避免了缩短字符串时所需内存重分配操作，并会将来可能增长操作提供优化。与此同时，SDS 也有相应的 API 真正地释放 SDS 的未使用空间。
二进制安全
C 字符串必须符合某种编码，并且除了字符串的末尾之外，字符串不能包含空字符（\0）,否则会被误认为字符串的末尾。这些限制导致不能保存图片、音频等这种二进制数据。
但是 Redis 就可以存储二进制数据，原因是因为 SDS 是使用 len 属性值而不是空字符来判断字符串是否结束的。
兼容部分 C 字符串函数
我们发现， SDS 的字节数组有和 C 字符串相似的地方，例如也是以 \0 结尾（但是不是以这个标志作为字符串的结束）。这就使得 SDS 可以重用 <string.h> 库定义的函数：
#include <stdio.h>
#include <strings.h>
#include "src/sds.h"
int main() {
s = sdsnew("Cat");
// 根据字符集比较大小
int ret = strcasecmp(s, "Dog");
printf("%d", ret);
return 0;
}
3. 总结
看完 Redis 的 SDS 的实现，终于知道 Redis 只所以快，肯定和 epoll 的网络 I/O 模型分不开，但是也和底层优化的简单数据结构分不开。
SDS 精妙之处在于通过 len 和 free 属性值来协调字节数组的扩展和伸缩，带来了较比 C 字符串太多的性能更好的优点。什么叫牛逼？这就牛逼！
