本系列文章从源码角度分析redis的设计与实现,分析的源码为最新版本7.2.4。下载地址(https://github.com/redis/redis/tree/7.2.4)。
本文是该系列的第一篇文章,从以下维度对SDS源码进行分析。
SDS是简单动态字符串的缩写(simple dynamic strings),是redis中最基本的一种数据结构,用于存储字符串和整数类型。是对c语言中原生字符串的封装,并且做到了兼容c语言原生字符串处理函数。相比c语言原生字符串,保证了二进制安全,使用更方便效率更高。
先来看SDS包含哪些基本字段,既然是对c语言原生字符串的包装,则内部必定有一个保存字符串字段,此外包含当前字符串分配的长度以及已使用长度信息。
下图是源码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字节对齐。通过上述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;
}
c语言中是没有字符串类型的,像高级语言Go中有string
类型。c语言中存储字符串,有两种存储方式。但本质是一块连续的内存空间,依次存放了字符串中每个字符。
\0
,如下面代码中的s2。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
字符,则会对整个字符串造成影响。
如果字符串中含有\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中可以保存任意二进制数据的需求。
使用\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;
}
SDS实现涵盖的知识点不外乎SDS的创建、修改、查找和释放等功能,实现代码在src下的sds.c文件中。本文主要从以下几点分析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;
}
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;
}
释放逻辑很简单,通过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';
}
SDS复制就是克隆一个原sds,直接通过sdsnewlen创建。创建SDS和SDS复制都是调用sdsnewlen实现的,所以sdsnewlen的第一个参数设置为 void* 类型。
sds sdsdup(const sds s) {
return sdsnewlen(s, sdslen(s));
}
缩容操作对外暴露的接口是 sdsRemoveFreeSpace,即将s中多余空闲的内存释放掉。
sds sdsRemoveFreeSpace(sds s, int would_regrow) {
return sdsResize(s, sdslen(s), would_regrow);
}
真正处理缩容的逻辑在sdsResize,关键点是比较s中当前实际使用的空间与缩容的目标大小size的关系。
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;
}
扩容接口,入参为要进行扩容的sds以及需要扩大的字节数。
sds sdsMakeRoomFor(sds s, size_t addlen) {
return _sdsMakeRoomFor(s, addlen, 1);
}
_sdsMakeRoomFor扩容策略如下:
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;
}
比较两个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;
}
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 不能使用柔性数组。
在定义SDS结构体时,将存储字符串的buf放在最后,使其成为一个柔性数组,在上层调用时,直接返回buf而不是SDS结构体。由于buf是直接指向字符串的指针,所以完美兼容c语言函数。真正读取字符串内容时,SDS会通过len限制读取长度,而不是\0
,从而保证二进制安全。
通过定义SDS结构,实现一套完整字符串创建、拼接、扩容等操作。可以使用预分配内存,甚至在原有长度类型不变基础上,利用原有内存进行扩容。对比SDS设计,可以看到它与Go语言中切片有异曲同工之处。进行扩容时,分配的空间比实际使用要大一些,采用合适的策略,避免每次append数据时都要重新进行内存分配。Go语言切片定义如下,与SDS结构体非常相似。
type slice struct {
array unsafe.Pointer //引用切片底层的数组
len int //实际存储的元素个数
cap int //切片所引用的数组的真实长度
}