redis SDS设计与实现分析
前言
本系列文章从源码角度分析redis的设计与实现，分析的源码为最新版本7.2.4。下载地址(https://github.com/redis/redis/tree/7.2.4）。
本文是该系列的第一篇文章，从以下维度对SDS源码进行分析。
Part1SDS是什么?
SDS是简单动态字符串的缩写（simple dynamic strings），是redis中最基本的一种数据结构，用于存储字符串和整数类型。是对c语言中原生字符串的封装，并且做到了兼容c语言原生字符串处理函数。相比c语言原生字符串，保证了二进制安全，使用更方便效率更高。
1SDS基本结构
先来看SDS包含哪些基本字段，既然是对c语言原生字符串的包装，则内部必定有一个保存字符串字段，此外包含当前字符串分配的长度以及已使用长度信息。
2SDS五种结构
下图是源码src/sds.h中定义的5种结构体类型，为啥一个SDS还要搞这么多类型呢？定义成上面的结构不就行了嘛？答案是为了节约内存，我们知道redis是一个内存数据库，k-v信息都是存在内存中，所以减少内存占用非常有必要。
选取合适类型
字符串长度有大有小，如果都千篇一律使用SDS基本结构会存在浪费，因为基本结构中 len 和 alloc 都是int类型，int类型占4个字节。如果字符串很短，长度不超过256，则 len 和 alloc 用 int8 完全够了， 没有必要使用int。相反，如果字符串很长很长，超过int范围，len 和 alloc 需要定义成int64。所以redis中为SDS定义了5种结构，根据字符串长度选择合适类型。
如何区分类型？
SDS结构引入多种类型后产生了一个问题，如何判断sds到底是哪种类型呢？redis处理方法是增加一个字段标记位flags表示类型，因为有5种类型（见如下代码，类型值依次为0、1、2、3、4），用3个bit（可以表示8种类型）就可以表示，在redis中定义为unsigned char类型（8个bit），所以还有5个bit剩余位，可以表示长度小于32的字符串。
#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
在低版本中，例如redis5.0中，长度小于32的字符串就是用 sdshdr5存储的。注意，在本次分析的7.2.4版本中，已不再使用sdshdr5，改为使用sdshdr8。
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; // 低3位存储类型，高5位存储长度
char buf[];
}
现在还有一个问题没有讨论：拿到一个sds对象，怎么判断它是哪种类型呢？因存在数据对齐问题，不同类型填充可能不一样。redis处理的很巧妙，具体来说有3点：
__attribute__ ((__packed__))修饰：一般情况下，结构体会按其所有变量大小的最小公倍数进行字节对齐，用packed修饰后，结构体按1字节对齐。- 柔性数组：柔性数组必须是结构体最后一个成员，可以看到buf是sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64最后一个字段，并且柔性数组前必须至少有一个其他成员。
- 合理字段编排：标记位flags位于buf前。
通过上述3点，知道buf后，buf[-1]的值即为flags值，可以快速判断sds到底是哪种类型。
static inline size_t sdslen(const sds s) {
// sds即为buf,直接取buf[-1]位置内容就是flags
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8:
return SDS_HDR(8,s)->len;
case SDS_TYPE_16:
return SDS_HDR(16,s)->len;
case SDS_TYPE_32:
return SDS_HDR(32,s)->len;
case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
}
Part2为啥不用原生字符数组?
c语言中是没有字符串类型的，像高级语言Go中有string类型。c语言中存储字符串，有两种存储方式。但本质是一块连续的内存空间，依次存放了字符串中每个字符。
- 存储方式1：使用字符串数组，将字符串中每个字符存储到数组中，并在末尾添加
\0，如下面代码中的s2。 - 存储方式2：使用字符指针，将一个字符串赋值给字符指针，如下面代码中的s1。
int main() {
char *s1 = "hello world";
char s2[] = "hello china";
printf("%s\n",s1);
printf("%s\n",s2);
return 0;
}
上述代码中字符串s1和s2在内存中结构如下：
可以看到c语言中字符数组的末尾带有字符\0，标准库中的字符串操作函数通过遍历检查\0判断字符串是否结束，操作效率低。此外如果字符串中本身带有\0字符，则会对整个字符串造成影响。
1二进制安全
如果字符串中含有\0字符，使用库函数时会产生意料之外结果，下面通过程序验证。
int main() {
char *s1 = "hello \0world";
printf("%s\n",s1);
printf("s1 len: %d\n",strlen(s1));
return 0;
}
运行输出结果如下：
hello
s1 len: 6
字符串s1中的world直接没有统计到，输出的长度6。这不符合redis中可以保存任意二进制数据的需求。
2操作效率低
使用\0作为字符串结束符还会导致操作函数的复杂度增加，例如求解长度函数 strlen，该函数需要遍历字符数组中的每一个字符，才能得到字符串长度，操作复杂度为O(n)。
字符串追加函数 strcat 将源字符串追加到目标字符串末尾时，需要通过遍历方式定位到源字符串的末尾，也是O(n)的操作复杂度。
char *strcat(char *dest, const char *src){
char *tmp = dest;
while(*dest){
dest++;
}
while((*dest++ = *src++) != '\0')
return tmp;
}
Part3SDS实现
SDS实现涵盖的知识点不外乎SDS的创建、修改、查找和释放等功能，实现代码在src下的sds.c文件中。本文主要从以下几点分析SDS实现。
1 创建SDS
根据c语言字符串init创建SDS，内部调用sdsnewlen进行初始化，暴露给使用者只需提供一个c字符串，不需要传递大小，可以通过strlen函数求解。
// 根据传入的原生字符串创建SDS
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
sdsnewlen函数非常简单，直接调用了_sdsnewlen函数。是不是有点多余？直接把_sdsnewlen逻辑写在sdsnewlen函数中不就可以了，为啥搞这么麻烦。版本迭代升级导致的，早期版本核心逻辑就是在sdsnewlen里面，没有_sdsnewlen函数。
sds sdsnewlen(const void *init, size_t initlen) {
return _sdsnewlen(init, initlen, 0);
}
真正创建sds的逻辑在 _sdsnewlen 函数， 根据传入的字符串长度确定选择哪种sds类型，然后malloc申请需要的内容空间，最后给初始化sds结构体各个字段值。
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
void *sh;
sds s;
// 根据字符串长度决定SDS类型
char type = sdsReqType(initlen);
// 创建的为空字符串，默认类型定为 sdshdr8
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
size_t usable;
// 防止溢出
assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
sh = trymalloc?
s_trymalloc_usable(hdrlen+initlen+1, &usable) :
s_malloc_usable(hdrlen+initlen+1, &usable);
...
// s指向sds中buf位置
s = (char*)sh+hdrlen;
// s向前偏移一位即为flags位置
fp = ((unsigned char*)s)-1;
...
if (initlen && init)
// 拷贝初始化字符串
memcpy(s, init, initlen);
s[initlen] = '\0';
return s;
}
2 SDS拼接
sds暴露给外部使用的拼接接口非常简洁，入参是要拼接的两个sds，返回拼接后的sds。
sds sdscatsds(sds s, const sds t) {
return sdscatlen(s, t, sdslen(t));
}
sdscatlen是内部函数，真正进行拼接处理，首先判断s是否能够容纳被拼接的内容，如果不能进行扩容操作，对应的处理逻辑在 sdsMakeRoomFor，详细分析在第6部分SDS扩容中讨论。最后将t中的内容拷贝到s中。
sds sdscatlen(sds s, const void *t, size_t len) {
// 求解s中已使用空间大小
size_t curlen = sdslen(s);
// 判断是否需要进行扩容
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
// 将sds t中的内容拼接到s中
memcpy(s+curlen, t, len);
// 设置s中已使用的空间大小
sdssetlen(s, curlen+len);
s[curlen+len] = '\0';
return s;
}
3 SDS释放
释放逻辑很简单，通过s定位到整个要释放空间的起始位置，即下图中字段len位置，调用s _free释放。
void sdsfree(sds s) {
if (s == NULL) return;
s_free((char*)s-sdsHdrSize(s[-1]));
}
sdsclear重置s，内存空间并没有释放，可以复用。
void sdsclear(sds s) {
sdssetlen(s, 0);
s[0] = '\0';
}
4 SDS复制
SDS复制就是克隆一个原sds，直接通过sdsnewlen创建。创建SDS和SDS复制都是调用sdsnewlen实现的，所以sdsnewlen的第一个参数设置为 void* 类型。
sds sdsdup(const sds s) {
return sdsnewlen(s, sdslen(s));
}
5 SDS缩容
缩容操作对外暴露的接口是 sdsRemoveFreeSpace，即将s中多余空闲的内存释放掉。
sds sdsRemoveFreeSpace(sds s, int would_regrow) {
return sdsResize(s, sdslen(s), would_regrow);
}
真正处理缩容的逻辑在sdsResize，关键点是比较s中当前实际使用的空间与缩容的目标大小size的关系。
- 情况1： 如果s分配的空间大小刚好等于size，则无需缩容。
- 情况2： 如果缩容的目标大小size小于当前s实际占用的空间，就要对s进行截断操作，通过realloc在原空间上缩容。
- 情况3： 如果缩容的目标大小size大于当前s实际占用的空间，此时其实是扩容，通过malloc分配新空间。
sds sdsResize(sds s, size_t size, int would_regrow) {
void *sh, *newsh;
// 求解s类型
char type, oldtype = s[-1] & SDS_TYPE_MASK;
// 求解s头部大小
int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
size_t len = sdslen(s);
// 定位到内存起始位置
sh = (char*)s-oldhdrlen;
// 如果没有浪费，即分配的空间全部使用，无需缩容
if (sdsalloc(s) == size) return s;
// 需要截断
if (size < len) len = size;
// 缩容后sds的类型
type = sdsReqType(size);
if (would_regrow) {
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
}
// 缩容后sds的头部大小
hdrlen = sdsHdrSize(type);
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) {
// 利用原空间通过 realloc缩容
int alloc_already_optimal = 0;
#if defined(USE_JEMALLOC)
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 {
// 重新分配一片空间
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;
}
6 SDS扩容
扩容接口，入参为要进行扩容的sds以及需要扩大的字节数。
sds sdsMakeRoomFor(sds s, size_t addlen) {
return _sdsMakeRoomFor(s, addlen, 1);
}
_sdsMakeRoomFor扩容策略如下：
- 情况1： 如果s中剩余的空间avail大于等于新增的空间addlen，直接在柔性数组buf末尾追加即可，无需扩容。
- 情况2： 如果s中剩余空间小于新增空间addlen, 并且两者加起来小于1MB, 则按2倍扩容。
- 情况3： 如果s中剩余空间小于新增空间addlen, 并且两者加起来大于等于1MB, 则多分配1MB空间。
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
void *sh, *newsh;
// 计算s中未使用空间大小
size_t avail = sdsavail(s);
size_t len, newlen, reqlen;
// 求解s的类型，是SDS_TYPE_8还是SDS_TYPE_16 ...
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
// s中剩余的空间足够容纳要拼接的字符串，无需进行扩容，直接返回
if (avail >= addlen) return s;
len = sdslen(s);
//定位到s对象的起始位置
sh = (char*)s-sdsHdrSize(oldtype);
// 拼接后占用的总空间大小
reqlen = newlen = (len+addlen);
assert(newlen > len);
// 是否进行贪婪分配
if (greedy == 1) {
// 拼接后总长度大小小于1M, 扩容加倍，否则只多分配1M空间
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
}
// 根据扩容后长度求解类型
type = sdsReqType(newlen);
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
assert(hdrlen + newlen + 1 > reqlen);
// 扩容前和扩容后类型相同
if (oldtype==type) {
// 通过realloc扩大柔性数组buf即可
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
// 重新申请一块新内存，将原s中的字符串内容拷贝到新分配的内存中
newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
// 释放掉原s占用的内存
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
// 设置总的分配空间大小
sdssetalloc(s, usable);
return s;
}
7 SDS比较
比较两个sds中buf内容是否完全相同，如果相同返回0. 如果其中s1是s2的子串，返回-1，如果s2是s1的子串，返回1，其它情况返回memcmp值。
int sdscmp(const sds s1, const sds s2) {
size_t l1, l2, minlen;
int cmp;
// 求解s1中buf字符串长度
l1 = sdslen(s1);
// 求解s2中buf字符串长度
l2 = sdslen(s2);
minlen = (l1 < l2) ? l1 : l2;
// 比较s1和s2中前minlen个字符串是否相同
cmp = memcmp(s1,s2,minlen);
// 进一步比较长度
if (cmp == 0) return l1>l2? 1: (l1<l2? -1: 0);
return cmp;
}
Part4思考总结
1 为啥SDS结构体不按内存对齐？
cpu在读取数据时以程序字长为单位，在32位系统上是4字长，在64位系统上是8字长，因为这样效率最好。对于一个把内存和cpu用到极致的人，redis作者为啥要把sds设计成非内存对齐呢。
如果采用内存对齐，在32位系统上，sdshdr8、sdshdr16、sdshdr32、sdshdr64内存结构如下。可以看到不同类型的sds里面，填充的bit数是不同的。如果我们要从sds指针位置定位到flags位置，在不知道类型的情况下是不可能的。sdshdr16、sdshdr32、sdshdr64填充都是24bit，如果去掉sdshdr8这种类型是否就可以了呢？最小的类型采用sdshdr16也不会浪费太多内存嘛，这样性能也有保障。注意这里只讨论了32位系统，在64位系统下，填充又有变化，所以这种方法不可取。
还有一种处理思路，把flags和buf交换下位置是否可以呢？也是不行的，有两个原因：1 无法兼容c语言原生字符串；2 不能使用柔性数组。
2 SDS怎么做到兼容c语言字符串
在定义SDS结构体时，将存储字符串的buf放在最后，使其成为一个柔性数组，在上层调用时，直接返回buf而不是SDS结构体。由于buf是直接指向字符串的指针，所以完美兼容c语言函数。真正读取字符串内容时，SDS会通过len限制读取长度，而不是\0，从而保证二进制安全。
3 SDS动态扩容非常高效
通过定义SDS结构，实现一套完整字符串创建、拼接、扩容等操作。可以使用预分配内存，甚至在原有长度类型不变基础上，利用原有内存进行扩容。对比SDS设计，可以看到它与Go语言中切片有异曲同工之处。进行扩容时，分配的空间比实际使用要大一些，采用合适的策略，避免每次append数据时都要重新进行内存分配。Go语言切片定义如下，与SDS结构体非常相似。
type slice struct {
array unsafe.Pointer //引用切片底层的数组
len int //实际存储的元素个数
cap int //切片所引用的数组的真实长度
}腾讯云开发者
