Redis 5.0 本文用到的源码
概览
我最近正在通过 Redis 学习 C 语言。不得不说Redis的代码真的是很整洁。本文将对Redis数据结构字符串的源码实现进行全面深入的讲解，希望大家能从中有所收获。
Redis的字符串源码主要放在sds.c和sds.h这两个文件中。具体实现已被剥离到一个单独的库中：.
Redis的动态字符串结构如下图所示：
SDS大致由header和data segment两部分组成，其中header还包含len、alloc和flags 3个字段。 len代表数据长度，alloc代表分配的内存长度，flags代表sds的数据类型。
在以前的版本中，sds header实际上占用了固定的8字节大小，所以如果所有小字符串都存储在redis中，sds header会占用大量内存空间。
但是随着sds版本的变化，在内存使用方面做了一些优化：
在 sds 2.0 之前，header 的大小是固定的 int 类型。在 2.0 版本之后，会根据传入的字符大小调整 header 的 len 和 alloc 类型，以节省内存使用。 header的结构用__attribute__修饰，主要是为了防止编译器自动对齐内存，这样可以减少编译器由于内存对齐导致的填充次数占用的内存。
当前版本定义了五种sds headers，其中sdshdr5没用，所以不画了：
源码分析sds的创建
sds的创建主要包括以下功能：
sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
所以通过上面的创建，我们可以知道最终会调用sdsnewlen来创建一个字符串，那么我们来看看这个函数是怎么实现的。
sdsnewlen
其实对于一个字符串对象的创建，其实是做了三件事：申请内存，构造一个结构体，把字符串拷贝到字符串内存区。下面我们来看看Redis的具体实现。
请求内存
sds sdsnewlen(const void *init, size_t initlen) {
void *sh; //指向SDS结构体的指针
sds s; //sds类型变量，即char*字符数组
char type = sdsReqType(initlen); //根据数据大小获取sds header 类型
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type); // 根据类型获取sds header大小
unsigned char *fp; /* flags pointer. */
assert(hdrlen+initlen+1 > initlen); /* Catch size_t overflow */
sh = s_malloc(hdrlen+initlen+1); //新建SDS结构，并分配内存空间，这里加1是因为需要在最后加上
...
return s;
}
在内存分配之前，需要做以下事情：
因为sds会根据传入的size来设计header类型，所以需要调用sdsReqType函数根据initlen获取header类型；然后调用sdsHdrSize根据header类型获取header占用的字节数；最后根据header长度和字符调用s_malloc字符串长度分配内存，这里需要加1，因为c中的字符串以结尾，为了兼容c的字符串格式。
既然说到了header类型，我们来看看header类型的定义：
struct __attribute__ ((__packed__)) sdshdr8 { // 占用 3 byte
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 { // 占用 5 byte
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 { // 占用 9 byte
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 { // 占用 17 byte
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
这里__attribute__用来防止内存对齐，否则会浪费一些存储空间。关于内存对齐相关的知识，我也在《Going for WaitGroup引起的内存对齐思考》一文中解释过。知识点比较笼统，有兴趣可以回溯过去。
看完上面的定义，我们自然可以认为Redis会根据传入的大小来判断生成的sds header类型：
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5) // 小于 32
return SDS_TYPE_5;
if (string_size < 1<<8) // 小于 256
return SDS_TYPE_8;
if (string_size < 1<<16) // 小于 65,536
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32)
return SDS_TYPE_32;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}
可以看到sdsReqType是根据传入字符串的长度来判断字符类型的。
构造结构
对于Redis来说，如果你没用过C语言，你会觉得这里构造结构的方式比较hacky。首先直接根据需要的内存大小申请一块内存，然后初始化头结构的指针指向的位置，最后给头结构的指针设置值。
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
sds sdsnewlen(const void *init, size_t initlen) {
...
sh = s_malloc(hdrlen+initlen+1); // 1.申请内存，这里长度加1是为了在最后面存放一个
if (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);// 2.将内存的值都设置为0
s = (char*)sh+hdrlen; //3.将s指针指向数据起始位置
fp = ((unsigned char*)s)-1; //4.将fp指针指向sds header的flags字段
switch(type) {
case SDS_TYPE_5: {
*fp = type | (initlen <len = initlen; // 初始化 header len字段
sh->alloc = initlen; // 初始化 header alloc字段
*fp = type; // 初始化 header flag字段
break;
}
...
}
...
return s;
}
上面的流程我已经标注清楚了。直接看代码可能很难理解构造头结构的过程。我会用下图来展示指针所指向的位置：
字符串复制
sds sdsnewlen(const void *init, size_t initlen) {
...
if (initlen && init)
memcpy(s, init, initlen); //将要传入的字符串拷贝给sds变量s
s[initlen] = ''; //变量s末尾增加，表示字符串结束
return s;
}
memcpy函数会将字符串逐字节复制到s对应的内存区域。
sdscatlen 字符串追加
sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s); // 获取字符串 len 大小
//根据要追加的长度len和目标字符串s的现有长度，判断是否要增加新的空间
//返回的还是字符串起始内存地址
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
// 将新追加的字符串拷贝到末尾
memcpy(s+curlen, t, len);
// 重新设置字符串长度
sdssetlen(s, curlen+len);
s[curlen+len] = '';
return s;
}
在这种字符串追加的方法中，空间检查和扩展其实都封装在了sdsMakeRoomFor函数中，只需要：
是否还有剩余空间，如果有，直接返回；如果没有剩余空间，那么需要扩展，多少？字符串是否可以在原位置追加空格，或者需要重新申请内存区域。
那我将sdsMakeRoomFor函数分为扩展和内存申请两部分。
扩展
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s); //这里是用 alloc-len,表示可用资源
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
if (avail >= addlen) return s; // 如果有空间剩余，那么直接返回
len = sdslen(s); // 获取字符串 len 长度
sh = (char*)s-sdsHdrSize(oldtype); //获取到header的指针
newlen = (len+addlen); // 新的内存空间
if (newlen < SDS_MAX_PREALLOC) //如果小于 1m， 那么存储空间直接翻倍
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC; //超过了1m，那么只会多增加1m空间
...
return s;
}
对于扩容，首先检查空间是否足够，即根据alloc-len，如果有剩余空间则直接返回。
然后Redis会根据sds的大小进行扩展。如果len+addlen空间小于1m，则直接增加一倍新空间；如果len+addlen空间大于1m，新空间只会增加1m。
内存请求
sds sdsMakeRoomFor(sds s, size_t addlen) {
...
type = sdsReqType(newlen); // 根据新的空间占用计算 sds 类型
hdrlen = sdsHdrSize(type); // header 长度
if (oldtype==type) { // 和原来header一样，那么可以复用原来的空间
newsh = s_realloc(sh, hdrlen+newlen+1); // 申请一块内存，并追加大小
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
//如果header 类型变了，表示内存头变了，那么需要重新申请内存
//因为如果使用s_realloc只会向后追加内存
newsh = s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh); // 释放掉原内存
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
sdssetalloc(s, newlen);//重新设置alloc字段
return s;
}
在内存申请中，Redis分为两种情况，一种是sds头类型没有改变，那么可以直接调用realloc在原内存后面增加一块新的内存区域；
另一个是sds头类型发生了变化。一般情况下，header占用的空间变大了。因为realloc不能向前添加内存区，所以只能调用malloc重新申请一块内存区，然后用memcpy把改变字符的字符串复制到新地址。
总结
通过这篇文章，我们深入了解了 Redis 字符串是如何实现的，以及通过版本变化做了哪些改变。您可以将 sds 与您熟悉的语言的字符串进行比较。看看在实现上有什么不同，哪个更好。
参考
暂无评论内容